Query Processing Concepts and Techniques for Set Containment Tests

Relational division is an operator of the relational algebra that realizes universal quantifications in queries against a relational database, which can be interpreted as a set containment test. Expressing a universal quantification problem in SQL is cumbersome. Division was introduced by Edgar Codd in 1972 together with other operators of the relational algebra. However, unlike the join operator, for example, it has never been implemented in a commercial relational database system. If the division operator would have a counterpart in a query language, a more intuitive formulation of universal quantification problems would be possible. Although division is a derived operator (like the join operator, it can be expressed using other basic algebra operators) the performance of queries involving a division problem can be significantly increased if it is implemented as a separate operator in a query processor. In this book, we study the set containment test problem and discuss the integration of the division operator into a relational database system. We also present a natural generalization of the division operator which is useful to solve problems like finding frequent itemsets.