Re: transitive closure of a graph

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; specifically stop when no new facts are inferred in seminaive evaluation. Received on Thu Oct 13 2005 - 12:43:34 CDT