Re: transitive closure of a graph

From: Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com>
Date: 13 Oct 2005 12:42:08 -0700
Message-ID: <1129232528.866733.157970@g49g2000cwa.googlegroups.com>

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.

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. Received on Thu Oct 13 2005 - 14:42:08 CDT