Search code examples
jsonpostgresqlrecursiontree

Get a ordered JSON tree from Postgres

I'm working on a dynamic menu and I need to get a JSON tree with data to build the options in the interface (using CSS, HTML and JS), based on the constraints defined in three tables ( SQL Fiddle still has postgres 9.6, but I'm using postgres 15.0 )

The general idea is to first find the nodes that point to a file (file IS NOT NULL), which are active (status = A) and which are from subsystem 1 (id_subsystem = 1), as long as the user 1 (id_user = 1) is also active (status = A) and has access permission (according to the users_modules table)

With these records, it would be enough to find each parent recursively related and add them to the tree, but keeping the order defined by the group_order field

users

CREATE TABLE users (
  id SMALLINT NOT NULL,
  name CHARACTER VARYING(20) NOT NULL,
  status CHAR(1) NOT NULL
);
id name status
1 John Doe A
2 Jane Doe A
3 Duh Doe I

modules

CREATE TABLE modules (
  id SMALLINT NOT NULL,
  id_subsystem SMALLINT NOT NULL,
  id_master SMALLINT,
  group_order SMALLINT NOT NULL,
  label CHARACTER VARYING(30) NOT NULL,
  file CHARACTER VARYING(30),
  icon CHARACTER VARYING(20),
  status CHAR(1) NOT NULL
);
INSERT INTO
  modules
VALUES
  (1,1,NULL,1,'Dashboard','dashboard','dashboard','A'),
  (2,1,NULL,2,'Registrations',NULL,'cabinet','A'),
  (3,1,2,1,'Customers','customers',NULL,'A'),
  (4,1,2,2,'Suppliers','suppliers',NULL,'A'),
  (5,1,2,3,'Products','products',NULL,'A'),
  (6,1,2,4,'Staff',NULL,NULL,'A'),
  (7,1,6,1,'Countries','countries',NULL,'A'),
  (8,1,6,2,'States','states',NULL,'A'),
  (9,1,6,3,'Cities','cities',NULL,'A'),
  (10,1,6,4,'Means of contacts',NULL,NULL,'A'),
  (11,1,10,1,'Electronic contacts','electronic_contacts',NULL,'A'),
  (12,1,10,2,'Phone contacts','phone_contacts',NULL,'A'),
  (13,1,10,3,'Deprecated contacts','deprecated_contacts',NULL,'I'),
  (14,1,NULL,3,'Settings','settings','sliders','A'),
  (15,2,NULL,1,'Dashboard','dashboard','dashboard','A'),
  (16,2,NULL,2,'Financial',NULL,'cash','A'),
  (17,2,16,1,'Bills to pay','bills_to_pay',NULL,'A'),
  (18,2,16,2,'Bills to receive','bills_to_receive',NULL,'A');
id id_subsystem id_master order label file icon status
1 1 NULL 1 Dashboard dashboard dashboard A
2 1 NULL 2 Registrations NULL cabinet A
3 1 2 1 Customers customers NULL A
4 1 2 2 Suppliers suppliers NULL A
5 1 2 3 Products products NULL A
6 1 2 4 Staff NULL NULL A
7 1 6 1 Countries countries NULL A
8 1 6 2 States states NULL A
9 1 6 3 Cities cities NULL A
10 1 6 4 Means of contacts NULL NULL A
11 1 10 1 Electronic contacts electronic_contacts NULL A
12 1 10 2 Phone contacts phone_contacts NULL A
13 1 10 3 Deprecated contacts deprecated_contacts NULL I
14 1 NULL 3 Settings settings sliders A
15 2 NULL 1 Dashboard dashboard dashboard A
16 2 NULL 2 Financial NULL cash A
17 2 16 1 Bills to pay bills_to_pay NULL A
18 2 16 2 Bills to receive bills_to_receive NULL A

users_modules

CREATE TABLE users_modules (
  id_user SMALLINT NOT NULL,
  id_module SMALLINT NOT NULL
);
INSERT INTO
  users_modules
VALUES
  (1,1),
  (1,3),
  (1,4),
  (1,5),
  (1,7),
  (1,8),
  (1,11),
  (1,12);
id_user id_module
1 1
1 3
1 4
1 5
1 7
1 8
1 11
1 12

I created the query below and it seems to be pretty close to solving the problem, but I still can't figure out what it is

WITH RECURSIVE
  sub1 (id_master,sub) AS
  (
    (

/*

  THE FIRST PART OF A RECURSIVE CTE IS FOR NON-RECURSIVE DATA

  HERE I GET ALL THE RECORDS THAT POINT TO A FILE THAT CAN BE ACCESSED BY THE USER, BUT ONLY IF IT DOESN'T HAVE THE ROOT AS THE PARENT

*/
      SELECT
        B.id_master,
        JSONB_AGG(
          JSONB_BUILD_OBJECT(
            'icon',B.icon,
            'label',B.label,
            'module',B.file
          )
          ORDER BY
            B.group_order
        ) AS sub
      FROM
        (
          SELECT
            X.id_module
          FROM
            users_modules X
          INNER JOIN
            users Y
          ON
            X.id_user=Y.id
          WHERE
            X.id_user=1 AND
            Y.status='A'
        ) A
      INNER JOIN
        modules B
      ON
        A.id_module=B.id
      WHERE
        B.id_master IS NOT NULL AND
        B.id_subsystem=1 AND
        B.status='A'
      GROUP BY
        B.id_master

    )
    UNION ALL
    (

/*

  THE SECOND PART OF A RECURSIVE CTE IS FOR RECURSIVE DATA

  HERE I ASSEMBLE THE TREE CONNECTING ALL FINAL NODES AND BRANCHES POINTED RECURSIVELY

*/
      SELECT
        A.id_master,
        JSONB_BUILD_OBJECT(
          'icon',A.icon,
          'label',A.label,
          'sub',B.sub
        ) AS sub
      FROM
        modules A
      INNER JOIN
        sub1 B
      ON
        A.id=B.id_master
      WHERE
        A.status='A'
      ORDER BY
        A.group_order

    )
  )

SELECT
  JSONB_AGG(sub ORDER BY group_order)
FROM
  (
    SELECT
      sub,
      group_order
    FROM
      (
        (

/*

  TYING AT THE ROOT ALL KNOTS POINTING TO THE ROOT

*/
          SELECT
            JSONB_BUILD_OBJECT(
              'icon',A.icon,
              'label',A.label,
              'sub',B.sub
            ) AS sub,
            A.group_order
          FROM
            modules A
          INNER JOIN
            sub1 B
          ON
            A.id=B.id_master
          WHERE
            A.id_master IS NULL AND
            A.id_subsystem=1 AND
            A.status='A'

        )
        UNION ALL
        (

/*

  ADDING ALL USER ACCESSIBLE FILE NODES THAT HAVE ROOT AS THE PARENT

*/
          SELECT
            JSONB_BUILD_OBJECT(
              'icon',B.icon,
              'label',B.label,
              'module',B.file
            ) AS sub,
            B.group_order
          FROM
            (
              SELECT
                A.id_module
              FROM
                users_modules A
              INNER JOIN
                modules B
              ON
                A.id_module=B.id
              WHERE
                A.id_user=1 AND
                B.id_master IS NULL AND
                B.status='A'
              GROUP BY
                A.id_module
            ) A
          INNER JOIN
            modules B
          ON
            A.id_module=B.id AND
            B.status='A'

        )
      ) sub2
  ) sub3

What I get is this:

[
  {
    "icon": "dashboard",
    "label": "Dashboard",
    "module": "dashboard"
  },
  {
    "icon": "cabinet",
    "label": "Registrations",
    "sub":
      [
        {
          "icon": null,
          "label": "Customers",
          "module": "customers"
        },
        {
          "icon": null,
          "label": "Suppliers",
          "module": "suppliers"
        },
        {
          "icon": null,
          "label": "Products",
          "module": "products"
        }
      ]
  },
  {
    "icon": "cabinet",
    "label": "Registrations",
    "sub":
      {
        "icon": null,
        "label": "Staff",
        "sub":
          [
            {
              "icon": null,
              "label": "Countries",
              "module": "countries"
            },
              {
              "icon": null,
              "label": "States",
              "module": "states"
            }
          ]
      }
  },
  {
    "icon": "cabinet",
    "label": "Registrations",
    "sub":
      {
        "icon": null,
        "label": "Staff",
        "sub":
          {
            "icon": null,
            "label": "Means of contacts",
            "sub":
              [
                {
                  "icon": null,
                  "label": "Electronic contacts",
                  "module": "electronic_contacts"
                },
                {
                  "icon": null,
                  "label": "Phone contacts",
                  "module": "phone_contacts"
                }
              ]
          }
      }
  }
]

But what I need is this:

[
  {
    "icon": "dashboard",
    "label": "Dashboard",
    "module": "dashboard"
  },
  {
    "icon": "cabinet",
    "label": "Registrations",
    "sub":
      [
        {
          "icon": null,
          "label": "Customers",
          "module": "customers"
        },
        {
          "icon": null,
          "label": "Suppliers",
          "module": "suppliers"
        },
        {
          "icon": null,
          "label": "Products",
          "module": "products"
        },
        {
          "icon": null,
          "label": "Staff",
          "sub":
            [
              {
                "icon": null,
                "label": "Countries",
                "module": "countries"
              },
                {
                "icon": null,
                "label": "States",
                "module": "states"
              },
              {
                "icon": null,
                "label": "Means of contacts",
                "sub":
                  [
                    {
                      "icon": null,
                      "label": "Electronic contacts",
                      "module": "electronic_contacts"
                    },
                    {
                      "icon": null,
                      "label": "Phone contacts",
                      "module": "phone_contacts"
                    }
                  ]
              }
            ]
        }
      ]
  },
  {
    "icon": "sliders",
    "label": "Settings",
    "module": "settings"
  }
]

Part of the members of the registrations node was not nested inside it and the settings node was lost

Almost there...

Solution

  • The query here below provides the expected result according to your data set :

    WITH RECURSIVE list AS (
SELECT m.id_subsystem
     , p.id :: integer AS id_master
     , array_agg(m.id :: integer ORDER BY m.group_order) AS children_array
     , bool_and(NOT EXISTS(SELECT 1 FROM modules where id_master = m.id)) AS leaves_only
     , jsonb_build_object('icon', p.icon, 'label', p.label,'sub', jsonb_agg(jsonb_build_object('icon', m.icon, 'label', m.label, 'module', m.file) ORDER BY m.group_order)) AS module_hierarchy
  FROM modules m
  LEFT JOIN modules p
    ON p.id = m.id_master
 GROUP BY m.id_subsystem, p.id, p.icon, p.label
), tree AS (
SELECT id_subsystem
     , id_master
     , module_hierarchy
  FROM list
 WHERE leaves_only -- starts with the leaf modules
UNION ALL
SELECT t.id_subsystem
     , l.id_master
     , jsonb_set(l.module_hierarchy, array['sub', (array_position(l.children_array, t.id_master) - 1) :: text], t.module_hierarchy, true)
  FROM tree t
 INNER JOIN list l
    ON l.children_array @> array[t.id_master] -- bottom-up tree build
   AND l.id_subsystem = t.id_subsystem
 WHERE t.id_master IS NOT NULL
)
SELECT id_subsystem, jsonb_pretty(module_hierarchy->'sub')
  FROM tree
 WHERE id_master IS NULL

    Some conditions are not implemented yet : status of the modules and users, users_modules relationship, but adding these conditions should not be a big deal.

    This query provides the expected result only if there is only one branch with 2 levels or more which is the case in your data set. When there are 2 or more branches with 2 levels or more, we need to merge the branches all together with a dedicated aggregate function :

    CREATE OR REPLACE FUNCTION jsonb_merge (x jsonb, y jsonb)
  RETURNS jsonb LANGUAGE sql IMMUTABLE AS $$
  SELECT jsonb_agg(
         CASE
           WHEN x.content->>'sub' IS NOT NULL AND y.content->>'sub' IS NOT NULL
           THEN (x.content - 'sub') || jsonb_build_object('sub', jsonb_merge(x.content->'sub', y.content->'sub'))
           WHEN x.content->>'sub' IS NOT NULL
           THEN x.content
           ELSE y.content
         END
         ORDER BY x.id
         )
    FROM jsonb_path_query(COALESCE(x, y), '$[*]') WITH ORDINALITY AS x(content, id)
   INNER JOIN jsonb_path_query(y, '$[*]') WITH ORDINALITY AS y(content, id)
      ON x.id = y.id
$$ ;

CREATE OR REPLACE AGGREGATE jsonb_merge(jsonb)
( stype = jsonb, sfunc = jsonb_merge) ;

    This aggregate function cannot be called directly inside the recursive query because postgres doesn't accept aggregate functions in the recursive part of the query, but it can be called after :

    WITH RECURSIVE list AS (
SELECT m.id_subsystem
     , p.id :: integer AS id_master
     , array_agg(m.id :: integer ORDER BY m.group_order) AS children_array
     , bool_and(NOT EXISTS(SELECT 1 FROM modules where id_master = m.id)) AS leaves_only
     , jsonb_build_object('icon', p.icon, 'label', p.label,'sub', jsonb_agg(jsonb_build_object('icon', m.icon, 'label', m.label, 'module', m.file) ORDER BY m.group_order)) AS module_hierarchy
  FROM modules m
  LEFT JOIN modules p
    ON p.id = m.id_master
 GROUP BY m.id_subsystem, p.id, p.icon, p.label
), tree AS (
SELECT id_subsystem
     , id_master
     , module_hierarchy
  FROM list
 WHERE leaves_only
UNION ALL
SELECT t.id_subsystem
     , l.id_master
     , jsonb_set(l.module_hierarchy, array['sub', (array_position(l.children_array, t.id_master) - 1) :: text], t.module_hierarchy, true)
  FROM tree t
 INNER JOIN list l
    ON l.children_array @> array[t.id_master]
   AND l.id_subsystem = t.id_subsystem
 WHERE t.id_master IS NOT NULL
)
SELECT id_subsystem
     , jsonb_pretty(jsonb_merge(module_hierarchy->'sub'))
  FROM tree
 WHERE id_master IS NULL
 GROUP BY id_subsystem

    This query should work for any kind of trees with any levels.

    see test result in dbfiddle