Re: transitive closure of a graph

Mikito Harakiri wrote:
> vc wrote:
> > It's not. In the naive case the stop condition is 'no change in the
> > set of rows representing the TC' whilst in the semi-naive case it's
> > 'delta is emty'.
>
> OK, rewind to pages 314. There you find an explicit algorithm for
> semi-naive evaluation of transitive closure. The rules apply to
> nonlinear recursion version, but that doesn't matter for the issue at
> hand.

I do not know what 'pages 314' or the previously mentioned page might be.

>
> First, they define temporary relation at step i+1 -- temp_i+1 -- which
> is join of delta on step i -- delta_i -- and dynamically build
> transitive closure relation anc_i(x,y). Second, they define delta at
> step i+1 -- delta_i+1 -- as a difference of temp_i+1 and anc_i. This
> difference is empty as soon as we reach fixed point.
>
> In general, it would look surprising if logical query output depended
> upon evaluation strategy.

Might be educational to take a look at Prolog for example. Received on Thu Oct 13 2005 - 22:16:13 CEST