Recursive queries: WITH RECURSIVE and Datalog

A recursive query repeats a join until it finds nothing new. In SQL it is a common table expression written WITH RECURSIVE, made of two parts joined by UNION or UNION ALL: an anchor, the rows to start from, and a recursive member, which refers to the expression’s own name and goes one step further from the rows found so far. The database runs the anchor, then runs the recursive member again and again on the rows of the previous step, and stops when a step adds no row. That answers questions whose depth is not known in advance: every city reachable by train, everyone who reports to a manager, every part inside an assembly. Relational algebra cannot express them, because each algebra expression joins a fixed number of times. Datalog, a language of facts and rules, has recursion at its centre, and the way Datalog is evaluated explains what WITH RECURSIVE does.

Every SQLite query here, and the Python program of the Datalog section, can be run from this page (SQLite 3.49.1 in sql.js 1.14.2, Python in Pyodide). PostgreSQL’s SEARCH and CYCLE clauses, which SQLite lacks, and its rules for the recursive part are shown as the output psql printed on PostgreSQL 18.6.

Questions with no fixed depth

Take a table of direct trains, one row per pair of cities. “Where can I go from Chennai with one train?” is a selection. “With two trains?” joins routes with itself once. Any fixed number of trains is a fixed number of joins, and a union of a few such expressions covers “at most three trains”. But “with any number of trains” would need as many joins as the longest trip in the data, and that number is not known when the query is written. Aho and Ullman proved that no relational algebra expression computes this transitive closure of a relation in general. A recursive query does:

-- Direct trains between cities, one row per pair. The data has two cycles.
CREATE TABLE routes (src TEXT NOT NULL, dst TEXT NOT NULL, PRIMARY KEY (src, dst));
INSERT INTO routes VALUES
  ('Chennai', 'Bengaluru'), ('Bengaluru', 'Mysuru'), ('Mysuru', 'Chennai'),
  ('Bengaluru', 'Hubballi'), ('Hubballi', 'Pune'), ('Pune', 'Mumbai'),
  ('Mumbai', 'Pune'), ('Kolkata', 'Bhubaneswar');

WITH RECURSIVE reach(city) AS (
  SELECT 'Chennai'                  -- the anchor: where the search starts
  UNION                             -- keeps only rows not produced before
  SELECT r.dst                      -- the recursive part: one more train
  FROM routes AS r JOIN reach ON r.src = reach.city
)
SELECT city FROM reach ORDER BY city;

┌───────────┐
│   city    │
├───────────┤
│ Bengaluru │
│ Chennai   │
│ Hubballi  │
│ Mumbai    │
│ Mysuru    │
│ Pune      │
└───────────┘

• The anchor is the single row Chennai. The recursive member joins the rows found so far with routes and returns the cities one more train away.
• The data has two cycles, Chennai, Bengaluru and Mysuru back to Chennai, and Pune to Mumbai and back. The query still ends, because UNION keeps only rows it has not produced before, so a city reached a second time adds nothing.
• Kolkata and Bhubaneswar are linked to each other but not to Chennai, so they never appear.

How WITH RECURSIVE runs

The query is written recursively, but PostgreSQL’s manual points out that it is evaluated by iteration. The evaluation keeps two things: the result so far, and a working table holding the rows of the last step.

1. The anchor runs once. Its rows (without duplicates, under UNION) fill both the result and the working table.
2. The recursive member then runs against the working table alone. Under UNION, every row it returns that is already in the result, or repeated in the same step, is thrown away. The rest are added to the result and become the new working table.
3. When a step returns nothing new, the working table is empty and the evaluation is over.

The key detail is that each step reads only the rows of the step before, never the whole result again. That keeps the work proportional to the rows that are new, and it is the idea Datalog calls semi-naive evaluation, which the last section measures.

SQLite reaches the same rows in a slightly different way. It keeps a queue of rows: it removes one, runs the recursive member with that single row standing in for the whole table, and appends whatever comes back. Without an ORDER BY in the recursive member the queue is first in, first out, which the manual says you should not rely on.

Cycles: when UNION stops the recursion and when it does not

UNION stopped the first query because its rows were just city names, and a city found again is an exact repeat. Add a column that changes on every step, such as the number of trains so far, and no row is ever an exact repeat: (Mysuru, 2), (Mysuru, 5) and (Mysuru, 8) are all different. The query then runs for ever, so this one carries a guard:

CREATE TABLE routes (src TEXT NOT NULL, dst TEXT NOT NULL, PRIMARY KEY (src, dst));
INSERT INTO routes VALUES
  ('Chennai', 'Bengaluru'), ('Bengaluru', 'Mysuru'), ('Mysuru', 'Chennai'),
  ('Bengaluru', 'Hubballi'), ('Hubballi', 'Pune'), ('Pune', 'Mumbai'),
  ('Mumbai', 'Pune'), ('Kolkata', 'Bhubaneswar');

-- With a train count in every row, a row is never repeated around a cycle, so
-- UNION no longer ends the recursion. The guard trains < 12 is what ends it.
WITH RECURSIVE trip(city, trains) AS (
  SELECT 'Chennai', 0
  UNION
  SELECT r.dst, trip.trains + 1
  FROM routes AS r JOIN trip ON r.src = trip.city
  WHERE trip.trains < 12
)
SELECT count(*) AS rows_made, count(DISTINCT city) AS cities FROM trip;

-- The fewest trains to each city: the same rows, reduced afterwards.
WITH RECURSIVE trip(city, trains) AS (
  SELECT 'Chennai', 0
  UNION
  SELECT r.dst, trip.trains + 1
  FROM routes AS r JOIN trip ON r.src = trip.city
  WHERE trip.trains < 12
)
SELECT city, min(trains) AS fewest_trains
FROM trip GROUP BY city ORDER BY fewest_trains, city;

-- How many rows the guarded query makes for four different guards.
WITH RECURSIVE trip(guard, city, trains) AS (
  SELECT column1, 'Chennai', 0 FROM (VALUES (6), (12), (24), (48))
  UNION
  SELECT trip.guard, r.dst, trip.trains + 1
  FROM routes AS r JOIN trip ON r.src = trip.city
  WHERE trip.trains < trip.guard
)
SELECT guard, count(*) AS rows_made FROM trip GROUP BY guard ORDER BY guard;

┌───────────┬────────┐
│ rows_made │ cities │
├───────────┼────────┤
│ 34        │ 6      │
└───────────┴────────┘
┌───────────┬───────────────┐
│   city    │ fewest_trains │
├───────────┼───────────────┤
│ Chennai   │ 0             │
│ Bengaluru │ 1             │
│ Hubballi  │ 2             │
│ Mysuru    │ 2             │
│ Pune      │ 3             │
│ Mumbai    │ 4             │
└───────────┴───────────────┘
┌───────┬───────────┐
│ guard │ rows_made │
├───────┼───────────┤
│ 6     │ 14        │
│ 12    │ 34        │
│ 24    │ 74        │
│ 48    │ 154       │
└───────┴───────────┘

The guard trip.trains < 12 is what ended the first query, after 34 rows for 6 cities. The second query keeps the smallest count per city, which is what a journey planner wants. The third query runs the same recursion with four guards at once and shows the price of guarding instead of detecting the cycle: the rows grow in step with the guard, from 14 for a guard of 6 to 154 for a guard of 48, although there are still only 6 cities. A guard is a safety net against runaway data, and a limit you have to choose; it is no substitute for knowing when a trip repeats itself.

To detect the repetition, carry the path in each row and refuse to step onto a city that is already on it. This version adds one more train, from Mysuru to Hubballi, and lists every trip from Chennai to Mumbai that visits no city twice:

CREATE TABLE routes (src TEXT NOT NULL, dst TEXT NOT NULL, PRIMARY KEY (src, dst));
INSERT INTO routes VALUES
  ('Chennai', 'Bengaluru'), ('Bengaluru', 'Mysuru'), ('Mysuru', 'Chennai'),
  ('Bengaluru', 'Hubballi'), ('Hubballi', 'Pune'), ('Pune', 'Mumbai'),
  ('Mumbai', 'Pune'), ('Kolkata', 'Bhubaneswar'), ('Mysuru', 'Hubballi');

-- Carry the path taken so far, and never step onto a city that is already on it.
WITH RECURSIVE trip(city, path) AS (
  SELECT 'Chennai', '/Chennai/'
  UNION ALL
  SELECT r.dst, trip.path || r.dst || '/'
  FROM routes AS r JOIN trip ON r.src = trip.city
  WHERE instr(trip.path, '/' || r.dst || '/') = 0
)
SELECT path FROM trip WHERE city = 'Mumbai' ORDER BY length(path), path;

┌─────────────────────────────────────────────────┐
│                      path                       │
├─────────────────────────────────────────────────┤
│ /Chennai/Bengaluru/Hubballi/Pune/Mumbai/        │
│ /Chennai/Bengaluru/Mysuru/Hubballi/Pune/Mumbai/ │
└─────────────────────────────────────────────────┘

PostgreSQL 14 added the SQL standard’s built-in form of the same idea. CYCLE city SET is_cycle USING path tracks the path in an array, sets is_cycle to true on the first row that returns to a city already on its path, and does not extend that row. SEARCH BREADTH FIRST BY city SET visit_order adds a column that sorts the result by distance from the start (DEPTH FIRST sorts it like a walk down each branch):

# PostgreSQL 18: the SQL-standard CYCLE and SEARCH clauses of a recursive query.
from pg_session import psql

psql("""
CREATE TABLE routes (src text NOT NULL, dst text NOT NULL, PRIMARY KEY (src, dst));
INSERT INTO routes VALUES
  ('Chennai', 'Bengaluru'), ('Bengaluru', 'Mysuru'), ('Mysuru', 'Chennai'),
  ('Bengaluru', 'Hubballi'), ('Hubballi', 'Pune'), ('Pune', 'Mumbai'),
  ('Mumbai', 'Pune'), ('Kolkata', 'Bhubaneswar');

-- UNION ALL with no guard of our own: CYCLE marks a row that returns to a city
-- already on its path, and does not extend that row any further.
WITH RECURSIVE trip(city, trains) AS (
    SELECT 'Chennai', 0
  UNION ALL
    SELECT r.dst, t.trains + 1 FROM routes AS r JOIN trip AS t ON r.src = t.city
) CYCLE city SET is_cycle USING path
SELECT city, trains, is_cycle, path FROM trip ORDER BY trains, city;

-- SEARCH BREADTH FIRST adds a column to sort by: nearer cities first.
WITH RECURSIVE trip(city, trains) AS (
    SELECT 'Chennai', 0
  UNION ALL
    SELECT r.dst, t.trains + 1 FROM routes AS r JOIN trip AS t ON r.src = t.city
) SEARCH BREADTH FIRST BY city SET visit_order
  CYCLE city SET is_cycle USING path
SELECT city, trains FROM trip WHERE NOT is_cycle ORDER BY visit_order;
""")

CREATE TABLE
INSERT 0 8
   city    | trains | is_cycle |                           path                            
-----------+--------+----------+-----------------------------------------------------------
 Chennai   |      0 | f        | {(Chennai)}
 Bengaluru |      1 | f        | {(Chennai),(Bengaluru)}
 Hubballi  |      2 | f        | {(Chennai),(Bengaluru),(Hubballi)}
 Mysuru    |      2 | f        | {(Chennai),(Bengaluru),(Mysuru)}
 Chennai   |      3 | t        | {(Chennai),(Bengaluru),(Mysuru),(Chennai)}
 Pune      |      3 | f        | {(Chennai),(Bengaluru),(Hubballi),(Pune)}
 Mumbai    |      4 | f        | {(Chennai),(Bengaluru),(Hubballi),(Pune),(Mumbai)}
 Pune      |      5 | t        | {(Chennai),(Bengaluru),(Hubballi),(Pune),(Mumbai),(Pune)}
(8 rows)

   city    | trains 
-----------+--------
 Chennai   |      0
 Bengaluru |      1
 Hubballi  |      2
 Mysuru    |      2
 Pune      |      3
 Mumbai    |      4
(6 rows)

The first query uses UNION ALL and no guard of its own, yet it ends: the two rows marked t are the moments a trip came back to Chennai and to Pune, and nothing grew from them. The second query drops those rows and lists each city once, nearest first. SQLite does not have these clauses:

CREATE TABLE routes (src TEXT NOT NULL, dst TEXT NOT NULL);

-- PostgreSQL's standard CYCLE clause: SQLite does not know it.
WITH RECURSIVE trip(city) AS (
  SELECT 'Chennai'
  UNION ALL
  SELECT r.dst FROM routes AS r JOIN trip ON r.src = trip.city
) CYCLE city SET is_cycle USING path
SELECT * FROM trip;

Parse error near line 4: near "CYCLE": syntax error

PostgreSQL also restricts what the recursive member may contain, and it stops evaluating when the outer query has read enough rows:

# What PostgreSQL 18 refuses in the recursive part of a query, and one way to stop a runaway query.
from pg_session import psql

psql("""
CREATE TABLE routes (src text NOT NULL, dst text NOT NULL);
INSERT INTO routes VALUES ('Chennai', 'Bengaluru'), ('Bengaluru', 'Mysuru');

-- An aggregate over the rows of the step itself.
WITH RECURSIVE reach(city, n) AS (
    SELECT 'Chennai', 1
  UNION
    SELECT r.dst, count(*) FROM routes AS r JOIN reach ON r.src = reach.city GROUP BY r.dst
)
SELECT * FROM reach;

-- Negation of the query's own result: "a city not reached yet".
WITH RECURSIVE far(city) AS (
    SELECT 'Chennai'
  UNION
    SELECT r.dst FROM routes AS r WHERE NOT EXISTS (SELECT 1 FROM far WHERE far.city = r.dst)
)
SELECT * FROM far;

-- No end condition at all: LIMIT in the outer query stops the evaluation here.
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n)
SELECT i FROM n LIMIT 3;
""")

CREATE TABLE
INSERT 0 2
ERROR:  aggregate functions are not allowed in a recursive query's recursive term
LINE 4:     SELECT r.dst, count(*) FROM routes AS r JOIN reach ON r....
                          ^
ERROR:  recursive reference to query "far" must not appear within a subquery
LINE 4: ... FROM routes AS r WHERE NOT EXISTS (SELECT 1 FROM far WHERE ...
                                                             ^
 i 
---
 1
 2
 3
(3 rows)

An aggregate in the recursive member is refused, because it would summarise a step while that step is still being computed; so is a subquery that refers to the expression’s own name, such as NOT EXISTS (… FROM far …), which would ask “not reached yet” about a result that is still growing. The last query has no end condition at all, and LIMIT 3 stops it because PostgreSQL computes only as many rows as the outer query fetches. The manual recommends this only for testing: other engines may compute everything first, and a sort or a join in the outer query reads all the rows anyway.

Hierarchies and bills of materials

The same pattern walks a tree. A reporting line needs no cycle check, as long as the data really is a tree, and SQLite has one extra feature that suits it: an ORDER BY in the recursive member chooses which queued row is expanded next. Sorting by level, deepest first, turns the walk into a depth-first one, so each manager is followed by their whole team before the next manager at the same level. Each row also carries its chain of managers, one name longer per step:

CREATE TABLE staff (id INTEGER PRIMARY KEY, name TEXT NOT NULL, manager INTEGER REFERENCES staff (id));
INSERT INTO staff VALUES
  (1, 'Leela', NULL), (2, 'Arjun', 1), (3, 'Divya', 1),
  (4, 'Farhan', 2), (5, 'Gita', 2), (6, 'Harish', 3), (7, 'Isha', 5);

-- SQLite only: ORDER BY inside the recursive part chooses which queued row is
-- expanded next. Deepest first walks each branch to its end before the next.
WITH RECURSIVE tree(id, name, level, chain) AS (
  SELECT id, name, 0, name FROM staff WHERE manager IS NULL
  UNION ALL
  SELECT s.id, s.name, tree.level + 1, tree.chain || ' > ' || s.name
  FROM staff AS s JOIN tree ON s.manager = tree.id
  ORDER BY 3 DESC
)
SELECT name, level, chain FROM tree;

┌────────┬───────┬─────────────────────────────┐
│  name  │ level │            chain            │
├────────┼───────┼─────────────────────────────┤
│ Leela  │ 0     │ Leela                       │
│ Arjun  │ 1     │ Leela > Arjun               │
│ Farhan │ 2     │ Leela > Arjun > Farhan      │
│ Gita   │ 2     │ Leela > Arjun > Gita        │
│ Isha   │ 3     │ Leela > Arjun > Gita > Isha │
│ Divya  │ 1     │ Leela > Divya               │
│ Harish │ 2     │ Leela > Divya > Harish      │
└────────┴───────┴─────────────────────────────┘

Arjun’s whole team, down to Isha, comes before Divya. In PostgreSQL, where the evaluation order is not yours to choose, the same listing comes from SEARCH DEPTH FIRST BY id SET walk and ORDER BY walk in the outer query.

A bill of materials adds arithmetic along the way. One bicycle needs 2 wheels, each wheel needs 36 spokes, so the recursion multiplies the quantities down every path and the outer query adds up the paths per part:

-- A bill of materials: one row per "this assembly needs qty of that part".
CREATE TABLE parts_of (assembly TEXT, part TEXT, qty INTEGER, PRIMARY KEY (assembly, part));
INSERT INTO parts_of VALUES
  ('bicycle', 'frame', 1), ('bicycle', 'wheel', 2), ('bicycle', 'pedal', 2),
  ('wheel', 'rim', 1), ('wheel', 'spoke', 36), ('wheel', 'hub', 1),
  ('hub', 'bearing', 2), ('pedal', 'bearing', 2);

-- Multiply the quantities along each path down the tree, then add up per part.
WITH RECURSIVE needs(part, qty) AS (
  SELECT part, qty FROM parts_of WHERE assembly = 'bicycle'
  UNION ALL
  SELECT p.part, needs.qty * p.qty
  FROM parts_of AS p JOIN needs ON p.assembly = needs.part
)
SELECT part, sum(qty) AS total FROM needs GROUP BY part ORDER BY part;

-- The same query with UNION: two different paths each give ('bearing', 4),
-- and UNION keeps only one of the two equal rows.
WITH RECURSIVE needs(part, qty) AS (
  SELECT part, qty FROM parts_of WHERE assembly = 'bicycle'
  UNION
  SELECT p.part, needs.qty * p.qty
  FROM parts_of AS p JOIN needs ON p.assembly = needs.part
)
SELECT part, sum(qty) AS total FROM needs WHERE part = 'bearing' GROUP BY part;

┌─────────┬───────┐
│  part   │ total │
├─────────┼───────┤
│ bearing │ 8     │
│ frame   │ 1     │
│ hub     │ 2     │
│ pedal   │ 2     │
│ rim     │ 2     │
│ spoke   │ 72    │
│ wheel   │ 2     │
└─────────┴───────┘
┌─────────┬───────┐
│  part   │ total │
├─────────┼───────┤
│ bearing │ 4     │
└─────────┴───────┘

Bearings come from two places: 2 wheels with one hub each and 2 bearings per hub, and 2 pedals with 2 bearings each. Both paths produce the row ('bearing', 4). UNION ALL keeps both and the total is 8; UNION treats the second as a repeat, drops it, and silently reports 4. UNION is not a free cycle check: it also merges rows that are equal for a good reason. Here the data is a tree, so UNION ALL is safe and correct.

Datalog: recursion as rules

Datalog writes a database as facts and a query as rules. A fact such as route("Chennai", "Bengaluru") is a row. A rule says that its head holds whenever every part of its body does, with shared variables meaning a join. Reachability is two rules:

• reach(X, Y) :- route(X, Y). A direct train is a trip.
• reach(X, Y) :- reach(X, Z), route(Z, Y). A trip followed by one more train is a trip.

The second rule mentions reach on both sides: that is recursion. Its meaning is the smallest set of facts that satisfies both rules, reached by applying the rules until nothing new appears. Naive evaluation joins every fact known so far in every round. Semi-naive evaluation joins only the facts that were new in the round before, because joining two old facts again can only rederive a fact already known. This program runs both on the lesson’s routes and counts how often the second rule fires:

"""The Datalog program of the lesson, evaluated twice: naively and semi-naively.

    reach(X, Y) :- route(X, Y).
    reach(X, Y) :- reach(X, Z), route(Z, Y).
    unreachable(Y) :- city(Y), not reach("Chennai", Y).

A naive round joins every reach fact known so far with route; a semi-naive round joins only the
facts that were new in the round before. Both stop when a round adds nothing new.
"""

ROUTES = {
    ("Chennai", "Bengaluru"), ("Bengaluru", "Mysuru"), ("Mysuru", "Chennai"),
    ("Bengaluru", "Hubballi"), ("Hubballi", "Pune"), ("Pune", "Mumbai"),
    ("Mumbai", "Pune"), ("Kolkata", "Bhubaneswar"),
}
CITIES = {c for pair in ROUTES for c in pair}


def evaluate(semi_naive):
    reach = set(ROUTES)              # first rule: every route is a reach fact
    delta = set(ROUTES)              # the facts that are new since the last round
    rounds, joined = 0, 0
    while delta:
        rounds += 1
        source = delta if semi_naive else reach
        derived = set()
        for x, z in source:
            for z2, y in ROUTES:
                if z == z2:
                    joined += 1      # one firing of the second rule
                    derived.add((x, y))
        delta = derived - reach
        reach |= delta
        print(f"  round {rounds}: {len(derived):2} derived, {len(delta):2} new, {len(reach)} facts")
    return reach, rounds, joined


for name, semi in (("naive", False), ("semi-naive", True)):
    print(f"{name}:")
    reach, rounds, joined = evaluate(semi)
    print(f"  {rounds} rounds, the second rule fired {joined} times\n")

from_chennai = sorted(y for x, y in reach if x == "Chennai")
print("reach(Chennai, Y):", ", ".join(from_chennai))
# Negation is applied only once reach is complete: it sits in a higher stratum.
unreachable = sorted(CITIES - set(from_chennai))
print("unreachable(Y):  ", ", ".join(unreachable))

naive:
  round 1:  8 derived,  8 new, 16 facts
  round 2: 17 derived,  6 new, 22 facts
  round 3: 23 derived,  2 new, 24 facts
  round 4: 24 derived,  1 new, 25 facts
  round 5: 24 derived,  0 new, 25 facts
  5 rounds, the second rule fired 102 times

semi-naive:
  round 1:  8 derived,  8 new, 16 facts
  round 2:  9 derived,  6 new, 22 facts
  round 3:  7 derived,  2 new, 24 facts
  round 4:  2 derived,  1 new, 25 facts
  round 5:  1 derived,  0 new, 25 facts
  5 rounds, the second rule fired 27 times

reach(Chennai, Y): Bengaluru, Chennai, Hubballi, Mumbai, Mysuru, Pune
unreachable(Y):   Bhubaneswar, Kolkata

Both find the same 25 facts in 5 rounds, but the naive version fired the rule 102 times and the semi-naive one 27 times, because naive rounds 2 to 5 rederived everything found earlier. The working table of WITH RECURSIVE is the semi-naive idea: each step joins only the rows of the step before.

The last line of the output uses negation: unreachable(Y) :- city(Y), not reach("Chennai", Y). It is safe only once reach is complete, because a city that looks unreachable in round 2 may be reached in round 4. Datalog therefore splits a program into strata: a predicate that is negated must be computed fully, in a lower stratum, before any rule that negates it runs. A program whose negation runs through its own recursion, such as “a city is far if it is not reached yet”, cannot be stratified, and it has no single sensible answer. The PostgreSQL error about NOT EXISTS (… FROM far …) above enforces exactly this, and the ban on aggregates in the recursive member follows the same reasoning. Ceri, Gottlob and Tanca’s survey sets out the evaluation methods and stratification in detail.

Exercise: the fewest trains from Delhi

-- Every city reachable from Delhi, with the fewest trains needed.
-- This version finds only the direct trains: make it follow changes too.
SELECT dst AS city, 1 AS trains
FROM routes
WHERE src = 'Delhi'
ORDER BY trains, city;

# Sample tests: each one builds a small routes table, runs your query and compares the rows it returns, in order.
tests:
  - name: a tree of routes, two and three trains deep
    ordered: true
    setup: |
      CREATE TABLE routes (src TEXT NOT NULL, dst TEXT NOT NULL, PRIMARY KEY (src, dst));
      INSERT INTO routes VALUES
        ('Delhi', 'Agra'), ('Agra', 'Jhansi'), ('Delhi', 'Jaipur'),
        ('Jaipur', 'Ajmer'), ('Jhansi', 'Bhopal');
    expected:
      columns: [city, trains]
      rows:
        - ['Agra', 1]
        - ['Jaipur', 1]
        - ['Ajmer', 2]
        - ['Jhansi', 2]
        - ['Bhopal', 3]
  - name: cycles back to Delhi and a direct train that beats a longer trip
    ordered: true
    setup: |
      CREATE TABLE routes (src TEXT NOT NULL, dst TEXT NOT NULL, PRIMARY KEY (src, dst));
      INSERT INTO routes VALUES
        ('Delhi', 'Agra'), ('Agra', 'Delhi'), ('Agra', 'Gwalior'),
        ('Gwalior', 'Jhansi'), ('Delhi', 'Jhansi'), ('Jhansi', 'Agra');
    expected:
      columns: [city, trains]
      rows:
        - ['Agra', 1]
        - ['Jhansi', 1]
        - ['Gwalior', 2]
  - name: cities that Delhi cannot reach stay out
    ordered: true
    setup: |
      CREATE TABLE routes (src TEXT NOT NULL, dst TEXT NOT NULL, PRIMARY KEY (src, dst));
      INSERT INTO routes VALUES
        ('Delhi', 'Chandigarh'), ('Kochi', 'Kollam'), ('Kollam', 'Delhi');
    expected:
      columns: [city, trains]
      rows:
        - ['Chandigarh', 1]

Check yourself

Interview questions

What is a recursive CTE, and what makes it stop? (warm-up)

A recursive common table expression, written WITH RECURSIVE, has an anchor query that produces the starting rows and a recursive query, joined to it by UNION or UNION ALL, that refers to the expression itself and produces the next rows from the rows of the previous step. The database runs the anchor once, then runs the recursive part again on each step’s new rows, and stops when a step adds nothing. It stops on its own only if the rows eventually stop being new: with UNION, repeated rows are dropped, so plain reachability over a cycle ends, but a counter or a path column makes every row new. Then you need a guard such as depth < 10, a path check, or PostgreSQL’s CYCLE clause. Use UNION ALL when equal rows from different paths must all count, as in a bill of materials.

Key takeaways

• WITH RECURSIVE is an anchor plus a recursive member; it repeats the member on the previous step’s rows until a step adds nothing. Relational algebra cannot do this, because every expression joins a fixed number of times.
• UNION stops cycles only while rows can repeat exactly; a counter or path column defeats it. Guards stop runaway queries but cost rows in proportion to the limit; path checks and PostgreSQL’s CYCLE clause detect the repeat.
• UNION also merges rows that are equal for a good reason, so totals that add up paths, as in a bill of materials, need UNION ALL on data without cycles.
• PostgreSQL forbids aggregates and self-referencing subqueries in the recursive member, has SEARCH and CYCLE, and evaluates only as many rows as the outer query reads. SQLite has neither clause but lets ORDER BY steer its queue.
• In Datalog, recursion is a rule that mentions its own head. Semi-naive evaluation, joining only new facts, is what the working table does, and negation must wait for the stratum below it to finish.