recursive WITH nested union ALL with NOCYCLE logic - Mailing list pgsql-sql

From Michael Moore
Subject recursive WITH nested union ALL with NOCYCLE logic
Date
Msg-id CACpWLjOS8euH8gAVYQWAfxhgBNvsfKwm1BvBLXyZwzFOpwUMLQ@mail.gmail.com
Whole thread Raw
Responses Re: recursive WITH nested union ALL with NOCYCLE logic
List pgsql-sql
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. 

In the mike_hier table note that:
aaa is the top of my target hierarchy with a children; bbb and ccc
However, from mike_map (see below) , we see that there are two alternative hierarchies for aaa, namely ddd, and eee .
 

CREATE TABLE mike_hier
(
  key character(3) NOT NULL,
  val character varying(5),
  parent character(3),
  CONSTRAINT key PRIMARY KEY (key)
);
INSERT INTO mike_hier( key, val, parent) VALUES  
('aaa','tom',''),
('bbb','cat','aaa'),
('ccc','tad','aaa'),
('ddd','cow',''),
('eee','rat','ddd'),
('fff','fan','ddd'),
('ggg','ram','eee'),
('hhh','sam',''),
('iii','ted','hhh'),
('jjj','abe','hhh'),
('kkk','red',''),
('lll','blu','kkk'),
('mmm','yl','kkk');

CREATE TABLE mike_map
(
  key character(3) NOT NULL,
  child character(3),
  parent character(3),
  CONSTRAINT key_const PRIMARY KEY (key)
);
insert into mike_map (key,child,parent) values
('111','ddd','aaa'),
('222','eee','aaa'),
('333','hhh','kkk');

I got pretty much what I want with :
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;

So far so good, but what if I introduce a data loop?
insert into mike_map (key,child,parent) values
('555','aaa','aaa');

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (        SELECT g.id, g.link, g.data, 1,          ARRAY[g.id],          false        FROM graph g      UNION ALL        SELECT g.id, g.link, g.data, sg.depth + 1,          path || g.id,          g.id = ANY(path)        FROM graph g, search_graph sg        WHERE g.id = sg.link AND NOT cycle
)
SELECT * FROM search_graph;
I can't figure out how to work this ARRAY concept into my existing query since I am not actually JOINing in the recursive part of my query. 


pgsql-sql by date:

Previous
From: Tom Lane
Date:
Subject: Re: Enhancement to SQL query capabilities
Next
From: "David G. Johnston"
Date:
Subject: Re: recursive WITH nested union ALL with NOCYCLE logic