Re: transitive closure of a graph

Adam Machanic wrote:
> That won't work for the following undirected graph:
>
> E
> / /\ \
> A / \ D
> \ / \ /
> B C
>
> CREATE TABLE Edges (point1 CHAR(1), point2 CHAR(1))
>
> INSERT Edges VALUES ('A', 'A')
> INSERT Edges VALUES ('B', 'B')
> INSERT Edges VALUES ('C', 'C')
> INSERT Edges VALUES ('D', 'D')
> INSERT Edges VALUES ('E', 'E')
> INSERT Edges VALUES ('E', 'A')
> INSERT Edges VALUES ('A', 'E')
> INSERT Edges VALUES ('E', 'D')
> INSERT Edges VALUES ('D', 'E')
> INSERT Edges VALUES ('A', 'B')
> INSERT Edges VALUES ('B', 'A')
> INSERT Edges VALUES ('D', 'C')
> INSERT Edges VALUES ('C', 'D')
> INSERT Edges VALUES ('B', 'E')
> INSERT Edges VALUES ('E', 'B')
> INSERT Edges VALUES ('C', 'E')
> INSERT Edges VALUES ('E', 'C')
>
>
> ... I don't think a solution is possible without string or binary
> manipulation, due to the fact that you only have access to the last anchor
> in the recursive part. If you had access to the entire set of preceding
> rows it might be different...

If I see the problem correctly, here is step-by-step execution

1.
AE, EA, AB, BA, CD, DC, BE, EB, CE, EC -- all included; the other edges in the candidate set
AA, BB, CC, DD, EE -- all excluded as invalidating tail <> head predicate

2. AE+EB=AB, AE+EC=AC, ..., AD, DA, AC, CA, BD, DB, BC, CB, -- all included;
the other edges in the candidate set
AA, BB, CC, DD, EE -- all excluded as invalidating e.head = ee.tail predicate

Including the AB edge twice is a big problem! Apparently, the source of the problem is DB2 and SQLServer 2005 artifact that they allow "union all" only...

P.S. Please don't remove the crossposts, as I might be lazy to look each of the 3 groups for followups. Received on Wed Oct 12 2005 - 05:04:33 CEST