Ackermann function (was factorial)

Hi Serge,

An interesting detail in the factorial example is that we push predicate "n<5" into the view definition, even though our query asks "n=5" only.

Now, how about Ackermann function:

with yplus1 as (
  values(0, 1)
    union all
  select y+1, ypp+1
    from yplus1

• some safety predicate here ), with ackermann (x,y,A) as ( select 0, y, ypp from yplus1 union all select x+1, 0, A from ackermann where y=1 union all select x, y, A from ackermann a0 where A=(select A from ackermann as a1 where a1.x=a0.x-1 and a1.y=(select A from ackermann as a2 where a2.x=a0.x and a2.y=a0.y-1))
  • some safety predicate here ) select a from ackerman where x=3 and y=3;

? Not only safety predicate is the problem (because, the engine would otherwise try to materialize the whole infinite relation 'yplus1'), but also subqueries are not allowed in db2.

Could I summarize the above as: The correct mathematical definition for SQL99 recursion is "limited primitive recursion"?

Serge Rielau <srielau_at_ca.ibm.com> wrote in message news:<3C38992A.BF1A1FA9_at_ca.ibm.com>...
> Hi Mikko,
>
> I think the smallest version is:
> with factorial (n, f) as
> ( values(1, 1)
> union all
> select n+1, f*(n+1)
> from factorial
> where n<5
> )
> select * from factorial where n = 5;
>
> DB2 today doesn't push the predicates into a recursion. From a algebraic point of
> view it could.
> however then it would need to push into both legs of the union (and then deduce
> that 1 < 5 and kick that out).
> However, in general the WITH clause is used to use the same result multiple times
> in the following query. In this case pushing of the predicate would have to follow
> a set of rules. In fact it couldn't be pushed. Rather the predicate describing the
> superset needs to be added to the recursion.
>
> Cheers
> Serge
Received on Mon Jan 07 2002 - 14:53:10 CET