Rule-Based Optimzation and Query Processing in an Extensible Geometric Database System : (Revised Version July 1990)
Gral is an extensible database system based on the formal concept of a many-sorted relational algebra. Many-sorted algebra is used to define any application's query language, its query execution language, and its optimization rules. In this paper we describe Gral's optimization component. lt provides (1) a sophisticated rule language - rules are transformations of abstract algebra expressions, (2) a general optimization framework under which more specific optimization algorithms can be implemented, and (3) several control mechanisms for the application of rules. An optimization algorithm can be specified as a series of steps. Each step is defined by its own collection of rules together with a selected control strategy. The general facilities are illustrated by the complete design of an example optimizer - in the form of a rule file - for a small non-standard query language and an associated execution language. The query language includes selection, join, ordering, embedding derived values, aggregate functions, and several geometric operations. The example shows in particular how the special processing techniques of a geometric database system such as spatial join methods and geometric index structures can be integrated into query processing and optimization of a relational database system. A similar, though larger, optimizer is fully functional within the geometric database system implemented as a Gral prototype.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten