208 CHAPTER 3 Relations
question is how to arrive at this table starting with the tables Registration and TeachingAs-
signments.
Table 3.18 JoinedRelation
JoinedRelation
Student Department Course Section Professor
John von Neumann English 101 3 Geoffrey Chaucer
Emmy Noether English 101 3 Geoffrey Chaucer
Herman Hollerith English 101 3 Geoffrey Chaucer
George Boole English 101 4 William Morris
Ren6 Descartes English 101 4 William Morris
Winston Churchill English 101 4 William Morris
John von Neumann English 103 1 Thomas Jefferson
Emmy Noether English 103 1 Thomas Jefferson
George Boole Mathematics 101 1 David Hilbert
Winston Churchill Mathematics 101 1 David Hilbert
George Boole Mathematics 101 1 Leonardo of Pisa
Winston Churchill Mathematics 101 1 Leonardo of Pisa
Ren6 Descartes Computer Science 103 3 Alan Turing
Herman Hollerith Computer Science 103 3 Alan Turing
After defining the join of two relations and giving a small example, we will present an
algorithm that could be used to actually find the join of two relations.
The formation of the join of two relations is a three-step process. In the first
step, we take two relations, R with attributes AI, A 2 , A 3 ,..., Am and S with attributes
B 1 , B 2 , B 3 ... , B, and form the database Cartesian product. The database Cartesian
product R x S is a relation with attributes A 1 , A 2 , .... Am, B 1 , B 2 , ... , Bn, and its tuples
are
{(al, a2 ... , am, bl, b2,..., bn) : (a,_. , am) e R and (bl, b 2 ,..., b,) E S}
Note that the database definition of the term Cartesian product differs slightly from the
set theoretic notion. The set theory definition results in 2-tuples, whereas here, all the
coordinates are kept without extra parentheses.
The second step of the process involves forming the equijoin of R and S on attributes
Ai and Bj by selecting all tuples from R x S where the values of attributes Ai and Bj are
the same. To form the equijoin on several pairs of attributes, Ai, Bjl, Ai 2 , Bj2,..., Aik, Bik,
perform k selections; that is, select tuples whose values on Ai, and Bj, are the same, whose
values on Ai 2 and Bj 2 are the same, and so on. Often, the names of attributes Ai and Bj will
in practice be the same. In that case, we may say we are taking the join on attribute Ai.
Note that in the equijoin, the attributes Ai and Bj contain the same informa-
tion. The third step of the join eliminates the second of the duplicated columns: The
join of R and S on attributes Ai and Bj is the projection of the equijoin on at-
tributes A 1 ... , Am, B 1 ... , Bj- 1 , Bj+I ... , B, The join on several attribute pairs omits
("projects out") the second attribute from each pair.
The natural join of relations R and S, written R >.i S, is the join of R and S on all
attribute pairs with the same name.