Discrete Mathematics for Computer Science

210 CHAPTER 3 Relations

INPUT: Relations R and S with common attributes B 1 , B2. Bj

OUTPUT: Relation J that is the join of R and S on B 1 , B2. Bj

J=0

for each tuple x E R do

Select all tuples y c S whose values on B 1. Bj

are all the same as x's

for each such tuple y do

Form a tuple z by concatenating x with y

Eliminate the duplicate entries for attributes

B 1 , B2. Bj, creating a tuple z'

J = J U {Z')

Example 3. Use relational algebra, applied to the relations Registration and Teaching-

Assignments, to find a list of all professors who have either Ren6 Descartes or Winston

Churchill as students.

Solution. First, form the natural join of Registration and TeachingAssignments. Then,

select all tuples in the joined relation with student Ren6 Descartes or Winston Churchill.

The result is shown in Table 3.19.

Table 3.19 Step lJoin

Step l Join

Student Department Course Section Professor

Ren6 Descartes English 101 4 William Morris

Winston Churchill English 101 4 William Morris

Winston Churchill Mathematics 101 1 David Hilbert

Winston Churchill Mathematics 101 1 Leonardo of Pisa

Ren6 Descartes Computer Science 103 3 Alan Turing

Finally, project the SteplJoin relation onto the attribute set {Professorl, and remove

any duplicate entries. The resulting relation is shown in Table 3.20.

The relation Professor answers the question of which professors have either Winston

Churchill or Ren6 Descartes as a student.^0