# DDIA Ch. 3: reachability needs recursion

## Concept

Store a location hierarchy the obvious way — each place records the place it is
`within` (Boise → Ada County → Idaho → United States → North America) — and ask
"is Boise in North America?" A SQL join follows exactly *one* edge, so the
natural query bakes in a fixed number of hops. You will write the sensible
two-level join, watch it answer **"Boise is not in North America"** — a
confident, silent *wrong* answer — and then watch `WITH RECURSIVE` get it right
at any depth. The lesson: transitive reachability can't be expressed by a
fixed-shape query, no matter how many joins you add.

## Provenance

*Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini,
2025), Chapter 3 — *Data Models and Query Languages*, §"Datalog: Recursive
Relational Queries" (and §"Graph Queries in SQL"):

> recursive queries on graphs are a particular strength of Datalog.

The book shows the same idea in SQL via recursive common table expressions
(Example 3-6) and illustrates transitive `within` reachability with Figure 3-7,
"Determining that Idaho is in North America." Here you make the fixed-join
version fail on purpose, then fix it with recursion.

## Prerequisites

The surprise is about what a join can and cannot express. These help; each line
notes where it shows up.

1. **The adjacency-list model** — a hierarchy stored as a self-referencing
   foreign key (`within_id` points at the parent row). One table encodes a whole
   tree/graph.
2. **A join is one edge** — `child JOIN parent ON child.within_id = parent.id`
   walks exactly *one* hop up the tree. k hops means k joins written into the
   query. The query's *shape* fixes the traversal depth.
3. **Transitive closure / reachability** — "is X reachable from Y by following
   edges repeatedly?" The path length is a property of the *data*, not the query.
4. **Recursive CTEs (`WITH RECURSIVE`)** — an *anchor* row set `UNION ALL` a
   *recursive* term that references the CTE itself, iterated until no new rows
   appear (a fixpoint). This is the tool that escapes the fixed-shape limit.

### Where to learn them

- **Recursive CTEs (#4):** the PostgreSQL manual, "WITH Queries (Common Table
  Expressions)" — the `WITH RECURSIVE` section walks the anchor + recursive-term
  structure with a graph example.
- **Adjacency list vs. alternatives (#1, #3):** search "adjacency list vs
  closure table SQL hierarchy" — the closure table is the denormalized way to
  make reachability a plain join (a Go-deeper below).
- **The graph framing (#2–#3):** DDIA's own Cypher examples (3-4/3-5) show the
  variable-length path operator `-[:WITHIN*]->` that says "any number of hops"
  directly — the thing SQL needs `WITH RECURSIVE` to express.

If only one is new, make it #4 — it's the whole fix.

## Environment

The behavior here is exact and reproducible (it's about correctness, not
timing), so your run will match line-for-line:

- macOS 26.5.2 (Darwin 25.5.0), arm64
- Docker 29.6.2 running the official `postgres:16` image → PostgreSQL 16.14
- One `locations` table, 10 rows (a small hierarchy of varying depth)

## Mental model

The `locations` table is an adjacency list: each row names a place and points at
the place it is `within`. That encodes a tree:

```
North America
└─ United States
   ├─ Idaho
   │  └─ Ada County
   │     └─ Boise
   └─ California
      └─ Los Angeles
```

A single join climbs one level of that tree. To ask "everything within North
America," you need to climb *all* the way down — but the number of levels
(Boise is 4 below North America; California is 2) is a fact about the data, and
a SQL join count is fixed when you write the query. That mismatch is the whole
exercise: a fixed number of joins answers for a fixed depth, and silently misses
anything deeper.

## Setup

```
# start Postgres 16 (first run pulls the image)
docker run -d --name ddia-ch3 -e POSTGRES_PASSWORD=study -e POSTGRES_DB=study postgres:16
sleep 3

# load the 10-row hierarchy (setup may be scripted — the queries may not)
docker cp recursion_setup.sql ddia-ch3:/tmp/
docker exec ddia-ch3 psql -U postgres -d study -f /tmp/recursion_setup.sql

# open an interactive session and type the steps below by hand
docker exec -it ddia-ch3 psql -U postgres -d study
```

## Steps

### Step 1 — one join, one hop (calibration)

**Predict.** What does a single self-join return for "what is directly within
the United States?"

```
SELECT child.name AS directly_within_us
FROM locations child
JOIN locations parent ON child.within_id = parent.id
WHERE parent.name = 'United States'
ORDER BY child.name;
```

**Observe.**

```
 directly_within_us
--------------------
 California
 Idaho
(2 rows)
```

Idaho and California — the two direct children. One join expresses exactly one
level of containment. This is all a join ever does.

### Step 2 — everything within North America, with joins (the surprise)

**Predict.** Now list *everything* within North America. The natural approach:
join down a couple of levels (children, then grandchildren). There are 6 places
under North America — how many does this two-level join return, and is Boise one
of them?

```
SELECT l1.name AS place, 1 AS hops_below_na
FROM locations l1
JOIN locations na ON l1.within_id = na.id
WHERE na.name = 'North America'
UNION ALL
SELECT l2.name, 2
FROM locations l2
JOIN locations l1 ON l2.within_id = l1.id
JOIN locations na ON l1.within_id = na.id
WHERE na.name = 'North America'
ORDER BY hops_below_na, place;
```

**Observe.**

```
     place     | hops_below_na
---------------+---------------
 United States |             1
 California    |             2
 Idaho         |             2
(3 rows)
```

Only **3** of the 6. The join reaches exactly two levels down and stops —
Ada County, Los Angeles, and Boise (all deeper) are simply gone. And it doesn't
error; it returns a tidy, confident, *incomplete* result. Ask it directly:

```
SELECT count(*) AS boise_found_by_fixed_join
FROM (
  SELECT l1.name FROM locations l1 JOIN locations na ON l1.within_id = na.id
    WHERE na.name = 'North America'
  UNION ALL
  SELECT l2.name FROM locations l2 JOIN locations l1 ON l2.within_id = l1.id
    JOIN locations na ON l1.within_id = na.id WHERE na.name = 'North America'
) t
WHERE name = 'Boise';
```

```
 boise_found_by_fixed_join
---------------------------
                         0
```

**The query says Boise is not in North America.** It is — Boise is 4 hops down.
You could add a third join, and a fourth, but the tree's depth is data; whatever
number you pick is wrong for something deeper.

### Step 3 — the same question, recursively (the fix)

**Predict.** `WITH RECURSIVE` starts at North America and re-applies the same
one-hop join until nothing new appears. How many places now, and does it find
Boise?

```
WITH RECURSIVE within_na AS (
  SELECT id, name, within_id, 0 AS hops_below_na
  FROM locations WHERE name = 'North America'
  UNION ALL
  SELECT l.id, l.name, l.within_id, w.hops_below_na + 1
  FROM locations l
  JOIN within_na w ON l.within_id = w.id
)
SELECT name AS place, hops_below_na
FROM within_na
WHERE name <> 'North America'
ORDER BY hops_below_na, place;
```

**Observe.**

```
     place     | hops_below_na
---------------+---------------
 United States |             1
 California    |             2
 Idaho         |             2
 Ada County    |             3
 Los Angeles   |             3
 Boise         |             4
(6 rows)
```

All **6**, down to Boise at 4 hops — and the query never mentions the number 4.
The recursive version answers "is Boise in North America?" correctly:

```
WITH RECURSIVE within_na AS (
  SELECT id, name, within_id FROM locations WHERE name = 'North America'
  UNION ALL
  SELECT l.id, l.name, l.within_id FROM locations l
    JOIN within_na w ON l.within_id = w.id
)
SELECT count(*) AS boise_found_by_recursion FROM within_na WHERE name = 'Boise';
```

```
 boise_found_by_recursion
--------------------------
                        1
```

## What you should see

- One join = one hop: direct children only (**2 rows** for the US).
- The fixed two-level join returns **3 of 6** places and reports Boise
  **not found (0)** — a silent, wrong answer, not an error.
- `WITH RECURSIVE` returns all **6** (Boise at depth 4) and finds Boise
  **(1)** — the same query regardless of how deep the tree goes.

## Why

A SQL join follows exactly one edge. `child JOIN parent ON child.within_id =
parent.id` is a single hop up the tree, so k levels of containment require k
joins physically written into the query. The *shape* of the query — how many
joins it contains — hard-codes a traversal depth at the moment you type it.

But "is X within Y?" is a question about a path whose length lives in the data:
Boise → Ada County → Idaho → United States → North America is four edges;
California → United States → North America is two. No single join count matches
every path, so any fixed-shape query is correct only for the depths it happens
to enumerate and quietly wrong for the rest. That is why Step 2 didn't throw an
error — it answered a *different*, shallower question ("within 2 hops") and
returned 0 for Boise. The dangerous failures here are false negatives that pass
every test written on shallow data and then miss deeper rows in production.

`WITH RECURSIVE` removes the fixed shape. It seeds the result with the anchor
(North America), then repeatedly applies the *same* one-hop join to whatever it
found last round, stopping only when a round adds nothing new — a fixpoint. One
query text, unbounded depth. This is the transitive closure of the `within`
relation, and computing it is inherently iterative: it is exactly what the book
means when it says recursive queries on graphs are a particular strength of
Datalog, and why graph query languages like Cypher give you a variable-length
path operator (`-[:WITHIN*]->`, "any number of `WITHIN` edges") as a first-class
primitive.

**The boundary — when you actually need it.** A fixed number of joins is fine
when the depth is genuinely fixed and known (a person → their employer →
that employer's country is always three hops). The moment the question is
"within / ancestor of / part of / reachable from … *at any depth*," the path
length is unbounded and a plain join hierarchy cannot express it — you need
recursion, a precomputed closure table, or a graph database. The tell is the
word "any": any level, any number of hops. That word is where relational joins
stop and recursion begins.

### Go deeper

1. **Add a level, break the fixed join again.** Insert `('North Boise' within
   'Boise')` and re-run Step 2. The fixed join's answer doesn't change; the
   recursive one now returns 7. Concrete proof the fixed shape tracks the query,
   not the data.
2. **The emigration query.** Add people with `born_in` and `lives_in` edges,
   then write the book's "who emigrated from the US to Europe?" — `born_in`
   something within the US and `lives_in` something within Europe. It needs the
   recursive `within` set twice.
3. **The closure-table alternative.** Precompute a `location_ancestors(descendant,
   ancestor)` table (every place paired with every ancestor). Now "is Boise in
   North America?" is a single indexed lookup — no recursion at query time.
   What did you trade away? (Every insert/move must maintain the closure — the
   denormalization tradeoff from the other Ch. 3 exercises, again.)