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

On 19 June 2018 at 21:14, Hellmuth Vargas <hivs77(at)gmail(dot)com> wrote:
>
> 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)

I just realized that this solution contains a problem. It only adds
weights at the top-level of the ingredients.
That works for this particular example, but not if, for example, a
'pizza bottom' contains 200.00g of 'dough' and 2.50g of 'carbon'.

The correct values in that case would be:
2: Pizza Bottom: 150 + 50 + 2.50 = 202.50g
2.2: Dough: 150 + 50 = 200 g
2.2.1: flour: 150 g
2.2.2: water: 50 g
2.2.3: salt: (null) g
2.3: Carbon: 2.50 g

What probably would work is to keep the path in an array and track the
(cumulative) sum at each depth in the path in another array. After
that, we can take the MAX of each array element using a similar window
function as in the original post, I think. The level of the tree would
then be the index into the array.

...Let's look at that tomorrow, before my head explodes ;)

> 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
>

--
If you can't see the forest for the trees,
Cut the trees and you'll see there is no forest.