# The OQL Optimizer

The OQL optimizer and the ODB DBMS are described in detail in the paper: "An Experimental Optimizer for OQL". The following web pages sumarize some of the differences between the paper and the actual system and present some examples:

- The OQL algebra
- The physical plan algebra
- Examples of query translation

The optimizer consists of the following stages:

1. Stage 1: normalization of comprehensions.
2. Stage 2: normalization of predicates.
3. Stage 3: translation into joins and unnests, and unesting nested queries.
4. Stage 4: materialization of path expressions.
5. Stage 5: join permutation.
6. Stage 6: plan generation.

The ODB source files are the following:

1. `basic.h`: The `Expr` class to represent terms, the list templates, etc.
2. `oql.y`: The yacc grammar for the oql syntax.
3. `oql.lex`: The lex scanner to parse tokens.
4. `typecheck.h/typecheck.gen`: The typechecking program.
5. `optimizer.gen`: The actual optimizer.
6. `evaluation.h/evaluation.gen`: The in-memory evaluator.
7. `constant.h/constant.cc`: Definition of some system functions (e.g., +, *).
8. `test.oql`: A simple schema, data, and a sample of few OQL queries against the schema.
9. `main.cc`: The main program.
10. `database`: The actual database state.
11. `common.cc`: it is included in `optimizer.gen`; it contains code for memoization and tracing.

Files `*_out.cc` and `*_str.h` are generated automatically by the compiler.