Recursive Common Table Expressions (CTEs)

Definition:

A Recursive Common Table Expression (CTE) is a type of CTE that references itself in order to retrieve hierarchical or sequential data. Recursive CTEs are useful when dealing with data structures like organizational charts, file systems, or any situation involving parent-child relationships. The recursion continues until a termination condition is met, allowing for easy exploration of hierarchical data.

Structure:

A recursive CTE consists of two main parts:

1. Anchor Member (Base Case): This is the starting point of the recursion.

2. Recursive Member: This is the part that refers back to the CTE itself, allowing it to recursively fetch more rows.

Syntax:

WITH RECURSIVE cte_name AS (
-- Anchor Member (Base Case)
SELECT base_query
UNION ALL
-- Recursive Member
SELECT recursive_query
FROM cte_name
WHERE condition
)
SELECT * FROM cte_name;

Example: Employee Hierarchy Problem

Problem Statement:

Suppose you have an employees table that shows a list of employees and their respective managers. The goal is to determine the hierarchy, showing all employees who report (directly or indirectly) to a particular manager. This can help answer the question: "Who is reporting to whom?"

Sample Data:

Alice (ID 1) is at the top of the hierarchy.

Bob and Charlie report to Alice.

David and Eve report to Bob.

Frank reports to Charlie.

Step-by-Step Solution:

1. Anchor Member (Base Case):

Select the top-level manager, which is Alice (employee ID 1). This will be the starting point.

Set level = 1 to indicate that Alice is at the first level of the hierarchy.

1. Recursive Member:

The recursive part will find employees who report to the current manager found by the base query.

Each time a new level is found, level will be incremented by 1 to indicate the depth in the hierarchy.

The recursion continues until no more employees are found who report to the managers in the previous level.

SQL Query:

WITH RECURSIVE EmployeeHierarchy AS (
-- Anchor Member: Start with Alice (Top-level manager)
SELECT employee_id, first_name, manager_id, 1 AS level
FROM employees
WHERE employee_id = 1

UNION ALL

-- Recursive Member: Find employees reporting to the employees found above
SELECT e.employee_id, e.first_name, e.manager_id, eh.level + 1
FROM employees e
INNER JOIN EmployeeHierarchy eh ON e.manager_id = eh.employee_id

)
-- Fetch results from the CTE
SELECT level, first_name, employee_id, manager_id
FROM EmployeeHierarchy
ORDER BY level, manager_id;

Detailed Explanation:

1. Anchor Member Execution:

The query starts by selecting Alice, the top-level manager (employee_id = 1). This acts as the base case and sets the level to 1.

Result of Anchor Member: | employee_id | first_name | manager_id | level | |-------------|------------|------------|-------| | 1 | Alice | NULL | 1 |

1. Recursive Execution:

The recursive part of the CTE will now execute and look for employees whose manager_id matches Alice's employee_id.

Bob and Charlie will be found, and they will be assigned level = 2.

This process continues, finding David, Eve, and Frank, and incrementing the level each time.

The recursion stops when no more matches are found.

1. Final Output: | level | first_name | employee_id | manager_id | |-------|------------|-------------|------------| | 1 | Alice | 1 | NULL | | 2 | Bob | 2 | 1 | | 2 | Charlie | 3 | 1 | | 3 | David | 4 | 2 | | 3 | Eve | 5 | 2 | | 3 | Frank | 6 | 3 |

Explanation of Output:

Alice is at level 1 and has no manager (NULL).

Bob and Charlie are at level 2, reporting to Alice.

David and Eve are at level 3, reporting to Bob.

Frank is also at level 3, reporting to Charlie.

Conclusion:

Recursive CTEs are extremely useful for querying hierarchical data.

The example demonstrates how to find all subordinates starting from a particular manager, making it clear who reports to whom at each level of the organization.

This approach can be adapted to various scenarios, such as processing directory structures, product categories, or any parent-child relationships.