PostgreSQL 如何用 WITH RECURSIVE 检测环（循环依赖）-SQL

PostgreSQL中WITH RECURSIVE检测环的核心逻辑是通过维护路径数组并在递归时用NOT next_id = ANY(path)过滤重复节点，被过滤即表明存在环；需显式记录path字段、排除已访问节点，并注意NULL、自环、多起点等细节。

什么是 WITH RECURSIVE 检测环的核心逻辑

PostgreSQL 的 WITH RECURSIVE 本身不直接提供“检测环”功能，而是靠在递归过程中显式记录路径（如数组），再用 @> 或 array_position() 判断当前节点是否已在路径中出现过。关键不是“有没有环”，而是“递归时能否及时发现重复访问”。

构建带路径追踪的递归 CTE

必须在递归查询中维护一个 path 字段（通常是 text[] 或 int[]），每次追加当前节点 ID，并在递归条件中排除已存在该 ID 的路径。

• 初始查询（non-recursive term）：把起点节点和单元素路径一起选出来，例如 ARRAY[dep_id]
• 递归查询（recursive term）：JOIN 依赖表后，用 path || next_id 扩展路径，且 WHERE 条件加上 NOT next_id = ANY(path)
• 如果某条路径因违反 NOT ... = ANY(path) 被过滤掉，说明此处尝试向下走会成环——这个“被过滤”就是环存在的证据

示例（假设依赖关系存于 deps(from_id, to_id)）：

WITH RECURSIVE walk AS (
  SELECT from_id, to_id, ARRAY[from_id] AS path
  FROM deps
  WHERE from_id = 1  -- 起点
  UNION ALL
  SELECT d.from_id, d.to_id, w.path || d.to_id
  FROM deps d
  JOIN walk w ON d.from_id = w.to_id
  WHERE NOT d.to_id = ANY(w.path)  -- 关键：防环
)
SELECT * FROM walk;

如何确认某个节点是否存在循环依赖

仅运行上面的 CTE 不足以回答“有没有环”，因为被过滤掉的分支不会输出。要确认环存在，需改用「找最长可能路径」或「对比可达节点数」策略。