PostgreSQL SQL 或 PL/pgSQL 查询，用于遍历有向图并返回找到的所有边

Question

我不太习惯生成复杂的 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都是为了遍历树而设计的，其中每个节点只有一个父节点。有没有人对如何最好地解决这个问题有任何提示/建议？

干杯，

将要

Answer 1

看：

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;