Appendix E — Relational Algebra Reference

A one-page companion to Chapter 4: the operations every SQL query is built from, their symbols, and their SQL mapping.

The core operators

Symbol Name Meaning SQL
σ (sigma) Selection keep rows satisfying a condition WHERE
π (pi) Projection keep chosen columns (set: dedups) SELECT list (+ DISTINCT for true set)
× Cartesian product every pairing of two relations CROSS JOIN / FROM a, b
⋈ (Theta/Natural) Join product + selection on a match JOIN ... ON
∪ Union tuples in R or S UNION
∩ Intersection tuples in both R and S INTERSECT
− Difference tuples in R but not S EXCEPT
ρ (rho) Rename rename relation/attributes AS / aliases
÷ Division tuples in R related to all of S (no direct SQL; emulated)

Extended (not in pure algebra): grouping/aggregation (GROUP BY, SUM…), outer joins (LEFT/RIGHT/FULL JOIN).

Key properties

  • Closure — every operation takes relations in and returns a relation out. This is why subqueries, CTEs, and views work (you can query a query's result).
  • Composition — operations chain: π name (σ price>200 (products)) = SELECT name FROM products WHERE price > 200.
  • Join = product + selection — A ⋈(A.x=B.y) B = σ A.x=B.y (A × B). A missing join condition leaves the full product (an accidental cross join).

SQL = algebra (the mapping to remember)

   π name, price ( σ price > 100 ( products ⋈ categories ) )
   =
   SELECT p.name, p.price          -- π
   FROM products p JOIN categories c ON c.category_id = p.category_id   -- ⋈
   WHERE p.price > 100;            -- σ
  • WHERE = σ · SELECT list = π · JOIN = ⋈ · CROSS JOIN = × · UNION/INTERSECT/EXCEPT = ∪/∩/− · AS = ρ.
  • False friend: SQL's keyword SELECT is projection (π), not selection (σ).

Equivalences (the basis of optimization)

The optimizer rewrites your query among equivalent expressions to find a cheaper one (Ch. 24). Examples:

  • Push selection down: σ_c (R ⋈ S) ≡ (σ_c R) ⋈ S when c only involves R — filter before the join.
  • Push projection down: drop unneeded columns early.
  • Join commutativity/associativity: R ⋈ S ≡ S ⋈ R; reorder joins.
  • Equivalence guarantees the same result, not the same cost.

Set vs. bag semantics

Pure algebra works on sets (no duplicates). SQL works on bags (duplicates allowed) by default → hence DISTINCT (force set projection) and UNION ALL (keep duplicates) vs UNION (dedup).

"Never / none" = difference (anti-join)

"X with no related Y" is a difference (−), expressed in SQL as EXCEPT, NOT EXISTS, or LEFT JOIN … WHERE right IS NULL. A WHERE row-filter can't express the absence of a related row.

See also: Chapter 4 (Relational Algebra), Chapter 6 (joins), Chapter 9 (subqueries), Chapter 10 (set operations), Chapter 24 (optimization).