Re: transitive closure of a graph

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.

Hmm, going to authorities is not the most convincing proof, but here is what the Alice book said (Example 14.1.1, p.345)

"A computation ends when T becomes stable, which means that no new edges are added in the current iteration, so T now holds transitive closure of G".

The other argument is, what if you have more than one rule with the relation T that occurs in the head and the body?

with TransClosedEdges (tail, head) as
( select tail, head from Edges
  union
  select e.tail, ee.head from Edges e, TransClosedEdges ee   where e.head = ee.tail
  union
  select e.tail, ee.head from TransClosedEdges e, Edges ee   where e.head = ee.tail
)
select * from TransClosedEdges

What the termination rule for this expression might be. Received on Thu Oct 13 2005 - 19:13:12 CEST