Modeling a query optimizer with multi-level logic programming

Authors: M. Bieliková, B. Finance, G. Gardarin, L. Molnár, P. Návrat, M. Smolárová and Z.H. Tang

Reference: Revue ingenierie des systemes d'information, 5(2):195-218, 1997.


  1. Introduction
  2. A Programming Technique for Implementing Multi-level Logic Programs
    • Reflection
    • Design of a Multilevel Logic Program
  3. Query Optimizer Architecture
  4. Optimizer Representation by a Multi-level Logic Program
    • Modules
    • Combining Modules in Multi-level Logic Programming
  5. Conclusions

Abstract: The paper describes a rule-based query optimizer for object-oriented databases. The originality of the approach is through a multi-level logic programming used to model both query rewriting and planning, as well as search strategies. Our approach offers means of abstraction for expressing various kinds of knowledge involved in a query optimizer. It also offers techniques for structuring them according to both generality levels and knowledge content, i.e. meta-levels. We present a programming technique that allows to write modules which can be at various meta-levels. This research has been motivated by the needs to provide more lucid and effective means for describing and structuring all the various knowledge contained in a query optimizer. To illustrate these ideas, we show how multi-level programming can be used to model a query optimizer for an object-oriented database.

Keywords: query optimization, object-oriented database, module, meta-interpretation, multi-level logic programming, Prolog.

PS version (389K file, 20 pages) together with a GZ version (109K file) is available.

to Homepage to Publications to the Top

Last updated:
Mária Bieliková bielik [zavináč] fiit-dot-stuba-dot-sk
Design © 2oo1 KoXo