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?

10
  • So, to find the connection between level and sublevel, one needs to fiddle with the name? Oct 11, 2021 at 19:12
  • Some background information on handing hierarchies in SQL: dba.stackexchange.com/questions/48/…
    – dwhitemv
    Oct 12, 2021 at 3:46
  • @GerardH.Pille Yes, I need to fiddle with the name of the level, but is it dishonestly? :-) Oct 12, 2021 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, 2021 at 5:20
  • The level names are predefined and they have a different pattern. Level_1, level_1_2 are only examples. Oct 12, 2021 at 6:12

3 Answers 3

1

PGSQL Tree relations

Hello, I just got a handle on this for a project I'm working on and figured I'd share my write-up Hope this helps. Let's get started with some prereqs

This is essentially the closure table solution mentioned above Using recursive calls. Thanks for those slides they are very useful I wish i saw them before this write up :)

pre-requisites

Recursive Functions

these are functions that call themselves ie

function factorial(n) {
    if (n = 0) return 1; //base case
    return n * factorial(n - 1); // recursive call
}

This is pretty cool luckily pgsql has recursive functions too but it can be a bit much. I prefer functional stuff cte with pgsql

WITH RECURSIVE t(n) AS (
    VALUES (1) -- nonrecusive term 
  UNION ALL
    SELECT n+1 FROM t WHERE n < 100 -- recusive term
    --continues until union adds nothing
)
SELECT sum(n) FROM t;

The general form of a recursive WITH query is always a non-recursive term, then UNION (or UNION ALL), then a recursive term, where only the recursive term can contain a reference to the query's own output. Such a query is executed as follows:

Recursive Query Evaluation

  1. Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.

  2. So long as the working table is not empty, repeat these steps:

    a. Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.

    b. Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.

to do something like factorial in sql you need to do something more like this so post

ALTER FUNCTION dbo.fnGetFactorial (@num int)
RETURNS INT
AS
BEGIN
    DECLARE @n  int

    IF @num <= 1 SET @n = 1
    ELSE SET @n = @num * dbo.fnGetFactorial(@num - 1)

    RETURN @n
END
GO

Tree data structures (more of a forest :)

wikipedia

The import thing to note is that a tree is a subset of a graph, This can be simply enforced by the relationship each node has only one parent.

Representing the Tree in PGSQL

I think it will be easiest to work it out a little more theoretically before we move on to the sql

The simple way of represent a graph relation without data duplication is by separating the nodes(id, data) from the edges. We can then restrict the edges(parent_id, child_id) table to enforce our constraint. be mandating that parent_id,child_id as well as just child id be unique

create table nodes (
    id uuid default uuid_generate_v4() not null unique ,
    name varchar(255) not null,
    json json default '{}'::json not null,
    remarks varchar(255),
);


create table edges (
    id uuid default uuid_generate_v4() not null,
    parent_id uuid not null,
    child_id uuid not null,
    meta json default '{}'::json,
    constraint group_group_id_key
        primary key (id),
    constraint group_group_unique_combo
        unique (parent_id, child_id),
    constraint group_group_unique_child
        unique (child_id),
    foreign key (parent_id) references nodes
        on update cascade on delete cascade,
    foreign key (child_id) references nodes
        on update cascade on delete cascade
);

Note that theoretical this can all be done with only one table by simply putting the parent_id in the nodes table and then

CREATE VIEW v_edges as (SELECT id as child_id, parent_id FROM nodes)

but for the proposal of flexibility and so that we can incorporate other graph structures to this framework I will use the common many-to-many relationship structure. This will ideally allow this research to be expanded into other graph algorithms.

Let's start out with a sample data structure

INSERT (id, my_data) VALUES ('alpha', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('bravo', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('charly', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('berry', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('zeta', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('yank', 'my big data') INTO nodes

INSERT (parent_id, child_id) VALUES ('alpha', 'bravo') INTO edges
INSERT (parent_id, child_id) VALUES ('alpha', 'berry') INTO edges
INSERT (parent_id, child_id) VALUES ('bravo', 'charly') INTO edges
INSERT (parent_id, child_id) VALUES ('yank', 'zeta') INTO edges

-- rank0       Alpha      Yank
-- rank1    Bravo Berry     Zeta
-- rank2  Charly         

Note the interesting properties of a tree (number of edges e) =( number of nodes n)-1 each child has exactly one parent.

We can then simplify the equations

let n = node
let p = parent 
let c = child
let ns = nodes = groups
let es = edges = group_group // because this is a relationship of a group entity to another group entity

So now what sort of questions will we ask.

"Given an arbitrary set of groups 's' what is the coverage of the graph assuming nodes inherit their children?"

This is a tricky question, it requires us to traverse the graph and find all children of each node in s

This continues off of this stack overflow post

        -- some DBMS (e.g. Postgres) require the word "recursive"
        -- some others (Oracle, SQL-Server) require omitting the "recursive"
        -- and some (e.g. SQLite) don't bother, i.e. they accept both
-- drop view v_group_descendant;
create view v_group_descendant as
with recursive descendants -- name for accumulating table
  (parent_id, descendant_id, lvl) -- output columns
as
  ( select parent_id, child_id, 1
    from group_group -- starting point, we start with each base group
  union all
    select d.parent_id, s.child_id, d.lvl + 1
    from descendants  d -- get the n-1 th level of descendants/ children
      join group_group  s -- and join it to find the nth level
        on d.descendant_id = s.parent_id -- the trick is that the output of this query becomes the input
        -- Im not sure when it stops but probably when there is no change
  )
select * from descendants;

comment on view v_group_descendant is 'This aggregates the children of each group RECURSIVELY WOO ALL THE WAY DOWN THE TREE :)';

after we have this view we can join with our nodes/groups to get out data back i will not provide these samples for every single step for the most part we will just work with ids.

select d.*, g1.group_name as parent, g2.group_name as decendent --then we join it with groups to add names
from v_group_descendant d, groups g1, groups g2
WHERE g1.id = d.parent_id and g2.id = d.descendant_id
order by parent_id, lvl, descendant_id;

sample output

+------------------------------------+------------------------------------+---+----------+---------+
|parent_id                           |descendant_id                       |lvl|parent    |decendent|
+------------------------------------+------------------------------------+---+----------+---------+
|3ef7050f-2f90-444a-a20d-c5cbac91c978|6c758087-a158-43ff-92d6-9f922699f319|1  |bravo     |charly   |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|3ef7050f-2f90-444a-a20d-c5cbac91c978|1  |alpha     |bravo    |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|7135b0c6-d59c-4c27-9617-ddcf3bc79419|1  |alpha     |berry    |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|6c758087-a158-43ff-92d6-9f922699f319|2  |alpha     |charly   |
|42529e8a-75b0-4242-a51a-ac60a0e48868|44758087-a158-43ff-92d6-9f922699f319|1  |yank      |zeta     |
+------------------------------------+------------------------------------+---+----------+---------+

Note that this is just the minimal node descendant relationship and has actual lost all nodes with 0 children such as charly.

In order to resolve this we need to add all nodes back which don't appear in the descendants list

 create view v_group_descendant_all as (
       select * from  v_group_descendant gd
       UNION ALL
       select  null::uuid as parent_id,id as descendant_id, 0 as lvl from groups g
       where not exists (select * from  v_group_descendant gd where gd.descendant_id = g.id )
);
comment on view v_group_descendant is 'complete list of descendants including rank 0 root nodes descendant - parent relationship is duplicated for all levels / ranks';
preview
+------------------------------------+------------------------------------+---+----------+---------+
|parent_id                           |descendant_id                       |lvl|parent    |decendent|
+------------------------------------+------------------------------------+---+----------+---------+
|3ef7050f-2f90-444a-a20d-c5cbac91c978|6c758087-a158-43ff-92d6-9f922699f319|1  |bravo     |charly   |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|3ef7050f-2f90-444a-a20d-c5cbac91c978|1  |alpha     |bravo    |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|7135b0c6-d59c-4c27-9617-ddcf3bc79419|1  |alpha     |berry    |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|6c758087-a158-43ff-92d6-9f922699f319|2  |alpha     |charly   |
|42529e8a-75b0-4242-a51a-ac60a0e48868|44758087-a158-43ff-92d6-9f922699f319|1  |yank      |zeta     |
|null                                |c1529e8a-75b0-4242-a51a-ac60a0e48868|0  |null      |alpha    |
|null                                |42529e8a-75b0-4242-a51a-ac60a0e48868|0  |null      |yank     |
+------------------------------------+------------------------------------+---+----------+---------+

Lets say for example we are getting our set s of groups bases on a users(id , data) table with a user_group(user_id, group_id) relation

We can then join this to another table removing duplicates because our set s of user_group relations may cause duplicates if a users is say assigned to both alpha assigned charly

+------+--------+
| user | group  |
+------+--------+
| jane | alpha  |
| jane | charly |
| kier | yank   |   
| kier | bravo  |
+------+--------+
--drop view v_user_group_recursive;
CREATE VIEW v_user_group_recursive AS (
SELECT DISTINCT dd.descendant_id AS group_id, ug.user_id 
    FROM v_group_descendant_all dd , user_group ug
    WHERE (ug.group_id = dd.descendant_id 
        OR ug.group_id = dd.parent_id)  -- should gic
);
SELECT * FROM v_user_group_recursive;
+------+--------+
| user | group  |
+------+--------+
| jane | alpha  |
| jane | bravo  |
| jane | berry  |
| jane | charly |
-- | jane | charly | Removed by DISTINCT
| kier | yank   |   
| kier | zeta   |   
| kier | bravo  |
| kier | charly |
+------+--------+

If we want we can now group by node and join we can do somthing k like the fallowing

CREATE VIEW v_user_groups_recursive AS (
    SELECT user_id, json_agg(json_build_object('id', id,'parent_id',parent_id, 'group_name', group_name, 'org_id', org_id, 'json', json, 'remarks', remarks)) as groups
    FROM v_user_group_recursive ug, v_groups_parent g
    WHERE ug.group_id = g.id GROUP BY user_id
);
comment on view v_user_group_recursive is 'This aggregates the groups for each user recursively ';
+------+-------------------------------+
| user | groups                        |
+------+-------------------------------+
| jane | [alpha, bravo, berry, charly] |
| kier | [yank, zeta, bravo, charly]   |   
+------+-------------------------------+

This is awesome we have answered the question. We now can simply ask which groups this use inherits

SELECT * from v_user_groups_recursive where user_id = 'kier

Displaying our hard work in the front end

And further we could use somthing like jstree.com to display our structure

  async function getProjectTree(user_id) {
        let res = await table.query(format('SELECT * from v_user_groups_recursive ug WHERE ug.user_id = %L', user_id));
        if (res.success) {
            let rows = res.data[0].groups.map(r => {

                return {
                    id: r.id, // required
                    parent: r.parent_id==null?'#':r.parent_id,// required
                    text: r.group_name,// node text
                    icon: 'P', // string for custom
                    state: {
                        opened: true,  // is the node open
                        disabled: false,  // is the node disabled
                        selected: false,  // is the node selected
                    },
                    li_attr: {},  // attributes for the generated LI node
                    a_attr: {}  // attributes for the generated A node
                }
            })
           
            return {success: true, data: rows, msg: 'Got all projects'}
        } else return res;
    }
<div id="v_project_tree" class="row col-10 mx-auto" style="height: 25vh"></div>
<script>
   function buildTree() {
      bs.sendJson('get', "/api/projects/getProjectTree").then(res => {
         bs.resNotify(res);
         if (!res.success) {
            //:(
            console.error(':(');
            return
         }
         console.log(res.data);
         $('#v_project_tree').jstree({
            'core': {
               'data': res.data
            }
         });
      })
   }
   window.addEventListener('load', buildTree);
</script>

jstree preview

blog

1
  • This is all very nice, but doesn't answer the original question. Also, the link to your blog is entirely irrelevant.
    – mustaccio
    May 7, 2022 at 11:51
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.

0

https://gist.github.com/kardasz/7094fa5f1b29506dd0bed05effce4065

CREATE OR REPLACE FUNCTION check_circular_reference() RETURNS TRIGGER AS $$
DECLARE
    circular_found int;
BEGIN
    IF NEW.parent_id IS NOT NULL
    THEN
        IF NEW.parent_id = NEW.id
        THEN
            RAISE EXCEPTION 'circular reference detected';
        END IF;

        WITH RECURSIVE circular_reference AS (
            SELECT id, parent_id FROM table_name WHERE parent_id = NEW.id
            UNION
            SELECT t.id, t.parent_id
            FROM table_name t
            INNER JOIN circular_reference cr ON cr.id = t.parent_id
        )
        SELECT 1 INTO circular_found FROM circular_reference WHERE id = NEW.parent_id;

        IF FOUND THEN
            RAISE EXCEPTION 'circular reference detected';
        END IF;
    END IF;

    RETURN NEW;
END;
$$ LANGUAGE plpgsql;

DROP TRIGGER IF EXISTS circular_reference_trigger ON table_name;
CREATE TRIGGER circular_reference_trigger BEFORE INSERT OR UPDATE ON table_name FOR EACH ROW EXECUTE FUNCTION check_circular_reference();
1
  • Welcome to DBA, you could improve your answer by explaining the sql, for those yet to come. Jun 6, 2023 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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