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查询示例都是为遍历每个节点只有一个父节点的树而设计的。有没有人有任何提示/建议如何最好地解决这个问题？

干杯，

将要

4

1 回答 1

4

看：

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

如果链接关系包含循环，则此查询将循环。因为我们需要“深度”输出，所以仅将 UNION ALL 更改为 UNION 不会消除循环。相反，我们需要识别在遵循特定链接路径时是否再次到达同一行。我们将两列路径和循环添加到容易循环的查询中：

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 回答