PostgreSQL recursive query for calculation parent value

user_3850678 0
Viewed 143

Here is entry's hierarchy. 
             _________Milky Way (30)________
            /               |               \
    Alpha(10)           Beta(20)            Delta(null)
     /  \                                       |
Mars(7) Jupiter(3)                          Delta-child(44)

Parents value is a sum of it's children's values. Ex.

Alpha = Mars + Jupiter = 7 + 3 = 10
Milky Way = Alpha + Beta + Delta = 10 + 20 + null = 30

The task: recalculate parents up to the root in case any child is updated. Let's even simplify the task: select all entries up to the root with recalculated values.
Imagine that Mars is updated. Now Mars value is 2.

             _________Milky Way (?)________
            /               |               \
    Alpha(?)            Beta(20)            Delta(null)
     /  \                                       |
Mars(2) Jupiter(3)                          Delta-child(44)

It means that all parents should be updated:

Alpha = Mars + Jupiter = 2 + 3 = 5
Milky Way = Alpha + Beta + Delta = 5 + 20 + null =  25.

Note: Delta -> Delta-child coupling is broken and it's fine. It can happen lets leave it out of scope here. 've added this sample just to be sure that it won't be counted during calculation as hierarchy can be huge enough and tehre is no task to recalculate all children leaf, just parents up to the root.

As a result of some "select .. from hierarchy.." I'd like to receive recalculated parents' values.
Ex.

id name value
1 Milky Way 25
2 Alpha 5

Code samples with already updated Mars (sqlfiddle links are below):
Schema

CREATE TABLE hierarchy
        (
        id int4,
        parent_id int4,
        name varchar(255),
        value int4
        );

Values

insert into hierarchy
values
(1, null, 'Milky Way', 30),
(2, 1, 'Alpha', 10),
(3, 1, 'Beta', 20),
(4, 1, 'Delta', null),
(5, 2, 'Mars', 2),
(6, 2, 'Jupiter', 3),
(7, 4, 'Delta-child', 44);

What I have tried:

  1. I was able to list all leafs which should be used in calculation
    sqlfiddle 1

    WITH RECURSIVE cte AS ( 
  SELECT h1.id,  h1.parent_id, h1.name , h1.value from hierarchy h1
  where h1.id = 5
     UNION
 SELECT h2.id,  h2.parent_id, h2.name , h2.value from hierarchy h2
 JOIN cte cte ON (cte.parent_id = h2.parent_id or cte.parent_id = h2.id ) 
 where cte.id != h2.id 
) select * from cte
order by id

  2. When I tried to sum values, query goes in infinite loop for some reason
    sqlfiddle 2

     WITH RECURSIVE cte AS ( 
  SELECT h1.id,  h1.parent_id, h1.name , h1.value from hierarchy h1
  where h1.id = 5
     UNION
 SELECT h2.id,  h2.parent_id, h2.name , (h2.value + cte.value) as value from hierarchy h2
 JOIN cte cte ON (cte.parent_id = h2.parent_id or cte.parent_id = h2.id ) 
 where cte.id != h2.id 
) select * from cte
order by id

  3. There is one more query that I have tried, unfortunately it doesn't count sibling of parents.
    sqlfiddle 3

                WITH RECURSIVE cte AS ( 
         SELECT h1.id,  h1.parent_id, h1.name , h1.value from hierarchy h1
          where h1.parent_id = (select parent_id from hierarchy where id = 5)  
             UNION
         SELECT h2.id,  h2.parent_id, h2.name , cte.value as value from hierarchy h2
         JOIN cte cte ON (cte.parent_id = h2.parent_id or cte.parent_id = h2.id ) 
         where cte.id != h2.id 
        ) select id, parent_id, name, sum(value) from cte
        group by id, parent_id, name
        order by id

I'd appreciate any assistance. :-)

recursive-query postgresql sql
3 Answers

It took me a while, but good work on your trials.

What i did is that I split the problem in parts.

  1. go down the hierarchy with the recursive query
with recursive base_qry as (
    select id, 
        parent_id,
        value,
        ARRAY[id] as id_array
    from hierarchy 
    union all 
    select h.id,
    h.parent_id,
    h.value,
    id_array || h.id as id_array 
    from hierarchy h join base_qry b on h.parent_id = b.id and h.value is not null
    )
  1. Understand the nodes affected filtering the last id of the array containing all the nodes with id_array[array_length(id_array,1)] = 5
nodes_affected as (
    select * from base_qry 
    where id_array[array_length(id_array,1)] = 5
    order by array_length(id_array,1) desc
    LIMIT 1)
  1. Find all the tree breanches than contribute to changed nodes (check here the filter for node id=5)
all_combinations as (
    select b.id, b.parent_id, b.value, b.id_array from
        base_qry b join nodes_affected n 
        on ARRAY[n.id_array] && ARRAY[b.id_array]
    where (b.id_array[array_length(b.id_array,1)] = 5 
        or b.id_array @> ARRAY[5] = false)
 )

aggregating up

select id_array[1]::int id, sum(value)
from all_combinations where id not in (select parent_id from all_combinations where parent_id is not null)
group by id_array[1]::int
order by 1

Whole query

with recursive base_qry as (
    select id, 
        parent_id,
        value,
        ARRAY[id] as id_array
    from hierarchy 
    union all 
    select h.id,
    h.parent_id,
    h.value,
    id_array || h.id as id_array 
    from hierarchy h join base_qry b on h.parent_id = b.id and h.value is not null
    ),
nodes_affected as (
    select * from base_qry 
    where id_array[array_length(id_array,1)] = 5
    order by array_length(id_array,1) desc
    LIMIT 1),
all_combinations as (
    select b.id, b.parent_id, b.value, b.id_array from
        base_qry b join nodes_affected n 
        on ARRAY[n.id_array] && ARRAY[b.id_array]
    where (b.id_array[array_length(b.id_array,1)] = 5 
        or b.id_array @> ARRAY[5] = false)
 )
select id_array[1]::int id, sum(value)
from all_combinations where id not in (select parent_id from all_combinations where parent_id is not null)
group by id_array[1]::int
order by 1
;
user_76057620

Start from the leafs and traverse all the nodes the leaf contributes to up the hierachy. Then just sum all contributions to a node.

WITH RECURSIVE cte AS ( 
         SELECT id, parent_id, value
         FROM hierarchy h1
         WHERE not exists (select 1 from hierarchy h2 where h2.parent_id = h1.id) 
             UNION ALL
         SELECT h.id, h.parent_id, case when h.value is null then 0 else cte.value end 
         FROM hierarchy h
         JOIN cte ON (cte.parent_id = h.id) 
) 

select h.id, h.name, v.value
from (
   select id, sum(value) as value
   from cte
   group by id
) v
join hierarchy h on h.id = v.id
order by h.id;

db<>fiddle

user_62199790

You can use a recursive CTE to get all nodes and their paths, and then for every non-leaf node in hierarchy, you can join the CTE back to hierarchy on the condition that the current hierarchy row id exists in the path and sum the values:

with recursive cte(id, p, n, v, t) as (
   select h.*, concat('[', h.id::text) from hierarchy h where h.parent_id is null
   union all
   select h.id, h.parent_id, h.name, h.value, concat(c.t, ', ', h.id)
   from cte c join hierarchy h on c.id = h.parent_id
)
select h.id, sum(c.v)
from hierarchy h join cte c on c.id != h.id and exists (select 1 from jsonb_array_elements(concat(c.t, ']')::jsonb) v where v.value::text = h.id::text) 
group by h.id order by h.id

Output:

id  sum
1   79
2   5
4   44
user_73267380
Related