Part 1 · 2 chapters · ~12 min

Relational Algebra and Calculus

Selection, projection and rename, union, difference and Cartesian product, joins derived (theta, equi, natural, semi, anti, division), algebraic equivalences used by optimisers, tuple and domain relational calculus, Codd's theorem (algebra equals safe calculus in expressive power), and what SQL cannot express without recursion.

Operators, implemented

code

const select  = (p) => (R) => R.filter(p);
const project = (cols) => (R) => dedupe(R.map(r => Object.fromEntries(cols.map(c => [c, r[c]]))));
const product = (R, S) => R.flatMap(r => S.map(s => ({ ...r, ...s })));
const njoin   = (R, S) => { const common = Object.keys(R[0]).filter(k => k in S[0]);
                            return R.flatMap(r => S.filter(s => common.every(c => r[c] === s[c])).map(s => ({ ...r, ...s }))); };
const semijoin = (R, S) => dedupe(njoin(R, S).map(j => pick(j, Object.keys(R[0]))));
const antijoin = (R, S) => diff(R, semijoin(R, S));
const division = (R, S) => { const A = project(as)(R); return diff(A, project(as)(diff(product(A, S), R))); };
// real output: σ owner=Ada → [{acct:"A1",owner:"Ada"}] · ⋈ → 3 rows · ⋉ → Ada, Bayo · ▷ → Chi · ÷ → [{acct:"A1"}]

RELATIONAL ALGEBRA, RUN

output of the course's TypeScript interpreter

swipe the figure sideways, or tap expand for full screen

1/4

unary operators

Selection σ keeps rows matching a predicate; projection π keeps columns and removes duplicates; rename ρ changes attribute names.

σ, π, ρrows, columns, names

Equivalences the optimiser uses

rule	equivalence	why it helps
cascade of selections	σ_p∧q(R) = σ_p(σ_q(R))	split predicates to push them separately
selection pushdown	σ_p(R ⋈ S) = σ_p(R) ⋈ S if p uses only R	filter before joining: fewer rows to join
projection pushdown	drop unused columns early	narrower rows, columnar engines read less
join commutativity and associativity	R ⋈ S = S ⋈ R; (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)	the optimiser may choose any join order (part 4)
subquery to semijoin	WHERE EXISTS (…) → R ⋉ S	enables hash semijoins instead of nested loops

Calculus and Codd's theorem: tuple relational calculus describes what to retrieve ({ t | t ∈ accounts ∧ ∃ s ∈ transfers (s.acct = t.acct) }) rather than how. Codd proved that relational algebra and safe relational calculus have the same expressive power, which is why a declarative SQL query can always be compiled into an algebra plan. What SQL could not express was transitive closure (all accounts reachable through a chain of transfers): neither algebra nor calculus can, which is why SQL:1999 added WITH RECURSIVE.