Tech Report CS-91-41

Object-Oriented Query Optimization: What's the Problem?

Gail Mitchell, Stanley B. Zdonik and Umeshwar Dayal

June 1991


An object-oriented database model can support features such as abstract data types, methods, encapsulation, subtyping (or inheritance), complex structures, and object identity. The processing of queries in such a model also entails support for these features. Query optimization will require new techniques for supporting the object-oriented features. Although many of the problems that must be solved by an object-oriented query optimizer are similar to problems solved by relational and extensible optimizers, there are also many problems that are unique to the object-oriented model.

In this paper we explore some of the problems that are encountered when trying to optimize queries in an object-oriented database. We present these problems in the context of the modeling constructs which generate the problem. We also survey current approaches to solving some of these problems and discuss problems that are not addressed by these approaches.

(complete text in pdf or gzipped postscript)