Common table expressions (CTE)

Recursive CTE

Author: Bezhaev A.Yu.

In the next realization of MS  A database management system (DBMS) by Microsoft Corporation. SQL(Structured Query Language) is a database computer language designed for the retrieval and management of data in relational database management systems (RDBMS), database schema creation and modification, and database object access control management.SQL Server 2005 the new possibility to use recursive CTE-constructions had appeared. The  CTE (common table expression) allows to determine a table in framework of a query for multiple referencings.CTE allows to realize cycles for generation of number sequences and iterative calculations.

The introduction to recursion in MS SQL Server may be founded in Microsoft`s corresponding manuals, this book and in the Internet. In this paragraph we`ll consider only new examples, useful in the practical mastering. The simplest example of using recursive CTE is generation limited number of natural sequence: 1,2,3, ... N.

Console

Execute

WITH Series(a) AS
(
 SELECT 1
 UNION ALL
 SELECT a+1 FROM Series WHERE a < 100
)
SELECT * FROM Series;

WITH Series(a) AS (  SELECT 1  UNION ALL  SELECT a+1 FROM Series WHERE a < 100 ) SELECT * FROM Series;

    Scheme

No scheme

This construction is meant for generation of natural sequences as one-column table with values from 1 to 100.

A. Iteration calculations

In the elementary and the high mathematics there are more interesting sequences with notable features. Some sequences converge and may be used for realization of calculate algorithms or for calculation of algebraic and transcendent numbers, values of trigonometric functions, for finding equation`s roots, solving linear equation systems and others. Other sequences, such as factorial, Binomial theorem and Fibonacci numbers are divergent sequences which have wide application in the probability theory and the mathematical statistics.

These sequences are made by iterations (recursions in SQL Server), for instance:
A1, A2, A3, A4 = fun(A1, A2, A3).

Here, A1, A2, A3 — start values for iteration process, fun — is a function for calculation 4th, 5th numbers etc, it always uses three previous numbers. Let`s suppose process starts with three equal numbers A1 = A2 = A3 = 1. Then the realization`s schema with using recursive CTE assumes such view:

WITH TABLE(iter, A1, A2, A3, A4) AS
(
 SELECT iter = 1, A1 = 1, A2 = 1, A3 = 1, A4 = fun(1, 1, 1)
 UNION ALL
 SELECT iter + 1, A1 = A2, A2 = A3, A3 = A4, A4=fun(A2, A3, A4)
 FROM TABLE WHERE iter < 50
)
SELECT * FROM TABLE;

Here [iter] column is using for iteration`s number output, [A1] column contains first fifty members of sequence and [A2], [A3], [A4] columns are auxiliary and contain intermediate results.

The generalization of this method is in this example. Let n >= 1, m >= 1. Then sequent calculations

A[n+1] = fun(A[1], A[2], …, A[n])

A[n+2] = fun(A[2], A[3], …, A[n+1])

…

A[n+m] = fun(A[m], A[m+1], …, A[m+n-1])

lead to generation of m new members of sequence A[n+1],…,A[n+m].

We aren`t going to make an example of using recursion in general, because it`s possible only in pseudocode perhaps. You can try to make it for your own. Note that the resulting table has such look:

A[1]    A[2]    …    A[n]      A[n+1]
A[2]    A[3]    …    A[n+1]    A[n+2]
…
A[m+1]  A[m+2]  …    A[m+n-1]  A[m+n]