CTEs (WITH clause) — recursive CTEs: Foundations

Before you can read the parent note, you need to actually see every symbol it throws at you. This page assumes you know nothing — not what a table is, not what a set-union means, not what an arrow in a diagram stands for. We build each piece, anchor it to a picture, and only then use it.

0. A row and a table — the atoms

Everything in a database is built from two words, so we start there.

Figure — CTEs (WITH clause) — recursive CTEs

Why the topic needs this: the recursive CTE's whole job is to produce rows round after round. When the parent says "an iteration produces zero new rows", it literally means "no new horizontal strips appeared in the grid". Hold that picture — it is the heartbeat of the entire algorithm.

1. `SELECT ... FROM ...` — asking the table a question

Definition The SELECT statement

SELECT chooses which columns you want; FROM names which table to read them from. Optional WHERE keeps only rows that pass a test.

SELECT name, salary      -- give me these two columns
FROM   employees         -- out of this table
WHERE  salary > 50000;   -- but only rows passing this test

Why the topic needs this: both the anchor and the recursive member are ordinary SELECT statements. If you can't read a SELECT, the parent's code blocks are gibberish.

2. `WHERE` and a comparison test — the gate

The WHERE clause holds a condition: a yes/no test applied to each row. Only rows where the answer is "yes" survive.

n < 5 — is this row's n smaller than 5? (< means "less than")
manager_id IS NULL — is the manager field empty? (more on NULL below)
e.src = r.node — does one row's src equal another row's node? (= means "equal")

3. `NULL` — the "there is nothing here" marker

Why the topic needs this: in the org-chart example, the CEO has manager_id IS NULL — the CEO reports to nobody, so that field is genuinely empty. The anchor query uses exactly that to find the top of the tree: "start from the person with no boss." Without understanding NULL, you can't see why WHERE manager_id IS NULL picks out precisely one starting row.

4. A `JOIN` — gluing two tables by a matching column

Why the topic needs this: the recursive member is almost always a join between the CTE (rows found so far) and a base table (all possible next rows). See SQL Joins for the full treatment. If join is fuzzy, the recursive step will look like magic.

5. `UNION` and `UNION ALL` — stacking two result sets

6. Sets and the symbols $\cup$ and $\emptyset$

The parent note writes maths like $R = W_{0} \cup W_{1} \cup \dots$ and $W_{n + 1} = \emptyset$ . Here's what those squiggles mean, in plain words.

So the parent's line $R = W_{0} \cup W_{1} \cup W_{2} \cup \dots \cup W_{n} where W_{n + 1} = \emptyset$ says in English: "the final answer $R$ is everything the anchor found, plus everything round 1 found, plus round 2… and we know to stop because round $n + 1$ produced the empty bag."

$R$ = the running total (the Result).
$W_{i}$ = the Working table — the bag of brand-new rows produced in round $i$ . The subscript $i$ is just a round counter: $W_{0}$ is the anchor's output, $W_{1}$ the next round, and so on.

7. Why this is induction, not mystery

The structure — one base case, one rule that builds the next case from the previous — is exactly Mathematical Induction run forwards.

Induction word	Recursive-CTE word	Picture
Base case	Anchor ( $W_{0}$ )	the first domino you push
Inductive step	Recursive member	"if domino $k$ falls, domino $k + 1$ falls"
Terminating bound	Stop guard (`WHERE`)	the last domino — nothing after it

Why the topic needs this: if you already trust induction (a base case + a step that always advances = a whole chain), you already trust that a recursive CTE terminates and covers every reachable row. Same idea, dressed in SQL.

8. What is a hierarchy / graph anyway?

The parent traverses org charts, folder trees, and graph paths. One shared picture underlies all three.

Why the topic needs this: the recursive member walks edges one hop per round. A tree guarantees termination for free (you can only go so deep). A cycle does not — hence the path array and <> ALL cycle guard in worked example 3. See Tree and Graph Data Structures.

Prerequisite map

Equipment checklist

Test yourself — each line hides its answer.

I can read SELECT name FROM emp WHERE salary > 100 aloud as a sentence

"Give me the name column, from the emp table, keeping only rows whose salary is over 100."

A query's output is the same kind of thing as its input

Yes — both are tables of rows; that symmetry is what lets a CTE reference itself.

NULL means

the value is absent / unknown — test it with IS NULL, never = NULL.

A JOIN B ON A.x = B.y produces

one combined row for every pair where A.x equals B.y.

The difference between UNION and UNION ALL

UNION removes duplicate rows (slower, can guard cycles); UNION ALL keeps all rows (faster, loops forever on cycles).

The symbol

\cup

means

union — combine two bags of rows into one.

The symbol

\emptyset

means

the empty set — zero rows; it signals the loop to stop.

W_{i}

stands for

the working table — the bag of brand-new rows produced in round

i

Why the recursive member reads only

W_{i - 1}

so each row is processed exactly once, guaranteeing the loop winds down (like a relay baton hand-off).

The three induction analogues (base / step / bound) map to

anchor / recursive member / stop guard.

A cycle in a graph is dangerous because

it can keep producing rows forever, so you need a visited-path guard, UNION, or a depth limit.

Connections

Parent topic — the full recursive-CTE note this page prepares you for
Common Table Expressions (WITH clause) — the non-recursive WITH you build on
SQL Joins — the glue inside every recursive member
UNION vs UNION ALL — the termination policy switch
Tree and Graph Data Structures — what you traverse
Mathematical Induction — base case + step = the same idea
Window Functions — the other advanced-read tool worth knowing next