Graph Reachability view?

I need to know if transitive closure AKA graph reachability is doable in Oracle8i, or 9i.

Suppose I have a two column table, Edge:

create table Edge
 (startpt VARCHAR2(20),
  endpt VARCHAR2(20));

startpt and endpt each contain names of nodes in a graph. So Edge might look like this:

startpt endpt
------- -----

A       B
A       C
B       D
C       D
D       E
D       F

(Sketch this out and you get something that looks sorta like a fish.)

Now I want to create a view, Reachable, that shows all paths in the graph. That is, (X Y) is a row in Reachable if you can use X as a startpt and go from there to an endpt in Edge, then use that endpt as the next startpt, and so on until you reach Y. Using the Edge table above, Reachable would look like this:

startpt endpt
------- -----

A       B
A       C
B       D
C       D
D       E
D       F
A       D
A       E
A       F
B       E
B       F
C       E
C       F

(I hope I got them all...)

This is recursive, and SQL is unable to do recursion. Oracle, however, has CONNECT BY PRIOR. Unfortunately, I can't quite get it to do what I want, either. I can get everything A can reach:

select endpt from Edge
  start with startpt='A'
  connect by prior endpt=startpt;

Or everything that can reach A:

select startpt from Edge
  start with endpt='A'
  connect by prior startpt=endpt;

But I can't get both at the same time. Is this possible in 8i or 9i without stored procedures and/or triggers? (I currently have a scheme where Reachable is a table maintained by triggers that watch Edge.) Received on Fri Jul 27 2001 - 17:04:46 CDT