Producing a path from each node to the root of a tree represented as edges in a table

hierarchical-data, hierarchy, postgresql, recursive-query, tree

Solution

You may want to examine the `ltree` contrib module if you're doing much of this sort of thing.

Here's a CTE that'll do the job, see SQLFiddle:

WITH RECURSIVE x(id,parent_fk,parents,last_id, depth) AS (
  SELECT id, parent_fk, ARRAY[id] AS parents, id AS last_id, 0 AS depth FROM table1
  UNION ALL
  SELECT x.id, x.parent_fk, parents||t1.parent_fk, t1.parent_fk AS last_id, x.depth + 1
  FROM x 
    INNER JOIN table1 t1 
    ON (last_id= t1.id)
  WHERE t1.parent_fk IS NOT NULL
)
SELECT id, parent_fk, array_to_string(parents,';')
FROM x 
WHERE depth = (SELECT max(sq.depth) FROM x sq WHERE sq.id = x.id);

Your table is a representation of a directed graph as a set of edges. You've specified that the graph is a tree, meaning that it's acyclic. What you want to do is to find the path from each node (inner or leaf) on the tree to the root and represent that as a semi-colon separated string.

Problem

I have the following table on a PostgreSQL database (parent_fk is a foreign key that references the same table): ``` id | parent_fk 72 | 342 | 72 583 | 342 ``` I want to query this table and discover the path of each element to the ultimate parent via intermediate parent/child relationships. For example, I would like to obtain the following as the answer to an SQL query: ``` id | parent_fk | path 72 | | 72 342 | 72 | 72;342 583 | 342 | 72;342;583 ``` I read about CTE (Common Table Expressions) and recursive queries on PostgreSQL but I couldn't solve this problem by myself yet. Any ideas? Thanks in advance.

Original source