Nested Queries in Object Bases

Sophie Cluet, Guido Moerkotte

           Many declarative query languages for object-oriented (oo)
           databases allow nested subqueries. This paper contains (1)
           the first algebra which is capable of handling arbitrary
           nested queries and (2) the first complete classification of
           oo nested queries and the according unnesting strategies.

           For unnesting, a two-phase approach is used. The first phase---
           called {\em dependency-based optimization}---transforms
           queries at the query language level in order to treat common
           subexpressions and independent subqueries more efficiently. The
           transformed queries are translated to nested algebraic
           expressions.  These entail nested loop evaluation which may be
           very inefficient.  Hence, the second phase {\em unnests} nested
           algebraic expressions to allow for more efficient evaluation.

           The paper also discusses the differences between unnesting
           in the relational and unnesting in the oo context. Since the
           first phase is rather simple, the paper concentrates on the
           second phase.