sql - 使用sql检测循环

Question

我想检测层次结构中的潜在循环。我有三个表，每个表都有一个父列和一个子列:

Table1 包含一些节点(在 child 列中)及其父节点(在 parent 列中)； Table2 包含 Table1 的所有父级(在 child 列中)及其父级(在 parent 列中)，依此类推。

例如，如果 A 是 B 的 child ，B 是 C 的 child ，C 是 A 的 child ，那么我有一个循环。

是否可以使用 sql 命令检测循环？

Answer 1

这是一个适用于任意深度的解决方案。

将所有关系存储在一张表中:

   Table t
Parent | Child
------ | -----
B      | A
C      | B
A      | C
E      | D
F      | E

然后你可以使用这个WITH RECURSIVE查询查找周期:

WITH RECURSIVE working(parent, last_visited, already_visited, cycle_detected) AS (
  SELECT parent, child, ARRAY[parent], false FROM t
  UNION ALL
  SELECT t.parent, t.child, already_visited || t.parent, t.parent = ANY(already_visited)
  FROM t
  JOIN working ON working.last_visited = t.parent
  WHERE NOT cycle_detected
)
SELECT parent, already_visited FROM working WHERE cycle_detected

Fiddle

它将为您提供作为循环一部分的父级，以及它们所在的循环:

A | A,C,B,A
B | B,A,C,B
C | C,B,A,C

它是这样工作的(因为这是关键字 RECURSIVE 指示 Postgres 执行的操作):

1. 运行第一个 SELECT，从表 t 中选择所有条目并将它们放入名为 working 的临时表中。
2. 然后运行第二个 SELECT，将 working 表与表 t 连接起来，以查找每个条目的子项。这些 child 被添加到已经看到的 child 的数组中。
3. 现在一次又一次地运行第二个 SELECT，只要将条目添加到 working 表中即可。
4. 当其中一个条目访问它之前访问过的子项(t.parent = ANY(already_visited))时检测到循环，在这种情况下 cycle_detected 已设置为 true，不再向条目中添加子项。