使用 RECURSIVE 查询来选择最长的路径

Question

WITH RECURSIVE我是PostgreSQL 的新手。我有一个相当标准的递归查询，它遵循邻接列表。如果我有，例如：

1 -> 2
2 -> 3
3 -> 4
3 -> 5
5 -> 6

它产生：

1
1,2
1,2,3
1,2,3,4
1,2,3,5
1,2,3,5,6

我想要的是：

1,2,3,4
1,2,3,5,6

但我不知道如何在 Postgres 中做到这一点。这似乎是“选择最长的路径”或“选择不包含在另一条路径中的路径”。我也许可以看到如何通过连接本身来做到这一点，但这似乎效率很低。

一个示例查询是：

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;

Answer 1

您已经有了一个触手可及的解决方案cycle，只需在末尾添加一个谓词即可。

但是将你的中断条件调整一级，目前你附加的一个节点太多了：

WITH RECURSIVE search AS (
   SELECT id, link, data, ARRAY[g.id] AS path, (link = id) AS cycle
   FROM   graph g
   WHERE  NOT EXISTS (SELECT FROM graph WHERE link = g.id)

   UNION ALL
   SELECT g.id, g.link, g.data, s.path || g.id, g.link = ANY(s.path)
   FROM   search s
   JOIN   graph g ON g.id = s.link
   WHERE  NOT s.cycle
   )
SELECT *
FROM   search
WHERE cycle;
-- WHERE cycle IS NOT FALSE;  -- alternative if link can be NULL

• 还包括@wildplasser 提到的启动条件。

• 的初始化条件cycle是 (link = id) 捕获快捷循环。CHECK如果您的表中有不允许这样做的约束，则没有必要。

• 确切的实施取决于缺失的细节。

• 这是假设所有图都以循环 or 终止，并且同一个表中link IS NULL存在从link到 的FK 约束。id确切的实施取决于缺失的细节。如果link实际上不是链接（没有引用完整性），则需要适应......