Definition of the Join

The join operation, denoted by $\Join$ , combines two relations R and Q to form a new relation S . If the attributes of R are referred to as $A_1, A_2, \dots, A_m$ and those of Q as $B_1, B_2, \dots, B_n$ then S has the m+n attributes $A_1, \dots, A_m, B_1, \dots B_n$ . Tuples s of S are formed by concatenating a tuple $r \in R$ with a tuple $q \in Q$ , denoted as $s = r \circ q$ . Usually there is a join condition C that has to be fulfilled by the tuples r and q that are concatenated to form an s. In total, the notation for the join looks like this:

$\begin{displaymath} S \;\;=\;\; R \Join_{\scriptscriptstyle C}Q\end{displaymath}$

Put differently: the join $R \Join_{\scriptscriptstyle C}Q$ is a subset of the cartesian product $R \times Q$ . The cartesian product of R and Q concatenates each tuple of R with every tuple of Q. This results in a new relation $R \times Q$ with $\vert R\vert \cdot \vert Q\vert$ tuples, with |R| and |Q| being the cardinalities of R and Q respectively. The result of the join $R \Join_{\scriptscriptstyle C}Q$ can then be retrieved from $R \times Q$ by selection over the join condition C. Thus

$\begin{displaymath} R \Join_{\scriptscriptstyle C}Q \;\;=\;\; \sigma_C ( R \times Q )\end{displaymath}$

(4)

As an example for a join, consider the two relations Staff and Student of figure 3.1. Imagine that these relations respectively hold members of staff and students of a certain university department. Staff members are described by their name, office, start and end dates of the period they worked in the department. Similarly, students have a name, a workroom that is assigned to them, a start and an end date. For simplicity, we assume that names are unique.

**Figure:** Example relations holding staff members and students.
$\begin{figure} \begin{center} \begin{small} \mbox{ \subfigure[{\bf \tt Staff}]{... ...r}}}\end{small}\end{center}\index{{\em Staff}} \index{{\em Student}}\end{figure}$

A typical query would be to find staff-student pairs who started in the department at the same time. These can be found by a join

$\begin{displaymath} \text{\tt Staff} \;\Join_{\scriptscriptstyle C}\; \text{\tt Student}\end{displaymath}$

$\begin{displaymath} C \;\;\equiv\;\; \text{\tt Staff.Start} = \text{\tt Student.Start}\end{displaymath}$

**Figure:** Result of the join $\text{\tt Staff} \Join_{\scriptscriptstyle C}\text{\tt Student}$ .
$\begin{figure} \begin{center} \begin{small} \begin{tabular} {\vert lccclccc\ver... ... 10 & Olga & Z & 1 & 3 \\ \hline\end{tabular}\end{small}\end{center}\end{figure}$