Generate JSON-tree-object from table containing paths

json, postgresql, sql, tree

Solution

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

Problem

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?

Original source