Relational Databases

You’ve heard of them. My absolute favorite is the humble SQLite, if only for its license ❤️

The relational part doesn’t come from the fact that tables in a database ‘relate’ to each other. It comes from the Math that was specified about these by EF Codd at IBM in 1970. This Mathamatical formalism is the reason why SQL is so elegant and powerful and will be around a long, long while¹. Having an overview is helpful. Codd’s is pretty heavy paper. I am going to try and distill a few things from it.

---

Relational Algebra

A relation is a set that looks like this: $S = \{(s_{j1}, s_{j2}, \ldots, s_{jn}) \mid j = 1 \ldots m\}$.

• It’s a set of tuples.
• $m$ is the cardinality — Number of rows.
• $n$ is the arity — Number of columns.
• Each $n$ is an attribute, a named column.
• Each column has a domain, a type, and every entry in the column is drawn from it.
  E.g. age is an integer for every row.
• A header is the list of attribute names, e.g. $(pid, name, age)$.
  Names are unique within a relation, which is how $\sigma$ and $\pi$ refer to columns (see below)

Note that a relation is a set: there are no duplicate rows and no row order². SQL tables relax both of these!

The Patient table below has arity 3, cardinality 3, header $(pid, name, age)$, and contains tuples like $(1, \text{Ana}, 34)$.

$$\overbrace{ \begin{array}{|c|c|c|} \hline \mathllap{\text{header} \rightarrow \qquad} \textbf{pid} & \textbf{name} & \textbf{age} \\ \hline\hline \mathllap{\text{tuple} \rightarrow \qquad} 1 & \text{Ana} & 34 \\ \hline 2 & \text{Bo} & 58 \mathrlap{\qquad \smash{\left.\vphantom{\begin{array}{|c|}\hline 1 \\ \hline 1 \\ \hline 1 \\ \hline \end{array}}\right\} \ \text{cardinality } m = 3}} \\ \hline 3 & \text{Cy} & 71 \\ \hline\hline \mathllap{\text{domain} \rightarrow \qquad} \mathbb{Z} & \text{string} & \mathbb{Z} \\ \hline \end{array} }^{\text{arity } n = 3}$$

• Relational algebra is a small set of operators that map relations $\rightarrow$ relations.
• Because outputs are relations, operators compose
  This is why SQL queries nest and why a database can rewrite them.
• SQL is basically a friendlier syntax over this.
  The Query Planner turns your SQL back into an algebra tree!

Cheatsheet

Keep it Basic

$\sigma, \pi, \rho, \times, \cup, -$

Those are the Primitives: Everything else can be built from those (joins, intersection) or is an extension added for practicality (outer joins, aggregation, NULL).

Operator	Name	SQL-Equivalent (Kinda)
$\sigma$	Selection	WHERE
$\pi$	Projection	SELECT col, ...
$\rho$	Rename	AS
$\times$	Cartesian product	CROSS JOIN / FROM A, B
$\bowtie$	Join	JOIN ... ON
$\cup$, $-$, $\cap$	Set ops	UNION, EXCEPT, INTERSECT
⟕, ⟖, ⟗	Outer joins	LEFT / RIGHT / FULL JOIN
$\ltimes$, $\triangleright$	Semi/anti join	EXISTS, NOT EXISTS
$\gamma$	Aggregation	GROUP BY + COUNT, SUM, …

---

Toy Example

Consider these two tables:

$$\begin{array}{c} \textbf{Patient} \\[4pt] \begin{array}{|c|c|c|} \hline pid & name & age \\ \hline 1 & \text{Ana} & 34 \\ 2 & \text{Bo} & 58 \\ 3 & \text{Cy} & 71 \\ \hline \end{array} \end{array} \qquad\qquad \begin{array}{c} \textbf{Visit} \\[4pt] \begin{array}{|c|c|c|} \hline vid & pid & dx \\ \hline 10 & 1 & \text{flu} \\ 11 & 3 & \text{copd} \\ 12 & 3 & \text{flu} \\ \hline \end{array} \end{array}$$

Selection $\sigma$ — Pick Rows

$$\sigma_{age > 50}(\text{Patient}) = \{(2, \text{Bo}, 58),\ (3, \text{Cy}, 71)\}$$

SELECT * FROM Patient WHERE age > 50;

THis naming is confusing since algebra’s selection is SQL’s WHERE, not SQL’s SELECT. Conditions combine with $\wedge, \vee, \neg$ = AND, OR, NOT.

Selection is what indexes speed up. A B-tree on age lets the engine find matching rows without scanning the table.

Projection $\pi$ — Pick Columns

$$\pi_{dx}(\text{Visit}) = \{\text{flu}, \text{copd}\}$$

SELECT dx FROM Visit;          -- flu, copd, flu
SELECT DISTINCT dx FROM Visit; -- flu, copd

This is important: Algebra works on sets, so duplicates vanish automatically. SQL works on bags (multisets) and keeps duplicates unless you say DISTINCT. Deduping costs a sort or hash, so SQL makes it optional. This set vs bag gap is where SQL diverges from theory!

Rename with $\rho$

$$\rho_{p}(\text{Patient})$$

SELECT * FROM Patient AS p;
SELECT name AS patient_name FROM Patient;

Seems silly, but it’s needed whenever a table meets itself (self join), since the two copies have identical column names otherwise.

Cartesian product $\times$ — Every Row With Every Other Row

$\text{Patient} \times \text{Visit}$ has $3 \times 3 = 9$ rows, most of them nonsense (Ana paired with Cy’s visits).

SELECT * FROM Patient CROSS JOIN Visit;
SELECT * FROM Patient, Visit;   -- same thing, old syntax

Rarely what you want by itself, but it’s the foundation of joins. Forgetting a join condition in the old comma syntax gives you this accidentally, which is the classic “why did my query return 40 million rows” bug.

Join $\bowtie$ — Product then Filter

A join is defined as a product followed by a selection:

$$\text{Patient} \bowtie_{\text{Patient.pid} = \text{Visit.pid}} \text{Visit} \;=\; \sigma_{\text{Patient.pid} = \text{Visit.pid}}(\text{Patient} \times \text{Visit})$$

pid	name	age	vid	dx
1	Ana	34	10	flu
3	Cy	71	11	copd
3	Cy	71	12	flu

SELECT * FROM Patient JOIN Visit ON Patient.pid = Visit.pid;
SELECT * FROM Patient NATURAL JOIN Visit;  -- joins on all same-named cols

Variants: theta join (any condition), equijoin (condition is =), natural join (equijoin on same-named columns, shared column kept once).

In a database: the definition says “build the product, then filter,” but no engine actually does that! SQL is declarative so it’s about expressing the meaning/what, not the algorithm/how.

Real engines use nested loop, hash join, or sort-merge join, all of which produce the same relation without materializing 9 or 9 billion rows.

Set Operations — $\cup$, $-$, $\cap$

Patients with no visits:

$$\pi_{pid}(\text{Patient}) - \pi_{pid}(\text{Visit}) = \{1,2,3\} - \{1,3\} = \{2\}$$

SELECT pid FROM Patient
EXCEPT
SELECT pid FROM Visit;

Operands must be union-compatible (same columns). In SQL that means same number of columns with compatible types³.

UNION dedupes via set semantics. UNION ALL keeps duplicates via bag semantics and is faster since it skips the dedupe.

Note that $\cap$ isn’t a primitive: $R \cap S = R - (R - S)$

Outer Joins ⟕ — Keep Unmatched Rows

Patient ⟕ Visit:

pid	name	age	vid	dx
1	Ana	34	10	flu
2	Bo	58	NULL	NULL
3	Cy	71	11	copd
3	Cy	71	12	flu

SELECT * FROM Patient LEFT JOIN Visit ON Patient.pid = Visit.pid;

Not part of Codd’s classical algebra, because filling gaps needs a NULL value, and pure relations have no such thing. This is where all of SQL’s three-valued logic weirdness (NULL = NULL is not true, IS NULL, etc.) enters!

A Full Outer Join is $R$ ⟗ $S$ = ($R$ ⟕ $S$) $\cup$ ($R$ ⟖ $S$).

Semijoin $\ltimes$ and antijoin $\triangleright$

• Semijoin: rows of the left that have some match, returning only left columns.
• Antijoin: rows with no match.

$$\begin{align*} \text{Patient} \triangleright \text{Visit} & = \{\text{Bo}\} \\ \text{Patient} \ltimes \text{Visit} & = \{\text{Ana}, \text{Cy}\} \end{align*}$$

SELECT * FROM Patient p WHERE EXISTS     (SELECT 1 FROM Visit v WHERE v.pid = p.pid);
SELECT * FROM Patient p WHERE NOT EXISTS (SELECT 1 FROM Visit v WHERE v.pid = p.pid);

Note Cy appears once in the semijoin even though Cy has two visits. A regular JOIN would duplicate Cy. In EXPLAIN output you’ll literally see “Semi Join” / “Anti Join” nodes, since planners rewrite EXISTS / IN / NOT EXISTS into these.

Aggregation $\gamma$ — Grouping

$${}_{dx}\gamma_{\text{COUNT}(*)}(\text{Visit}) = \{(\text{flu}, 2),\ (\text{copd}, 1)\}$$

SELECT dx, COUNT(*) FROM Visit GROUP BY dx;

Also an extension and not in the original algebra. Grouping columns go on the left of $\gamma$, aggregate functions on the right. Same rule as SQL: anything in SELECT must be grouped or aggregated.

---

Queries are Trees 🌳

Let’s try this: “Names of patients over 50 diagnosed with flu”. Expressed in Relational Algebra,

$$\pi_{name}\big(\sigma_{age > 50 \,\wedge\, dx = \text{`flu'}}(\text{Patient} \bowtie \text{Visit})\big) = \{\text{Cy}\}$$

SELECT name
FROM Patient JOIN Visit ON Patient.pid = Visit.pid    -- ⋈
WHERE age > 50 AND dx = 'flu';                        -- σ
-- SELECT name                                        -- π

Read the algebra inside-out and you get SQL’s logical execution order: FROM/JOIN → WHERE → GROUP BY → HAVING → SELECT → ORDER BY. This is why you can’t use a SELECT alias in WHERE: projection happens after selection.

Query Optimization

Because operators have algebraic laws, the planner can rewrite a tree into an equivalent, cheaper one. The big one is selection pushdown: filter as early as possible so joins see fewer rows.

$$\sigma_{age > 50 \,\wedge\, dx = \text{'flu'}}(\text{Patient} \bowtie \text{Visit}) \;\equiv\; \sigma_{age > 50}(\text{Patient}) \bowtie \sigma_{dx = \text{'flu'}}(\text{Visit})$$

Left side joins 3 × 3 then filters. Right side filters to 2 patients and 2 visits first, then joins. Same answer, less work. In Will-It-Scale-Bro scenarios, this can be the difference between seconds and minutes.

Other tricks the planner uses becuase of the lovely Math:

• Joins are commutative and associative, so $A \bowtie B \bowtie C$ can run in any order. Picking the order (using table statistics) is most of what a cost-based optimizer does.
• $\sigma_{a \wedge b} = \sigma_a(\sigma_b(\cdot))$, so compound WHERE clauses can be split and pushed to different tables.
• Projection can be pushed down too (only carry needed columns), which is what columnar stores like DuckDB and Parquet readers exploit.

Be curious

Best way to learn this stuff is to run EXPLAIN on any query to see the actual operator tree the database chose.

Footnotes

1. Like how LISP is undergirded by Lambda Calculus and will stick around for a long while. ↩

2. This becomes important when you look at the First Normal Form. ↩

3. Which is why you might see “each UNION query must have the same number of columns” error. ↩