Find all nodes in an adjacency list model with oracle connect by

Question

Given the following model:

create table child_parent (
  child number(3),
  parent number(3)
);

Given the following data:

insert into child_parent values(2,1);
insert into child_parent values(3,1);
insert into child_parent values(4,2);
insert into child_parent values(5,2);
insert into child_parent values(6,3);

results in the following tree:

        1
       / \
      2   3
     / \   \
    4   5   6

Now i can find the parents of 5 like this:

SELECT parent FROM child_parent START WITH  child = 5 
              CONNECT BY NOCYCLE PRIOR parent = child;

But how can I get all the nodes (1,2,3,4,5,6) starting from 5?

Jeanette

Answer 1

Oracle's CONNECT BY syntax is intended for traversing hierarchical data: it is uni-directional so not a suitable for representing a graph, which requires bi-directionality. There's no way to go 2 -> 1 -> 3 in one query, which is what you need to do to get all the nodes starting from 5.

---

A long timne ago I answered a question on flattening nodes in a hierarchy (AKA transitive closure) i.e. if 1->2->3 is true, `1->3' is true as well. It links to a paper which demonstrates a PL/SQL solution to generate all the edges and store them in a table. A similar solution could be used in this case. But obviously it is only practical if the nodes in the graph don't chnage very often. So perhaps it will only be of limited use. Anyway, find out more.

Sap

Answer 2

Finally I came up with a solution similar like this:

  SELECT child FROM child_parent START WITH parent =
   (
    SELECT DISTINCT parent FROM   
     (
      SELECT parent
      FROM child_parent
      WHERE CONNECT_BY_ISLEAF = 1
        START WITH child = 5
        CONNECT BY PRIOR parent = child
      UNION
      SELECT parent
      FROM child_parent
      WHERE parent = 5
     ) 
   )
   CONNECT BY NOCYCLE PRIOR child = parent
   UNION
   SELECT DISTINCT parent FROM   
   (
    SELECT parent
    FROM child_parent
    WHERE CONNECT_BY_ISLEAF = 1
      START WITH child = 5
      CONNECT BY PRIOR parent = child
    UNION
    SELECT parent
    FROM child_parent
    WHERE parent = 5
   );

It works with all nodes for the provided example. But if one of the leafs has a second parent and the starting point is above this node or in a different branch it don't work.

But for me it is good enough.

A solution to get all nodes in graph could be: implement the opposite of the query above (from top to bottom) and then execute them (bottom to top, top to bottom) vice versa until you find no more new nodes. This would need PL/SQL and I also don't know about the performance.

Jeanette

Answer 3

Using 5 you cannot traverse whole tree and it's going to very very tricky even if you can achieve it as it is a leaf element.

Try below query, it will traverse whole tree but you will have to start from root instead of leaf:

select * from (
SELECT child FROM child_parent START WITH  parent = 1 
              CONNECT BY NOCYCLE PRIOR child = parent
union
select 1 from dual)
order by child;

you can replace "1" with any other root element, all elements below that root will be printed including that root.

Penna