Oracle DB Order Tree Siblings By Sibling Linked List

Question

I intend to store tree objects in a database table. This is my schema:

CREATE TABLE Nodes (
  ID number(11) NOT NULL,
  dataID number(11) NOT NULL,
  parentNode number(11),
  siblingNode number(11),
);

Suppose I have three trees A,B,C whose root nodes have NULL as a parent. I would like to select all records from the node table grouped by which tree they belong to, ordered like a depth first search with siblings ordered by their respective linked lists. For example, if D,E, and F were children of node A, and the intended order was F->E->D then F would have siblingNode NULL, E would have F's ID as siblingNode and D would have E's ID as siblingNode.

I have accomplished so far a usual CONNECT BY query, and I see that there is a ORDER SIBLINGS BY clause, but this only works by sorting ascending or descending values, not with a linked list. My query thus far simply sorts on the ID and does not take into consideration the sibling linkage (and works provided the order of entry of siblings can be guaranteed).

SELECT ID, connect_by_root(ID) root
FROM Nodes
START WITH parentNode IS NULL
CONNECT BY PRIOR ID = parentNode
ORDER SIBLINGS BY ID ASC;

Ultimately I would like to use LISTAGG to make a string from data function to create a view on my trees. This view would have one row per tree (A,B,C) that contains a string representing the tree in polish notation. So far I have:

SELECT DISTINCT connect_by_root(ID) root, LISTAGG(dataString(ID), ' ') WITHIN GROUP (ORDER BY ID ASC) OVER (PARTITION BY connect_by_root(ID)) polish
FROM Nodes
START WITH parentNode IS NULL
CONNECT BY PRIOR ID = parentNode
ORDER SIBLINGS BY ID ASC;

I am new to Oracle DB, and don't know if there is a better way to do any of the above. I welcome any comments, and particularly would like to know how to order siblings by their linkage.

Sample Data:

ID: 1; dataID=>'-'; parentNode: null; siblingNode: null;
ID: 2; dataID=>'1'; parentNode: 1; siblingNode: 3;
ID: 3; dataID=>'6'; parentNode: 1; siblingNode: null;
ID: 4; dataID=>'*'; parentNode: null; siblingNode: null;
ID: 5; dataID=>'8'; parentNode: 4; siblingNode: null;
ID: 6; dataID=>'8'; parentNode: 4; siblingNode: 5;

Desired Output:

ID: 1; POLISH: '+ 6 1'
ID: 4; POLISH: '* 8 8'

The problem with ORDER SIBLINGS BY ID ASC is the first output would return '- 1 6' which is different from '- 6 1'.

I've created a fiddle with the sample data demonstrating the problem. Also, for some reason it won't let me use the ORDER SIBLINGS BY clause... http://sqlfiddle.com/#!4/6ec46/4

Answer 1

I've managed to produce a query that gives me my expected results by joining to a second query connected by siblingNode and sorting by the sibling LEVEL:

SELECT DISTINCT wut.root,
   LISTAGG(wut.data, ' ')
    WITHIN GROUP (ORDER BY wut.polishOrder)
    OVER (PARTITION BY wut.root) polish
FROM        
( SELECT connect_by_root(n.ID) root, data, ROWNUM polishOrder
 FROM Nodes n
 JOIN
 (SELECT m.ID, LEVEL l
  FROM Nodes m
  START WITH m.siblingNode IS NULL
  CONNECT BY PRIOR m.ID = m.siblingNode) mm
 ON n.ID = mm.ID
     START WITH n.parentNode IS NULL
     CONNECT BY PRIOR n.ID = n.parentNode
     ORDER SIBLINGS BY mm.l
) wut

http://sqlfiddle.com/#!4/94facf/25

Answer 2

If I am understanding your question correctly you would like a Hierarchical Query to return Polish notation (the leaf node) with it's corresponding nodes -> root node path. You will then use this query to supply a view of the Polish notation relationships.

Instead of the LISTAGG function, can you use the SYS_CONNECT_BY_PATH and use a space, or any other valid VARCHAR, as the separator? The query would look something like the following:

SELECT DISTINCT ID AS root, SYS_CONNECT_BY_PATH(dataString(ID), ' ') POLISH
FROM Nodes
START WITH parentNode IS NULL
CONNECT BY PRIOR ID = parentNode
ORDER SIBLINGS BY ID ASC;

Let me know if I have misunderstood your question and I will update my answer.