Home > Blockchain >  Find top parent of child, multiple levels
Find top parent of child, multiple levels

Time:12-02

ENTRY TABLE
 __________________
| ID |  PARENT_ID  |
| 1  |    null     |
| 2  |     1       |
| 3  |     2       |
| 4  |    null     |
| 5  |     4       |
| 6  |     5       |
...

I make copies of the entries in some cases and they are conneted by parent ID.

Each entry can have one copy:

THIS WONT HAPPEN
 __________________
| ID |  PARENT_ID  |
| 1  |    null     |
| 2  |     1       |
| 3  |     1       |
...

Sometimes I need to take a copy and query for it's top level parent. I need to find the top parent entries for all the entries I search for.

For example, if I query for the parents of ID 6 and 3, I would get ID 4 and 1. If I query for the parents of ID 5 and 2, I would get ID 4 and 1. But also If I query for ID 5 and 1, it should return ID 4 and 1 because the entry ID 1 is already the top parent itself.

I don't know where to begin since I don't know how to recursively query in such case.

Can anyone point me in the right direction?

I know that the query below will just return the child elemements (ID 6 and 3), but I don't know where to go from here honestly.

I am using OracleSQL by the way.

SELECT * FROM entry WHERE id IN (6, 3);

CodePudding user response:

You can use recursive CTE to walk the graph and find the initial parent. For example:

with
n (starting_id, current_id, parent_id, v) as (
  select id, id, parent_id, 0 from entry where id in (6, 3)
 union all
  select n.starting_id, e.id, e.parent_id, n.v - 1
  from n
  join entry e on e.id = n.parent_id
)
select starting_id, current_id as initial_id
from (
  select n.*, row_number() over(partition by starting_id order by v) as rn
  from n
) x
where rn = 1

Result:

 STARTING_ID  INITIAL_ID 
 ------------ ----------
 3            1         
 6            4         

See running example at db<>fiddle.

CodePudding user response:

You can use a hierarchical query and CONNECT_BY_ROOT.

Either starting at the root of the hierarchy and working down:

SELECT id,
       CONNECT_BY_ROOT(id) AS root_id
FROM   entry
WHERE  id IN (6, 3)
START WITH parent_id IS NULL
CONNECT BY PRIOR id = parent_id;

Or, from the entry back up to the root:

SELECT CONNECT_BY_ROOT(id) AS id,
       id AS root_id
FROM   entry
WHERE  parent_id IS NULL
START WITH id IN (6, 3)
CONNECT BY PRIOR parent_id = id;

Which, for the sample data:

CREATE TABLE entry( id, parent_id ) AS
SELECT 1, NULL FROM DUAL UNION ALL
SELECT 2, 1 FROM DUAL UNION ALL
SELECT 3, 2 FROM DUAL UNION ALL
SELECT 4, NULL FROM DUAL UNION ALL
SELECT 5, 4 FROM DUAL UNION ALL
SELECT 6, 5 FROM DUAL UNION ALL
SELECT 7, 6 FROM DUAL

Both output:

ID ROOT_ID
3 1
6 4

db<>fiddle here

  • Related