SQL Recursive Query That Gets All Ancestors of an Item

SQL recursive query that gets all ancestors of an item

with name_tree as (
   select id, parent_id, name
   from the_unknown_table
   where id = 1 -- this is the starting point you want in your recursion
   union all
   select c.id, c.parent_id, c.name
   from the_unknown_table c
     join name_tree p on p.parent_id = c.id  -- this is the recursion
) 
select *
from name_tree
where id <> 1; -- exclude the starting point from the overall result

SQLFiddle: http://sqlfiddle.com/#!3/87d0c/1

Recursive CTE to find all ancestors OF ALL ITEMS

Assuming I understand you right, it should be as simple as recursing backwards from the leaf nodes (which is easy since the table Items is storing only the leaf nodes):

;with AncestryTree as (
  select Item, Parent
  from Items
  where Parent is not null
  union all
  select Items.Item, t.Parent  
  from AncestryTree t 
  join Items on t.Item = Items.Parent
 )
select * from AncestryTree
order by Item, Parent

SQL Fiddle demo

MySQL - Recursively list all parents and ancestors of all items in table

If you are running MySQL 8.0, this is best solved with a recursive query:

with recursive cte as (
    select id, parent_id, 1 lvl from mytable
    union all
    select c.id, t.parent_id, lvl + 1
    from cte c
    inner join mytable t on t.id = c.parent_id
)
select id, group_concat(parent_id order by lvl) all_parents
from cte
group by id

Demo on DB Fiddle:

id | all_parents
-: | :----------
 1 | 0          
 2 | 0          
 3 | 0          
17 | 3,0        
31 | 17,3,0     

Recursively find all ancestors given the child

This is more or less what you want:

-- CTE to prepare hierarchical result set
;WITH #results AS
(
    SELECT  id, 
            parentid 
    FROM    [table] 
    WHERE   id = @childId
    UNION ALL
    SELECT  t.id, 
            t.parentid 
    FROM    [table] t
            INNER JOIN #results r ON r.parentid = t.id
)
SELECT  *
FROM    #results;

Reference:

• CTE: Common Table Expression

Working example:

-- create table with self lookup (parent id)
CREATE TABLE #tmp (id INT, parentid INT);

-- insert some test data
INSERT INTO #tmp (id, parentid) 
SELECT 1,0 UNION ALL SELECT 2,1 UNION ALL SELECT 3,2
UNION ALL SELECT 4,0 UNION ALL SELECT 5,3;

-- prepare the child item to look up
DECLARE @childId INT;
SET @childId = 5;

-- build the CTE
WITH #results AS
(
    SELECT  id, 
            parentid 
    FROM    #tmp 
    WHERE id = @childId
    UNION ALL
    SELECT  t.id, 
            t.parentid 
    FROM    #tmp t
            INNER JOIN #results r ON r.parentid = t.id
)

-- output the results
SELECT  * 
FROM    #results 
WHERE   id != @childId 
ORDER BY id;

-- cleanup
DROP TABLE #tmp;

Output:

1 | 0

2 | 1

3 | 2

Get all ancestors of a child in postgres recursive query

A RECURSIVE CTE is what you're looking for. It might look confusing at the first glance, but after a little practice it becomes self-explanatory. In the end, it is just a UNION with slightly different queries:

WITH RECURSIVE get_ancestor(child,parent,cost) AS (
  SELECT r.user_id,r.parent_id,c.cost FROM user_relation r
  JOIN product_cost c ON c.user_id = r.user_id
  UNION 
  SELECT g.child,g.parent,c.cost FROM get_ancestor g
  JOIN user_relation r ON r.user_id = g.child
  JOIN product_cost c ON c.user_id = r.user_id 
)
SELECT * FROM get_ancestor;

Demo: SQL Fiddle

The Recursive CTE to query all ancestors of a Parent-Child table is slow

Well. It turns out the reason for the slowness, and the fix are far more interesting than anticipated.

Sql server optimizes the queries based on their definition and not by what semantic meaning they might have. The view in question starts with all Categories and adds new rows by finding elements from the CTE itself and their children. Now the way to find all rows in which some row has appeared as a child, you need to calculate the whole query and then filter it out. Only the human reader understands that the query calculates all the descendants of any Category, which of course also has all Ancestors of any Category. Then you know you can start from bottom and find parents recursively. This is not apparent from the query definition, only from its semantic meaning.

Rewriting the view as follows will make it fast:

Create View Ancestors
as
with A(Id, ParentId) as 
(
    select Id, Id from Categories 
    union all
    select p.Id, e.ParentId from Categories e 
    join A p on e.Id = p.ParentId
)
select * from A

This view creates almost the same result as the view in question. The only difference is that it also shows null as an ancestor for all Categories, which makes no difference for our usage.

This view starts to build the hierarchy from bottom and goes up, which is compatible with the way we intend to query it.

How to get all parents and ancestors from a MySql table?

In the CTE, you can get all the parents/ancestors by generating all routing table using the recursive call.
The following query filters by TargetItemId after generating table.

with recursive Ancesters as (
  select 1 as Level, ChildItemId as TargetItemId, RowId, ItemId as AncesterId, ChildItemId
  from MyTable
  where ChildItemId is not null
  union all
  select a.Level+1, a.TargetItemId, m.RowId, m.ItemId, m.ChildItemId
  from MyTable m inner join Ancesters a
  on m.ChildItemId = a.AncesterId
)
select distinct AncesterId from Ancesters where TargetItemId=1

You can also filter by ChildItemId in advance .

with recursive Ancesters as (
  select 1 as Level, ChildItemId as TargetItemId, RowId, ItemId as AncesterId, ChildItemId
  from MyTable
  where ChildItemId=1
  :

Recursive query that returns itself and all of its descendants

WITH    q (LevelId, Description, DescendantId, Descendant_Description) AS
        (
        SELECT  LevelId, Description, LevelId, Description
        FROM    mytable
        UNION ALL
        SELECT  t.LevelId, t.Description, q.DescendantId, q.Descendant_Description
        FROM    q
        JOIN    mytable t
        ON      t.ParentLevelId = q.LevelId
        )
SELECT  *
FROM    q
ORDER BY
        LevelId, DescendantId

Since this query returns all ancestor-descendant pairs in the system (builds a such called transitive closure), all you need to put it the other way round is to swap the fields and change the ordering:

WITH    q (LevelId, Description, DescendantId, Descendant_Description) AS
        (
        SELECT  LevelId, Description, LevelId, Description
        FROM    mytable
        UNION ALL
        SELECT  t.LevelId, t.Description, q.DescendantId, q.Descendant_Description
        FROM    q
        JOIN    mytable t
        ON      t.ParentLevelId = q.LevelId
        )
SELECT  DescendantId AS LevelId, Descendant_Description AS Description,
        LevelId AS DescendantId, Description AS Descendant_Description
FROM    q
ORDER BY
        LevelId, DescendantId

---

Related Topics