On the reusability of query optimization algorithms (Q750138)

In the paper the problem of software reusability is solved. The author demonstrates the reusability on nonrecursive query optimization algorithms which establish important building-blocks for database system construction. The goal of the paper is to achieve the reusability by (1) imposing standardized interfaces and (2) expressing algorithms in a DBMS- implementation-independent manner. Section 2 gives a background for the query processing. It contains a description of relational algebra operations like restriction, join, join-filter, and cross product. Section 3 shows that the plug compatibility of a class of query optimization algorithms can be achieved by distinguishing between reducing phase and joining phase algorithms, and imposing standardized interfaces based on query graphs. A list of known algorithms covering these phases is given. The most essential part of the paper is contained in Section 4. First, to each query a query graph based on above relational operations is assumed. Then, a rule-based query processing is applied by giving a set of rules making it possible to rewrite query graphs. Due to a high level of abstraction we can describe query optimization algorithms as parametric, implementation-independent procedures. Algorithms described in the above formalism are reusable in DBMSs with radically different storage structures. (An implementation of relational operation is solved on a lower level.) The approach is useful in so called extensible database systems which are often referred to as the DBMSs of the 1990's. In agreement with the author, the results in the paper are practical contributions to the realization of extensible database system technology.