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:

• Overview of OPTGEN and OPTL
• OPTL Reference Guide
• Optimizer Specification in OPTL
• OPTL Rule Syntax

• The monoid comprehension calculus
• The monoid algebra
• The physical plan operators
• Examples of query translation

The optimizer consists of the following stages:

1. parsing OQL queries (files oql.y and oql.lex).
2. translation of OQL queries into monoid comprehensions (file translator.gen).
3. checking the calculus for type correctness (file typecheck.gen).
4. algebraic rewriting, including normalization of comprehensions and materialization of path expressions into pointer joins (file optimizer.gen).
5. query unnesting and translation of the monoid comprehension calculus into the monoid algebra (file optimizer.gen).
6. join permutation using a cost-based heuristic (file cost_optimizer.gen).
7. physical plan generation using a rule-based cost-driven system (file rule_based_opt.gen).
8. generation of intermediate code (file code_generator.gen).
9. translation of intermediate code into C++ code (file C++_generator.gen).
10. interpretation of the intermediate code (file interpreter.gen).

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 necessary). Components:

1. the LDB storage manager, which is a SHORE Value-Added Server (VAS) (files ldb_sm.h and ldb_sm.cc).
2. the interface to the evaluation library (file eval.h).
3. the implementation of the evaluation functions (file eval.cc).

This part is very sketchy. Eventually, we will use the standard ODMG meta classes. Components:

1. parsing ODL specifications (files odl.y and odl.lex).
2. manipulation of ODL specifications: mapping ODL to SDL and updating the system catalog (files odl.gen).