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

Hi
It may not be the most elegant solution but....works!

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)
), parcial_weight as
(
select a.path,sum(b.weight) as sum_weight
from pizza as a cross join pizza as b
where b.path ilike a.path || '%'
group by 1
order by path

)
select a.path, a.ingredient, a.quantity, a.rel_qty, a.unit,
a.weight,b.sum_weight as partial_ weigh,sum(a.weight) over() as total_weight
from pizza as a
left join parcial_weight as b on a.path=b.path
order by a.path;

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

El mié., 20 de jun. de 2018 a la(s) 10:54, Alban Hertroys (
haramrae(at)gmail(dot)com) escribió:

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

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