CODEWITHSUNDEEP
sqlpostgresqlcommon-table-expressionhierarchical-datarecursive-query
Shalev Sror
Shalev Sror

Reputation: 69

select node-ancestors recursively

Suppose I have the following tree:

tree-visual

The table that stores the data is presented below accordingly:

node_id parent_id
A null
B A
C A
D B

I want to select all node ancestors for every node in the tree.

the root node has no ancestors so it'll not show up.

Example of what I want -

node_id ancestor_id
B A
C A
D B
D A

Glad for any help :)

I am working with pgsql.

Upvotes: 0

Views: 53

Answers (1)

Edouard
Edouard

Reputation: 7065

You need a recursive query :

WITH RECURSIVE cte AS (
SELECT node_id, parent_id AS ancestor_id
  FROM your_table
 WHERE parent_id is not null
UNION ALL
SELECT children.node_id, parent.parent_id
  FROM cte AS chidren
 INNER JOIN your_table AS parent
    ON parent.node_id = children.parent_id
)
SELECT *
  FROM cte ;

This query may not stop if you have a loop in the node_id => paren_id tree. In order to avoid infinite loops in the recursive query, you have to add a test :

WITH RECURSIVE cte AS (
SELECT node_id, parent_id AS ancestor_id, array[node_id, parent_id] AS check
  FROM your_table
 WHERE parent_id is not null
UNION ALL
SELECT children.node_id, parent.parent_id, children.check || parent.parent_id
  FROM cte AS chidren
 INNER JOIN your_table AS parent
    ON parent.node_id = children.parent_id
 WHERE NOT children.check @> array[parent.parent_id]  -- this condition will avoid infinite loops
)
SELECT node_id, ancestor_id
  FROM cte ;

Upvotes: 1

Related Questions