使用 sql 检测循环

Question

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

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

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

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

Answer 1

您的任务中的表之间存在非常奇怪的引用。然而，这是我检查现有循环的方法。

表 1 的示例：

CREATE OR REPLACE FUNCTION fn_table1_check() RETURNS trigger
LANGUAGE plpgsql
AS $$
DECLARE
BEGIN
  PERFORM 1 FROM table2
    JOIN table3 ON table3.parent=table2.child
  WHERE table2.parent=NEW.child AND table3.child=NEW.parent
  LIMIT 1;
  IF FOUND THEN
    RAISE EXCEPTION 'Found recursive loop!';
  END IF;
  RETURN NEW;
END;
$$;
CREATE TRIGGER tg_table1_check BEFORE INSERT OR UPDATE ON table1 FOR EACH ROW EXECUTE PROCEDURE fn_table1_check();

Answer 2

按照您现在构建表格的方式，以下 SQL 应该有效：

SELECT * FROM Table1
INNER JOIN Table2 on Table1.child = Table2.parent
INNER JOIN Table3 on Table2.child = Table3.parent
WHERE Table1.parent = Table3.child;

Answer 3

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

将所有关系存储在一个 table:

   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

它将为您提供作为循环一部分的 parents，以及它们所在的循环：

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

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

运行第一个 SELECT，从 table t 中选择所有条目并将它们放置在名为 working 的临时 table 中。
然后运行第二个 SELECT，加入 working table 与 table t 以找到 child每个条目的任。那些 children 被添加到已经看到的数组 children.
现在运行第二个SELECT周而复始，只要条目都加到workingtable.
当其中一个条目访问它之前访问过的 child 时检测到一个循环 (t.parent = ANY(already_visited)) 在这种情况下 cycle_detected 设置为 true 并且不再 children被添加到条目中。

使用 sql 检测循环

Detect cycles using sql

sql

postgresql

hierarchical-data