Обсуждение: Recursive Parent-Child Function Bottom Up

IMPORTANT - This email and any attachments is intended for the above named addressee(s), and may contain information which is confidential or privileged. If you are not the intended recipient, please inform the sender immediately and delete this email: you should not copy or use this e-mail for any purpose nor disclose its contents to any person.

@font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4;}@font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4;}p.MsoNormal, li.MsoNormal, div.MsoNormal {margin:0cm; margin-bottom:.0001pt; text-align:right; direction:rtl; unicode-bidi:embed; font-size:11.0pt; font-family:"Calibri",sans-serif;}a:link, span.MsoHyperlink {mso-style-priority:99; color:#0563C1; text-decoration:underline;}a:visited, span.MsoHyperlinkFollowed {mso-style-priority:99; color:#954F72; text-decoration:underline;}span.EmailStyle17 {mso-style-type:personal-compose; font-family:"Calibri",sans-serif; color:windowtext;}.MsoChpDefault {mso-style-type:export-only; font-family:"Calibri",sans-serif;}div.WordSection1 {page:WordSection1;}

Hi,

 

I would like to populate the children_ids column with all the ids of the children recursively (+ grandchildren etc.)

If I do it top-bottom I will end up doing extra work since there is no need to go all levels down if I can just compute my IMMEDIATE children "children_ids" and just concatenate all their lists.

 

I looked at https://stackoverflow.com/questions/41376655/how-can-i-traverse-a-tree-bottom-up-to-calculate-a-weighted-average-of-node-va

But was not able to get it to work on my case.  

 

Your assistance is most welcome!

 

 

create table tree(id int primary key, parent int, children_ids text);

insert into tree (id, parent) values

(273,   0),

(274,      273),

(275,      273),

(277,      273),

(278,      277),

(280,      275),

(281,      280),

(282,      281),

(283,      282),

(284,      282),

(285,      282),

(286,      282),

(287,      282),

(288,      282),

(289,      282),

(290,      281),

(291,      290),

(292,      290),

(293,      290),

(294,      290),

(295,      290);

IMPORTANT - This email and any attachments is intended for the above named addressee(s), and may contain information which is confidential or privileged. If you are not the intended recipient, please inform the sender immediately and delete this email: you should not copy or use this e-mail for any purpose nor disclose its contents to any person.

I'm sorry, what output format are you looking for?  Perhaps an array of all descendants for each founder? (founder int, descendants int[]).   I recommend a null for no-known-parent rather than zero.  Or just founder int, descendant int? With or without sub-trees?

@font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4;}@font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4;}p.MsoNormal, li.MsoNormal, div.MsoNormal {margin:0cm; margin-bottom:.0001pt; text-align:right; direction:rtl; unicode-bidi:embed; font-size:11.0pt; font-family:"Calibri",sans-serif;}a:link, span.MsoHyperlink {mso-style-priority:99; color:#0563C1; text-decoration:underline;}a:visited, span.MsoHyperlinkFollowed {mso-style-priority:99; color:#954F72; text-decoration:underline;}span.EmailStyle17 {mso-style-type:personal-compose; font-family:"Calibri",sans-serif; color:windowtext;}.MsoChpDefault {mso-style-type:export-only; font-family:"Calibri",sans-serif;}div.WordSection1 {page:WordSection1;}

Hi,

 

I would like to populate the children_ids column with all the ids of the children recursively (+ grandchildren etc.)

If I do it top-bottom I will end up doing extra work since there is no need to go all levels down if I can just compute my IMMEDIATE children "children_ids" and just concatenate all their lists.

 

I looked at https://stackoverflow.com/questions/41376655/how-can-i-traverse-a-tree-bottom-up-to-calculate-a-weighted-average-of-node-va

But was not able to get it to work on my case.  

 

Your assistance is most welcome!

 

 

create table tree(id int primary key, parent int, children_ids text);

insert into tree (id, parent) values

(273,   0),

(274,      273),

(275,      273),

(277,      273),

(278,      277),

(280,      275),

(281,      280),

(282,      281),

(283,      282),

(284,      282),

(285,      282),

(286,      282),

(287,      282),

(288,      282),

(289,      282),

(290,      281),

(291,      290),

(292,      290),

(293,      290),

(294,      290),

(295,      290);

IMPORTANT - This email and any attachments is intended for the above named addressee(s), and may contain information which is confidential or privileged. If you are not the intended recipient, please inform the sender immediately and delete this email: you should not copy or use this e-mail for any purpose nor disclose its contents to any person.

oops, didn't see the third column in the create table statement.

> On 26 Jul 2021, at 17:19, Avi Weinberg <AviW@gilat.com> wrote:
>
> Hi,
>
> I would like to populate the children_ids column with all the ids of the children recursively (+ grandchildren etc.)
> If I do it top-bottom I will end up doing extra work since there is no need to go all levels down if I can just
computemy IMMEDIATE children "children_ids" and just concatenate all their lists.  

(…)

> create table tree(id int primary key, parent int, children_ids text);
> insert into tree (id, parent) values
> (273,   0),
> (274,      273),
> (275,      273),
> (277,      273),
> (278,      277),
> (280,      275),
> (281,      280),
> (282,      281),
> (283,      282),
> (284,      282),
> (285,      282),
> (286,      282),
> (287,      282),
> (288,      282),
> (289,      282),
> (290,      281),
> (291,      290),
> (292,      290),
> (293,      290),
> (294,      290),
> (295,      290);

First you need to figure out what your starting set of nodes is, and since you’re going to go bottom-up, those are your
leafnodes. Without any indicators for that though, you’ll have to determine that from a sub-query. 

Something like this:

with recursive foo (id, parent, children_ids) as (
    select id, parent, null::text
      from tree t
     where not exists (
        select 1 from tree c where c.parent = t.id
     )
    union all
    select t.id, t.parent
    ,    f.id || case f.children_ids when '' then '' else ',’ end || f.children_ids
      from foo f
      join tree t on f.parent = t.id
     where f.parent <> 0
;

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 26 Jul 2021, at 17:52, Alban Hertroys <haramrae@gmail.com> wrote:
> Something like this:
>
> with recursive foo (id, parent, children_ids) as (
>     select id, parent, null::text
>       from tree t
>      where not exists (
>         select 1 from tree c where c.parent = t.id
>      )
>     union all
>     select t.id, t.parent
>     ,    f.id || case f.children_ids when '' then '' else ',’ end || f.children_ids
>       from foo f
>       join tree t on f.parent = t.id
>      where f.parent <> 0
> ;

Almost, the null::text in the initial select should of course be '’ in your case, and a unicode quote slipped into the
laststring of that case statement. 

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

On 26 Jul 2021, at 17:52, Alban Hertroys <haramrae@gmail.com> wrote:
Something like this:

with recursive foo (id, parent, children_ids) as (	select id, parent, null::text	  from tree t	 where not exists (		select 1 from tree c where c.parent = t.id	 )	union all	select t.id, t.parent	,	f.id || case f.children_ids when '' then '' else ',’ end || f.children_ids	  from foo f	  join tree t on f.parent = t.id	 where f.parent <> 0
;

Almost, the null::text in the initial select should of course be '’ in your case, and a unicode quote slipped into the last string of that case statement.

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

this might be what you want?
with recursive fulltree (id, parent, children_ids) as (
    select id, parent, id::text as decsendants
      from tree t
     where not exists (
        select 1 from tree c where c.parent = t.id
     )
    union all
    select t.id,
           t.parent,   
           f.id  || case f.children_ids when '' then '' else ',' end || f.children_ids as descendants
      from fulltree f
      join tree t on f.parent = t.id
      where f.parent != 0
)
select * from fulltree order by parent
;


I do think it breaks when there is more than one zero parent.

On 7/26/21 9:55 AM, Alban Hertroys wrote:
>> On 26 Jul 2021, at 17:52, Alban Hertroys <haramrae@gmail.com> wrote:
>> Something like this:
>>
>> with recursive foo (id, parent, children_ids) as (
>>     select id, parent, null::text
>>       from tree t
>>      where not exists (
>>         select 1 from tree c where c.parent = t.id
>>      )
>>     union all
>>     select t.id, t.parent
>>     ,    f.id || case f.children_ids when '' then '' else ',’ end || f.children_ids
>>       from foo f
>>       join tree t on f.parent = t.id
>>      where f.parent <> 0
>> ;
> Almost, the null::text in the initial select should of course be '’ in your case, and a unicode quote slipped into
thelast string of that case statement.
 
>
> Alban Hertroys
> --
> If you can't see the forest for the trees,
> cut the trees and you'll find there is no forest.
>
>
>
well actually I find this closer to the target.

with recursive kids (founder, firstoff, descendant )
as (select parent as founder, id as firstoff, id::text
      from tree
      where parent = 0
union all
select k.firstoff, t.id, t.id::text
from kids k join tree t on k.firstoff = t.parent
)
select founder, array_agg(descendant) as descendants
from kids group by founder
order by founder;
  founder |           descendants
---------+-------------------------------
        0 | {273}
      273 | {274,275,277}
      275 | {280}
      277 | {278}
      280 | {281}
      281 | {282,290}
      282 | {283,284,285,286,287,288,289}
      290 | {291,292,293,294,295}
(8 rows)