LDB: System Overview
The following is a tour over the LDB source code.
The *.gen files contain OPTL code, which is processed by OPTGEN (an
OPTimizer GENerator). OPTGEN is a tool for writing query optimizers
for both object-relational and object-oriented databases. It is based on a
highly declarative language, OPTL, in which you can specify query
transformation rules as rules in an attribute grammar. You can find
more information from the following web pages:
The OQL optimizer is described in detail in the paper:
"Optimizing Object Queries Using an Effective Calculus".
The following web pages summarize some of the differences between the
paper and the actual system and present some examples:
The optimizer consists of the following stages:
- parsing OQL queries (files oql.y
- translation of OQL queries into monoid comprehensions
- checking the calculus for type correctness
- algebraic rewriting, including normalization of comprehensions and
materialization of path expressions into pointer joins
- query unnesting and translation of the monoid comprehension calculus into the monoid algebra
- join permutation using a cost-based heuristic
- physical plan generation using a rule-based cost-driven system
- generation of intermediate code
- translation of intermediate code into C++ code
- interpretation of the intermediate code
The physical plans generated by the query optimizer are translated
into C++ code (last stage of the optimizer). The C++ code consists of
calls to a library of evaluation functions. Since the physical plan
operators are higher-order in nature, most evaluation functions are
higher-order too (ie. they are C++ functions that take functions as
parameters). The query evaluation is done in a pipelined fashion
(i.e. streams are materialized in the secondary storage only when
- the LDB storage manager, which is a SHORE Value-Added Server (VAS) (files ldb_sm.h and ldb_sm.cc).
- the interface to the evaluation library (file eval.h).
- the implementation of the evaluation functions (file eval.cc).
This part is very sketchy. Eventually, we will use the standard ODMG meta classes.
- parsing ODL specifications (files odl.y
- manipulation of ODL specifications: mapping ODL to SDL and updating the system catalog (files odl.gen).
Last modified: 8/9/02 by Leonidas Fegaras