Re: transitive closure of a graph
Date: 12 Oct 2005 20:36:31 -0700
Message-ID: <1129174591.012900.108730_at_g43g2000cwa.googlegroups.com>
Mikito Harakiri wrote:
> vc wrote:
> > Mikito Harakiri wrote:
> > > vc wrote:
> > > > Mikito Harakiri wrote:
> > > > > I fail to see why. Start with the temporary table
> > > > >
> > > > > {(1,2), (2,1), (2,3), (3,2)}
> > > > >
> > > > > First join would produce new edges
> > > > >
> > > > > {(1,1), (2,2), (3,3), (1,3), (3,1)}
> > > >
> ...
> > Ok. So without duplicates, we would have:
> >
> > First, the current join set and TransClosedEdges:
> > {(1,2), (2,1), (2,3), (3,2)}
> >
> > then the current join set would be:
> >
> > {(1,1), (2,2), (3,3), (1,3), (3,1)}
>
> Glad you made that far.
What's that supposed to mean ?
>> >
> > and TransClosedEdges would become (and stay unchanged):
> > {(1,1), (2,2), (3,3), (1,3), (3,1), (1,2), (2,1), (2,3), (3,2)}
>
> As soon as new step doesn't add any new tuples to TransClosedEdges, the
> execution stops.
No, it does not.
> 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. Received on Thu Oct 13 2005 - 05:36:31 CEST