Find oldest ancestor for each entry in a SQL table-CodePudding

I have a SQL table where the rows in the table have a parent-child relationship with each other. I would like to write a recursive SQL query to find the oldest ancestor for each of these rows (or the row itself if it has no parent). So in other words, if my table looks like this:

Child	Parent
1	null
2	1
3	2
4	null
5	4
6	null
7	null
8	3
9	5

Then my final output should be:

Child	OldestAncestor
1	1
2	1
3	1
4	4
5	4
6	6
7	7
8	1
9	4

Can this be done? I know how to use recursive SQL to find an individual parent-child relationship, I'm just not sure if that can be taken a step further to find the parent's parent, etc.

CodePudding user response：

Update - I was able to figure out a solution based on this article:https://www.webcodeexpert.com/2020/04/sql-server-cte-recursive-query-to-get.html

WITH parentChild(Child, Parent) AS
(
    SELECT 1, null UNION ALL
    SELECT 2, 1 UNION ALL
    SELECT 3, 2 UNION ALL
    SELECT 4, null UNION ALL
    SELECT 5, 4 UNION ALL
    SELECT 6, null UNION ALL
    SELECT 7, null UNION ALL
    SELECT 8, 3 UNION ALL
    SELECT 9, 5
),
MyCTE AS
(
    SELECT pc.Child, pc.Child AS 'OldestAncestor'
    FROM parentChild pc
    WHERE pc.Parent IS NULL

    UNION ALL

    SELECT pc2.Child, m.OldestAncestor AS 'OldestAncestor'
    FROM parentChild pc2
    INNER JOIN MyCTE m ON pc2.Parent = m.Child
)
SELECT * FROM MyCTE ORDER BY Child

CodePudding user response：

In Oracle, you can use:

SELECT child,
       CONNECT_BY_ROOT child AS oldest_ancestor
FROM   table_name
START WITH parent IS NULL
CONNECT BY parent = PRIOR child
ORDER BY child;

or a recursive sub-query factoring clause (WITH clause):

WITH rsqfc (child, oldest_ancestor) AS (
  SELECT child, child
  FROM   table_name
  WHERE  parent IS NULL
UNION ALL
  SELECT t.child, r.oldest_ancestor
  FROM   rsqfc r
         INNER JOIN table_name t
         ON (t.parent = r.child)
)
SELECT *
FROM   rsqfc
ORDER BY child;

Which, for the sample data:

CREATE TABLE table_name (Child, Parent) 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, null FROM DUAL UNION ALL
SELECT 7, null FROM DUAL UNION ALL
SELECT 8, 3    FROM DUAL UNION ALL
SELECT 9, 5    FROM DUAL;

Both output:

CHILD OLDEST_ANCESTOR

1 1

2 1

3 1

4 4

5 4

6 6

7 7

8 1

9 4

db<>fiddle here

CodePudding user response：

You can use a recursive CTE to find the paths from the parents to the leaf nodes, and then join the CTE back onto the original table:

with recursive cte(n1, n2) as (
    select child, child from tbl where parent is null
    union all
    select c.n1, t.child from cte c join tbl t on c.n2 = t.parent
)
select t1.child, c.n1 from tbl t1 join cte c on t1.child = c.n2;