Reachability Needs Recursion

Ask "is Boise in North America?" of a location hierarchy and the natural two-level join answers no — a confident, silent wrong answer, because a join follows exactly one edge and Boise is four hops deep. WITH RECURSIVE gets it right at any depth. Transitive reachability can't be a fixed-shape query.

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.

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

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;

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;

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';

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;

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';

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.

Go deeper

• 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.
• 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.
• 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.)

Sources: DDIA 2e, Ch. 3, §"Datalog: Recursive Relational Queries" and §"Graph Queries in SQL" (Example 3-6, Figure 3-7) · PostgreSQL manual, "WITH Queries (Common Table Expressions)."