Posted by: Serge Rielau
Motivation
There are multiple ways in which DB2 supports recursion in SQL.
One of which is recursion using the ANSI SQL recursive UNION ALL approach.
The other approach is using the CONNECT BY clause.
Actually I like to add explanation of recursion into my "SQL on Fire" talks because the topic never seems to get old.
In this blog however I will not talk about recursion in SQL itself.
Instead I want to answer a frequent email question about how to achieve recursion in SQL PL (or PL/SQL).
Fibonacci number
A commonly used example when discussing recursion is the generation of Fibonacci numbers.
So, since I'm lazy, let's use that for the purpose of this post.
A Fibonacci number is defined like this:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n -2) where n > 1
If we want to model this logic in SQL PL it might look like this:
CREATE OR REPLACE FUNCTION Fib(n INTEGER) RETURNS DECIMAL(31, 0)
BEGIN
DECLARE res DECIMAL(31, 0);
CASE WHEN n = 0 THEN
SET res = 0;
WHEN n = 1 THEN
SET res = 1;
WHEN n > 1 THEN
SET res = Fib(n - 1) + Fib(n - 2);
ELSE
SIGNAL SQLSTATE '78000' SET MESSAGE_TEXT = 'Bad input';
END CASE;
RETURN res;
END;
/
ERROR near line 9:
SQL0440N No authorized routine named "FIB" of type "FUNCTION" having compatible arguments was found.
This definition is a bit fluffy.
One could imagine a simple RETURN with a DECODE.
But that won't change the error message.
The problem is that DB2 does not allow a function to refer to itself directly or even indirectly in that manner.
DB2 will not insert the function into the DB schema in SYSCAT.ROUTINES until it is done parsing it.
And it won't parse successfully because the function "FIB" does not yet exist.
Does that mean that DB2 does not support recursive routines?
Far from it!
Recursion using dynamic SQL
One way to break this dependency on its own existence is to avoid parsing and compiling the recursive step when the function is created.
When the function is being executed it can call itself with a dynamic statement without trouble:
CREATE OR REPLACE FUNCTION Fib(n INTEGER) RETURNS DECIMAL(31, 0)
BEGIN
DECLARE res DECIMAL(31, 0);
CASE WHEN n = 0 THEN
SET res = 0;
WHEN n = 1 THEN
SET res = 1;
WHEN n > 1 THEN
BEGIN
DECLARE stmt STATEMENT;
PREPARE stmt FROM 'SET ? = Fib(? - 1) + Fib(? - 2)';
EXECUTE stmt INTO res USING n, n;
END;
ELSE
SIGNAL SQLSTATE '78000' SET MESSAGE_TEXT = 'Bad input';
END CASE;
RETURN res;
END;
/
VALUES Fib(10);
1
---------------------------------
55
What if the recursive step is in a query?
The only thing that changes is that now the query needs to be dynamic.
Typically this means a dynamic cursor:
CREATE OR REPLACE FUNCTION Fib(n INTEGER) RETURNS DECIMAL(31, 0)
BEGIN
DECLARE res DECIMAL(31, 0);
CASE WHEN n = 0 THEN
SET res = 0;
WHEN n = 1 THEN
SET res = 1;
WHEN n > 1 THEN
BEGIN
DECLARE stmt STATEMENT;
DECLARE cur CURSOR FOR stmt;
PREPARE stmt FROM 'SELECT Fib(? - 1) + Fib(? - 2) FROM SYSIBM.SYSDUMMY1';
OPEN cur USING n, n;
FETCH cur INTO res;
CLOSE cur;
END;
ELSE
SIGNAL SQLSTATE '78000' SET MESSAGE_TEXT = 'Bad input';
END CASE;
RETURN res;
END;
/
VALUES Fib(20);
1
---------------------------------
6765/
The same technique also works for a recursive procedure:
CREATE OR REPLACE PROCEDURE Fib(IN n INTEGER, OUT res DECIMAL(31, 0))
BEGIN
DECLARE FibNMinus1,
FibNMinus2 DECIMAL(31, 0);
CASE WHEN n = 0 THEN
SET res = 0;
WHEN n = 1 THEN
SET res = 1;
WHEN n > 1 THEN
BEGIN
DECLARE stmt STATEMENT;
PREPARE stmt FROM 'CALL Fib(?, ?)';
EXECUTE stmt INTO FibNMinus1 USING n - 1;
EXECUTE stmt INTO FibnMinus2 USING n - 2;
SET res = FibNMinus1 + FibNMinus2;
END;
ELSE
SIGNAL SQLSTATE '78000' SET MESSAGE_TEXT = 'Bad input';
END CASE;
END;
/
CALL Fib(20, ?);
Value of output parameters
--------------------------------
RES = 6765
Note that I was able to reuse the same prepared CALL statement for both recursive invocations.
There is also another approach which does not involve dynamic SQL.
Recursion using modules (or PL/SQL Packages)
Another way to allow DB2 to compile a recursive invocation is separate the definition of the routine in the catalogs from the definition of its body.
This is only possible for routines defined in modules or in PL/SQL Packages.
Here is an example using a module.
First we create the module and add the function prototype without the body.
Since we want to reference the function globally we need to PUBLISH the function.
CREATE OR REPLACE MODULE M;
ALTER MODULE m PUBLISH FUNCTION Fib(n INTEGER) RETURNS DECIMAL(31, 0);
/
The function exists now in SYSCAT.ROUTINES
SELECT ROUTINENAME FROM SYSCAT.ROUTINES WHERE ROUTINEMODULENAME = 'M';
ROUTINENAME
--------------------------------------------------
FIB
We can now add the function body including the self references:
ALTER MODULE m ADD FUNCTION Fib(n INTEGER) RETURNS DECIMAL(31, 0)
BEGIN
DECLARE res DECIMAL(31, 0);
CASE WHEN n = 0 THEN
SET res = 0;
WHEN n = 1 THEN
SET res = 1;
WHEN n > 1 THEN
SET res = Fib(n - 1) + Fib(n - 2);
ELSE
SIGNAL SQLSTATE '78000' SET MESSAGE_TEXT = 'Bad input';
END CASE;
RETURN res;
END;
/
VALUES M.Fib(20);
1
---------------------------------
6765
Having to add the module name for every invocation may not be what we want.
But it's easy to write a simple wrapper.
Being defined in inline SQL PL the wrapper has no runtime overhead:
CREATE OR REPLACE FUNCTION Fib(n INTEGER) RETURNS DECIMAL(31, 0)
RETURN M.Fib(n);
/
VALUES Fib(20);
1
---------------------------------
6765
The same concept also holds when defining a recursive procedure:
CREATE OR REPLACE MODULE M;
ALTER MODULE m PUBLISH PROCEDURE Fib(IN n INTEGER, OUT res DECIMAL(31, 0));
/
ALTER MODULE m ADD PROCEDURE Fib(IN n INTEGER, OUT res DECIMAL(31, 0))
BEGIN
DECLARE FibNMinus1,
FibNMinus2 DECIMAL(31, 0);
CASE WHEN n = 0 THEN
SET res = 0;
WHEN n = 1 THEN
SET res = 1;
WHEN n > 1 THEN
CALL Fib(n - 1, FibNMinus1);
CALL Fib(n - 2, FibNMinus2);
SET res = FibNMinus1 + FibNMinus2;
ELSE
SIGNAL SQLSTATE '78000' SET MESSAGE_TEXT = 'Bad input';
END CASE;
END;
/
CREATE OR REPLACE PROCEDURE Fib(IN n INTEGER, OUT res DECIMAL(31, 0))
BEGIN
CALL M.Fib(n, res);
END;
/
CALL Fib(20, ?);
Value of output parameters
--------------------------------
RES = 6765
Limitations
To prevent runaway recursion DB2 imposes the maximum level of nesting of any routine, trigger and anonymous block to 64 levels.
#Db2