Re: transitive closure of a graph

vc wrote:
> Mikito Harakiri wrote:
> > I guess you argue that the explicit rule to stop
> > execution is when the join produces no tuples. I object: the execution
> > stops when the union doesn't inflate temporary table anymore.
>
> You can object all you want, but that's how the recursive query works.

OK, now that we know the culprit, let's approach it from another angle. Consider rewriting recursive SQL as view equation

TC(x,y) = A(x,y) union project_xy(A(x,z) join TC(z,y))

In this form, TC is defined declaratively as [minimal] solution of the equation. There is no stop condition anywhere, because there is no procedural execution anywhere in sight.

Now if we expand this equation into a series

TC(x,y) = A(x,y) union project_xy(A(x,z) join A(z,y)) union project_xy(A(x,z1) join A(z1,z2) join A(z2,y))) union ...

then we get a naive evaluation stratedy for recursive view TC. This is a formally infinite series, however, and we have to have a criteria when to abrupt it. You suggest that we stop as soon as A power n vanishes, but that's not how inflationary semantics is defined! Unlike (arithmetic) addition, union is idempotent operator, so that we have to check if ading A power n to TC doesn't increment TC. Received on Thu Oct 13 2005 - 07:27:46 CEST