Oracle: Numbered groups in a hierarchical query

Question

In my Oracle DB, I have a table deifining a hierarchy of predecessors/successors, which can both branch and loop. I have attached an SQL fiddle to demonstrate how the table works. My intention is to assign each isolated tree it's own number. See picture below for explanation of the desired result (please note that in this picture the members are named a,b,c,d... whereas in the fiddle attached, they are numbered 1,2,3,4...):

http://sqlfiddle.com/#!4/4c887d/4/0

I haven't yet figured out how to build such a query and at this very moment I'm pretty much desperate. Any help, or even a pointer to the solution - any kind of input - will be appreciated.

Thank you all in advance.

Answer 1

Those aren't hierarchies; they are directed graphs. You can still use CONNECT BY in Oracle to work with them, but without a root node to START WITH, performance might be a problem if your data set is large.

Anyway, what you need to do is CONNECT BY NOCYCLE without a START WITH. That will compute a tree starting from each separate node. Then, get the CONNECT_BY_ROOT for each node and take the MIN() for each distinct node value.

Here is a working example, with data. It's more complicated than it needs to be because there is nowhere to get a complete list of all the nodes, so you have to split each vertex into two rows (one have the from_node and one have the to_node) to make sure you're including all of them.

CREATE TABLE tbl_tst ( from_node VARCHAR2(1), to_node VARCHAR2(1) );

INSERT INTO tbl_tst VALUES ( 'a', 'b');
INSERT INTO tbl_tst VALUES ( 'b', 'c');
INSERT INTO tbl_tst VALUES ( 'b', 'd');
INSERT INTO tbl_tst VALUES ( 'd', 'a');
INSERT INTO tbl_tst VALUES ( 'd', 'e');

INSERT INTO tbl_tst VALUES ( 'f', 'g');
INSERT INTO tbl_tst VALUES ( 'g', 'h');
INSERT INTO tbl_tst VALUES ( 'h', 'f');

INSERT INTO tbl_tst VALUES ( 'i', 'j');

COMMIT;


WITH groups AS (
SELECT DISTINCT 
       tt.from_node, 
       tt.to_node, 
       MIN(CONNECT_BY_ROOT(from_node)) 
             OVER ( PARTITION BY tt.from_node) group_min
FROM   tbl_tst tt
CONNECT BY NOCYCLE from_node = PRIOR to_node
              OR   to_node = PRIOR from_node
)
SELECT DENSE_RANK() OVER ( ORDER BY group_min ) group_number,
       DECODE(splitter.rn,1,groups.from_node,2,groups.to_node) node       
FROM groups 
CROSS JOIN ( SELECT rownum rn FROM dual CONNECT BY rownum <= 2 ) splitter
GROUP BY DECODE(splitter.rn,1,groups.from_node,2,groups.to_node),
         group_min
ORDER BY group_min, node;

+--------------+------+
| GROUP_NUMBER | NODE |
+--------------+------+
|            1 | a    |
|            1 | b    |
|            1 | c    |
|            1 | d    |
|            1 | e    |
|            2 | f    |
|            2 | g    |
|            2 | h    |
|            3 | i    |
|            3 | j    |
+--------------+------+

Answer 2

Disclaimer: This solution works in PostgreSQL, not in Oracle as requested.

The query below demonstrates a strategy to solve the problem of assigning unique serial numbers to each subgraph.

Note: I tried to write the query for Oracle but it seems the XMLTable() function is buggy. Maybe you can adapt it to Oracle if you find a workaround (I gave up).

with recursive
n (root_id, pred, succ, s) as (
  select pred, pred, succ, '/' || least(pred, succ) || '/' || greatest(pred, succ) || '/' from t
 union all
  select n.root_id, t.pred, t.succ, (
    select '/' || string_agg(vl, '/') || '/' from (
      select unnest(string_to_array(substring(n.s from 2 for length(n.s) - 2), '/')) as vl
      union all select (case when t.pred = n.pred or t.pred = n.succ then t.succ else t.pred end)
      order by vl
      ) y
    )
  from n
  join t on not (n.pred = t.pred and n.succ = t.succ) and (n.pred = t.pred or n.pred = t.succ or n.succ = t.pred or n.succ = t.succ)
            and not n.s ~ ('/' || case when t.pred = n.pred or t.pred = n.succ then t.succ else t.pred end || '/')
),
s as (
  select distinct s from (
    select distinct on (root_id) root_id, s from n group by root_id, s order by root_id, length(s) desc
  ) j
)
select * from (
  select
    unnest(string_to_array(substring(s from 2 for length(s) - 2), '/')) as node,
    row_number() over(order by s) as g 
  from s order by s
) z
order by g, node;

Result:

node  g
----  -
a     1
b     1
c     1
d     1
e     1
f     2
g     2
h     2
i     3
j     3

See running example at DB Fiddle.

Answer 3

As I understood in other words, for each root_node you need a group number assigned to it. To find the root node we can use connect_by_root and then we can use dense_rank to give it a number.

So far I got this, could you check sqlfiddle

SELECT predecessor
      ,successor
      ,sys_connect_by_path(successor
                          ,'/') AS hierarchy_path
      ,LEVEL node_level
      ,dense_rank() over(ORDER BY connect_by_root successor) group_number
FROM   tbl_tst
CONNECT BY nocycle PRIOR predecessor = successor;