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

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