Exercises — CTEs (WITH clause) — recursive CTEs

• Anchor: SELECT 10 AS x — runs once, seeds $W_0=\{10\}$.
• Recursive member: SELECT x - 2 FROM t WHERE x > 2 — it references t, so yes it loops.
• It does terminate because each round subtracts 2 and the guard x > 2 eventually fails.

Round trace — remember the recursive member only sees last round's rows:

Result: 10, 8, 6, 4, 2.

False. Both are legal. UNION de-duplicates each round (set semantics) — sometimes used as a free cycle guard. UNION ALL keeps everything and is faster. See UNION vs UNION ALL.

WITH RECURSIVE evens AS (
    SELECT 2 AS n
    UNION ALL
    SELECT n + 2 FROM evens WHERE n < 12
)
SELECT n FROM evens;

Result: 2, 4, 6, 8, 10, 12 — six rows summing to 42.

WITH RECURSIVE chain AS (
    SELECT id, name, manager_id, 1 AS lvl
    FROM emp WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, c.lvl + 1
    FROM emp e JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, lvl FROM chain ORDER BY lvl, id;

Each round adds people whose manager was found last round (see SQL Joins for the join mechanics):

Result:

Deepest level = 4. Total employees returned = 5.

Diagnosis: the recursive member has no stop guard, so $W_i$ never empties: $W_0=\{1\},W_1=\{2\},W_2=\{3\},W_3=\{4\},\dots$ — infinitely. The outer LIMIT 3 cannot save you: the CTE must finish building before the outer SELECT runs (in standard engines), so it hangs during construction.

Fix — put the bound inside the recursive member so a round eventually yields zero rows:

WITH RECURSIVE nums AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM nums WHERE n < 3
)
SELECT n FROM nums;   -- 1, 2, 3

Now $W_3=\{\}$ because 3 < 3 is false → termination. Result rows: 1, 2, 3 (three rows, sum 6).

Why it loops: with UNION ALL and a 3-cycle A→B→C→A, the working table keeps regenerating nodes: $W_0=\{A\},W_1=\{B\},W_2=\{C,D\},W_3=\{A\}$ (from $C\to A$), $W_4=\{B\},\dots$ — never empty (see Tree and Graph Data Structures).

Fix 1 — UNION (set semantics): de-duplicates each round. Once $\{A,B,C,D\}$ have all appeared, a new round adds nothing new → $W_{n+1}=\varnothing$.

WITH RECURSIVE reach AS (
    SELECT 'A' AS node
    UNION                          -- dedupe = free cycle guard
    SELECT e.dst FROM edges e JOIN reach r ON e.src = r.node
)
SELECT node FROM reach;

Fix 2 — carry a visited path and refuse revisits:

WITH RECURSIVE reach AS (
    SELECT 'A' AS node, ARRAY['A'] AS path
    UNION ALL
    SELECT e.dst, r.path || e.dst
    FROM edges e JOIN reach r ON e.src = r.node
    WHERE e.dst <> ALL(r.path)
)
SELECT DISTINCT node FROM reach;

Both return the reachable set {A, B, C, D} — 4 distinct nodes.

Carry depth, start at 0 for A, add 1 each hop; then take the minimum depth where node = 'E'.

WITH RECURSIVE walk AS (
    SELECT 'A' AS node, 0 AS depth, ARRAY['A'] AS path
    UNION ALL
    SELECT e.dst, w.depth + 1, w.path || e.dst
    FROM edges e JOIN walk w ON e.src = w.node
    WHERE e.dst <> ALL(w.path)          -- cycle guard (safe even if none here)
)
SELECT MIN(depth) AS shortest FROM walk WHERE node = 'E';

Trace of depths reaching each node:

E first appears at depth 3, and there is no shorter route → shortest = 3 hops (A→B→D→E or A→C→D→E).

Keep two carried values: the current n and the accumulated product f. Multiply as you climb.

WITH RECURSIVE fact AS (
    SELECT 1 AS n, 1 AS f            -- 1! = 1
    UNION ALL
    SELECT n + 1, f * (n + 1)
    FROM fact
    WHERE n < 5
)
SELECT n, f FROM fact ORDER BY n;

Result: (1,1) (2,2) (3,6) (4,24) (5,120). The last factorial 5! = 120.

Carry a growing string. Anchor = CEO with just their name; recursive member appends ' > ' || name.

WITH RECURSIVE chain AS (
    SELECT id, name, name::text AS path_str, 1 AS lvl
    FROM emp WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, c.path_str || ' > ' || e.name, c.lvl + 1
    FROM emp e JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, path_str, lvl FROM chain ORDER BY lvl, id;

Ez's path has 4 names; the longest chain length is 4.

A simple path never revisits a node — so we carry the path array and forbid revisits with <> ALL. Every row of the CTE is one distinct simple path.

WITH RECURSIVE paths AS (
    SELECT 'A' AS node, ARRAY['A'] AS path
    UNION ALL
    SELECT e.dst, p.path || e.dst
    FROM edges e JOIN paths p ON e.src = p.node
    WHERE e.dst <> ALL(p.path)          -- keep it simple (no revisits)
)
SELECT COUNT(*) AS num_paths FROM paths;

Enumerate the simple paths from A:

• A
• A→B
• A→B→C (from C, only edge is C→A, but A is already in the path → blocked)
• A→D
• A→D→E

The cycle A→B→C→A is cut exactly when C→A would revisit A. Distinct simple paths = 5.

$W_i$ trace (each entry is a path array):

Total rows = $1+2+2=5$.

L1 recognise parts ::: anchor vs recursive member; both UNION/UNION ALL legal L2 apply patterns ::: even sequence; org-chart levels (join e.manager_id = c.id) L3 diagnose failures ::: missing guard hangs; cycles need UNION or visited-set; outer LIMIT can't save it L4 synthesise carriers ::: depth counter for shortest hops; accumulator for factorial L5 invent under constraints ::: text path string; count simple paths with <> ALL