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.

Update 2024

With jsonb and jsonb_object_agg(), producing a denser result where each edge is one key/value pair.

jsonb removes duplicate key values out of the box. No DISTINCT required:

SELECT jsonb_object_agg(node, parent) AS edges
FROM  (
   SELECT 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;

jsonb_object_agg_strict() also removes objects with null values, effectively trimming a dangling edge at the root:

SELECT jsonb_object_agg_strict(node, parent) AS edges
FROM  (
   -- same as above
   ) sub;

Original answer 2014

Legacy json solution. First remove duplicate edges, as json keeps all objects, even duplicate keys.

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 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;

fiddle
_{Old sqlfiddle}