Re: Is postorder tree traversal possible with recursive CTE's? - Mailing list pgsql-general

> 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
representationof 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
alreadyhad 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
kindsof 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
recursionreturns: 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
113g, 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.
Butsince this tends to be kept as a temporary materialized result set with no indices, that's not performing great and
itadds 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
usinga postorder tree traversal, the desired result would be readily available to pick up when the recursive CTE
travelsup 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
resultfor '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
pizzabottom'. 
>
> 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
wouldnot 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
quantitiesare 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
actuallyviable. 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.