查询以查找循环引用

Question

我有两张桌子

ID  Task
1   1
2   2
3   3
4   4

Col1  depend
2     3
2     4
3     1
4     2

ID和Col1通过 FK 约束相关。我想找出所有循环引用。这里ID和Col1仅用于组合来自 2 个表的行，例如：

Task 1 can start anytime.
Task 2 can start only after completion of 3, 4 etc

1 –
2 – 3, 4, 1, 2   -- for 2 there is circular dependency
3 – 1
4 – 2, 3, 4      -- also circular dependency

案例2：

Col1  depend
2     3
2     4
3     1
4     5
5     2

ID  Task
1   1
2   2
3   3
4   4
5   5

1
2 – 3, 4, 1, 5, 2     -- circular reference
3 – 1
4 – 5, 2, 3, 4        -- circular reference
5 – 2, 3, 4, 5        -- circular reference

循环引用可以在任何递归级别使用。如何找到这样的循环引用？
我们尝试了递归查询，但我们进入了无限循环。如何为此编写递归查询？

Answer 1

我根据您的情况改编了http://www.postgresql.org/docs/8.4/static/queries-with.html中的示例：

WITH RECURSIVE search_graph(id, depends, depth, path, cycle) AS (
        SELECT g.Col1, g.depends, 1,
          ARRAY[g.Col1],
          false
        FROM deps g
      UNION ALL
        SELECT g.Col1, g.depends, sg.depth + 1,
          path || g.Col1,
          g.Col1 = ANY(path)
        FROM deps g, search_graph sg
        WHERE g.Col1 = sg.depends AND NOT cycle
)
SELECT distinct id FROM search_graph where cycle = true;

结果：

ID
 4
 2

对于第一个例子，

ID
 4
 2
 5

第二个

您可以在http://sqlfiddle.com/#!15/87a96/2找到 sql fiddle