PostgreSQLのSQLクエリは

Question

私はエッジを持った二つの列で、有向グラフのエッジを表して、私のPostgreSQLデータベース内テーブル： node_to node_fromと（値はノードのIDです）。

私はグラフ全体を横断できるようにしたいが、無向ようにしたい単一のノード（ initial_node ）を考えます。

私は何を意味以下のグラフのインスタンスのために、次のとおりです。

(a->b) 
(c->b) 
(c->d) 

initial_nodeはどのような場合には、、B、C、またはDであれば、私は〜,b,c,d]。

私は（http://www.postgresql.org/docs/8.4/static/queries-with.htmlに基づいて）次のSQLクエリを使用：

WITH RECURSIVE search_graph(uniq, depth, path, cycle) AS (
     SELECT 
      CASE WHEN g.node_from = 'initial_node' THEN g.node_to ELSE g.node_from END, 
      1, 
      CASE WHEN g.node_from = 'initial_node' THEN ARRAY[g.node_from] ELSE ARRAY[g.node_to] END, 
      false 
     FROM edges g 
     WHERE 'initial_node' in (node_from, node_to) 
     UNION ALL 
     SELECT 
      CASE WHEN g.node_from = sg.uniq THEN g.node_to ELSE g.node_from END, 
      sg.depth + 1, 
      CASE WHEN g.node_from = sg.uniq THEN path || g.node_from ELSE path || g.node_to END, 
      g.node_to = ANY(path) OR g.node_from = ANY(path) 
     FROM edges g, search_graph sg 
     WHERE sg.uniq IN (g.node_from, g.node_to) AND NOT cycle 
) 
SELECT * FROM search_graph 

それがうまく働いた...私はすべての方向に、全て一緒に接続されている12個のノードを持つケースを持っていたまでは（ペアごとに私は（a-> b）と（b-> a）の両方を持っているので、クエリループは無限になります。 （UNION ALLをUNIONに変更してもループが解消されるわけではありません。）

この問題を処理するアドバイスはありますか？

乾杯、

アントワーヌ。私はこれに着い

Answer 1

、それはあらゆる種類のデータで無限ループに入るべきではありません。

--create temp table edges ("from" text, "to" text); 
--insert into edges values ('initial_node', 'a'), ('a', 'b'), ('a', 'c'), ('c', 'd'); 

with recursive graph(points) as (
    select array(select distinct "to" from edges where "from" = 'initial_node') 
    union all 
    select g.points || e1.p || e2.p 
    from graph g 
    left join lateral (
    select array(
     select distinct "to" 
     from edges 
     where "from" =any(g.points) and "to" <>all(g.points) and "to" <> 'initial_node') AS p) e1 on (true) 
    left join lateral (
    select array(
     select distinct "from" 
     from edges 
     where "to" =any(g.points) and "from" <>all(g.points) and "from" <> 'initial_node') AS p) e2 on (true) 
    where e1.p <> '{}' OR e2.p <> '{}' 
) 
select distinct unnest(points) 
from graph 
order by 1 

再帰クエリは非常に選択することができるかという点で制限されている、と彼らは使用して許可していないので、副選択内の再帰的結果、NOT IN（select * from recursive where ...）を使用することはできません。 LEFT JOIN LATERALを使用し、= ANY（）と<> ALL（）を使用して結果を配列に格納すると、この問題が解決しました。