Re: transitive closure of a graph

Mikito Harakiri wrote:
> Transitive closure (TC) of a graph is
>
> with TransClosedEdges (tail, head) as
> ( select tail, head from Edges
> union all
> select e.tail, ee.head from Edges e, TransClosedEdges ee
> where e.head = ee.tail
> )
> select distinct * from TransClosedEdges
>
> except that this query might never terminate. I was surprised to learn
> from Graeme Birchall's DB2 cookbook that there is no really
> satisfactory solution to this problem. Graeme suggests building a path
> and searching for repeated node entry in the path. Is there a more
> satisfactory approach that doesn't require string parsing? I understand
> that the problem of finding loops is undecideable in general case, but,
> cmon, we are taking about very narrowly scoped transitive closure
> problem here.
>
> BTW, TC with goofy oracle syntax is just 3 lines
>
> select connect_by_root(tail), tail
> from Edges
> connect by nocycle prior head = tail
>
> with cycles being automatically taken care of.
>

I wonder if the non-termination problem is a result of the sql syntax rather than the basic relationships.

I don't know sql well enough to express an alternative solution but it seems to me that the basic 'parts explosion' problem, if we ignore part counts and part levels, doesn't require recursion.

Ie., if the starting table can be viewed as a set of pairs of nodes then each row represents an arc between adjacent nodes. Say this this table's columns are named A and B, where A and B stand, respectively, say for 'part' and 'sub-part'. Ignoring issues of optimization we could take the product of this table and a copy of itself where A and B have been renamed to C and D. This table might be theoretically big but it would be finite. It would contain a row for every possible pair of arcs in the graph. I would think we need only to select pairs of arcs that are connected, either because the original table says they are or because the tail of the LHS arc matches the head of the RHS arc. I'd think this would give all sub-parts of every part because there could be no possible arc pair that wasn't in the product.

The simple closure of the original table would be the union of the rows where B = C and the rows where {B,C} match the original {A,B} rows with the original column names now being represented by the A and D columns.   That whole mess unioned with the original table would give all the derived pairs.

That's how I worked some small examples out on paper, even ones that had loops and multiple graphs. I imagine if filtering was applied as the product was built, then a large cross-product intermediate result could be avoided. Also, simple (uncompounded) part counts would be possible, but not levels as far as I can see. Maybe compound counts and levels could be produced from the simple closure, after the fact.

cheers,
paul c. Received on Wed Oct 12 2005 - 19:46:26 CEST