Write element's ancestry to Postgres table from adjacency list

Question

I want to write a 1 to n-hierarchy that's stored as an adjacency list to a table that lists each of an element's ancestors. I'm using a Postgres database (Postgres 10, but the machine on which the code is to be deployed runs Postgres 9.x).

Sample input table (adjacency list):

INSERT INTO public.test (id, name, parent_id)
VALUES (1, 't', 1),
   (11, 't1', 1),
   (12, 't2', 1),
   (13, 't3', 1),
   (111, 't11', 11),
   (112, 't12', 11),
   (121, 't21', 12),
   (14, 't4', 1),
   (141, 't41', 14),
   (142, 't42', 14)

As a result I would like a table that looks like this (just a few rows shown; furthermore, the real-life problem I'm trying to solve has seven hierarchical levels instead of just two):

+-----+-------+--------+--------+
| id  | level | level0 | level1 |
+-----+-------+--------+--------+
|   1 |     0 | NULL   | NULL   |
|  11 |     1 | 1      | NULL   |
|  12 |     1 | 1      | NULL   |
| 111 |     2 | 1      | 11     |
+-----+-------+--------+--------+

id is the element's id, level is the level at which this element is located within the hierarchy (0 being the root level), level0/1 is the element's ancestor at the respective level.

I'm new to SQL, so I haven't got any code I could show you. Googling has told me that I probably neet to use a recursive CTE to obtain the desired result and perform a self-join, but I haven't been able to figure out how to do it. Thanks for your help.

EDIT

This is what I have tried so far:

WITH RECURSIVE cte AS
(
SELECT m.id AS id,
    0 AS level,
    m.parent_id AS level0,
    m.parent_id AS level1,
    m.parent_id AS parent
    FROM public.test AS m
    WHERE m.parent_id IS NULL

UNION ALL

SELECT 
    m.id,
    cte.level + 1,
    cte.parent AS level0,
    cte.parent AS level1,
    m.parent_id AS parent
    FROM public.test AS m 
        INNER JOIN cte
            ON m.parent_id = cte.id 
)
SELECT *
FROM cte;

Of course, setting level0 and level1 to the element's parent doesn't yield the desired result, but I had to set it to something and haven't got further than this.

`but I haven't been able to figure out how to do it` What have you tried? BTW: google is correct. — wildplasser, Feb 07 '18 at 11:49
I have also found this question (https://stackoverflow.com/questions/42955335/sql-server-recursive-self-join), but I haven't been able to adapt the solution to my needs as I have to add several columns instead of building up a string. — canavanin, Feb 07 '18 at 16:35
Relational databases are designed to work with a stable schema. It means that the number of columns is fixed. You want to generate a result set with a dynamic list of columns. Usually it means that you need some sort of dynamic SQL for it. 1) Write a query that would return fixed number of columns: `id, level, parent_level, parent_level_id`. 2) Use some sort of dynamic pivot to transpose these values into a result with non-fixed number of columns (`level_0, level_1, ..., level_n`). — Vladimir Baranov, Feb 16 '18 at 05:36

score 1 · Answer 1 · answered Feb 16 '18 at 06:17

if the position of the object is not changed in time (i.e. if it was put from the beginning on level 6 it will stay on that level forever) you can introduce some sane id with 7 numbers, showing 7 levels, separated by lets say semicolon(:):

'1:1:1:1:1:1:1'

and then introduce some functional indexes, like:

CREATE INDEX level1_idx ON main_table USING (regexp_split_to_array(id, '\\:')[1])
CREATE INDEX level2_idx ON main_table USING (regexp_split_to_array(id, '\\:')[2])
CREATE INDEX level3_idx ON main_table USING (regexp_split_to_array(id, '\\:')[3])

then you can alaways make an efficient query:

SELECT id, regexp_split_to_array(id, '\\:')[1] as level1, regexp_split_to_array(id, '\\:')[2] as level2, ...
ORDER BY level1, level2, level3 ...

dnswlt · Accepted Answer · 2018-02-17T12:42:58.180

SQL is a strictly typed language that does not allow the number of columns returned from a SELECT to vary depending on the data it is acting upon. See e.g. Split comma separated column data into additional columns for a discussion.

However, PostgreSQL offers you an array type that you can use to collect values of dynamic size into a single column. The following recursive CTE collects all ancestors of every row into such an array:

with recursive rec(id, level, parent_id, ancestors) as (
  select id, 0, parent_id, array[] :: int[]
  from test
  where parent_id = id
  union all
  select t.id, rec.level + 1, t.parent_id, rec.ancestors || array[t.parent_id]
  from test t
  join rec on t.parent_id = rec.id
  where t.parent_id <> t.id
)
select 
  rec.id,
  rec.level,
  rec.ancestors
from rec;

If there's a known limit to the levels, you can select the elements from the array per column:

select
  rec.id,
  rec.level,
  rec.ancestors[1] level1,
  rec.ancestors[2] level2,
  ...

SQL Fiddle

Write element's ancestry to Postgres table from adjacency list

2 Answers2

Related