Nested join on same table (tree structure)

Question

My date is organized in tree structure.

The following applies (Oracle SQL syntax):

CREATE TABLE TREE
(
  NAME VARCHAR2(20),
  ID NUMBER(10, 0),
  PARENT NUMBER(10, 0)
)
;

INSERT INTO "TREE" (NAME, ID) VALUES ('a', '1');
INSERT INTO "TREE" (NAME, ID, PARENT) VALUES ('a.1', '2', '1');
INSERT INTO "TREE" (NAME, ID, PARENT) VALUES ('a.2', '3', '1');
INSERT INTO "TREE" (NAME, ID, PARENT) VALUES ('a.2.1', '4', '3');
INSERT INTO "TREE" (NAME, ID, PARENT) VALUES ('a.2.2', '5', '3');
INSERT INTO "TREE" (NAME, ID) VALUES ('b', '6');

I would like to return full tree by id, so for query :

select name, id <<<TODO LOGIC>> where id = 1

I would get

|  name  |  id  |
|  a     |  1   |
|  a.1   |  2   |
|  a.2   |  3   |
|  a.2.1 |  4   |
|  a.2.2 |  5   |

for a sub tree I would get:

select name, id <<<TODO LOGIC>> where id = 3

I would get

|  name  |  id  |
|  a.2   |  3   |
|  a.2.1 |  4   |
|  a.2.2 |  5   |

Where as, for flat entry b, it would get

select name, id <<<TODO LOGIC>> where id = 6

I would get

|  name  |  id  |
|  b     |  6   |

It seems that plain left out join queries fails to fulfill this purpose, or am I missing something?

The following query does return the full structure, but when starting to filter with where statements it fails.

select t1.id t1Id, t2.id t2Id, t1.name t1Name, t2.name t2Name from tree t1 left outer join tree t2 on t1.id = t2.parent

Answer 1

You could use union for this, and you need to limit the depth of the tree to make it possible to select it in one query.

SELECT id, name
FROM TREE as node
WHERE 
  node.id = :id
UNION
SELECT child1.id, child1.name
FROM TREE as node
  inner join TREE as child1 on node.id = child1.parent
WHERE 
  node.id = :id
UNION
SELECT child2.id, child2.name
FROM TREE as node
  inner join TREE as child1 on node.id = child1.parent
  inner join TREE as child2 on child1.id = child2.parent
WHERE 
  node.id = :id

The problem here is, SQL is very bad in recursion (while relational structures are actually great in this).

To make it fully dynamic, use a query for each level in the tree, or use a database engine specific SQL extension if there is anything usable.

Answer 2

You can use start with - connect by syntax on Oracle. If I'm not mistaken, it goes like this

select * from Tree t
start with t.ID = 1 connect by prior t.ID = t.Parent

But I have no Oracle to check it right away. Maybe its prior t.Parent = t.ID. Beware that it can be slow sometimes, use with caution.

Alternative is to create table to store all indirect relationship between nodes (not just a-a.1, but also a-a.2.1 and so on). You can fill it using PL/SQL recursive stored procedure. Two ways:

1. Simple way is to make a procedure that will do complete refill of indirect table. You can call it before running reports.

2. If you need instant effects, you should write refill procedure so that it will update indirect relationship just for one record in tree. Then you prohibit direct inserts and updates to Tree and force them to go via stored PL/SQL procedures (like InsertTree/UpdateTree) which in turn will call procedure to update table with indirect relationships.

Answer 3

When you have a tree structure, you likely need a hierarchical query. Here it is:

 select t.*
   from tree t
connect by prior t.id = t.parent
  start with t.id = :id
  order siblings by t.id

See Hierarchical Queries for details.