Chapter 15, Problem 8PE

Explanation of Solution

Sort-based algorithm for computing the relational division operation:

Suppose be two relations and has to be computed.

• Sort relation “s” on “S” for sort-based algorithm. Sort relation “r” on (T, S).
• Now, start scanning “r” and look at the “T” attribute values of the first tuple.
• Scan “r” till tuples have same value of “T”. Also scan “s” simultaneously and check whether every tuple of “s” also occurs as the “S” attribute of “r”, in a fashion similar to merge join.
• If this is the case, output that value of “T” and proceed with the next value of “T”.
• Relation “s” may have to be scanned multiple times but “r” will only be scanned once.
• Total disk accesses, after sorting both the relations, will be “|r| 9 N * |s|”, where “N” is the number of distinct values of “T” in “r”.

Hash-based algorithm for computing the relational division operation:

• Let assume that for any value of “T”, all tuples in “r” with that “T” value fit in memory, and consider the general case at the end...