4

私は複雑な SQL クエリを生成することに特に慣れておらず、ネットワーク トラバーサル用の再帰クエリを考案する際に、手続き型言語とセットベースの操作の理解を組み合わせるのに苦労しています。有向グラフの深さ優先検索を実行して、特定のノードの「上流」にある一連のエッジを見つけたいと考えています (各ノードには複数の上流エッジを含めることができます)。これを SQL で実装するのが理想的です。

私がやりたいことの擬似コードは次のようになります。

interesting_pipes = Pipes[]

func find_all_pipes_upstream(node n)
 if is_inlet(nodename)
    return Nil
 else
   for p in upstream_pipes:
     if p in interesting_pipes:
       return Nil
   else
     interesting_pipes.append(p)
     find_all_pipes_upstream(upstream_node(p))

純粋な SQL で次の関数を既に作成しました。

upstream_pipes(node_name varchar) RETURNS SETOF "Pipes"
upstream_node(pipe_name varchar) RETURNS "Node"
is_inlet(node_name) RETURNS boolean

WITH RECURSIVEしかし、上記の疑似コードを PostgreSQLクエリまたは PL/pgSQL 関数に変換するときに、スコープと戻り値の型を管理する方法を理解するのに苦労しています。私が見たWITH RECURSIVEクエリの例のほとんどは、各ノードが親を 1 つしか持たないツリーをトラバースするために考案されたものです。これについての最善の方法について、誰かヒント/アドバイスはありますか?

乾杯、

意思

4

1 に答える 1

4

見る：

http://www.postgresql.org/docs/8.4/static/queries-with.html

リンク関係にサイクルが含まれている場合、このクエリはループします。「深さ」の出力が必要なため、UNION ALL を UNION に変更するだけでは、ループは解消されません。代わりに、リンクの特定のパスをたどっているときに、同じ行に再び到達したかどうかを認識する必要があります。ループが発生しやすいクエリに 2 つの列パスとサイクルを追加します。

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;
于 2010-08-11T12:04:16.457 に答える