使用sql检测周期

Question

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

表1包含一些节点（在子列中）及其父节点（在父列中）；Table2 包含 Table1 的所有父级（在 child 列中）及其父级（在 parent 列中），依此类推。

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

是否可以使用 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

小提琴

它将为您parent提供属于循环的s 以及它们所在的循环：

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

它是这样工作的（因为这是关键字RECURSIVE指示 Postgres 做的事情）：

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