Parameterized Queries and Nesting Equivalencies

Two difficulties found in a number of papers dealing with subquery evaluation and optimization are: How do they exactly relate SQL subqueries, and how extensive is the machinery required to understand and prove the results. This is important for database implementors, who need to decide when and how to use the techniques, on arbitrary SQL queries. In this paper we describe how to represent SQL queries algebraically. The mapping is comprehensive, in the sense that it covers all SQL subqueries; the target algebra is the standard relational algebra augmented by a new operator, Apply, that abstracts parameterized execution. To deal with SQL, duplicate semantics are considered. Properties of Apply can be derived relatively easily from known properties of relational operators. Out of Apply properties follow some known subquery optimizations, along with tight, but easy to understand preconditions. Based on the mapping into the semantically clean relational algebra, we show that arbitrary SQL subqueries can always be unnessted; that is, we show how to rewrite any query containing subqueries into one without them.