high level user query —–> query processor ——-> low level data manipulation commands

Query processing: A 3-step process that transforms a high-level query (of relational
calculus/SQL) into an equivalent and more efficient lower-level query (of relational

1. Parsing and translation
– Check syntax and verify relations.
– Translate the query into an equivalent
relational algebra expression.
2. Optimization
– Generate an optimal evaluation plan
(with lowest cost) for the query plan.
3. Evaluation
– The query-execution engine takes an
(optimal) evaluation plan, executes that
plan, and returns the answers to the

Query Decomposition
Input : Calculus query on global relations
■ Normalization
➠ manipulate query quantifiers and qualification

➠ detect and reject “incorrect” queries
➠ possible for only a subset of relational calculus

➠ eliminate redundant predicates

➠ calculus query
Τalgebraic query
➠ more than one translation is possible
➠ use transformation rules

Combine the rules already specified:
➠ Remove empty relations generated by contradicting
selections on horizontal fragments;
➠ Remove useless relations generated by projections
on vertical fragments;
➠ Distribute joins over unions in order to isolate and
remove useless joins.