Re: transitive closure of a graph
Date: 12 Oct 2005 20:15:23 -0700
Message-ID: <1129173322.971887.279870_at_g14g2000cwa.googlegroups.com>
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)}
> 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. 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. Received on Thu Oct 13 2005 - 05:15:23 CEST