Re: transitive closure of a graph

From: vc <boston103_at_hotmail.com>
Date: 12 Oct 2005 20:36:31 -0700
Message-ID: <1129174591.012900.108730@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 Wed Oct 12 2005 - 22:36:31 CDT