Relational algebra

Why it matters

SQL is what you write; relational algebra is what the database actually executes. The optimizer turns every query into a tree of algebra operators, rearranges the tree into a cheaper equivalent, and runs it. Exams ask you to write algebra for English questions, and understanding the operators explains why a query plan looks the way it does and why some SQL rewrites make no difference while others matter enormously.

The idea

Relational algebra is a set of operators that each take one or two relations and produce a new relation. Because the output is always a relation, operators compose into expressions, just as arithmetic operators compose numbers. Six operators are fundamental; the rest can be built from them.

Operator	Symbol	Does	SQL equivalent
Selection	σ condition (R)	Keeps the tuples satisfying a condition	WHERE
Projection	π attributes (R)	Keeps chosen attributes, removes duplicates	SELECT DISTINCT columns
Rename	ρ name (R)	Renames a relation or its attributes	AS
Union	R ∪ S	Tuples in either (same schema required)	UNION
Set difference	R − S	Tuples in R but not in S	EXCEPT
Cartesian product	R × S	Every pairing of a tuple of R with a tuple of S	FROM R, S (CROSS JOIN)

Derived operators

Operator	Defined as	SQL equivalent
Intersection R ∩ S	R − (R − S)	INTERSECT
Theta join R ⋈θ S	σθ (R × S)	JOIN ... ON condition
Equi-join	Theta join whose condition uses only =	JOIN ... ON a = b
Natural join R ⋈ S	Equi-join on all same-named attributes, keeping one copy of each	NATURAL JOIN or JOIN ... USING
Left / right / full outer join	Join plus unmatched tuples padded with NULL	LEFT / RIGHT / FULL JOIN
Semi-join R ⋉ S	Tuples of R that have a match in S	WHERE EXISTS (...)
Division R ÷ S	Tuples of R related to every tuple of S	Double NOT EXISTS
Assignment	temp ← expression	WITH (a CTE)

Writing expressions

Work from the inside out. "Names of employees in the Research department": join Employee with Department on dept_id, select Research, project names:

π name (σ dname = 'Research' (Employee ⋈ Department))

The same query can be written with the selection pushed inside the join, which produces the same result much more cheaply because the join sees one department instead of all:

π name (Employee ⋈ σ dname = 'Research' (Department))

Division: the "for all" operator

Division answers questions with "every" or "all": students who have taken every subject in a list, suppliers who supply all red parts. If Takes(student, subject) and Required(subject), then Takes ÷ Required gives the students related to every required subject. It is defined as π student (Takes) − π student ((π student (Takes) × Required) − Takes): all students, minus those missing at least one required subject. In SQL it becomes a double NOT EXISTS ("there is no required subject that this student has not taken") or a GROUP BY with HAVING COUNT equal to the number of required subjects.

Algebra versus calculus

Relational algebra is procedural: an expression describes the steps. Relational calculus (tuple and domain calculus) is declarative: it describes the result as a logical formula ("tuples t such that..."). Codd showed they have the same expressive power for safe queries, and a language with that power is called relationally complete. SQL is based on calculus-style declarations and compiled into algebra, with extensions (aggregation, ordering, duplicates, NULLs) that pure algebra lacks.

Trade-offs

Pure relational algebra works on sets, has no aggregation or ordering, and ignores NULLs, which keeps it clean enough to prove equivalences that optimizers rely on. Real engines extend it to bags (duplicates), grouping and outer joins, and those extensions restrict which rewrites are valid. Knowing which algebraic laws hold (selection pushdown, join commutativity and associativity) explains what the optimizer is allowed to change.

In an interview

Translate a question into algebra out loud and then optimise it: "Project names from the join of Employee and Department filtered to Research. I would push the selection onto Department first so the join only sees matching departments; projection can also be pushed down to carry fewer columns." For "find X related to all Y", name division and give the double NOT EXISTS form.