PostgreSQL - Generate JSON-tree-object from table containing paths

Question

Given a table that contains paths/nodes of a tree structure which is unknown:

| id | path_id | node
| 1  | p1      | n1
| 2  | p1      | n2
| 3  | p1      | n3
| 4  | p2      | n1
| 5  | p2      | n2
| 6  | p2      | n4

The corresponding tree structure would be

    n1 
   /  
  n2
 /  \
n3   n4

Is it possible to generate a JSON-object for this tree using SQL and PostgreSQL-functions?

Answer 1

Seems like you have a list of paths, where parts overlap.
First remove duplicate edges:

SELECT DISTINCT  node
               , lag(node) OVER (PARTITION BY path_id ORDER BY id) AS parent
FROM   tbl
ORDER  BY parent NULLS FIRST, node;  -- ORDER BY optional

parent is NULL for the root node. You may want to remove this "non-edge" from the result.
Then, to generate a JSON-object for this tree you could use json_agg():

SELECT json_agg(sub) AS array_of_edges
FROM  (
   SELECT DISTINCT node
                 , lag(node) OVER (PARTITION BY path_id ORDER BY id) AS parent
   FROM   tbl
   ORDER  BY parent NULLS FIRST, node  -- ORDER BY optional
   ) sub;

SQL Fiddle.