SQL Recursive CTE — Applied RBAC, BOM, Double Recursion

QUESTION 1

Level-Based Salary Ranking — Calculate Within-Depth Ranks with WITH RECURSIVE + RANK()

WITH RECURSIVEWINDOW FUNCTIONOrganization ChartRANK / PARTITION BY

Background ▼

Once a recursive CTE assigns each node a depth, the result can be passed to a window function in the outer query. This lets you complete “ranking within the same hierarchy level” and “aggregation by hierarchy level” in a single query.

WITH RECURSIVE emp_tree AS (
  -- Anchor: root employee (depth=0)
  SELECT emp_id, manager_id, salary, 0 AS depth FROM employees
  WHERE manager_id IS NULL
  UNION ALL
  -- Recursive member: add subordinates at depth+1
  SELECT e.emp_id, e.manager_id, e.salary, et.depth + 1
  FROM employees e JOIN emp_tree et ON e.manager_id = et.emp_id
)
-- Apply the window function in the outer query (not inside the recursive member)
SELECT emp_id, depth, salary,
  RANK() OVER (PARTITION BY depth ORDER BY salary DESC) AS rank_in_level
FROM emp_tree;

Key constraint: window functions cannot be used inside the recursive member. Putting RANK() in the recursive CTE's SELECT list causes a syntax error. Always apply it in the outer query. The recursive CTE should focus on “generating the depth column,” leaving the window calculation outside.

Problem ▼

The employees table stores employees, managers, and salaries. Retrieve each employee's organizational depth (depth) and salary ranking within the same depth (rank_in_level). Use RANK() and rank salaries from highest to lowest (DESC) within each depth. Return emp_id, emp_name, depth, salary, rank_in_level, sorted by depth ascending and then rank_in_level ascending.

Tables used

▸ employees

emp_id	emp_name	manager_id	salary
1	Alice (CEO)	NULL	1200000
2	Bob	1	850000
3	Carol	1	950000
4	Dave	2	520000
5	Eve	2	680000
6	Frank	3	590000
7	Grace	3	730000

Organization structure: Alice(depth=0) → Bob/Carol(depth=1) → Dave/Eve/Frank/Grace(depth=2)
Within depth=2, Grace(730000) has the highest salary → rank_in_level=1

Expected Output ▼

emp_id	emp_name	depth	salary	rank_in_level
1	Alice (CEO)	0	1200000	1
3	Carol	1	950000	1
2	Bob	1	850000	2
7	Grace	2	730000	1
5	Eve	2	680000	2
6	Frank	2	590000	3
4	Dave	2	520000	4

Model Answer ▼

WITH RECURSIVE emp_tree AS (

  -- ① Anchor member: register the root employee (manager_id IS NULL) with depth=0
  SELECT
    emp_id,
    emp_name,
    manager_id,
    salary,
    0 AS depth
  FROM  employees
  WHERE manager_id IS NULL

  UNION ALL

  -- ② Recursive member: add subordinates at depth+1 (window functions cannot be used here)
  SELECT
    e.emp_id,
    e.emp_name,
    e.manager_id,
    e.salary,
    et.depth + 1         -- add 1 to the parent's depth to track the hierarchy
  FROM  employees e
  JOIN  emp_tree et ON e.manager_id = et.emp_id

)
-- ③ Outer query: apply the window function to the recursive result
SELECT
  emp_id,
  emp_name,
  depth,
  salary,
  RANK() OVER (
    PARTITION BY depth          -- reset the ranking for each depth level
    ORDER BY     salary DESC    -- rank from the highest salary
  ) AS rank_in_level
FROM  emp_tree
ORDER BY depth, rank_in_level;

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

Explanation (table transitions & key points) ▼

WITH RECURSIVE
  emp_tree AS (
  SELECT
    emp_id, emp_name, manager_id, salary,
    0 AS depth
  FROM  employees
  WHERE manager_id IS NULL
  UNION ALL
  SELECT
    e.emp_id, e.emp_name, e.manager_id, e.salary,
    et.depth + 1
  FROM  employees e
  JOIN  emp_tree et ON e.manager_id = et.emp_id
)
SELECT
  emp_id, emp_name, depth, salary,
  RANK() OVER (
    PARTITION BY depth
    ORDER BY     salary DESC
  ) AS rank_in_level
FROM  emp_tree
ORDER BY depth, rank_in_level;

LEGEND ▼

Rows read / loaded

Excluded / hidden data

① Anchor member (depth=0) ▼

WHERE manager_id IS NULL → retrieve Alice onlyRetrieve only the root employee (Alice) where manager_id IS NULL and initialize depth=0. This one row becomes the first Working Table (the current target row) and the starting point for the next recursive expansion.

1 / 6

emp_id	emp_name	manager_id	salary	depth
1	Alice（CEO）	NULL	1200000	0

Anchor: 1 row

 Two-stage flow: recursive CTE → window function

PHASE 1 Assign depth to every employee with WITH RECURSIVE

emp_tree after recursion (7 rows)

emp_id	depth	salary
Alice(1)	0	1,200,000
Bob(2)	1	850,000
Carol(3)	1	950,000
Dave(4)	2	520,000
Eve(5)	2	680,000
Frank(6)	2	590,000
Grace(7)	2	730,000

→

PHASE 2: Apply RANK()

PARTITION BY depth	RANK(salary DESC)
depth=0 (Alice only)	→ rank=1
depth=1 (Carol, Bob)	→ rank=1, 2
depth=2 (Grace, Eve, Frank, Dave)	→ rank=1, 2, 3, 4

LEARNING POINTS

Window functions cannot be used inside the recursive member: This is a SQL-standard restriction. Putting RANK(), ROW_NUMBER(), and similar functions in the recursive CTE's SELECT list causes an error. The recursive CTE should focus on “generating rows,” while the outer query performs the window calculation.

RANK vs DENSE_RANK: RANK() skips the next rank after a tie (1,1,3…). DENSE_RANK() does not skip (1,1,2…). Use DENSE_RANK when “what position among the people” matters, and RANK when “how many people are ahead of me” matters. DENSE_RANK is generally preferred for salary reports.

PARTITION BY controls where ranking resets: With PARTITION BY depth, depth=0, 1, and 2 become independent windows. Without PARTITION BY, all 7 rows form one window and produce a global ranking from 1 to 7.

ANTI-PATTERNS

Putting a window function in the recursive member: Writing RANK() OVER (...) inside the recursive SELECT causes an error: “Window functions are not allowed in a recursive CTE.” Think in two stages: build the structure (depth) recursively, then apply the window function outside.

Forgetting PARTITION BY and creating a global ranking: Omitting PARTITION BY depth produces a global ranking of all employees: Alice(rank=1), Carol(rank=2), and so on. The rule is to always state the unit at which ranking should reset with PARTITION BY.

Practical column: HR dashboard use case

The pattern in this question—build the structure with a recursive CTE, then analyze it with window functions—is common in HR analytics. In practice, it can measure the average salary gap by depth (promotion incentives) and salary-distribution skew within the same depth (pay-equity checks). Combined with NTILE(4) OVER (PARTITION BY depth ORDER BY salary), it calculates salary quartiles (Q1–Q4) by hierarchy level and provides a basis for identifying high performers. Combining recursive CTEs to obtain “tree-structure attributes” with window functions for “statistical analysis” is an essential BI and analytics-engineering technique.

QUESTION 2

Graph Path Exploration (Cycle Prevention with an Array) — Safely Enumerate All Routes with a Visited Array

WITH RECURSIVEGraph ExplorationArrays / ARRAYCycle Prevention

Background ▼

Recursive CTEs apply not only to trees but also to graphs (directed graphs) that contain cycles. A cycle can cause an infinite loop, so record visited nodes in an array and prevent the recursion from visiting the same node again.

WITH RECURSIVE paths AS (
  -- Anchor: starting point and initialization of the visited array
  SELECT 'A' AS cur, 0 AS cost,
    ARRAY['A'] AS visited, 'A' AS route
  UNION ALL
  -- Recursive member: move to an unvisited node
  SELECT r.to_code, p.cost + r.cost,
    p.visited || r.to_code,            -- append to the array with ||
    p.route || '→' || r.to_code
  FROM paths p JOIN routes r ON r.from_code = p.cur
  WHERE r.to_code != ALL(p.visited)   -- prevent cycles
    AND array_length(p.visited, 1) < 4 -- maximum 3 flights
)

How the array prevents cycles: Accumulate traversed city codes in the visited column. Proceed only after confirming that the next candidate city is different from every array element with != ALL(visited). In PostgreSQL, ARRAY['TYO'] || 'OSA' appends an element to an array. MySQL 8 has no array type, so use the string 'TYO,OSA,' with FIND_IN_SET instead.

Problem ▼

Consider a directed airline-route network. Enumerate all routes from TYO to FUK using at most 3 flights, ordered by increasing cost. Use the visited array to prevent revisiting the same city (cycles). Return route_str, total_cost.

Tables used

▸ routes (directed graph; some routes are reciprocal)

from_code	to_code	cost
TYO	OSA	13000
TYO	NGO	8000
NGO	OSA	6000
NGO	FUK	18000
OSA	FUK	15000
OSA	HIR	7000
HIR	FUK	8000
OSA	TYO	13000

Because the reverse route OSA→TYO exists, TYO→OSA→TYO→… could loop forever. Cycle prevention with the visited array is required.

Expected Output ▼

route_str	total_cost
TYO→NGO→FUK	26000
TYO→OSA→FUK	28000
TYO→OSA→HIR→FUK	28000
TYO→NGO→OSA→FUK	29000

Model Answer ▼

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
  */

Explanation (table transitions & key points) ▼

WITH RECURSIVE
  paths AS (
  SELECT
    'TYO' AS current_city, 0 AS total_cost,
    ARRAY['TYO'] AS visited,
    'TYO' AS route_str
  UNION ALL
  SELECT
    r.to_code, p.total_cost + r.cost,
    p.visited || r.to_code,
    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)
    AND   array_length(p.visited, 1) < 4
)
SELECT
  route_str, total_cost
FROM  paths
WHERE current_city = 'FUK'
ORDER BY total_cost;

LEGEND ▼

Rows read / loaded

① Anchor member (initialize the starting point) ▼

Register TYO as the starting point with visited=['TYO']Register origin TYO. Initializing visited to ['TYO'] lets later recursion detect a return to TYO. Set cost=0 and route_str='TYO'; this becomes the first Working Table.

1 / 7

current_city	total_cost	visited	route_str
TYO	0	['TYO']	TYO

Anchor: 1 row

 How the array prevents cycles

KEY MECHANISM != ALL(visited) is the core cycle check

Preventing TYO→OSA→TYO (a cycle)

Step	visited	Next candidate	Evaluation
Start	['TYO']	OSA	✓ Unvisited
TYO→OSA	['TYO','OSA']	TYO (reverse)	✗ TYO ∈ visited → Exclude
TYO→OSA	['TYO','OSA']	FUK, HIR	✓ Unvisited → Continue

→

Depth limit from array length

visited length	array_length<4	Recursion
1 ('TYO')	TRUE	Continue
2 ('TYO','OSA')	TRUE	Continue
3 ('TYO','OSA','HIR')	TRUE	Continue
4 ('TYO','OSA','HIR','FUK')	FALSE	Stop

LEARNING POINTS

The key difference between trees and graphs: A tree has only one route to each node, so it cannot cycle. A graph can have multiple routes and return paths, so a recursive CTE may loop forever. Graph traversal must include a visited-node check, a hop limit, or both.

PostgreSQL 14+ CYCLE clause: PostgreSQL 14 and later support CYCLE node_col SET is_cycle USING path to detect cycles automatically. It is more concise than managing an array manually. The CYCLE clause only detects a cycle and stops; a depth limit is still required when enumerating all routes.

Alternative for MySQL 8: MySQL has no array type, so manage visited as a CSV string such as 'TYO,OSA,' and check unvisited nodes with FIND_IN_SET(r.to_code, p.visited) = 0. Performance is lower, but the logic is the same.

ANTI-PATTERNS

Expanding a graph without an array check: Omitting the visited check on a graph with cycles makes recursion loop forever and can cause memory or timeout errors in the database. Never assume “this is a tree”; unless the data is guaranteed acyclic, always add a guard.

Using a CTE when you need only the minimum-cost route: A recursive CTE is appropriate here because the goal is to enumerate all routes. But if you need only the shortest or least-cost route, an application-side algorithm such as Dijkstra's or the pgRouting extension is more efficient. Expanding every route with a recursive CTE and then taking MIN() becomes exponentially slow.

Practical column: Graph traversal in practice

Recursive-CTE graph traversal appears in many real-world scenarios: friend-of-friend exploration in social networks, transfer-point analysis in supply chains, and impact-range tracing for network failures. A hop limit such as array_length < N controls how many degrees of connection to follow; friend recommendations on social networks are usually limited to two or three degrees. For very large graphs with millions of nodes, graph databases such as Apache Spark GraphX or Neo4j are more practical than recursive CTEs.

QUESTION 3

Permission Aggregation through Role Inheritance — Implement an RBAC Permission Chain with Bottom-Up Recursion

WITH RECURSIVEBottom-UpRBACPermission Management

Background ▼

In role-based access control (RBAC), roles can form a hierarchy in which a role inherits permissions from its parent, for example viewer → editor → admin → super_admin. Tracing every ancestor role bottom-up from a user's role and aggregating the permissions assigned to each role is a common pattern in authentication and authorization systems.

WITH RECURSIVE role_chain AS (
  -- Anchor: the target user's direct role (bottom-up starting point)
  SELECT r.role_id, r.role_name, r.parent_role_id, 0 AS chain_level
  FROM users u JOIN roles r ON r.role_id = u.role_id
  WHERE u.user_id = :uid
  UNION ALL
  -- Recursive member: follow parent_role_id upward (bottom-up)
  SELECT r.role_id, r.role_name, r.parent_role_id, rc.chain_level + 1
  FROM roles r
  JOIN role_chain rc ON r.role_id = rc.parent_role_id  -- reverse join to the parent role
)

How this differs from bottom-up basics: The direction of ancestor traversal is the same as the basic set's category breadcrumbs, but this question adds deduplication when multiple roles grant the same permission and recording which role granted it (an audit trail).

Problem ▼

Retrieve all permissions held by user_id=1 (alice) by following the role-inheritance chain. List permissions from both the direct and inherited roles. Return permission_name, granted_by_role, chain_level, sorted by chain_level ascending and then permission_name ascending.

Tables used

▸ roles

role_id	role_name	parent_role_id
1	super_admin	NULL
2	admin	1
3	editor	2
4	viewer	3

▸ permissions

role_id	permission_name
1	system.config
1	user.delete
2	user.create
2	user.edit
3	content.edit
3	content.publish
4	content.read

▸ users

user_id	username	role_id
1	alice	3
2	bob	4
3	carol	2

alice's role chain: editor(3) → admin(2) → super_admin(1)
editor does not inherit viewer(4)'s permissions (inheritance moves upward only)
chain_level=0: alice's direct role (editor); chain_level=1: admin; chain_level=2: super_admin

Expected Output ▼

permission_name	granted_by_role	chain_level
content.edit	editor	0
content.publish	editor	0
user.create	admin	1
user.edit	admin	1
system.config	super_admin	2
user.delete	super_admin	2

Model Answer ▼

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
  */

Explanation (table transitions & key points) ▼

WITH RECURSIVE
  role_chain AS (
  SELECT
    r.role_id, r.role_name, r.parent_role_id,
    0 AS chain_level
  FROM  users u
  JOIN  roles r ON r.role_id = u.role_id
  WHERE u.user_id = 1
  UNION ALL
  SELECT
    r.role_id, r.role_name, r.parent_role_id,
    rc.chain_level + 1
  FROM  roles r
  JOIN  role_chain rc ON r.role_id = rc.parent_role_id
)
SELECT
  p.permission_name,
  rc.role_name AS granted_by_role,
  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;

LEGEND ▼

Columns / keys under evaluation

Excluded / hidden data

① Anchor member (JOIN evaluation) ▼

JOIN users and roles to retrieve the direct roleRetrieve the target user (user_id=1: alice) from users and join roles to identify the starting role (editor).

1 / 7

▸ users (WHERE user_id=1)

user_id	username	role_id
1	alice	3

⋈

▸ roles

role_id	role_name	parent_role_id
1	super_admin	NULL
2	admin	1
3	editor	2
4	viewer	3

Evaluation: users JOIN roles → role_id=3 matches

 Role-inheritance chain expansion flow (alice)

ANCHOR alice's direct role: editor(role_id=3)

Retrieved role chain

chain_level	role_name	parent
0	editor(3)	admin(2)
1	admin(2)	super_admin(1)
2	super_admin(1)	NULL → End

→

JOIN permissions → all permissions held by alice

permission	from
content.edit	editor (direct)
content.publish	editor (direct)
user.create	admin (inherited)
user.edit	admin (inherited)
system.config	super_admin (inherited)
user.delete	super_admin (inherited)

LEARNING POINTS

chain_level provides an audit trail: chain_level=0 means a direct grant; larger values mean a more distant ancestor role. Recording which role a permission was inherited from helps trace the impact of permission changes and detect suspicious privilege escalation.

Extending to users with multiple roles: This question assumes one role per user, but real RBAC systems often assign multiple roles. Use a many-to-many user_roles table, change the anchor to JOIN user_roles ON user_roles.user_id = u.user_id JOIN roles ON roles.role_id = user_roles.role_id, and deduplicate in the outer query with SELECT DISTINCT permission_name.

Optimizing an effective permission check: Enumerating all permissions is useful for a permission-list screen. If you only need a True/False check for one permission, add WHERE p.permission_name = 'user.create' LIMIT 1 to short-circuit the query.

ANTI-PATTERNS

Leaving role cycles (diamond inheritance) unguarded: If a role-design error creates a cycle such as roleA→roleB→roleA, this query loops forever. Guarantee acyclic role design in the application, or combine it with an accumulated path array to detect cycles.

Forgetting DISTINCT and returning duplicate permissions: If multiple inheritance paths reach the same permission, the same permission_name appears on multiple rows. Use SELECT DISTINCT permission_name, ... in the outer query or retain only the most direct grant with MIN(chain_level).

Practical column: Comparison with AWS IAM / Google Cloud IAM

This role-inheritance pattern is fundamentally the same as inheriting roles and policies in AWS IAM or hierarchical permissions in Google Cloud IAM. When implementing an RDBMS-based authorization system in-house, the WITH RECURSIVE + JOIN permissions pattern is a reliable foundation. In practice, two points matter: (1) when permission checks are frequent, persist the expanded result in a materialized view or dedicated permission_cache table; and (2) add a trigger to invalidate the cache automatically when roles change. When the hierarchy exceeds five levels, consider persisting a closure-table pattern instead of recalculating it recursively (see Q5).

QUESTION 4

BOM Expansion × Cost Rollup — Calculate Total Product Cost with Recursive Expansion and Quantity Multiplication

WITH RECURSIVECumulative Quantity MultiplicationBOM / ManufacturingAggregation / GROUP BY

Background ▼

A manufacturing bill of materials (BOM) is a tree structure of product → subassembly → component. Because quantities multiply as you move through each level, you must combine recursive expansion with quantity multiplication rather than using a simple SUM.

WITH RECURSIVE bom_tree AS (
  -- Anchor: the starting products and components
  SELECT part_id, part_id AS root_id, 1 AS accumulated_qty
  FROM parts
  UNION ALL
  -- Recursive member: expand to child components and multiply the quantity
  SELECT b.child_part_id, bt.root_id, bt.accumulated_qty * b.quantity
  FROM bom_tree bt
  JOIN bom b ON b.parent_part_id = bt.part_id
)

Design point: start every part at the anchor and recursively expand to child parts through the BOM. Carry quantity with accumulated_qty * child_quantity, count only leaf-part rows (unit_cost IS NOT NULL), and aggregate them at the end.

Cumulative quantity: At each level of a BOM, carry forward parent accumulated quantity * child required quantity. Use multiplication (*), not addition (+).

Problem ▼

Using the product structure below, calculate total_component_cost for each part, subassembly, and finished product with a recursive CTE.

・Only leaf components (unit_cost IS NOT NULL) contribute cost; intermediate assemblies do not have their own cost
・Multiply quantities across the entire parent-to-child path (for example, the number of screws in Finished Product X = screws per Sub α × number of Sub α units)
・Return part_id, part_name, total_component_cost, sorted by part_id ascending

Tables used

▸ parts (NULL means a subassembly or finished product)

part_id	part_name	unit_cost
1	Finished Product X	NULL
2	SubASSY-α	NULL
3	SubASSY-β	NULL
4	M3 Screw	5
5	M8 Bolt	12
6	Frame	200
7	Circuit Board	150

▸ bom (parent → child × quantity)

parent_part_id	child_part_id	quantity	Notes
1	2	2	Finished X → Sub α ×2
1	3	1	Finished X → Sub β ×1
1	6	1	Finished X → Frame ×1
2	4	6	Sub α → Screw ×6
2	5	2	Sub α → Bolt ×2
3	4	4	Sub β → Screw ×4
3	7	1	Sub β → Board ×1

Expected Output ▼

part_id	part_name	total_component_cost
1	Finished Product X	478
2	SubASSY-α	54
3	SubASSY-β	170
4	M3 Screw	5
5	M8 Bolt	12
6	Frame	200
7	Circuit Board	150

Model Answer ▼

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
  */

Explanation (table transitions & key points) ▼

WITH RECURSIVE bom_expand AS (
  SELECT
    p.part_id    AS root_id,
    p.part_id    AS current_id,
    1            AS accumulated_qty,
    p.unit_cost
  FROM parts p
  UNION ALL
  SELECT
    be.root_id,
    b.child_part_id    AS current_id,
    be.accumulated_qty * b.quantity
      AS accumulated_qty,
    p.unit_cost
  FROM bom_expand be
  JOIN bom b ON b.parent_part_id = be.current_id
  JOIN parts p ON p.part_id = b.child_part_id
)
SELECT
  p.part_id,
  p.part_name,
  SUM(be.accumulated_qty * be.unit_cost)
    AS total_component_cost
FROM bom_expand be
JOIN parts p ON p.part_id = be.root_id
WHERE be.unit_cost IS NOT NULL
GROUP BY p.part_id, p.part_name
ORDER BY p.part_id;

LEGEND ▼

Rows read / loaded

Excluded / hidden data

INPUT ▼

parts table & bom tableReview the input data. A parts row with unit_cost NULL is a subassembly or product (it has no cost of its own). bom expresses the parent-to-child quantity relationship.

1 / 6

▸ parts (parts master)

part_id	part_name	unit_cost
1	Finished Product X	NULL
2	SubASSY-α	NULL
3	SubASSY-β	NULL
4	M3 Screw	5
5	M8 Bolt	12
6	Frame	200
7	Circuit Board	150

⋈

▸ bom (part expansion table)

parent	child	qty
1 (Finished Product)	2 (Sub α)	2
1 (Finished Product)	3 (Sub β)	1
1 (Finished Product)	6 (Frame)	1
2 (Sub α)	4 (Screw)	6
2 (Sub α)	5 (Bolt)	2
3 (Sub β)	4 (Screw)	4
3 (Sub β)	7 (Board)	1

parts: 7 rows / bom: 7 rows

 BOM expansion and quantity multiplication

ANCHOR Start all 7 parts (root_id = current_id = itself, qty = 1)

iter1: Expand direct BOM children

root	current	qty
Finished Product X	Sub α	1×2=2
Finished Product X	Sub β	1×1=1
Finished Product X	Frame	1×1=1
Sub α	Screw	1×6=6
Sub β	Screw	1×4=4

→

iter2: Multiply quantities down to leaf components

root	current	qty×cost
Finished Product X	Screw (via α)	2×6×5=60
Finished Product X	Bolt (via α)	2×2×12=48
Finished Product X	Screw (via β)	1×4×5=20
Finished Product X	Board (via β)	1×1×150=150
Total: 200+60+48+20+150 = 478

LEARNING POINTS

Why make every part an anchor: If only root parts are anchors, you cannot calculate the cost of a subassembly or a leaf component by itself. Starting every part lets the same query calculate total cost for leaves, intermediate assemblies, and finished products. A leaf naturally stops because it is not a parent in the BOM.

Multiplication propagation in accumulated_qty: be.accumulated_qty * b.quantity multiplies quantity along the entire path. For “Finished Product X → Sub α (×2) → Screw (×6),” the screw's accumulated quantity is 1×2×6=12. This is the core of BOM expansion.

Role of WHERE unit_cost IS NOT NULL: If assembly rows with unit_cost=NULL enter SUM, NULL propagation can cause errors. Filtering to leaf rows before aggregation produces an accurate bottom-up cost rollup.

ANTI-PATTERNS

Adding quantities with SUM where multiplication is required: Replacing be.accumulated_qty + b.quantity with addition is wrong. If two Sub α units each contain six screws, the requirement is 2×6=12 screws; only multiplication gives the correct rollup.

Infinite loops when the BOM contains a cycle: A design or data error can make part A a child of part B while also being its parent, creating an infinite loop. PostgreSQL can detect this with CYCLE part_id SET is_cycle USING path. Always add a guard in production.

Practical column: BOM expansion and ERP systems

SAP multi-level BOM expansion (CS11/CS15) and Oracle Manufacturing BOM Explosion use essentially the same recursive quantity-multiplication rollup as this query. ERP systems often implement it procedurally, but PostgreSQL and SQL Server can achieve an equivalent expansion with one WITH RECURSIVE query. In practice, add (1) cost-version management (effective-dated unit_cost), (2) alternate components (alternate BOM), and (3) production scrap/yield rates. Add effective_date, alternate_flag, and scrap_rate columns to the bom table, then extend the WHERE condition and quantity formula.

QUESTION 5

Double-Recursive Department Budget Aggregation — Aggregate All Descendant Budgets with dept_tree + closure CTEs

WITH RECURSIVEClosure TableOrganization / HierarchyChained CTEs

Background ▼

This question demonstrates the “double recursion” pattern: chain multiple recursive CTEs in one query. The first recursive CTE expands a department tree (dept_tree) with path strings and depth; the second generates a Closure Table.

WITH RECURSIVE
  -- ① First recursive CTE: expand the hierarchy tree
  tree_cte AS (
    SELECT id, parent_id, name FROM nodes WHERE parent_id IS NULL
    UNION ALL
    SELECT n.id, n.parent_id, n.name
    FROM nodes n JOIN tree_cte t ON n.parent_id = t.id
  ),
  -- ② Second recursive CTE: generate the closure table
  closure_cte AS (
    SELECT id AS ancestor, id AS descendant FROM nodes
    UNION ALL
    SELECT c.ancestor, n.id AS descendant
    FROM closure_cte c JOIN nodes n ON n.parent_id = c.descendant
  )
-- Combine the two CTEs for aggregation and other operations
SELECT ...

A Closure Table stores every (ancestor_id, descendant_id) pair, allowing all descendants of any department to be retrieved with an O(1) JOIN. Summing each department's own_budget through this table produces total_budget, including both direct and indirect descendants.

Double recursion (chained CTEs): PostgreSQL and MySQL 8.0+ let you declare multiple recursive CTEs after declaring WITH RECURSIVE once, separated by commas. A later CTE may reference an earlier CTE, but an earlier CTE cannot reference a later one (no forward references).

Problem ▼

Using the department table below, chain two recursive CTEs and output the following:

・dept_tree (recursive CTE 1): expand every department while adding depth and a path string (for example, HQ > Engineering > Backend)
・closure (recursive CTE 2): build a Closure Table containing every (ancestor_id, descendant_id) pair
・In the outer query, use closure to SUM each department's descendant own_budget
・Return dept_id, dept_name, depth, path, own_budget, total_budget, sorted by depth ascending and then dept_id ascending

Tables used

▸ departments

dept_id	dept_name	parent_id	own_budget
1	HQ	NULL	5000
2	Engineering	1	3000
3	Sales	1	2000
4	Backend	2	1500
5	Frontend	2	1200
6	Domestic Sales	3	1800
7	International Sales	3	900

Expected Output ▼

dept_id	dept_name	depth	path	own_budget	total_budget
1	HQ	0	HQ	5000	15400
2	Engineering	1	HQ > Engineering	3000	5700
3	Sales	1	HQ > Sales	2000	4700
4	Backend	2	HQ > Engineering > Backend	1500	1500
5	Frontend	2	HQ > Engineering > Frontend	1200	1200
6	Domestic Sales	2	HQ > Sales > Domestic Sales	1800	1800
7	International Sales	2	HQ > Sales > International Sales	900	900

Model Answer ▼

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
*/

Explanation (table transitions & key points) ▼

WITH RECURSIVE
dept_tree AS (
  SELECT
    dept_id, dept_name, parent_id, own_budget,
    0 AS depth,
    dept_name AS path
  FROM departments
  WHERE parent_id IS NULL
  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
  FROM departments d
  JOIN dept_tree dt ON d.parent_id = dt.dept_id
),
closure AS (
  SELECT
    dept_id AS ancestor_id,
    dept_id AS descendant_id
  FROM departments
  UNION ALL
  SELECT
    c.ancestor_id,
    d.dept_id AS descendant_id
  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
FROM dept_tree dt
JOIN closure cl ON cl.ancestor_id = dt.dept_id
JOIN departments d2 ON d2.dept_id = cl.descendant_id
GROUP BY dt.dept_id, dt.dept_name, dt.depth, dt.path, dt.own_budget
ORDER BY dt.depth, dt.dept_id;

LEGEND ▼

Rows read / loaded

INPUT ▼

departments tableHierarchy of 7 departments. parent_id=NULL is the root (HQ).

1 / 9

dept_id	dept_name	parent_id	own_budget
1	HQ	NULL	5000
2	Engineering	1	3000
3	Sales	1	2000
4	Backend	2	1500
5	Frontend	2	1200
6	Domestic Sales	3	1800
7	International Sales	3	900

7 rows

 Double-recursive CTE expansion flow

CTE① dept_tree: expand all 7 departments while assigning path and depth

dept_tree result (7 rows)

depth	dept_name	path
0	HQ	HQ
1	Engineering	HQ > Engineering
1	Sales	HQ > Sales
2	Backend	HQ > Engineering > Backend
2	Domestic Sales	HQ > Sales > Domestic Sales

closure result (17 pairs) → SUM

ancestor	descendant
HQ(1)	HQ(1)
HQ(1)	Engineering(2)
HQ(1)	Sales(3)
HQ(1)	Backend(4)
HQ(1)	Frontend(5)
…7 pairs summed	= 15400

LEARNING POINTS

The power of a Closure Table: Because a Closure Table stores every ancestor-to-descendant pair, all descendants of any department can be retrieved with an O(1) equijoin (=). Without recursion, WHERE ancestor_id = 1 returns every descendant of HQ, making aggregation, permission checks, and display especially fast.

Important note on double WITH RECURSIVE in PostgreSQL: PostgreSQL lets one WITH RECURSIVE declaration define multiple recursive CTEs. CTEs are defined in order, so a later CTE may reference an earlier CTE, but an earlier CTE cannot reference a later one. This question places dept_tree before closure.

Practical value of the path string: The path generated with dt.path || ' > ' || d.dept_name can drive breadcrumbs, sorting, and prefix searches such as path LIKE 'HQ > Engineering%'. If a department name contains > , the delimiter collides with the data; use a safer delimiter or PostgreSQL's ltree extension in production.

ANTI-PATTERNS

Forgetting self-pairs in the closure anchor: Without the self-pair (ancestor=descendant=itself), a department's own_budget is not included in total_budget. A leaf department's total should equal its own budget, but would become 0. Always include self-pairs in the anchor.

Not persisting the closure table: Generating it on demand with WITH RECURSIVE is useful for small data sets, but performance degrades as the department count grows. In practice, persist the closure table and update it with a trigger or application code when departments are added, moved, or deleted.

Practical column: Three storage patterns for hierarchical data

There are three common storage models: (1) the adjacency list (parent_id), used here—simple, but descendant queries require recursion; (2) the Closure Table, which stores every pair in a separate table—fast for aggregation and search, but with write overhead; and (3) Nested Sets, which represent ranges with left/right values—fast reads, but complex inserts. Use a Closure Table when reads are frequent and writes are rare; choose an adjacency list plus WITH RECURSIVE when simplicity matters. PostgreSQL's ltree extension is another option.