Recursive Queries Using Common Table Expressions

A common table expression (CTE) provides the significant advantage of being able to reference itself, thereby creating a recursive CTE. A recursive CTE is one in which an initial CTE is repeatedly executed to return subsets of data until the complete result set is obtained.

In SQL Server 2005, a query is referred to as a recursive query when it references a recursive CTE. Returning hierarchical data is a common use of recursive queries, for example: Displaying employees in an organizational chart, or data in a bill of materials scenario in which a parent product has one or more components and those components may, in turn, have subcomponents or may be components of other parents.

A recursive CTE can greatly simplify the code required to run a recursive query within a SELECT, INSERT, UPDATE, DELETE, or CREATE VIEW statement. In earlier versions of SQL Server, a recursive query usually requires using temporary tables, cursors, and logic to control the flow of the recursive steps. For more information about common table expressions, see Using Common Table Expressions.

Structure of a Recursive CTE

The structure of the recursive CTE in Transact-SQL is similar to recursive routines in other programming languages. Although a recursive routine in other languages returns a scalar value, a recursive CTE can return multiple rows.

A recursive CTE consists of three elements:

1. Invocation of the routine.
   The first invocation of the recursive CTE consists of one or more CTE_query_definitions joined by UNION ALL, UNION, EXCEPT, or INTERSECT operators. Because these query definitions form the base result set of the CTE structure, they are referred to as anchor members.
   CTE_query_definitions are considered anchor members unless they reference the CTE itself. All anchor-member query definitions must be positioned before the first recursive member definition, and a UNION ALL operator must be used to join the last anchor member with the first recursive member.
2. Recursive invocation of the routine.
   The recursive invocation includes one or more CTE_query_definitions joined by UNION ALL operators that reference the CTE itself. These query definitions are referred to as recursive members.
3. Termination check.
   The termination check is implicit; recursion stops when no rows are returned from the previous invocation.

Pseudocode and Semantics

The recursive CTE structure must contain at least one anchor member and one recursive member. The following pseudocode shows the components of a simple recursive CTE that contains a single anchor member and single recursive member.

WITH cte_name ( column_name [,...n] )

AS

(

CTE_query_definition –- Anchor member is defined.

UNION ALL

CTE_query_definition –- Recursive member is defined referencing cte_name.

)

-- Statement using the CTE

SELECT *

FROM cte_name

The semantics of the recursive execution is as follows:

1. Split the CTE expression into anchor and recursive members.
2. Run the anchor member(s) creating the first invocation or base result set (T0).
3. Run the recursive member(s) with Ti as an input and Ti+1 as an output.
4. Repeat step 3 until an empty set is returned.
5. Return the result set. This is a UNION ALL of T0 to Tn.

Example

The following example shows the semantics of the recursive CTE structure by returning a hierarchical list of employees, starting with the highest ranking employee, in the Adventure Works Cycles company. The statement that executes the CTE limits the result set to employees in the Research and Development Group. A walkthrough of the code execution follows the example.

USE AdventureWorks;
GO
WITH DirectReports (ManagerID, EmployeeID, Title, DeptID, Level)
AS
(
-- Anchor member definition
    SELECT e.ManagerID, e.EmployeeID, e.Title, edh.DepartmentID, 
        0 AS Level
    FROM HumanResources.Employee AS e
    INNER JOIN HumanResources.EmployeeDepartmentHistory AS edh
        ON e.EmployeeID = edh.EmployeeID AND edh.EndDate IS NULL
    WHERE ManagerID IS NULL
    UNION ALL
-- Recursive member definition
    SELECT e.ManagerID, e.EmployeeID, e.Title, edh.DepartmentID,
        Level + 1
    FROM HumanResources.Employee AS e
    INNER JOIN HumanResources.EmployeeDepartmentHistory AS edh
        ON e.EmployeeID = edh.EmployeeID AND edh.EndDate IS NULL
    INNER JOIN DirectReports AS d
        ON e.ManagerID = d.EmployeeID
)
-- Statement that executes the CTE
SELECT ManagerID, EmployeeID, Title, Level
FROM DirectReports
INNER JOIN HumanResources.Department AS dp
    ON DirectReports.DeptID = dp.DepartmentID
WHERE dp.GroupName = N'Research and Development' OR Level = 0;
GO

Example Code Walkthrough

1. The recursive CTE, DirectReports, defines one anchor member and one recursive member.

2. The anchor member returns the base result set T0. This is the highest ranking employee in the company; that is, an employee who does not report to a manager.
   Here is the result set returned by the anchor member:

   ManagerID EmployeeID Title                                   Level
   --------- ---------- --------------------------------------- ------
   NULL      109        Chief Executive Officer                 0
   

3. The recursive member returns the direct subordinate(s) of the employee in the anchor member result set. This is achieved by a join operation between the Employee table and the DirectReports CTE. It is this reference to the CTE itself that establishes the recursive invocation. Based on the employee in the CTE DirectReports as input (Ti), the join (Employee.ManagerID = DirectReports.EmployeeID) returns as output (Ti+1), the employees who have (Ti) as their manager. Therefore, the first iteration of the recursive member returns this result set:

   ManagerID EmployeeID Title                                   Level
   --------- ---------- --------------------------------------- ------
   109       12         Vice President of Engineering           1
   

4. The recursive member is activated repeatedly. The second iteration of the recursive member uses the single-row result set in step 3 (containing EmployeeID``12) as the input value, and returns this result set:

   ManagerID EmployeeID Title                                   Level
   --------- ---------- --------------------------------------- ------
   12        3          Engineering Manager                     2
   

   The third iteration of the recursive member uses the single-row result set above (containing EmployeeID``3) as the input value, and returns this result set:

   ManagerID EmployeeID Title                                   Level
   --------- ---------- --------------------------------------- ------
   3         4          Senior Tool Designer                    3
   3         9          Design Engineer                         3
   3         11         Design Engineer                         3
   3         158        Research and Development Manager        3
   3         263        Senior Tool Designer                    3
   3         267        Senior Design Engineer                  3
   3         270        Design Engineer                         3
   

   The fourth iteration of the recursive member uses the previous set of rows for EmployeeID values 4, 9, 11, 158, 263, 267, and 270 as the input value.
   This process repeats until the recursive member returns an empty result set.

5. The final result set returned by the running query is the union of all result sets generated by the anchor and recursive members.
   Here is the complete result set returned by the example:

   ManagerID EmployeeID Title                                   Level
   --------- ---------- --------------------------------------- ------
   NULL      109        Chief Executive Officer                 0
   109       12         Vice President of Engineering           1
   12        3          Engineering Manager                     2
   3         4          Senior Tool Designer                    3
   3         9          Design Engineer                         3
   3         11         Design Engineer                         3
   3         158        Research and Development Manager        3
   3         263        Senior Tool Designer                    3
   3         267        Senior Design Engineer                  3
   3         270        Design Engineer                         3
   263       5          Tool Designer                           4
   263       265        Tool Designer                           4
   158       79         Research and Development Engineer       4
   158       114        Research and Development Engineer       4
   158       217        Research and Development Manager        4
   (15 row(s) affected)
   

See Also

Concepts

Using Common Table Expressions

Other Resources

WITH common_table_expression (Transact-SQL)
Query Hint (Transact-SQL)
INSERT (Transact-SQL)
UPDATE (Transact-SQL)
DELETE (Transact-SQL)
EXCEPT and INTERSECT (Transact-SQL)

Help and Information

Getting SQL Server 2005 Assistance