Subtree selection with connect by-CodePudding

I have some hierarchic data, similar to this diagram

this is done for example in a table with a parent and child id

link_table
--------------
parent_id
child_id

for simplicity, the id's (sort of) from above would be like this:

parent_id    child_id
---------------------
1            11
1            12
12           121
121          1211
12           122
122          1221
122          1222
2            21

my challenge is this:

Given a selected node (122) - I need to return the tree that contains the (non cycling) root path (1 and 12 - but not 11), the selected item (122) and all further children (1221, 1222) and nothing from other trees (the original parent is a null for all trees)

I can write a normal connect by to start with the selected id and get the 'child tree'

and I can write a connect by to go upwards to the connect_by_root.

my question is: how do I combine these into one statement that returns a nice LEVEL and the nodes in the highlighted tree?

CodePudding user response：

My suggestion would be to parse the tree using two recursive CTE :

-A first recursive CTE to parse the tree bottom up to find all ancestors

-A second recursive CTE to parse the tree top down to find all descendants

After that, you can simply union those two CTEs to get desired result.

For instance :

WITH 
ancestor(parent_id,child_id) AS (
  SELECT parent_id,child_id 
  FROM link_table
  WHERE child_id = 122
  
  UNION ALL
  
  SELECT link_table.parent_id, link_table.child_id
  FROM link_table
  INNER JOIN ancestor ON
    ancestor.parent_id = link_table.child_id
),
descendant(parent_id,child_id) AS (
  SELECT parent_id,child_id 
  FROM link_table
  WHERE parent_id = 122
  
  UNION ALL
  
  SELECT link_table.parent_id, link_table.child_id
  FROM link_table
  INNER JOIN descendant ON
    descendant.child_id = link_table.parent_id
)


SELECT parent_id,child_id FROM ancestor
UNION ALL
SELECT parent_id,child_id FROM descendant

Try it online

Edit :

I noticed you also needed the node level within the hierarchy. I edited my query accordingly :

WITH 
/*Find all ancestors from the node 122. 
The node level is 0 for the node 122, and decreased by one for each parent*/
ancestor(parent_id, child_id, node_level) AS (
  SELECT parent_id,child_id, 0
  FROM link_table
  WHERE child_id = 122
  
  UNION ALL
  
  SELECT link_table.parent_id, link_table.child_id, ancestor.node_level -1
  FROM link_table
  INNER JOIN ancestor ON
    ancestor.parent_id = link_table.child_id
),
/*Find all descendant from the node 122. 
The node level is increased by one for each level of descendant*/
descendant(parent_id,child_id,node_level) AS (
  SELECT parent_id,child_id, 1 
  FROM link_table
  WHERE parent_id = 122
  
  UNION ALL
  
  SELECT link_table.parent_id, link_table.child_id, descendant.node_level  1
  FROM link_table
  INNER JOIN descendant ON
    descendant.child_id = link_table.parent_id
),
/*the following query allows us to find the whole branch of the hierarchy
However, the node level is negative for the parent*/
hierarchy_branch (parent_id, child_id, node_level) AS (
SELECT parent_id,child_id,node_level FROM ancestor
  
  UNION ALL
  
  SELECT parent_id,child_id,node_level FROM descendant
)
/*Using the previous query, we can now calculate the corrected node level by 
substracting the node_level from the root from each node_level.

The root_node level is found using min within a window function :
   MIN(node_level) OVER()

the uncorrected node_level is still here for information
*/
SELECT parent_id,child_id, node_level, node_level - MIN(node_level) OVER() 1 corrected_node_level   
FROM hierarchy_branch
ORDER by corrected_node_level

Try it online

CodePudding user response：

You can use a hierarchical query:

SELECT parent_id AS id, depth
FROM   (
  SELECT parent_id, 1-LEVEL AS depth
  FROM   table_name
  START WITH child_id = 122
  CONNECT BY
       PRIOR parent_id = child_id
  ORDER BY LEVEL DESC
)
UNION ALL
SELECT child_id, depth
FROM   (
  SELECT child_id, LEVEL AS depth
  FROM   table_name
  START WITH child_id = 122
  CONNECT BY
         parent_id = PRIOR child_id
  ORDER SIBLINGS BY child_id
);

Which, for the sample data:

CREATE TABLE table_name (parent_id, child_id) AS
SELECT 1,   11   FROM DUAL UNION ALL
SELECT 1,   12   FROM DUAL UNION ALL
SELECT 12,  121  FROM DUAL UNION ALL
SELECT 121, 1211 FROM DUAL UNION ALL
SELECT 12,  122  FROM DUAL UNION ALL
SELECT 122, 1221 FROM DUAL UNION ALL
SELECT 122, 1222 FROM DUAL UNION ALL
SELECT 2,   21   FROM DUAL;

Outputs:

ID DEPTH

1 -1

12 0

122 1

1221 2

1222 2

ID	DEPTH
1	-1
12	0
122	1
1221	2
1222	2

db<>fiddle here