Query Unnesting in Object-Oriented Databases
Leonidas Fegaras (University of Texas at Arlington)
There is already a sizable body of proposals on OODB query
optimization. One of the most challenging problems in this area is
query unnesting, where the embedded query can take any form, including
aggregation and universal quantification. Although there is already a
number of proposed techniques for query unnesting, most of these
techniques are applicable to only few cases. We believe that the lack
of a general and simple solution to the query unnesting problem is due
to the lack of a uniform algebra that treats all operations (including
aggregation and quantification) in the same way.
This paper presents a new query unnesting algorithm that generalizes
many unnesting techniques proposed recently in the literature. Our
system is capable of removing any form of query nesting using a
very simple and efficient algorithm. The simplicity of the system is
due to the use of the monoid comprehension calculus as an intermediate
form for OODB queries. The monoid comprehension calculus treats
operations over multiple collection types, aggregates, and quantifiers
in a similar way, resulting in a uniform way of unnesting queries,
regardless of their type of nesting.