Recursive CTEs: Single Parents
CTEs can contain references to themselves and, by doing so, apply recursion. Recursive CTEs are useful in manipulating single-parent hierarchies (trees) such as employee organizational charts and forum discussions. They're also useful for multiparent hierarchies (graphs) such as bills of materials (BOMs).
The use of recursive CTEs in T-SQL has several important advantages over other ways of manipulating hierarchical data both in SQL Server and in other database systems. Other methods for manipulating hierarchical data in SQL Server include the use of UDFs or stored procedures that apply recursion or loops to data from temporary tables or table variables. The code of such UDFs and stored procedures is usually lengthy, hard to follow, and hard to maintain—and it's not ANSI compliant. Recursive CTEs keep your code short and ANSI compliant. For hierarchical data manipulation, some other database systems use proprietary code that's non-portable; others apply cursors internally, making the solution inefficient. Recursive CTEs use a series of set-based queries, making for highly efficient solutions. Figure 1 shows the syntax of a basic recursive CTE.
The CTE header functions the same way in recursive and non-recursive queries, so let's focus on the recursive CTE's body and outer query. The body includes at least two queries separated by a UNION ALL operator. (Later, I discuss options you have when specifying more than two queries.) The Anchor Member is a query that SQL Server invokes only once and that doesn't reference the CTE's name. The Recursive Member—a query that contains a reference to the CTE's name—uses the query result in its first iteration. SQL Server invokes the Recursive Member repeatedly until it returns an empty set. In the first invocation, the reference to the CTE's name represents the result the Anchor Member returned. In subsequent invocations, the reference to the CTE's name represents the result the previous invocation of the Recursive Member returned. The reference to the CTE's name in the outer query represents the UNION ALL of all the invocations of both members.
Let's walk through an example to better understand recursive CTEs. Run the code that Listing 5 shows to return Employee 12 and all subordinates at all levels. The Anchor Member at callout A returns details about Employee 12. Then, the Recursive Member at callout B returns the direct subordinates of the employees that the previous step returned. Because the first step is the invocation of the Anchor Member, the Recursive Member returns direct subordinates of Employee 12 (Employee 3). The next invocation returns direct subordinates of Employee 3 (4, 9, 11, 158, 263, 267, 270). The next invocation returns direct subordinates of employees 158 (79, 114, 217) and 263 (5, 265). The final invocation of the Recursive Member returns no subordinates, so SQL Server doesn't invoke the Recursive Member again. The outer query returns Employee 12 and all that employee's subordinates at all levels.
Set-Operation Rules
As I mentioned, a recursive CTE can contain more than two members and has rules governing which set operations (UNION, UNION ALL) you can use between the members. UNION ALL takes two inputs and generates a result containing the rows from both inputs, and UNION does the same with the addition of performing a DISTINCT operation over the unified results to remove duplicates. (For details about the UNION and UNION ALL set operations, see my December 2003 column, "Set-Operation Alternatives," InstantDoc ID 40321.) When one of the CTE members is a Recursive Member, SQL Server repeatedly performs the UNION ALL set operation between members of a recursive CTE until the Recursive Member returns an empty set. SQL Server 2005 doesn't support recursive CTEs where a Recursive Member participates in a UNION operation, directly or indirectly.
Table 1 shows valid and invalid set operations in a recursive CTE. Notice that any scenario where a Recursive Member participates in a UNION operation is invalid. For example, in the scenario AM U RM, the Recursive Member participates in a UNION operation directly, which is invalid. In the scenario RM UA AM U AM, the Recursive Member participates in a UNION operation indirectly because SQL Server performs a UNION between the result of RM UA AM and AM, also an invalid operation.
Listing 6 contains code examples of two recursive CTEs. The first is a valid CTE that applies the AM U AM UA RM scenario; the second CTE is invalid because it applies the AM UA RM U AM scenario.
Prev. page
1
[2]
3
next page 
