Postgres - multilevel parent child relation data

Question

We have a parent child relation as below.

Script to generate tables as below.

create table dependency ( packageid int, dependant_packageid int);
insert into dependency values (2,1);
insert into dependency values (3,1);
insert into dependency values (4,1);
insert into dependency values (5,2);
insert into dependency values (6,3);
insert into dependency values (7,4);
insert into dependency values (7,5);
insert into dependency values (8,5);
insert into dependency values (8,3);
insert into dependency values (4,5);
insert into dependency values (6,4);
insert into dependency values (5,3);

We wanted to get data based on below mentioned quer.

for the given package get the possible dependant hierarchy


Ex:
packageid : 6
Result should be: [(3,1),(4,1),(4,5,2,1),(4,5,3,1)]
packageid : 7
Result should be: [(4,1),(4,5,2,1),(4,5,3,1)]
packageid : 8
Result should be: [(5,2,1),(5,3,1),(3,1)]

for the given package get the list of parent packages


Ex:
1 - 2,3,4
2 - 5
3 - 6,8,5
4 - 7,6
5 - 7,8,4

If we need to maintain this kind of parent child relation (many to many), what should be ideal schema structure (Keeping in mind performance) ?

Appreciate any help....happy coding....:)

Your schema is fine for this. What you need here is called a RECURSIVE CTE. It's a two part query inside a CTE that iteratively joins back to itself until the join fails. — JNevill, Nov 27 '19 at 14:20
Fyi, here's an [older SO post about alternatives for an adjacency list](https://stackoverflow.com/q/4048151/4003419) you might be an interesting read. — LukStorms, Nov 27 '19 at 14:33

score 0 · Accepted Answer · answered Nov 27 '19 at 14:40

Here's a quick shot at a recursive query that spits out your distinct full dependency lists for each id:

WITH RECURSIVE rcte AS (
    --Recursive Seed
    SELECT packageid as initialid, 
        packageid,
        dependant_packageid, 
        CAST(packageid || ',' || dependant_packageid as varchar(30)) as path,
        1 as depth
    FROM dependency
    UNION ALL
    --Recursive Term
    SELECT initialid,
        dependency.packageid,
        dependency.dependant_packageid,
        CAST(rcte.path || ',' || dependency.dependant_packageid as varchar(30)),
        rcte.depth + 1
    FROM rcte
        INNER JOIN dependency ON rcte.dependant_packageid = dependency.packageid
)
SELECT r1.initialid as packageid, path as dependant_packages 
FROM rcte r1
    LEFT OUTER JOIN rcte r2
        ON r2.path LIKE r1.path || '%' AND r1.depth < r2.depth
WHERE r2.initialid IS NULL
ORDER BY r1.path;

That recursive CTE has two parts. The recursive seed is run once. It gathers the records from the table(s) that will be initially fed into the second part, the recursive term which will iterate until its JOIN fails. In that recursive term we join the CTE rcte back to the table and join the dependant_packageid of the CTE to the packageid of the table.

Finally the SELECT statement refernces those results from the CTE and self-joins to find the longest distinct path from all those iterations.

Using this same recursive logic you can get your remaining record sets.

score 0 · Answer 2 · answered Nov 27 '19 at 15:37

I would suggest adding an primary key to your table:

create table dependency (serial id, packageid int, dependant_packageid int);

Then, to get the hierarchy you could use a query like this:

WITH RECURSIVE rcte AS (
    SELECT id,
        packageid AS initial_packageid,
        dependant_packageid, 
        ARRAY[dependant_packageid::text]::text[] as path,
        1 as depth
    FROM dependency
    UNION ALL
    SELECT rcte.id,
        rcte.initial_packageid,
        dependency.dependant_packageid,
        rcte.path || dependency.dependant_packageid::text,
        rcte.depth + 1
    FROM rcte
        JOIN dependency ON rcte.dependant_packageid = dependency.packageid ),
    cte_hierarchy AS (
        SELECT initial_packageid AS packageid,
            (ARRAY_AGG( '(' || ARRAY_TO_STRING(path, ',') || ')' ORDER BY depth DESC))[1] AS hierarchy
        FROM rcte
        GROUP BY id, initial_packageid )
SELECT packageid, STRING_AGG(hierarchy, ',')
FROM cte_hierarchy
GROUP BY packageid
ORDER BY packageid

And to get the parent packages simply use:

SELECT dependant_packageid AS packageid, ARRAY_AGG(DISTINCT packageid)
FROM dependency
GROUP BY dependant_packageid
ORDER BY dependant_packageid

Postgres - multilevel parent child relation data

2 Answers2