Object-oriented databases (OODBs) provide powerful data abstractions and mo
deling facilities, but they generally lack a suitable framework for query p
rocessing and optimization. The development of an effective query optimizer
is one of the key factors for OODB systems to successfully compete with re
lational systems, as well as to meet the performance requirements of many n
ontraditional applications. We propose an effective framework with a solid
theoretical basis for optimizing OODB query languages. Our calculus, called
the monoid comprehension calculus, captures most features of ODMG OQL, and
is a good basis for expressing various optimization algorithms concisely.
This article concentrates on query unnesting (also known as query decorrela
tion), an optimization that, even though it improves performance considerab
ly, is not treated properly (if at all) by most OODB systems. Our framework
generalizes many unnesting techniques proposed recently in the literature,
and is capable of removing any form of query nesting using a very simple a
nd efficient algorithm. The simplicity of our method is due to the use of t
he monoid comprehension calculus as an intermediate form for OODB queries.
The monoid comprehension calculus treats operations over multiple collectio
n types, aggregates, and quantifiers in a similar way, resulting in a unifo
rm method of unnesting queries, regardless of their type of nesting.