Optimizing object queries using an effective calculus

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.