Discrete Mathematics for Computer Science

Relational Databases: An Introduction 209

Example 2. Define the relations R and S as shown:

R S

Name Class Average Name Major

Joe 2004 3.14 Joe Mathematics

Sue 2004 2.97 Sue Computer Science

Mary 2005 3.76 Mary Sociology

Form the join of R and S on Name.

Solution. First, form the database Cartesian product R x S.

Database Cartesian Product of R x S

Name Class Average Name Major

Joe 2004 3.14 Joe Mathematics

Joe 2004 3.14 Sue Computer Science

Joe 2004 3.14 Mary Sociology

Sue 2004 2.97 Joe Mathematics

Sue 2004 2.97 Sue Computer Science

Sue 2004 2.97 Mary Sociology

Mary 2005 3.76 Joe Mathematics

Mary 2005 3.76 Sue Computer Science

Mary 2005 3.76 Mary Sociology

Now, form the equijoin: Extract the subset of R x S for which the entries for Name are

equal, giving R'.

RxS

Name Class Average Name Major

Joe 2004 3.14 Joe Mathematics

Sue 2004 2.97 Sue Computer Science

Mary 2005 3.76 Mary Sociology

Finally, project R x S on {Name, Class, Average, Name, Major} - {Name} to form the
join of R and S on Name.

RxS

Name Class Average Major

Joe 2004 3.14 Mathematics

Sue 2004 2.97 Computer Science

Mary (^2005) 3.76 Sociology U
One of the problems with database queries involves the complexity of finding the join
of two relations. A join on more than a single attribute can be defined. The first example
had three common attributes. The algorithm for finding the join makes the complexity of
this operation clearer.