15.8

Design sort-based and hash-based algorithms for computing the relational division operation (see Practice Exercise 2.9 for a definition of the division operation).

---

From Practice Exercise 2.9 we know that we can express the relational division operation as follows:

\[ r \div s = \Pi_{R-S}(r) - \Pi_{R-S}((\Pi_{R-S}(r) \times s) - \Pi_{R-S, S}(r)) \]

From section 15.6.2 we know how to implement projection.

From section 15.6.3 we know how to implement set difference.

And for the cartesian product \(\Pi_{R-S}(r) \times s\) we can use Block Nested-Loop Join discussed in section 15.5.2 (except that we don’t have any predicate to test.)

Thus to implement \(r \div s\) simply use pipelined evaluation (see section 15.7.2) on the following expression:

\[ \Pi_{R-S}(r) - \Pi_{R-S}((\Pi_{R-S}(r) \times s) - \Pi_{R-S, S}(r)) \]

Note: For an alternative answer to the above you can read page 5 of https://www.db-book.com/Practice-Exercises/PDF-practice-solu-dir/15.pdf