Question: Suppose a join operation over some attribute is to be done on two tables of cardinality p and q, respectively.
a. The first step is usually to form the Cartesian product of the two relations and then examine the resulting tuples to find those with a common attribute value. How many tuples result from the Cartesian product that then have to be examined to complete the join operation?
b. Now suppose that the two tables have each been sorted on the common attribute. Explain how the join operation can be done more cleverly, avoid the Cartesian product, and examine (read) at most only (p + q) rows.
c. To accomplish a join operation of Author and Writes over Name, how many rows must be examined? d. To accomplish a join operation of Book and Writes over ISBN, how many rows must be examined? (See Exercise 26 for why this operation would not be a good idea anyway.)