Re: transitive closure of a graph

Mikito Harakiri wrote:
> 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!

Who cares ? What matters here is the evaluation strategy (that you are confused about). What you call naive is actually a semi-naive strategy because it checks for deltas at the expense of getting into cycles. What you suggest is a naive evaluation stategy, completely impractical for obvious performance reasons.

>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 - 19:21:29 CEST