Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases

download complete text (postscript, 77k)

Jens Claußen
Alfons Kemper
Guido Moerkotte
Klaus Peithner
Proc. of the 23st Intl. Conf. on Very Large Data Bases (VLDB), Athens, Greece, August 1997, pages 286-295.
We investigate the optimization and evaluation of queries with universal quantification in the context of the object-oriented and object-relational data models. The queries are classified into 16 categories depending on the variables referenced in the so-called range and quantifier predicates. For the three most important classes we enumerate the known query evaluation plans and devise some new ones. These alternative plans are primarily based on anti-semijoin, division, generalized grouping with count aggregation, and set difference. In order to evaluate the quality of the many different evaluation plans a thorough performance analysis on some sample database configurations was carried out. The quantitative analysis reveals that---if applicable---the anti-semijoin-based plans are superior to all the other alternatives, even if we employ the most sophisticated division algorithms. Furthermore, exploiting object-oriented features, anti-semijoin plans can be derived even when this is not possible in the relational context.
An extented version is available as
Technical Report MIP-9706, Universität Passau, March 1997
download complete text (postscript, 178k)

Last modified: Wed Nov 10 12:05:03 MET 1999