Recursive CTEs

Dependency Paths

Carry a Route

Recursive CTE rows can carry derived text such as the path taken through a dependency graph.

Program

Play the script to choose a starting node and see the routes reachable from it.

start_node
dependency_paths.sql
Replay: real traced execution (multi-file project)
CREATE TABLE edges (parent TEXT, child TEXT);
INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');
WITH RECURSIVE params(start_node) AS (VALUES ('app')), walk(node, route, depth) AS (SELECT (SELECT start_node FROM params), (SELECT start_node FROM params), 0 UNION ALL SELECT edges.child, walk.route || ' > ' || edges.child, walk.depth + 1 FROM edges JOIN walk ON edges.parent = walk.node) SELECT node, route, depth FROM walk ORDER BY depth, node;

CREATE TABLE edges (parent TEXT, child TEXT);
INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');
WITH RECURSIVE params(start_node) AS (VALUES ('api')), walk(node, route, depth) AS (SELECT (SELECT start_node FROM params), (SELECT start_node FROM params), 0 UNION ALL SELECT edges.child, walk.route || ' > ' || edges.child, walk.depth + 1 FROM edges JOIN walk ON edges.parent = walk.node) SELECT node, route, depth FROM walk ORDER BY depth, node;

CREATE TABLE edges (parent TEXT, child TEXT);
INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');
WITH RECURSIVE params(start_node) AS (VALUES ('worker')), walk(node, route, depth) AS (SELECT (SELECT start_node FROM params), (SELECT start_node FROM params), 0 UNION ALL SELECT edges.child, walk.route || ' > ' || edges.child, walk.depth + 1 FROM edges JOIN walk ON edges.parent = walk.node) SELECT node, route, depth FROM walk ORDER BY depth, node;

  1. tables ← 1 row

    1CREATE TABLE edges (parent TEXT, child TEXT);2INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');
    values this step1 rowtables

  2. edges ← 6 rows

    1CREATE TABLE edges (parent TEXT, child TEXT);2INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');3WITH RECURSIVE params(start_node) AS (VALUES ('app')), walk(node, route, depth) AS (SELECT (SELECT start_node FROM params), (SELECT start_node FROM params), 0 UNION ALL SELECT edges.child, walk.route || ' > ' || edges.child, walk.depth + 1 FROM edges JOIN walk ON edges.parent = walk.node) SELECT node, route, depth FROM walk ORDER BY depth, node;
    values this step6 rowsedges

  3. result ← 7 rows

    2INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');3WITH RECURSIVE params(start_node) AS (VALUES ('app')), walk(node, route, depth) AS (SELECT (SELECT start_node FROM params), (SELECT start_node FROM params), 0 UNION ALL SELECT edges.child, walk.route || ' > ' || edges.child, walk.depth + 1 FROM edges JOIN walk ON edges.parent = walk.node) SELECT node, route, depth FROM walk ORDER BY depth, node;
    values this step7 rowsresult

  1. tables ← 1 row

    1CREATE TABLE edges (parent TEXT, child TEXT);2INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');
    values this step1 rowtables

  2. edges ← 6 rows

    1CREATE TABLE edges (parent TEXT, child TEXT);2INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');3WITH RECURSIVE params(start_node) AS (VALUES ('api')), walk(node, route, depth) AS (SELECT (SELECT start_node FROM params), (SELECT start_node FROM params), 0 UNION ALL SELECT edges.child, walk.route || ' > ' || edges.child, walk.depth + 1 FROM edges JOIN walk ON edges.parent = walk.node) SELECT node, route, depth FROM walk ORDER BY depth, node;
    values this step6 rowsedges

  3. result ← 3 rows

    2INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');3WITH RECURSIVE params(start_node) AS (VALUES ('api')), walk(node, route, depth) AS (SELECT (SELECT start_node FROM params), (SELECT start_node FROM params), 0 UNION ALL SELECT edges.child, walk.route || ' > ' || edges.child, walk.depth + 1 FROM edges JOIN walk ON edges.parent = walk.node) SELECT node, route, depth FROM walk ORDER BY depth, node;
    values this step3 rowsresult

  1. tables ← 1 row

    1CREATE TABLE edges (parent TEXT, child TEXT);2INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');
    values this step1 rowtables

  2. edges ← 6 rows

    1CREATE TABLE edges (parent TEXT, child TEXT);2INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');3WITH RECURSIVE params(start_node) AS (VALUES ('worker')), walk(node, route, depth) AS (SELECT (SELECT start_node FROM params), (SELECT start_node FROM params), 0 UNION ALL SELECT edges.child, walk.route || ' > ' || edges.child, walk.depth + 1 FROM edges JOIN walk ON edges.parent = walk.node) SELECT node, route, depth FROM walk ORDER BY depth, node;
    values this step6 rowsedges

  3. result ← 3 rows

    2INSERT INTO edges VALUES ('app', 'api'), ('app', 'worker'), ('api', 'db'), ('api', 'cache'), ('worker', 'queue'), ('queue', 'db');3WITH RECURSIVE params(start_node) AS (VALUES ('worker')), walk(node, route, depth) AS (SELECT (SELECT start_node FROM params), (SELECT start_node FROM params), 0 UNION ALL SELECT edges.child, walk.route || ' > ' || edges.child, walk.depth + 1 FROM edges JOIN walk ON edges.parent = walk.node) SELECT node, route, depth FROM walk ORDER BY depth, node;
    values this step3 rowsresult
graph edges Each `edges` row points from one node to a dependent node.
carried route `walk.route || ' > ' || edges.child` records the path as recursion advances.
bounded data The fixed acyclic data keeps the replay deterministic and finite.