Jacek Plodzien, Kazimierz Subieta

Optimization of Object-Oriented Queries by Factoring Out Independent Subqueries

889

Abstract

We generalize query optimization methods based on rewriting for a general object-oriented model and a formalized OQL-like query language. Our approach makes it possible to detect and factor out independent subqueries in queries built upon traditional or new query operators, including dependent joins of OQL, quantifiers, generalized path expressions and method invocations. In contrast to well-known methods relying on specific patterns of algebraic or calculus expressions, our method is based on a formal analysis of scoping and binding rules for names occurring in a query and its subqueries. It neither depends on the complexity of an independent subquery nor on the operator connecting this subquery to its parent query. Being very general, the method is simple to understand and analyze. We follow the stack-based approach to object-oriented query languages (having roots in the semantics of programming languages), rather than object algebras or calculi.

Key words: object-oriented data model, query processing, environment stack, static analysis of queries, query optimization, rewriting rules, stack-based approach, independent subqueries, factoring out.