About generation of number sequences in SQL Server

Author: Bezhaev A.Yu.

In the next realization of MS SQL Server 2005 the new possibility to use recursive CTE-constructions had appeared. The 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 Microsofts corresponding manuals, [this book](/en/book_recursive_cte.html "Recursive CTE") and in the Internet. In this paragraph well 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.

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

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. Lets suppose process starts with three equal numbers A1 = A2 = A3 = 1. Then the realizations 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 arent going to make an example of using recursion in general, because its 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]  

B. About Fibonacci sequence

The Fibonacci sequence might be calculated by this iteration formula:

A[i+2] = A[i] + A[i+1];  i = 1,…, n; A[1] = A[2] = 1.

Its simple to see the analogy with general case in previous point if we bring in function f(x,y)=x+y. The [iter] column is used for keeping iterations number, [a] column is used for keeping A[i], [b] and [c] for A[i+1] and A[i+2] correspondingly. The [d] column is not in use. The calculation of Fibonacci numbers may be put into code accordingly to general method like this:

with Fibonacci(iter,a,b,c) as  
(  
 select iter=1, a=1, b=1, c=1+1  
 UNION all  
 select iter+1, a=b, b=c, c=b+c  
 from Fibonacci where b < 1000  
)  
select * from Fibonacci;

Let`s give the result of query for calculation Fibonacci numbers are less than 1000 (2nd column).

C. Equation`s root finding

The large section of mathematical and functional analysis is dedicated to finding equations` roots of one-variable and multivariable functions. The root of equation g(x) = 0 is a number r (or vector r) which complies with condition g(r) = 0. The general method of solving such equations is in reduction to the problem of fixed point:

x=f(x).

The sense of this reduction is in the finding of such function f which makes equations g(x) = 0 and x = f(x) equivalent. Besides, operator f must be contracting. That is if the value r1 takes place near solution r, than the value r2 = f(r1) must be even nearer to the solution: abs(r-r2) < A * abs(r-r1), where positive constant A is less then unity (A<1) and isn`t depends on select of r1 value.

The contracting mappings are possible be many. The preference ones are that for which A constant takes less value. The less the constant the process of finding of equation`s g(x) root converges faster:

r2 = f(r1), r3 = f(r2),  r4 = f(r3) …

Let`s note an illustrating example in SQL.

D. Iterative calculation of square root

Square root from A number is a solution of equation x * x = A. In the terms of previous point it is a root of equation g(x) = 0, where g(x) = x * x - a. The calculation of this numbers isnt difficult. In SQL we may use SQRT(a) or POWER(a, 0.5) for it. Lets exemplify the method, nevertheless, which is useful in the case when there is no standard function but the contracting mapping is known.

The iterative analytical algorithm for calculation of square root is well known from basic course of mathematics and you can see it here.

It may be written in the form of contracting mapping x = f(x), where

f(x)=1/2*(x+a/x).

 Its easy to get evidence in that the equation x = 1/2 * (x+a/x) is equivalent to equation x*x = a for x <> 0. The reader with mathematical education may try to prove that this transformation is really contracting, and therefore may be used for iteration process of finding equations root.

For illustration of this algorithm let`s note an example of SQL-code for calculation the square root from a = 3:

with Square3(a,b,c) as  
(  
 select 1, cast(3 as float(53)), cast(3 as float(53))  
 UNION all  
 select a+1, 1./2.*(b+3/b), 1./6.*3*(c+3./c) from Square3 where a < 7  
)  
  
select iteration=a, Exact=sqrt(cast(3 as float(53))), Res1=b, Res2=c  
from Square3;

Here the [a] column is introduced for iteration`s number, the [b] and [c] columns calculate square root by two arithmetically equivalent methods. Iterations do not use built-in operations such as SQRT or POWER, but for control we outputted the value of square root which is calculated by using standard function in the [exact] column.

It is evident that the 6th iteration calculations in the third column [Res1] had leaded to coincidence with value of built-in function SQRT(3) in [Exact] column in the FLOAT(53) precision limits. Calculations in the fourth column [Res2] had not. What`s the difference? It is not so obvious, but the reason in that the expression (1./6.) calculates with big mistake as operands are not casted to the 8-byte representation for real numbers (double precision). It affects on all calculations and we have only 5-6 valid significant digits in the result that is corresponds to the theory of calculations with single precision arithmetic.