The Relational Algebra

A relation is a set of tuples over a fixed schema of named attributes. The relational algebra defines operators that take one or two relations as input and produce a new relation as output. This closure property — relations map to relations — is the algebra's defining feature, analogous to how `+` and `×` on integers produce integers, letting you nest `(2+3)×4` without leaving the world of integers. Because relational operators are closed, you can nest them: `σ(π(R ⋈ S))` is itself a relation, ready to be fed into another operator. There are six fundamental operators, chosen because no smaller set can express everything the algebra expresses, and because every other useful operator (join, intersection, division) can be derived from them:

• Selection (σ), written σ_predicate(R): keeps rows of R satisfying a Boolean predicate. It filters horizontally.
• Projection (π), written π_attributes(R): keeps only specified columns, discarding the rest, and removes any duplicate rows that result (since a relation is a set). It filters vertically.
• Union (∪), written R ∪ S: the set union of two relations, valid only when R and S are union-compatible — same number of attributes, matching domains.
• Set difference (−), written R − S: tuples in R that are not in S, also requiring union-compatibility.
• Cartesian product (×), written R × S: every tuple of R paired with every tuple of S, with no compatibility restriction — attribute names are simply concatenated (and renamed if they clash).
• Rename (ρ), written ρ_S(A₁,…,Aₙ)(R): relabels a relation and/or its attributes without changing its contents, resolving name clashes before a product or join.

Every other operator is derived — expressible as a combination of the six. Intersection R ∩ S equals R − (R − S). Join, the algebra's most celebrated derived operator, is defined as ``` R ⋈_θ S ≡ σ_θ(R × S) ``` a Cartesian product followed by a selection on the join condition θ. The common special case, natural join, further projects away duplicate columns that share a name across R and S, matching tuples where those shared attributes agree. This derivation is not a curiosity — it is the single fact that makes cost-based query optimization possible, because it tells the optimizer that a join can legally be rewritten as its constituent product-plus-selection, and, crucially, that selections and projections can often be pushed inside a join to shrink intermediate results before the expensive pairing happens.

An algebra query is not evaluated as flat text; it is parsed into an expression tree, where leaves are base relations and internal nodes are operators. Evaluation proceeds bottom-up: each node consumes the relation(s) produced by its children and produces a new relation, until the root yields the final answer. Consider the query "names of students who got an A in a course taught by 'Kirmani'," over relations `Enrollment(sid, cid, grade)`, `Course(cid, title, instructor)`, `Student(sid, name)`. ``` π_name( σ_(grade='A' ∧ instructor='Kirmani')( Enrollment ⋈_(Enrollment.cid = Course.cid) Course ) ⋈_(sid) Student ) ``` Below is language-agnostic pseudocode for evaluating an arbitrary expression tree, plus the concrete implementations of the physical operators it dispatches to. Each function returns a materialized relation — a set of tuples with a schema — matching the closure property. ``` // A relation is a pair: (schema: list of attribute names, tuples: set of tuples) function EVALUATE(node): if node is a LEAF (base relation R): return R.load() // read from storage else if node.op == SELECT(predicate): child = EVALUATE(node.child) result.schema = child.schema result.tuples = { t in child.tuples : predicate(t) } return result else if node.op == PROJECT(attrs): child = EVALUATE(node.child) result.schema = attrs result.tuples = SET({ t.restrict(attrs) : t in child.tuples }) // dedup! return result else if node.op == UNION: left = EVALUATE(node.left) right = EVALUATE(node.right) assert left.schema ~ right.schema // union-compatible result.schema = left.schema result.tuples = left.tuples ∪ right.tuples return result else if node.op == DIFFERENCE: left = EVALUATE(node.left) right = EVALUATE(node.right) assert left.schema ~ right.schema result.schema = left.schema result.tuples = { t in left.tuples : t not in right.tuples } return result else if node.op == PRODUCT: left = EVALUATE(node.left) right = EVALUATE(node.right) result.schema = left.schema + right.schema // concatenate, rename clashes result.tuples = { concat(t1, t2) : t1 in left.tuples, t2 in right.tuples } return result else if node.op == RENAME(newName, newAttrs): child = EVALUATE(node.child) return relabel(child, newName, newAttrs) else if node.op == JOIN(theta): // derived operator return EVALUATE( SELECT(theta, PRODUCT(node.left, node.right)) ) ``` Two implementation notes matter for correctness. First, projection must deduplicate — because a relation is a set of tuples, projecting onto fewer columns can make previously distinct tuples collide, and the algebra's semantics demand the duplicates be removed (this is exactly why `π` is more expensive than it looks: it needs a sort or hash pass, not just a column copy). Second, union and difference require union-compatibility — same arity, corresponding domains — otherwise the result is not a well-formed relation and the expression is simply illegal, not merely inefficient. A real query engine does not evaluate `JOIN` literally as `SELECT(PRODUCT(...))` — it substitutes a physical operator (hash join, sort-merge join, nested-loop join) that computes the same result set far more efficiently by never materializing the full product. The algebra guarantees these physical operators are interchangeable precisely because they all compute the same relation as `σ_θ(R × S)` — the algebra is the specification, the physical operator is the implementation.

Correctness rests on an invariant maintained by every operator: the input to each node is a well-formed relation (a finite set of tuples with a fixed schema), and the output is also a well-formed relation. This is proved by structural induction on the expression tree.

• Base case: a leaf is a stored relation, well-formed by definition (the Relational Model guarantees this at the storage layer).
• Inductive step: assume the child/children of a node are well-formed relations. Selection filters a set by a predicate — still a set, same schema, so well-formed. Projection maps tuples to a shorter tuple and takes the resulting set (removing duplicates) — still a well-formed relation, by construction. Union and difference are standard set operations on two sets of the same schema (guaranteed by the union-compatibility check), so the result is a well-formed set of that schema. Product pairs every tuple of one relation with every tuple of another, producing a set of concatenated tuples over the concatenated schema — well-formed as long as attribute name clashes are resolved by rename.

Since every operator preserves well-formedness given well-formed inputs, induction gives well-formedness for the whole tree, including the root — i.e., every syntactically valid algebra expression denotes a relation. This is exactly the closure property the whole system depends on.

Complexity. Let R have `r` tuples and S have `s` tuples, both over relations with tuples of bounded size (schema is fixed and small compared to `r, s`).

The critical honesty point: product is genuinely quadratic, and a naive evaluator that literally computes `σ(R × S)` for every join pays O(r·s) time and space, materializing a huge intermediate relation before filtering it down. This is why real systems never implement join this way. A hash join builds a hash table on the smaller relation's join attribute (O(r) to build, assuming r ≤ s) and then streams S, probing the hash table in expected O(1) per tuple, giving expected O(r + s) total time — orders of magnitude better than O(r·s) for large r, s. A sort-merge join sorts both sides (O(r log r + s log s)) and merges in O(r + s), giving O((r+s) log(r+s)) overall, which is worse than hash join in expectation but has better worst-case guarantees and produces sorted output "for free," useful when a subsequent operator wants sorted input. The algebra's equivalence rules — e.g., σ commutes past projection when the predicate only mentions retained attributes, and selection distributes over union/difference/product ("push selections down") — are what let an optimizer replace a query tree that computes a huge product early with an equivalent tree that filters first and joins last, shrinking every intermediate relation the query touches. The rewriting is sound precisely because both trees denote the same relation by the well-formedness/closure proof above — algebraic equivalence, not guesswork, licenses the optimization.

Take three small relations. `Enrollment(sid, cid, grade)`:

`Course(cid, title, instructor)`:

`Student(sid, name)`:

Query: names of students with grade A in a course taught by Kirmani.

Step 1 — Cartesian product `Enrollment × Course` conceptually produces all 4×2 = 8 combinations (shown only as a concept — a real engine never materializes this): 8 rows total, pairing every enrollment with every course row.

Step 2 — Selection `σ_(Enrollment.cid = Course.cid ∧ grade='A' ∧ instructor='Kirmani')` on that product keeps only rows where the join condition holds and the extra predicate holds:

(The (101, CS210) row is dropped — Rao, not Kirmani, and grade B. The (103, CS340) row is dropped — grade C.)

Step 3 — Join with Student on `sid`, keeping only matching rows:

Step 4 — Projection `π_name` keeps only the `name` column and deduplicates:

Trace the cost: the naive plan materializes the full 8-row product before filtering, i.e. O(r·s) = O(4×2). A real optimizer instead pushes the `grade='A'` selection down to `Enrollment` before the join (shrinking it from 4 rows to 2), and pushes `instructor='Kirmani'` down to `Course` before the join (shrinking it from 2 rows to 1) — so the join itself pairs 2 rows with 1 row instead of 4 with 2. On this toy example the saving is small, but on tables with 10⁶ and 10⁴ rows respectively, filtering first versus filtering after a full product is the difference between a fast query and one that never returns.

The relational algebra was introduced alongside the relational model itself, as the formal query mechanism that gave the model teeth: a rigorous way to say what a query means, independent of any particular database system's internals.

Every production relational database — PostgreSQL, MySQL, Oracle, SQL Server, SQLite, and cloud warehouses like BigQuery, Snowflake, and Redshift — parses SQL into an internal algebraic (or near-algebraic) representation before executing it. Query optimizers work entirely in this algebraic space: they enumerate equivalent expression trees using rewrite rules derived directly from the algebra's laws (selection pushdown, join reordering, projection pruning) and choose the cheapest one using cost estimates built on the complexity facts above. Distributed query engines such as Apache Spark's Catalyst optimizer and Apache Calcite (used inside Hive, Flink, and Druid) are explicit, general-purpose implementations of relational-algebra rewriting and cost-based planning, decoupled from any single storage engine. Even NoSQL and dataframe libraries that reject full SQL — pandas, Spark DataFrames, Polars — still expose selection, projection, join, and union as their core operations, because the algebra captures the minimal, composable vocabulary that any tabular data-processing system eventually needs. Understanding the algebra is also the direct prerequisite for reasoning about Relational Calculus, its declarative counterpart, and for understanding why certain schema designs guarantee Lossless-Join Decomposition — a property stated and proved entirely in the algebra's own vocabulary of join and projection.

Ask the tutor: How does a cost-based query optimizer decide which algebraically equivalent expression tree to actually execute?