Re: Is postorder tree traversal possible with recursive CTE's?

Hi

with partial sum:

with recursive pizza (name, step, ingredient, quantity, unit, rel_qty,
path, weight)
as (
select
name, step, ingredient, quantity, unit
, quantity::numeric(10,2)
, step::text
, case when unit = 'g' then quantity::numeric(10,2) else null
end
from recipe
where name = 'pizza'
union all
select
recipe.name, recipe.step, recipe.ingredient,
recipe.quantity, recipe.unit
, (pizza.rel_qty * recipe.quantity)::numeric(10,2)
, pizza.path || '.' || recipe.step
, case when recipe.unit = 'g' then (pizza.rel_qty *
recipe.quantity)::numeric(10,2) else null end
from pizza
join recipe on (recipe.name = pizza.ingredient)
)
select path, ingredient, quantity, rel_qty, unit, weight,*sum(weight)
over(partition by split_part(path,'.',1)) as parcial_weight*, *sum(weight)
over() as total_weight*
from pizza
order by path;

path | ingredient | quantity | rel_qty | unit | weight |
parcial_weight | total_weight
-------+--------------+----------+---------+-------+--------+----------------+--------------
1 | tomato sauce | 1.00 | 1.00 | pcs | |
113.00 | 313.00
1.1 | tomato | 100.00 | 100.00 | g | 100.00 |
113.00 | 313.00
1.2 | basil | 10.00 | 10.00 | g | 10.00 |
113.00 | 313.00
1.3 | salt | 3.00 | 3.00 | g | 3.00 |
113.00 | 313.00
2 | pizza bottom | 1.00 | 1.00 | pcs | |
200.00 | 313.00
2.2 | dough | 1.00 | 1.00 | pcs | |
200.00 | 313.00
2.2.1 | flour | 150.00 | 150.00 | g | 150.00 |
200.00 | 313.00
2.2.2 | water | 50.00 | 50.00 | g | 50.00 |
200.00 | 313.00
2.2.3 | salt | 1.00 | 1.00 | pinch | |
200.00 | 313.00
(9 rows)

El mar., 19 de jun. de 2018 a la(s) 11:49, Hellmuth Vargas (hivs77(at)gmail(dot)com)
escribió:

> Hi
>
> with recursive pizza (name, step, ingredient, quantity, unit, rel_qty,
> path, weight)
> as (
> select
> name, step, ingredient, quantity, unit
> , quantity::numeric(10,2)
> , step::text
> , case when unit = 'g' then quantity::numeric(10,2) else
> null end
> from recipe
> where name = 'pizza'
> union all
> select
> recipe.name, recipe.step, recipe.ingredient,
> recipe.quantity, recipe.unit
> , (pizza.rel_qty * recipe.quantity)::numeric(10,2)
> , pizza.path || '.' || recipe.step
> , case when recipe.unit = 'g' then (pizza.rel_qty *
> recipe.quantity)::numeric(10,2) else null end
> from pizza
> join recipe on (recipe.name = pizza.ingredient)
> )
> select path, ingredient, quantity, rel_qty, unit, weight, *sum(weight)
> over() as total_weight*
> from pizza
> order by path;
>
> path | ingredient | quantity | rel_qty | unit | weight | total_weight
> -------+--------------+----------+---------+-------+--------+--------------
> 1 | tomato sauce | 1.00 | 1.00 | pcs | | 313.00
> 1.1 | tomato | 100.00 | 100.00 | g | 100.00 | 313.00
> 1.2 | basil | 10.00 | 10.00 | g | 10.00 | 313.00
> 1.3 | salt | 3.00 | 3.00 | g | 3.00 | 313.00
> 2 | pizza bottom | 1.00 | 1.00 | pcs | | 313.00
> 2.2 | dough | 1.00 | 1.00 | pcs | | 313.00
> 2.2.1 | flour | 150.00 | 150.00 | g | 150.00 | 313.00
> 2.2.2 | water | 50.00 | 50.00 | g | 50.00 | 313.00
> 2.2.3 | salt | 1.00 | 1.00 | pinch | | 313.00
> (9 rows)
>
>
>
>
>
> El mar., 19 de jun. de 2018 a la(s) 08:39, Alban Hertroys (
> haramrae(at)gmail(dot)com) escribió:
>
>> Hi all,
>>
>> I'm struggling with a hierarchical query where I'm tasked to calculate
>> weights of items in an (exploded) Bill of Materials, based on the weights
>> of their components. Not all components are measured with a weight,
>> sometimes there are pieces, meters, areas, etc, and the hierarchy is of
>> varying levels of depth.
>>
>> It would help if I could track a sum() throughout the explosion that
>> would write back onto parent rows when the recursion returns: postorder
>> traversal.
>>
>> I created a simplified example about making pizza:
>>
>> CREATE TABLE ingredient (
>> name text NOT NULL
>> );
>>
>> CREATE TABLE recipe (
>> name text NOT NULL,
>> ingredient text NOT NULL,
>> quantity numeric(6,2) NOT NULL,
>> unit text NOT NULL,
>> step integer NOT NULL
>> );
>>
>> COPY ingredient (name) FROM stdin;
>> tomato
>> basil
>> salt
>> tomato sauce
>> flour
>> water
>> yeast
>> dough
>> pizza bottom
>> pizza
>> \.
>>
>> COPY recipe (name, ingredient, quantity, unit, step) FROM stdin;
>> tomato sauce tomato 100.00 g 1
>> dough flour 150.00 g 1
>> tomato sauce basil 10.00 g 2
>> pizza pizza bottom 1.00 pcs 2
>> tomato sauce salt 3.00 g 3
>> dough salt 1.00 pinch 3
>> pizza tomato sauce 1.00 pcs 1
>> pizza bottom dough 1.00 pcs 2
>> dough water 50.00 g 2
>> \.
>>
>> ALTER TABLE ONLY ingredient
>> ADD CONSTRAINT ingredient_pkey PRIMARY KEY (name);
>>
>> ALTER TABLE ONLY recipe
>> ADD CONSTRAINT recipe_pkey PRIMARY KEY (name, ingredient);
>>
>> ALTER TABLE ONLY recipe
>> ADD CONSTRAINT recipe_ingredient_fkey FOREIGN KEY (ingredient)
>> REFERENCES ingredient(name);
>>
>> ALTER TABLE ONLY recipe
>> ADD CONSTRAINT recipe_name_fkey FOREIGN KEY (name) REFERENCES
>> ingredient(name);
>>
>>
>> A query listing the recipe for 'pizza' would be as follows:
>> development=> with recursive pizza (name, step, ingredient, quantity,
>> unit, rel_qty, path, weight)
>> as (
>> select
>> name, step, ingredient, quantity, unit
>> , quantity::numeric(10,2)
>> , step::text
>> , case when unit = 'g' then quantity::numeric(10,2) else
>> null end
>> from recipe
>> where name = 'pizza'
>> union all
>> select
>> recipe.name, recipe.step, recipe.ingredient,
>> recipe.quantity, recipe.unit
>> , (pizza.rel_qty * recipe.quantity)::numeric(10,2)
>> , pizza.path || '.' || recipe.step
>> , case when recipe.unit = 'g' then (pizza.rel_qty *
>> recipe.quantity)::numeric(10,2) else null end
>> from pizza
>> join recipe on (recipe.name = pizza.ingredient)
>> )
>> select path, ingredient, quantity, rel_qty, unit, weight
>> from pizza
>> order by path;
>>
>> path | ingredient | quantity | rel_qty | unit | weight
>> -------+--------------+----------+---------+-------+--------
>> 1 | tomato sauce | 1.00 | 1.00 | pcs |
>> 1.1 | tomato | 100.00 | 100.00 | g | 100.00
>> 1.2 | basil | 10.00 | 10.00 | g | 10.00
>> 1.3 | salt | 3.00 | 3.00 | g | 3.00
>> 2 | pizza bottom | 1.00 | 1.00 | pcs |
>> 2.2 | dough | 1.00 | 1.00 | pcs |
>> 2.2.1 | flour | 150.00 | 150.00 | g | 150.00
>> 2.2.2 | water | 50.00 | 50.00 | g | 50.00
>> 2.2.3 | salt | 1.00 | 1.00 | pinch |
>> (9 rows)
>>
>>
>> With these results, I somehow need to calculate that the weights of
>> 'tomato sauce', 'dough' and 'pizza bottom' are 113 g, 200 g and 200 g
>> respectively, bringing the total weight of 'pizza' to 313 g.
>>
>> My first thought was to traverse the result of this recursive CTE using
>> another one, but in the opposite direction. But since this tends to be kept
>> as a temporary materialized result set with no indices, that's not
>> performing great and it adds a fair amount of complexity to the query too.
>>
>> Then I realised that if we somehow could track the sum() of 'weight'
>> throughout exploding these recipe items, by using a postorder tree
>> traversal, the desired result would be readily available to pick up when
>> the recursive CTE travels up through the hierarchy.
>>
>> In above example; When the CTE would reach '1.3 salt', it would write the
>> summed 'weight' value 113 back on the result for '1 tomato sauce' and when
>> it reached '2.2.2 salt' it would write back 200 to '2.2 dough' and then 200
>> to '2 pizza bottom'.
>>
>> Is that possible?
>>
>> I've seen a couple of "solutions" on the internet that just summed up the
>> results of the CTE, but that won't do as it would not put the correct
>> weights onto intermediate levels of the tree as far as I can see (in above,
>> the weight of 'dough').
>>
>>
>> Regards,
>>
>> Alban Hertroys
>>
>>
>> PS. Don't try to make pizza using this recipe, it probably won't succeed.
>> I forgot the yeast, for one thing, and quantities are probably way off. Not
>> to mention that there are probably more ingredients missing…
>>
>> PS2. In my real case the ingredients have a base quantity and unit, which
>> makes adjusting to relative quantities actually viable. Those aren't
>> necessary to describe the problem though.
>> --
>> If you can't see the forest for the trees,
>> cut the trees and you'll find there is no forest.
>>
>>
>>
>
> --
> Cordialmente,
>
> Ing. Hellmuth I. Vargas S.
> Esp. Telemática y Negocios por Internet
> Oracle Database 10g Administrator Certified Associate
> EnterpriseDB Certified PostgreSQL 9.3 Associate
>
>

--
Cordialmente,

Ing. Hellmuth I. Vargas S.
Esp. Telemática y Negocios por Internet
Oracle Database 10g Administrator Certified Associate
EnterpriseDB Certified PostgreSQL 9.3 Associate