# 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.

Tags:
function
procedure
sql
routine
sql_pl
fibonacci
recursion
1YONGLEIG commented PermalinkCool

2lelle12 commented PermalinkNice article (as usual). Perhaps it is worth mentioning that the recursion described in this article adds more expressive power than what is possible using CTE's (and I assume connect by as well), nested recursive calls comes to mind.

3SergeRielau commented PermalinkLennart,

The SQL Standard went beyond IBM's initial support to also allow for DEPTH FIRST recursion.

Also I think some of the limitations we currently have are unnecessary.

For example it would be fine to allow OLAP, ORDER BY and aggregates.

Allowing more fancy FROM clauses (perhaps multiple references to the recursive view) would semantically trickier, I think.

As you note there seems to be little pressure to enhance.

If I were to re-open CTE I would support them in general FROM clauses.

Serge

4BigBrett58 commented PermalinkI think this is very interesting and believe I understand how this works. I've tried to compile a couple of your examples without success. Specifically, I tried with the module with function and the function with the dynamic cursor. Both attempts ended with basically the same error. The dynamic cursor function would compile, but I received the error Lookup Error - DB2 Database Error: ERROR [42887] [IBM][DB2/LINUXX8664] SQL0390N The function "schema.FIB" resolved to specific function "xxxx" that is not valid in the context where it is used. The function within the module had the same error when trying to add the function body. I'm working with DB2 LUW 9.7 fix pack 5. It is a partitioned database. I've messed around quite awhile trying to figure out some way to get it to work. I can get it to compile within the module if I change to "begin atomic" and change CASE WHENs to IFs, but the result is the same when I try values(m.Fib(10); So, best guesses in descending order are that this is supposed to be for single partition database, for DB2 LUW 10.1, or DB2 Z/OS.

5SergeRielau commented PermalinkBrett,

It's a rather fundamental restriction independent of recursion.

When you go to BEGIN ATOMIC you are using inline SQL PL which is supported.

But inline SQL PL has many functional limitations such as no dynamic SQL.

Serge

6BigBrett58 commented PermalinkThanks for the reply. I'm actually happy to know that it wasn't possible, because I thought I tried everything I could think of. This academic exercise lead me to start taking a look at modules. I started to rewrite a pretty complex process I made 18 months ago. I really enjoy blog entries like this one. It gets my creative juices flowing.

7pbarbas commented PermalinkVery nice article. I was trying to use this implementation but with a small diference:

1