Recursive SQL (WITH RECURSIVE)

The WITH keyword

The WITH keyword in SQL allows a recursive declaration: a query that refers to its own name. This enables expressing computations that would otherwise require an unbounded number of RA expressions.

Non-terminating recursion

A naive recursive query has no fixed point and runs forever:

WITH R AS (
  SELECT 1 AS n
)
SELECT n + 1 FROM R;

This generates 1, 2, 3, … indefinitely. Real recursive CTEs require a base case and a termination condition.

Bounded recursion with a base case

WITH countUp AS (
  SELECT 1 AS n                   -- base case
  UNION ALL
  SELECT n + 1 FROM countUp       -- recursive step
  WHERE n < 3                     -- termination condition
)
SELECT * FROM countUp;

Result:

n
1
2
3

The recursive CTE works as follows:

1. Evaluate the base case (seed: n = 1).
2. Apply the recursive step to the result of the previous iteration.
3. Add the new rows to the result.
4. Repeat from step 2 until the recursive step produces no new rows.

RECURSIVE keyword

SQL:1999 introduced WITH RECURSIVE. Some implementations require the keyword; others infer recursion from the self-reference.

Bacon numbers with recursion

The Bacon number problem can be solved cleanly with a recursive CTE:

WITH RECURSIVE bacon(n, pid) AS (
  SELECT 0 AS n, pid2 AS pid
  FROM coactors
  WHERE pid1 = 'nm0000102'    -- Kevin Bacon's person_id
    AND pid1 = pid2           -- ensures reflexivity for Bacon himself

  UNION

  SELECT n + 1 AS n, c.pid2 AS pid
  FROM bacon
  JOIN coactors AS c ON c.pid1 = bacon.pid
  WHERE NOT (c.pid2 IN (SELECT pid FROM bacon))  -- exclude already-found actors
    AND n < 20                                    -- safety limit
)
SELECT n, COUNT(*)
FROM (
  SELECT MIN(n) AS n, pid
  FROM bacon
  GROUP BY pid
) AS shortest
GROUP BY n;

Key elements of this query:

Element	Purpose
Base case n = 0	Seeds the recursion with Kevin Bacon
AND pid1 = pid2	Ensures Bacon has Bacon number 0 (reflexive self-co-acting)
UNION (not UNION ALL)	Avoids duplicates that could cause infinite loops
NOT (c.pid2 IN (SELECT pid FROM bacon))	Prevents revisiting actors; ensures shortest path is found
n < 20	Safety limit; prevents infinite recursion on pathological data
Outer MIN(n)	For actors reachable via multiple paths, picks the shortest

Graph databases

As noted in the lecture, computing Bacon numbers is much easier in a graph database (covered in Lecture 8), where shortest-path queries are a primitive operation. The recursive SQL approach is instructive for understanding transitive closure but is not the most natural tool for the job.

Recursive CTE mechanics

A recursive CTE has this general form:

WITH RECURSIVE cte_name(columns) AS (
  <non-recursive base query>
  UNION [ALL]
  <recursive query referencing cte_name>
)
SELECT ... FROM cte_name;

Variant	Behaviour
UNION	Eliminates duplicates each iteration (safer, avoids cycles)
UNION ALL	Preserves duplicates (faster, but risks infinite loops if not careful)

Summary

• WITH RECURSIVE enables expressing computations requiring transitive closure in SQL.
• A recursive CTE has a base case, a recursive step, and (ideally) a termination condition.
• n < 20 is a safety limit to prevent infinite recursion.
• The Bacon number query shows a complete recursive CTE: base, recursion, deduplication, and shortest-path extraction.
• Graph databases handle shortest-path queries more naturally than recursive SQL.