Re: transitive closure of a graph

Mikito Harakiri wrote:
> vc wrote:
> > 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.
>
> OK, rewind to p.313. Naive strategy computes full joins of relations as
> in the series
>
> T = G \/ G^2 \/ G^3 \/ ...
>
> until fixpoint is reached, while semi-naive strategy computes deltas
> (less work). The stop condition is identical in both cases;

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'.

> specifically stop when no new facts are inferred in seminaive
> evaluation.
Received on Thu Oct 13 2005 - 21:07:33 CEST