A formal foundation for object-oriented, algebraic query processing
Karen Davis · 1990
The field of object-oriented database systems is characterized by many implemented systems but no consensus on an underlying formal data model. The lack of a theoretical foundation has hindered research into formal query languages and accompanying research into provably correct logical query optimization. This research introduces the Class Algebra, an object-oriented query language, and develops a formal foundation for logical query optimization. The Class Algebra extends the semantics of relational algebra to support complex objects, including both object-based query processing and value-oriented query processing. The Class Algebra may serve as a query language for any structurally similar model, i.e., any model which supports generalization, aggregation, encapsulation, and strict inheritance. The Class Algebra has the classical benefits of an algebraic query language; it supports view mapping, query language studies, and logical query optimization. The Class Algebra is defined using denotational semantics in order to provide a formal specification of object-oriented database query evaluation. The semantic domains of the formal definition include descriptions of both the intension and extension of a structurally-rich object-oriented data model, enabling query results to be specified both intensionally and extensionally. Contributions of the Class Algebra include closure, lazy evaluation of query results, and support for reasoning about algebraic expressions. A formal foundation is established for two facets of logical query optimization for the Class Algebra: algebraic transformations and application of the Classifier. Algebraic transformations, proven correct using the formal definition, provide the basis for rewriting algebraic expressions into more efficient forms. The Classifier, a tool for inferring structural relationships based on class membership definitions, can be applied to database problems such as schema design, schema integration, and query processing. The Class Algebra Classifier is based on rules of inference, proven to be sound, complete, and tractable. The role of the Classifier in logical query optimization is briefly explored; inferred information can be used to simplify query expressions and to establish logical access paths to the query result. This research contributes a detailed formal foundation for query processing in an object-oriented data model.