1

I need to store objects in a PostgreSQL database version 13.

Each object has an ID, a name, occupies a level and belongs to a parent object, relation denoted by belongs_to.

The values for the levels are stored in the levels table:

CREATE TABLE public.levels (
    id integer NOT NULL,
    name character varying(32) NOT NULL,
    CONSTRAINT pk_levels PRIMARY KEY (id),
    CONSTRAINT uk_levels UNIQUE (name)
);

For this example I defined 4 distinct values for these levels, where, for example, the 'level_1_2' is a sublevel of 'level_1', and so on:

insert into public.levels (id, name) values
(1, 'level_1'),
(2, 'level_1_2'),
(3, 'level_1_2_3'),
(4, 'level_1_2_3_4');

The objects are stored in this table:

CREATE TABLE public.objects(
    id integer NOT NULL,
    level integer NOT NULL,
    name character varying(32) NOT NULL,
    belongs_to integer,
    CONSTRAINT pk_objects PRIMARY KEY (id),
    CONSTRAINT fk_object_levels FOREIGN KEY (level)
        REFERENCES public.levels (id) MATCH SIMPLE
        ON UPDATE NO ACTION
        ON DELETE NO ACTION,
    CONSTRAINT fk_object_parent FOREIGN KEY (belongs_to)
        REFERENCES public.objects (id) MATCH SIMPLE
        ON UPDATE NO ACTION
        ON DELETE NO ACTION
);

and the objects are:

insert into public.objects(id, level, name, belongs_to) values
( 1, 1, 'obj 1', null),
( 2, 2, 'obj 2', 1),
( 3, 2, 'obj 3', 1),
( 4, 2, 'obj 4', 1),
( 5, 3, 'obj 5', 2),
( 6, 3, 'obj 6', 2),
( 7, 3, 'obj 7', 3),
( 8, 3, 'obj 8', 4),
( 9, 3, 'obj 9', 4),
(10, 3, 'obj 10', 4),
(11, 4, 'obj 11', 6),
(12, 4, 'obj 12', 5),
(13, 1, 'obj 13', null),
(14, 2, 'obj 14', 1);

What I would like to achieve is a view (normal or materialized), with the following content:

id    level_1    level_1_2    level_1_2_3    level_1_2_3_4
----------------------------------------------------------
 1          1         null           null             null
 2          1            2           null             null
 3          1            3           null             null
 4          1            4           null             null
 5          1            2              5             null
 6          1            2              6             null
 7          1            3              7             null
 8          1            4              8             null
 9          1            4              3             null
10          1            4             10             null
11          1            2              6               11
12          1            2              5               12
13         13         null           null             null
14          1           14           null             null

The view contains only IDs. The ID of an object appears once in the ID column and once more in the corresponding level's column.

Example:

The ID of 'obj 12' is 12, this appears in the ID column and in the level_1_2_3_4 column. Beside these, the parent level columns, for this 'obj 12' contain the parent ID of 12, the parent ID of the parent ID, and so on.

My question is, how should I define a query to get the above result?

9
  • So, to find the connection between level and sublevel, one needs to fiddle with the name? Oct 11 at 19:12
  • Some background information on handing hierarchies in SQL: dba.stackexchange.com/questions/48/…
    – dwhitemv
    Oct 12 at 3:46
  • @GerardH.Pille Yes, I need to fiddle with the name of the level, but is it dishonestly? :-) Oct 12 at 4:48
  • Are the names of the levels dynamic, and do they always number from 1? I have a query to convert the adjacency table to a path enumeration but if the level names are not static then some Dynamic SQL is required.
    – dwhitemv
    Oct 12 at 5:20
  • The level names are predefined and they have a different pattern. Level_1, level_1_2 are only examples. Oct 12 at 6:12
0

This is a partial answer to try and illustrate the issue with the column names that we are discussing in the comments. I will mark this as Community Wiki so others can update it if needed.

I see two parts to developing the query:

  1. Computing the paths through the table to each node.
  2. Determining & applying the column names for the data presented.

Part 1

As theobjects table is an Adjacency List, we use a Recursive CTE to plot all the paths through the table. This is a common pattern, so much so that the base query is in the PostgreSQL documentation as a depth-first search:

WITH RECURSIVE search_tree(id, link, data, path) AS (
    SELECT t.id, t.link, t.data, ARRAY[t.id]
    FROM tree t
  UNION ALL
    SELECT t.id, t.link, t.data, path || t.id
    FROM tree t, search_tree st
    WHERE t.id = st.link
)
SELECT * FROM search_tree ORDER BY path;

The query returns path as an array of node IDs:

id belongs_to name path
1 NULL obj 1 {1}
2 1 obj 2 {2}
1 NULL obj 1 {2,1}
3 1 obj 3 {3}
1 NULL obj 1 {3,1}
4 1 obj 4 {4}
1 NULL obj 1 {4,1}
...
12 5 obj 12 {12}
5 2 obj 5 {12,5}
2 1 obj 2 {12,5,2}
1 NULL obj 1 {12,5,2,1}
13 NULL obj 13 {13}
14 1 obj 14 {14}
1 NULL obj 1 {14,1}

To apply this query to the problem, we make a few changes:

  • Change the parent column link to belongs_to
  • Change data to name
  • Reverse the array append to path so the resultant array lists the path from the top down
  • Add a WHERE belongs_to IS NULL so only the completed paths are returned (otherwise all the intermediate paths are also included)
  • Add column names (static)

The modified query is thus:

WITH RECURSIVE search_tree(id, belongs_to, name, path) AS (
    SELECT t.id, t.belongs_to, t.name, ARRAY[t.id]
    FROM objects t
  UNION ALL
    SELECT t.id, t.belongs_to, t.name, t.id || path
    FROM objects t, search_tree st
    WHERE t.id = st.belongs_to
)
SELECT path[array_upper(path, 1)] AS id, 
       path[1] AS level_1, 
       path[2] AS level_1_2, 
       path[3] AS level_1_2_3, 
       path[4] AS level_1_2_3_4 
FROM search_tree WHERE belongs_to IS NULL ORDER BY 1;

Which returns the desired output:

id level_1 level_1_2 level_1_2_3 level_1_2_3_4
1 1 NULL NULL NULL
2 1 2 NULL NULL
3 1 3 NULL NULL
4 1 4 NULL NULL
5 1 2 5 NULL
6 1 2 6 NULL
7 1 3 7 NULL
8 1 4 8 NULL
9 1 4 9 NULL
10 1 4 10 NULL
11 1 2 6 11
12 1 2 5 12
13 13 NULL NULL NULL
14 1 14 NULL NULL

Issues

The query has some limitations.

  • The output only works if the tree is 4 or less nodes deep.
  • The column names are hard-coded when the specification states that they need to be taken from another table (levels).

Part 2

This is where I'm running into trouble. In the current schema, there is a levels table which lists level names by ID. This ID relates to objects.level, which is an attribute of a objects tree node. How do we determine which node's level field to use to label our columns? What if there are differing levels for nodes at the same depth in the tree, or the same level is used for two different depths?

Maybe it would help to explain why the path components have to be broken out into columns that have names determined by a table.

This problem would be easier to solve if the levels table was keyed by depth instead of an ID:

depth level
1 level_1
2 level_1_2
3 level_1_2_3
4 level_1_2_3_4

Then there is a neat linear relationship.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.