208
CHAPTER 3 Relations
question is how to arrive at this table starting with the tables Registration and TeachingAssignments.
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 information. 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 attributes 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.
CHAPTER 3 Relations
question is how to arrive at this table starting with the tables Registration and TeachingAssignments.
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 information. 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 attributes 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.