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

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

On 06/19/2018 01:14 PM, Hellmuth Vargas 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 <http://recipe.name&gt;, 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 <http://recipe.name&gt; =
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)

This is gorgeous but I suspect any level greater than 10 wide will
present sorting problems, no?  Maybe a fixed two-digit, zero filled
number per level? Pushing the problem off by an order of magnitude :)
An exercise left to the OP perhaps.

*Hi*

This is gorgeous but I suspect any level greater than 10 wide will present
sorting problems, no?

*no, it should not be inconvenient*

Maybe a fixed two-digit, zero filled number per level?

*neither*

Pushing the problem off by an order of magnitude :)
An exercise left to the OP perhaps.

El mar., 19 de jun. de 2018 a la(s) 14:52, Rob Sargent (
robjsargent@gmail.com) escribió:

On 06/19/2018 01:14 PM, Hellmuth Vargas 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)

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

On 19 Jun 2018, at 21:14, Hellmuth Vargas <hivs77@gmail.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)

That is certainly an interesting solution and it begs the question whether a text field ('path') is actually the right representation of the hierarchy (some type of array would seem to be a better fit). Good out-of-the-box thinking!
This is probably usable for my actual case, so thanks for that, wouldn't have thought of it myself (even though I already had all the right "bits" in place!).

On the more theoretical front: The question remains whether it is possible to calculate fields in post-order tree traversal. I think that would be a semantically proper way to express this type of problem and it wouldn't need the kinds of pre/post-processing that after-the-fact aggregation (like in above solution) requires. So, leaner, and probably faster.
That implies that the SQL committee thought of the possibility in the first place though, which I'm beginning to doubt...

El mar., 19 de jun. de 2018 a la(s) 11:49, Hellmuth Vargas (hivs77@gmail.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@gmail.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.

Regards,

Alban Hertroys
--
If you can't see the forest for the trees,
cut the trees and you'll find there is no forest.

On 06/19/2018 02:05 PM, Alban Hertroys wrote:

On the more theoretical front: The question remains whether it is possible to calculate fields in post-order tree traversal. I think that would be a semantically proper way to express this type of problem and it wouldn't need the kinds of pre/post-processing that after-the-fact aggregation (like in above solution) requires. So, leaner, and probably faster.
That implies that the SQL committee thought of the possibility in the first place though, which I'm beginning to doubt...

If this interests you, you might enjoy this StackOverflow question:

https://stackoverflow.com/questions/35956486/generate-nested-json-with-couting-in-postgresql

Briefly, how do you construct a nested JSON structure from a recursive
CTE? The only answers at that link rely on plpgsql, but of course that
is cheating. :-) I took a stab at it a couple years ago but couldn't
figure it out, and it seemed like post-order processing was exactly the
missing piece.

If anyone has any ideas I'd be intrigued to hear them!

--
Paul ~{:-)
pj@illuminatedcomputing.com

how the fuck i unsubscribe to this mailing list , i get more than 100 emails a day

Bye

________________________________
From: Paul Jungwirth <pj@illuminatedcomputing.com>
Sent: Wednesday, June 20, 2018 2:31 AM
To: pgsql-general@lists.postgresql.org
Subject: Re: Is postorder tree traversal possible with recursive CTE's?

On 06/19/2018 02:05 PM, Alban Hertroys wrote:

On the more theoretical front: The question remains whether it is possible to calculate fields in post-order tree traversal. I think that would be a semantically proper way to express this type of problem and it wouldn't need the kinds of pre/post-processing that after-the-fact aggregation (like in above solution) requires. So, leaner, and probably faster.
That implies that the SQL committee thought of the possibility in the first place though, which I'm beginning to doubt...

If this interests you, you might enjoy this StackOverflow question:

https://stackoverflow.com/questions/35956486/generate-nested-json-with-couting-in-postgresql

Briefly, how do you construct a nested JSON structure from a recursive
CTE? The only answers at that link rely on plpgsql, but of course that
is cheating. :-) I took a stab at it a couple years ago but couldn't
figure it out, and it seemed like post-order processing was exactly the
missing piece.

If anyone has any ideas I'd be intrigued to hear them!

--
Paul ~{:-)
pj@illuminatedcomputing.com

how the fuck i unsubscribe to this mailing list , i get more than 100 emails a day

Bye

________________________________
From: Alban Hertroys <haramrae@gmail.com>
Sent: Wednesday, June 20, 2018 2:05 AM
To: Hellmuth Vargas
Cc: pgsql-general@postgresql.org
Subject: Re: Is postorder tree traversal possible with recursive CTE's?

On 19 Jun 2018, at 21:14, Hellmuth Vargas <hivs77@gmail.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)

That is certainly an interesting solution and it begs the question whether a text field ('path') is actually the right representation of the hierarchy (some type of array would seem to be a better fit). Good out-of-the-box thinking!
This is probably usable for my actual case, so thanks for that, wouldn't have thought of it myself (even though I already had all the right "bits" in place!).

On the more theoretical front: The question remains whether it is possible to calculate fields in post-order tree traversal. I think that would be a semantically proper way to express this type of problem and it wouldn't need the kinds of pre/post-processing that after-the-fact aggregation (like in above solution) requires. So, leaner, and probably faster.
That implies that the SQL committee thought of the possibility in the first place though, which I'm beginning to doubt...

El mar., 19 de jun. de 2018 a la(s) 11:49, Hellmuth Vargas (hivs77@gmail.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@gmail.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.

Regards,

Alban Hertroys
--
If you can't see the forest for the trees,
cut the trees and you'll find there is no forest.

On 19 June 2018 at 21:14, Hellmuth Vargas <hivs77@gmail.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@gmail.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@gmail.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.

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@gmail.com) escribió:

On 19 June 2018 at 21:14, Hellmuth Vargas <hivs77@gmail.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@gmail.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@gmail.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