SQL Recursive CTE — Applied Graph Traversal, RBAC, BOM

WITH RECURSIVE paths AS (

  -- ① Anchor member: register TYO as the origin and initialize the visited array
  SELECT
    'TYO'         AS current_city,
    0             AS total_cost,
    ARRAY['TYO'] AS visited,        -- array of visited city codes
    'TYO'         AS route_str

  UNION ALL

  -- ② Recursive member: move to an unvisited next city within the hop limit
  SELECT
    r.to_code,
    p.total_cost + r.cost,
    p.visited || r.to_code,             -- append the next city to the array (|| is PostgreSQL array concatenation)
    p.route_str || '→' || r.to_code
  FROM  paths p
  JOIN  routes r ON r.from_code = p.current_city
  WHERE r.to_code != ALL(p.visited)     -- cycle prevention: only a city different from every visited element
    AND   array_length(p.visited, 1) < 4 -- maximum 3 flights: array length must be less than 4

)
SELECT
  route_str,
  total_cost
FROM  paths
WHERE current_city = 'FUK'  -- keep only routes that reach the destination FUK
ORDER BY total_cost;

/*
  Execution order (SQL logical evaluation order):
  1. Anchor member
  2. Recursion iteration 1 (from TYO)
  3. Recursion iteration 2 (from OSA, NGO)
  4. Recursion iteration 3 (from HIR, OSA via NGO)
  5. Recursion iteration 4
  6. Outer query
  */

WITH RECURSIVE role_chain AS (

  -- ① Anchor member: register alice (user_id=1)'s direct role (editor)
  SELECT
    r.role_id,
    r.role_name,
    r.parent_role_id,
    0 AS chain_level         -- direct role = chain_level 0
  FROM  users u
  JOIN  roles r ON r.role_id = u.role_id
  WHERE u.user_id = 1          -- target user

  UNION ALL

  -- ② Recursive member: follow the current role's parent_role_id upward
  SELECT
    r.role_id,
    r.role_name,
    r.parent_role_id,
    rc.chain_level + 1        -- chain_level increases for each higher role
  FROM  roles r
  JOIN  role_chain rc ON r.role_id = rc.parent_role_id  -- JOIN in the bottom-up direction

)
SELECT
  p.permission_name,
  rc.role_name  AS granted_by_role,  -- role that granted it (useful for audit logs)
  rc.chain_level
FROM  role_chain rc
JOIN  permissions p ON p.role_id = rc.role_id
ORDER BY rc.chain_level, p.permission_name;

/*
  Execution order (SQL logical evaluation order):
  1. Anchor member
  2. Recursion iteration 1
  3. Recursion iteration 2
  4. Recursion iteration 3
  5. Outer query
  */

WITH RECURSIVE bom_expand AS (
  -- Anchor: initialize every part as a direct starting point for itself
  SELECT
    p.part_id    AS root_id,        -- part that provides the cost-aggregation root
    p.part_id    AS current_id,     -- part currently being expanded (the frontier)
    1            AS accumulated_qty, -- cumulative quantity (starts at 1)
    p.unit_cost                       -- unit cost of a leaf component (NULL for assemblies)
  FROM parts p

  UNION ALL

  -- Recursive member: expand to child parts through the BOM and carry multiplied quantity
  SELECT
    be.root_id,                                                   -- keep the root unchanged
    b.child_part_id    AS current_id,                             -- the expansion target becomes the new frontier
    be.accumulated_qty * b.quantity                               -- ★ multiply quantities cumulatively
      AS accumulated_qty,
    p.unit_cost
  FROM bom_expand be
  JOIN bom b        ON b.parent_part_id = be.current_id           -- join child parts
  JOIN parts p      ON p.part_id = b.child_part_id                -- retrieve child-part information
)
SELECT
  p.part_id,
  p.part_name,
  SUM(be.accumulated_qty * be.unit_cost) AS total_component_cost  -- aggregate leaf cost (cumulative quantity × unit cost)
FROM bom_expand be
JOIN parts p          ON p.part_id = be.root_id
WHERE be.unit_cost IS NOT NULL                                    -- only leaf rows contribute; exclude assembly rows
GROUP BY p.part_id, p.part_name
ORDER BY p.part_id;

/*
  Execution order:
  1. WITH RECURSIVE bom_expand  → initialize every part as its own anchor
  2. UNION ALL recursive member (iter1) → expand direct children
  3. UNION ALL recursive member (iter2) → expand grandchildren, then stop
  4. Outer WHERE unit_cost IS NOT NULL → exclude intermediate assemblies
  5. GROUP BY + SUM → total cost by root_id
  6. JOIN parts + ORDER BY part_id → add names and output in ascending order
  */

WITH RECURSIVE
dept_tree AS (                                  -- ① Department tree: expand top-down while assigning depth and path
  SELECT
    dept_id, dept_name, parent_id, own_budget,
    0              AS depth,
    dept_name      AS path                      -- the root department name starts the path
  FROM departments
  WHERE parent_id IS NULL                       -- HQ is the root anchor

  UNION ALL

  SELECT
    d.dept_id, d.dept_name, d.parent_id, d.own_budget,
    dt.depth + 1                         AS depth,
    dt.path || ' > ' || d.dept_name    AS path          -- ★ concatenate the path
  FROM departments d
  JOIN dept_tree dt ON d.parent_id = dt.dept_id
),
closure AS (                                            -- ② Closure Table: generate every (ancestor, descendant) pair
  SELECT
    dept_id AS ancestor_id,
    dept_id AS descendant_id                            -- self-pair (distance=0)
  FROM departments

  UNION ALL

  SELECT
    c.ancestor_id,
    d.dept_id AS descendant_id         -- ★ expand pairs from each ancestor to all descendants
  FROM closure c
  JOIN departments d ON d.parent_id = c.descendant_id
)

SELECT
  dt.dept_id,
  dt.dept_name,
  dt.depth,
  dt.path,
  dt.own_budget,
  SUM(d2.own_budget) AS total_budget  -- sum own_budget for every descendant department
FROM dept_tree dt
JOIN closure cl    ON cl.ancestor_id = dt.dept_id   -- find rows where the target department is the ancestor
JOIN departments d2 ON d2.dept_id = cl.descendant_id -- retrieve descendant budgets
GROUP BY dt.dept_id, dt.dept_name, dt.depth, dt.path, dt.own_budget
ORDER BY dt.depth, dt.dept_id;

/*
  Execution order:
  1. dept_tree (anchor): retrieve only HQ where parent_id IS NULL (1 row)
  2. dept_tree (recursive iter1): expand Engineering and Sales, append ' > ' to path (+2 rows)
  3. dept_tree (recursive iter2): expand Backend, Frontend, Domestic Sales, and International Sales (+4 rows) → 7 total
  4. closure (anchor): generate 7 self-pairs (ancestor=descendant)
  5. closure (recursive iter1): add pairs to each department's direct children (+6 pairs)
  6. closure (recursive iter2): add HQ→grandchild pairs (Backend, etc.) (+4 pairs) → 17 total
  7. Outer query: dept_tree JOIN closure (ancestor=department) JOIN departments (d2=descendant)
  8. GROUP BY + SUM: total own_budget across all pairs for each ancestor department
  9. ORDER BY depth, dept_id: output by depth and department ID
*/