An expression is a tree. The leaves are relations, and every other node is an operator. Evaluate it from the bottom up.
text
π name, title (σ year = 2026 (instructor ⋈ teaches))π name, title
lastσ year = 2026
then⋈
firstinstructorleaf
teachesleaf
SQL to algebra
A query of this shape:
text
SELECT DISTINCT a1, a2 FROM r1, r2 WHERE pis this expression:
text
π a1, a2 (σ p (r1 × r2))| SQL clause | Operator | Place in the tree |
|---|---|---|
FROM r1, r2 / JOIN | × / ⋈ | bottom |
WHERE p | σ p | above FROM |
GROUP BY g + aggregates | g γ … | above WHERE |
HAVING q | σ q | above γ |
SELECT DISTINCT a | π a | top |
AS | ρ | where the name is needed |
UNION / INTERSECT / EXCEPT | ∪ / ∩ / − | joins two trees |
ORDER BY, LIMIT | none | relations have no order |
Without DISTINCT, SQL keeps duplicate rows. Relational algebra never does.
Equivalent expressions
Different trees can return the same relation:
text
σ year = 2026 (instructor ⋈ teaches) = instructor ⋈ σ year = 2026 (teaches)The second tree joins fewer tuples. A DBMS rewrites your query into a tree like it before it runs the query. Chapter 13 shows the plan it chooses.