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.

dependency_paths.sql 
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 ()), 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 ()), 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 ()), 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;
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.