Ludger Becker (1), Ralf Hartmut Güting (2)
becker@hrz.uni-siegen.dbp.de, gueting@dhafeu61.bitnet
(1) Universität Gesamthochschule Siegen, Fachbereich 12, Informationssysteme und geometrische Datenverarbeitung, Postfach 101240, D-5900 Siegen, West Germany
(2) Praktische Informatik IV, FB Mathematik und Informatik, FernUniversitt Hagen, Postfach 940, 5800 Hagen, West Germany
Abstract: 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. It 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.
Keywords: Rule-based optimization, extensibility, relational algebra, many-sorted algebra, geometric query processing.
Published: ACM Transactions on Database Systems 17 (1992), 247-303.