Обсуждение: recursive WITH nested union ALL with NOCYCLE logic

I have two tables, 1 is a hierarchical table and the other a map to alternative hierarchies. Given a starting node, I need to be able to return the hierarchy and all related hierarchies. 

with

    recursive inn_t(keyv, val, parent) as (

       select * from (

          select key as keyv, val, parent 

             from mike_hier hi where hi.key ='aaa'

          union all

            -- get all alt hierarchies

            select child ,null ,null from mike_map ma  where ma.parent ='aaa' ) gg

    union all

    (

       with xxx as ( select * from inn_t i ) -- only a single reference allowed to inn_t

         select * from 

          (

          select mh.key     , mh.val        , mh.parent 

           from mike_hier mh

           where  mh.parent in (select keyv from xxx) -- normally would join inn_t

          union all

           select child ,null ,null 

           from mike_map ma  

           where ma.parent in (select keyv from xxx)  -- normally would join inn_t

          ) unionall

      )

     ) 

   select distinct * from inn_t where val is not null;

On Fri, Mar 18, 2016 at 2:06 PM, Michael Moore <michaeljmoore@gmail.com> wrote:

I have two tables, 1 is a hierarchical table and the other a map to alternative hierarchies. Given a starting node, I need to be able to return the hierarchy and all related hierarchies. 

with

    recursive inn_t(keyv, val, parent) as (

       select * from (

          select key as keyv, val, parent 

             from mike_hier hi where hi.key ='aaa'

          union all

            -- get all alt hierarchies

            select child ,null ,null from mike_map ma  where ma.parent ='aaa' ) gg

    union all

    (

       with xxx as ( select * from inn_t i ) -- only a single reference allowed to inn_t

         select * from 

          (

          select mh.key     , mh.val        , mh.parent 

           from mike_hier mh

           where  mh.parent in (select keyv from xxx) -- normally would join inn_t

          union all

           select child ,null ,null 

           from mike_map ma  

           where ma.parent in (select keyv from xxx)  -- normally would join inn_t

          ) unionall

      )

     ) 

   select distinct * from inn_t where val is not null;

Where should I send the bill for the pain relievers :)

​with recursive --applies to the second CTE really but placed at the top by convention (maybe by rule)

inn_t(keyv, val, parent) as (  --not recursive, no reference to inn_t in this CTE

-- Given a base tree lets return all rows where it is the primary...

       select * from (

          select key as keyv, val, parent 

             from mike_hier hi where hi.key ='aaa'

-- ...as well as the primary rows for any of its alises (derived though they may be it should work)

          union all

            -- get all alt hierarchies

            select child ,null ,null from mike_map ma  where ma.parent ='aaa' ) gg

), recurse_here_instead AS (

-- Now for each of the those primary rows locate in mike_heir locate the direct descendants

-- and add them to the working set.  On the next pass the original parents will be skipped

-- because they were already processed but all of these newly added children will be

-- put through the wringer to find their children.

         select * from inn_t i   --initial condition is a complex query so simplify the recursive portion by referecing a CTE

         UNION ALL

          select mh.key     , mh.val        , mh.parent 

           from mike_hier mh

           join inn_t ON (mh.parent = inn_t.keyv)

)

-- got rid of distinct...honestly not positive why but I suspect if you write the query correct DISTINCT on the outer layer should

-- be redundant.

   select * from recurse_here_instead where val is not null;

​I haven't yet coded a variation of this query that used the path array and cycle-avoidance logic so I'm leaving that open for the moment.  Now that this is written more correctly incorporating that from other's examples should be easier.

David J.

​

​

​

David,

If I am understanding you correctly, you are assuming that alternative hierarchies are mapped to only ROOT level hierarchies. It's a reasonable assumption on your part given my illustration only covered this use case. But lets add another mapping.

insert into mike_map (key,child,parent) values

('555','kkk','bbb');

This creates an alternative hierarchy that branches from a CHILD (bbb) of the ROOT (aaa) hierarchy.

So I think I still need the UNION ALL inside the recursive part. 

On Fri, Mar 18, 2016 at 4:11 PM, Michael Moore <michaeljmoore@gmail.com> wrote:

David,

If I am understanding you correctly, you are assuming that alternative hierarchies are mapped to only ROOT level hierarchies. It's a reasonable assumption on your part given my illustration only covered this use case. But lets add another mapping.

insert into mike_map (key,child,parent) values

('555','kkk','bbb');

This creates an alternative hierarchy that branches from a CHILD (bbb) of the ROOT (aaa) hierarchy.

So I think I still need the UNION ALL inside the recursive part. 

​You are correct about my assumed premise - and I'm not sure I want to deal with the brain damage that would result from exploring the model you are working with...

​If you can change how you model "mike_map" this should be workable.

The following provides the desired result for the original data as well as, I think, the correct result when adding you kkk/bbb alias.

I think this gets you closer..but probably not all of the way to your goal.

My specific concern is that none of these queries (including your original) have considered "ddd,cow,null" as a valid result...because it lacks a parent.

I'll leave to you to copy-paste and make it readable...

​WITH recursive

mike_map_alt (parent, children) AS (

--using an array here is probably not mandatory but makes the logic below simpler by use of unnest()

VALUES ('aaa',ARRAY['ddd','eee']::text[]), ('bbb',ARRAY['kkk']::text[])

), mike_hier_aliased AS (

--here we "canonical-ize" the data so that for each row we know which direct aliases are in play

SELECT mh.key::text AS key, mh.val, mh.parent::text AS parent, 

mh.key::text || COALESCE(mp.children, ARRAY[]::text[]) AS key_aliases,

mh.parent::text || COALESCE(mk.children, ARRAY[]::text[]) AS parent_aliases

FROM mike_hier mh

LEFT JOIN mike_map_alt mp ON (mh.key = mp.parent)

LEFT JOIN mike_map_alt mk ON (mh.parent = mk.parent)

)

--SELECT * FROM mike_hier_aliased  --used for debugging the transformed data

, recursive_part (my_key, my_val, my_parent) AS (

-- unnest the for the original row output the value; we start at the root so parent should be null for all records

-- for aliases we don't know what their root entry is yet so simply record null for value

-- and let the first iteration pick up the real record

-- this could be altered to left join the mike_heir_aliased table records containing null parents

-- and coalesce the joined "val" column.  This would cause "cow" from the "ddd' record to be added to the

-- initial "ddd" unnested alias record.

SELECT me_key, CASE WHEN key = me_key THEN val ELSE null::text END AS my_val, null::text AS my_parent FROM (

SELECT *, unnest(key_aliases) AS me_key FROM mike_hier_aliased WHERE mike_hier_aliased.key = 'aaa'

) src

-- on each iteration we again have to look for aliases and create

-- dummy records for them (via unnest) for the next iteration

UNION  --let the recursive part take care of duplicates

SELECT me_key, 

CASE WHEN key = me_key THEN val ELSE null::text END AS my_val, 

CASE WHEN key = me_key THEN parent ELSE null::text END AS my_parent 

FROM (

SELECT mha.key, mha.val, mha.parent, unnest(mha.key_aliases) AS me_key

FROM mike_hier_aliased mha

JOIN recursive_part rp

ON (rp.my_key = mha.parent)  --fails to match mha.(ddd,cow,null) though rp.(ddd,null,null) is present

) rec_src

)

SELECT * FROM recursive_part WHERE my_val IS NOT NULL

​--our dummy records all have null for my_val so lets remove them

​

David J.