Relational Algebra

Relational algebra is the formal, set-theoretic query language of the relational model. It defines what a query computes (semantics) independently of how it is executed. Every SQL query can be expressed as an extended relational algebra expression — although SQL itself goes beyond the pure algebra, with bag semantics, three-valued NULL logic, ORDER BY, and LIMIT.

A relation is a set of tuples over a schema: the notions of relation, tuple, attribute, and key are defined in Schema.

Authoritative sources

Database System Concepts, Ch. 5 (Silberschatz, Korth, Sudarshan)

Database Systems: The Complete Book, Ch. 2 (Garcia-Molina, Ullman, Widom)

Core operations

Operation	Notation	Effect
Select	σ_p(R)	Rows of R satisfying predicate p
Project	π_{a₁,…,aₖ}(R)	Columns a₁,…,aₖ of R (duplicates removed)
Cartesian product	R × S	All pairs (r, s) with r ∈ R, s ∈ S
Join	R ⋈ S	Cartesian product filtered to matching join attributes
Union	R ∪ S	Rows in R or S (duplicates removed)
Difference	R − S	Rows in R but not in S
Division	R ÷ S	Rows of R that pair with every row of S
Rename	ρ_S(R)	Rename relation R to S

The first seven operations (select, project, Cartesian product, union, difference, division, rename) form Codd’s original algebra. Join is a derived operation — an abbreviation for a Cartesian product followed by a select, $R \bowtie S \equiv \sigma_p(R \times S)$ — listed in the table because of its overwhelming practical importance. So when a text speaks of “the seven core operations”, join is not counted.

Details

Set vs. bag semantics: pure relational algebra operates on sets (no duplicates, no order). In practice, SQL uses bag (multiset) semantics: SELECT without DISTINCT preserves duplicates. The bag variant of project is written $\pi^*$ .

Closure: the set of all expressions built from these operations is closed: the result of any expression is itself a relation, so operations can be composed arbitrarily.

Expressiveness: relational algebra is equivalent in expressive power to the relational calculus (Codd’s theorem). Any query expressible in one is expressible in the other. The practical consequence: any SQL query can be translated to a relational algebra expression, and the query optimizer works by rewriting algebraic expressions.

Reading an expression: nested expressions are read from the inside out — the innermost operation executes first, and its result (a relation, by closure) feeds the next operation outward.

Worked example — read $\pi_{\text{name}}\bigl(\sigma_{\text{city}='Paris'}(\text{customers})\bigr)$ :

Innermost: $\sigma_{\text{city}='Paris'}(\text{customers})$ — keep only the rows of customers whose city is Paris. Say this yields {(1, Alice, Paris), (3, Carol, Paris)}.
Outer: $\pi_{\text{name}}(\cdot)$ — keep only the name column of that intermediate relation, removing duplicates. Result: {Alice, Carol}.

The same inside-out reading scales to any depth: in $\pi_{\text{name}}(\sigma_{\text{city}='Paris'}(\text{customers}) \bowtie \text{orders})$ , first filter customers, then join with orders, then project to name.

Example problem: in the expression $\pi_{\text{city}}\bigl(\sigma_{\text{amount}>100}(\text{orders})\bigr)$ , what does the innermost operation produce, and what does the whole expression return, given orders = {(10, 1, 200), (11, 1, 50), (12, 3, 150)} with schema orders(oid, cust_id, amount)?

Solution

Innermost $\sigma_{\text{amount}>100}(\text{orders})$ keeps rows with amount over 100: {(10, 1, 200), (12, 3, 150)} — the row (11, 1, 50) is eliminated.
Outer $\pi_{\text{city}}$ is ill-typed here: city is not an attribute of orders. This is the point of the exercise — every attribute named in a projection must exist in the schema of its input relation. The correct expression would first join with customers (which has the city column), e.g. $\pi_{\text{city}}(\sigma_{\text{amount}>100}(\text{orders}) \bowtie \text{customers})$ .

Joins

A join $R \bowtie S$ on attribute $a$ produces all pairs $(r, s)$ where $r.a = s.a$ . The result has all columns of $R$ and $S$ (with the join column appearing once). Joins are the most common operation in real queries: almost every query that touches more than one table joins.

Join types:

Inner join ( $\bowtie$ ): only matching rows.
Left outer join ( $\bowtie_{\text{left}}$ ): all rows of $R$ ; unmatched $S$ columns are NULL.
Right outer join ( $\bowtie_{\text{right}}$ ): all rows of $S$ ; unmatched $R$ columns are NULL.
Full outer join ( $\bowtie_{\text{full}}$ ): all rows of both; unmatched columns are NULL.
Cross join ( $\times$ ): Cartesian product (no join predicate).

How joins are executed (nested loop, hash join, sort-merge join, and their complexities) is covered in SQL & Query Planning.

Details

Join correctness: the inner join $R \bowtie_{R.a = S.a} S$ is equivalent to $\sigma_{R.a = S.a}(R \times S)$ . The outer join extends this: a left outer join is $(R \bowtie S) \cup (R - \pi_R(R \bowtie S))$ with NULLs filled in the $S$ columns.

Natural join: $R \bowtie S$ joins on all shared attribute names. An equi-join specifies the join predicate explicitly: $R \bowtie_{R.a = S.b} S$ .

Theta join: the join predicate is any comparison ( $R.a < S.b$ , $R.a \neq S.b$ ). An equi-join is the special case where the predicate is equality.

Multi-way joins: $R \bowtie S \bowtie T$ is ambiguous without parentheses. The query optimizer (see SQL & Query Planning) chooses the join order that minimizes cost. Join is associative and commutative (for inner joins), so the optimizer is free to reorder.

Semi-join ( $R \ltimes S$ ): returns rows of $R$ that have a match in $S$ , without duplicating $S$ columns. Useful for EXISTS subqueries.

Anti-join: rows of $R$ with no match in $S$ . Useful for NOT EXISTS.

Example problem: with customers = {(1, Alice, Paris), (2, Bob, Lyon)} and orders = {(10, 1, 200), (11, 1, 50)}, what is the left outer join $\text{customers} \bowtie_{\text{left}} \text{orders}$ on id = cust_id?

Solution

Alice (id 1) matches both orders, so she contributes two rows. Bob (id 2) has no matching order, so he contributes one row with the orders columns filled with NULL:

(1, Alice, Paris, 10, 1, 200)
(1, Alice, Paris, 11, 1, 50)
(2, Bob,   Lyon,  NULL, NULL, NULL)

An inner join would have dropped Bob entirely; the left outer join keeps him. In SQL: SELECT * FROM customers LEFT JOIN orders ON customers.id = orders.cust_id;

Visual: how a join works

Interactive: step-by-step relational algebra

The simulation below walks through two scenarios step by step: a join query (“names of Paris customers with an order over 100”) and a division query (“students enrolled in all courses”).

Division

Division $R \div S$ answers “all” queries: it returns the rows of $R$ that are associated with every row of $S$ .

Details

Formal definition: let $A$ be the set of attributes of $R$ that do not appear in $S$ , and let $r_A$ denote the tuple $r$ restricted to the attributes $A$ . Then:

R \div S = \{\, r_A \mid \forall s_B \in S,\; (r_A, s_B) \in R \,\}

In words: keep each $A$ -value that appears in $R$ paired with every tuple of $S$ . Note the condition is membership in $R$ itself — not in $R \times S$ , which would be trivially true and make the definition vacuous.

Equivalently, using only the core operations (with $A$ the attributes of $R$ not in $S$ ):

R \div S = \pi_A(R) - \pi_A\!\bigl(\pi_A(R) \times S - R\bigr)

Read it inside-out: $\pi_A(R) \times S$ builds every combination of an $A$ -value with a tuple of $S$ ; subtracting $R$ leaves the combinations that are missing; projecting those to $A$ gives the $A$ -values that fail the “all” test; subtracting them from $\pi_A(R)$ leaves the ones that pass.

Worked example: “Find students enrolled in all courses.” Let Enrolled(student, course) contain:

(Alice, Math)  (Alice, CS)   (Alice, Bio)
(Bob, Math)
(Carol, Math)  (Carol, CS)  (Carol, Bio)

and Courses(course) contain (Math), (CS), (Bio). Then Enrolled ÷ Courses = {(Alice), (Carol)}: Alice and Carol each appear paired with Math, CS and Bio, while Bob is missing CS and Bio.

SQL equivalent:

SELECT student
FROM Enrolled e
WHERE NOT EXISTS (
  SELECT c.course FROM Courses c
  WHERE NOT EXISTS (
    SELECT 1 FROM Enrolled e2
    WHERE e2.student = e.student AND e2.course = c.course
  )
);

Example problem: with Enrolled as above but Courses = {(Math), (CS)} (Bio no longer offered), what is Enrolled ÷ Courses?

Solution

Now every student must be paired with Math and CS.

Alice: Math ✓, CS ✓ → kept.
Bob: Math ✓, CS ✗ → dropped.
Carol: Math ✓, CS ✓ → kept.

Answer: {(Alice), (Carol)}. Notice the answer grew relative to the three-course version: shrinking $S$ makes the “all” condition easier to satisfy. Division is monotone decreasing in $S$ .

Aggregation

Aggregation ( $\gamma$ ): groups rows by a set of attributes and computes a summary function (SUM, COUNT, AVG, MIN, MAX) over each group. This is an extension beyond pure relational algebra, but it is the most important one in practice — every practical SQL query that uses GROUP BY relies on it.

Details

Notation: $\gamma_{a_1,\ldots,a_k;\; F_1(b_1),\ldots,F_m(b_m)}(R)$ where $a_1,\ldots,a_k$ are the grouping attributes and $F_i$ are aggregate functions applied to attribute $b_i$ .

How it works: partition the rows of $R$ into groups that share the same values of the grouping attributes, then collapse each group into a single output row carrying the group key and the aggregate values.

Example: “Total amount per city”:

\gamma_{\text{city};\; \text{SUM}(\text{amount})}(\text{orders} \bowtie \text{customers})

With the data in the diagram, the groups are {Paris: 200+50+150} and {Lyon: 120}, so the result is {(Paris, 400), (Lyon, 120)}.

SQL equivalent:

SELECT c.city, SUM(o.amount)
FROM orders o JOIN customers c ON o.customer_id = c.id
GROUP BY c.city;

Why it is an extension: pure relational algebra (the seven core operations) cannot express aggregation. Codd’s theorem holds for the unextended algebra; aggregation requires the extended relational algebra. See Silberschatz, Korth & Sudarshan, Ch. 5.2.

Example problem: with orders ⋈ customers = {(Alice, Paris, 200), (Alice, Paris, 50), (Bob, Lyon, 120), (Carol, Paris, 150)}, compute $\gamma_{\text{city};\; \text{COUNT}(*),\; \text{MAX}(\text{amount})}(\text{orders} \bowtie \text{customers})$ .

Solution

Partition by city:

Group Paris: rows (Alice, Paris, 200), (Alice, Paris, 50), (Carol, Paris, 150) → COUNT = 3, MAX(amount) = 200.
Group Lyon: row (Bob, Lyon, 120) → COUNT = 1, MAX(amount) = 120.

Result: {(Paris, 3, 200), (Lyon, 1, 120)}. Each group collapses to exactly one row, carrying the group key plus one value per aggregate function.

Algebraic properties

The algebraic laws of relational algebra are what make query optimization possible: the optimizer rewrites an expression into an equivalent one that is cheaper to execute.

Law	Form
Commutativity of union	R ∪ S = S ∪ R
Commutativity of join	R ⋈ S = S ⋈ R (inner join)
Associativity of union	(R ∪ S) ∪ T = R ∪ (S ∪ T)
Associativity of join	(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T) (inner join)
Distributivity of select over join	σ_p(R ⋈ S) = σ_p(R) ⋈ S (when p references only R)
Distributivity of project over union	π_A(R ∪ S) = π_A(R) ∪ π_A(S)
Absorption	R ∪ (R ∩ S) = R; R ∩ (R ∪ S) = R

Details

Why these matter: the distributivity of select over join is the basis of predicate pushdown — pushing a filter below a join reduces the number of rows entering the join. The commutativity and associativity of join let the optimizer reorder multi-way joins to find the cheapest plan. Together, these laws give the optimizer a search space of equivalent expressions from which it picks the most efficient one.

Worked example: consider $\sigma_{\text{city}='Paris'}(\text{customers} \bowtie \text{orders})$ . Since the predicate references only attributes of customers, distributivity gives $\sigma_{\text{city}='Paris'}(\text{customers}) \bowtie \text{orders}$ . If customers has 1,000,000 rows of which 500 are in Paris, the join input shrinks from 1,000,000 rows to 500 — before a single pair is matched.

Example problem: using the algebraic laws, rewrite $\pi_{\text{name}}\bigl(\sigma_{\text{city}='Paris'}(\text{customers} \bowtie \text{orders})\bigr)$ into an equivalent expression that is likely cheaper to execute, and justify each rewrite.

Solution

Push the select down (distributivity of select over join, predicate references only customers): $\pi_{\text{name}}\bigl(\sigma_{\text{city}='Paris'}(\text{customers}) \bowtie \text{orders}\bigr)$ .
Push the projection down (distributivity of project over join): only name (from customers) and cust_id (the join column of orders) are needed: $\pi_{\text{name}}\bigl(\pi_{\text{name},\text{id}}(\sigma_{\text{city}='Paris'}(\text{customers})) \bowtie \pi_{\text{cust\_id}}(\text{orders})\bigr)$ .

Both rewrites preserve the result exactly (they are instances of the laws in the table), but the second plan touches far fewer columns and rows — this is precisely the kind of transformation a query planner performs, as described in SQL & Query Planning.

See SQL & Query Planning for how these laws are applied in practice.

Example problem

Problem: Given tables orders(id, customer_id, amount) and customers(id, name, city), write the relational algebra expression for: “names of customers in Paris who have placed at least one order over 100.”

Solution

π_name( σ_city='Paris'(customers) ⋈ σ_amount>100(orders) )

Step by step:

$\sigma_{\text{amount} > 100}(\text{orders})$ — select orders over 100.
$\sigma_{\text{city} = 'Paris'}(\text{customers})$ — select Paris customers.
$\bowtie$ on customer_id = id — join the two filtered relations.
$\pi_{\text{name}}$ — project to just the name column (removes duplicates).

Equivalent SQL:

SELECT c.name
FROM customers c
JOIN orders o ON c.id = o.customer_id
WHERE c.city = 'Paris' AND o.amount > 100;

The optimizer may reorder these steps using the algebraic laws above; see SQL & Query Planning for the execution strategies.

Relational Algebra §

Core operations §

Joins §

Visual: how a join works §

Interactive: step-by-step relational algebra §

Division §

Aggregation §

Algebraic properties §

Example problem §

Relational Algebra

Core operations

Joins

Visual: how a join works

Interactive: step-by-step relational algebra

Division

Aggregation

Algebraic properties

Example problem