Common Table Expressions and Recursive Queries

You can use CTEs to implement recursion because CTEs can contain references to themselves. The basic syntax for a CTE for recursive queries is

WITH cte_name (column_list) AS
  (anchor_member
  UNION ALL
  recursive_member)
outer_query

cte_name and column_list have the same meaning as in CTEs for nonrecursive queries. The body of the WITH clause comprises two queries that are connected with the UNION ALL operator. The first query will be invoked only once, and it starts to accumulate the result of the recursion. The first operand of UNION ALL does not reference the CTE (see Example 6.80). This query is called the anchor query or seed.

The second query contains a reference to the CTE and represents the recursive portion of it. For this reason it is called the recursive member. In the first invocation of the recursive part, the reference to the CTE represents the result of the anchor query.

The recursive member uses the query result of the first invocation. After that, the system repeatedly invokes the recursive part. The invocation of the recursive member ends when the result of the previous invocation is an empty set.

The UNION ALL operator joins the rows accumulated so far, as well as the additional rows that are added in the current invocation. (Inclusion of UNION ALL means that no duplicate rows will be eliminated from the result.)

Finally, outer query defines a query specification that uses the CTE to retrieve all invocations of the union of both members.

The table definition in Example 6.80 will be used to demonstrate the recursive form of CTEs.

USE sample;
CREATE TABLE airplane
  (containing_assembly VARCHAR(10),
  contained_assembly VARCHAR(10),
  quantity_contained INT,
  unit_cost DECIMAL (6,2));
insert into airplane values ( 'Airplane', 'Fuselage',1, 10);
insert into airplane values ( 'Airplane', 'Wings', 1, 11);
insert into airplane values ( 'Airplane', 'Tail',1, 12);
insert into airplane values ( 'Fuselage', 'Cockpit', 1, 13);
insert into airplane values ( 'Fuselage', 'Cabin', 1, 14);
insert into airplane values ( 'Fuselage', 'Nose',1, 15);
insert into airplane values ( 'Cockpit', NULL, 1,13);
insert into airplane values ( 'Cabin', NULL, 1, 14);
insert into airplane values ( 'Nose', NULL, 1, 15);
insert into airplane values ( 'Wings', NULL,2, 11);
insert into airplane values ( 'Tail', NULL, 1, 12);

The airplane table contains four columns. The column containing_assembly specifies an assembly, while contained_assembly comprises the parts (one by one) that build the corresponding assembly. (Figure 6-1 shows graphically how an airplane with its parts could look.)

Suppose that the airplane table contains 11 rows, which are shown in Table 6-2. (The INSERT statements in Example 6.80 insert these rows in the airplane table.)

Table 6-2 – Content of the airplane Table

Example 6.81 shows the use of the WITH clause to define a query that calculates the total costs of each assembly.

USE sample;
WITH list_of_parts(assembly1, quantity, cost) AS
  (SELECT containing_assembly, quantity_contained, unit_cost
    FROM airplane
    WHERE contained_assembly IS NULL
  UNION ALL
  SELECT a.containing_assembly, a.quantity_contained,
  CAST(l.quantity*l.cost AS DECIMAL(6,2))
    FROM list_of_parts l,airplane a
    WHERE l.assembly1 = a.contained_assembly)
SELECT * FROM list_of_parts;

The WITH clause defines the CTE called list_of_parts, which contains three columns: assembly, quantity, and cost. The first SELECT statement in Example 6.81 will be invoked only once, to accumulate the results of the first step in the recursion process.

The SELECT statement in the last row of Example 6.81 displays the following result.

The first five rows in the preceding output show the result set of the first invocation of the anchor member of the query in Example 6.81. All other rows are the result of the recursive member (second part) of the query in the same example. The recursive member of the query will be invoked twice: the first time for the fuselage assembly and the second time for the airplane itself.

The query in Example 6.82 will be used to get the costs for each assembly with all its subparts.

USE sample;
WITH list_of_parts(assembly, quantity, cost) AS
  (SELECT containing_assembly, quantity_contained, unit_cost
    FROM airplane
    WHERE contained_assembly IS NULL
  UNION ALL
  SELECT a.containing_assembly, a.quantity_contained,
    CAST(l.quantity*l.cost AS DECIMAL(6,2))
    FROM list_of_parts l,airplane a
    WHERE l.assembly = a.contained_assembly )
SELECT assembly, SUM(quantity) parts, SUM(cost) sum_cost
  FROM list_of_parts
  GROUP BY assembly;

The output of the query in Example 6.82 is as follows:

There are several restrictions for a CTE in a recursive query:

• The CTE definition must contain at least two SELECT statements (an anchor member and one recursive member) combined by the UNION ALL operator.
• The number of columns in the anchor and recursive members must be the same. (This is the direct consequence of using the UNION ALL operator.)
• The data type of a column in the recursive member must be the same as the data type of the corresponding column in the anchor member.
• The FROM clause of the recursive member must refer only once to the name of the CTE.
• The following options are not allowed in the definition part of a recursive member: SELECT DISTINCT, GROUP BY, HAVING, aggregation functions, TOP, and subqueries. (Also, the only join operation that is allowed in the query definition is an inner join.)