Re: transitive closure of a graph

From: Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com>
Date: 12 Oct 2005 20:15:23 -0700
Message-ID: <1129173322.971887.279870@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)}

Glad you made that far.

> 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 Wed Oct 12 2005 - 22:15:23 CDT