在CTE中找到无限递归循环

Question

我不是SQL专家.如果有人可以帮助我通过.

我已经递归CTE来获取如下的值.

Child1 - > Parent 1

Parent1 - > Parent 2

Parent2 - > NULL

如果数据填充出错了,那么我将有类似下面的内容,因为CTE可能会进入无限递归循环并产生最大的递归错误.由于数据量很大,我无法手动检查这些不良数据.如果有办法找到它,请告诉我.

Child1 - > Parent 1

Parent1 - > Child1

要么

Child1 - > Parent 1

Parent1 - > Parent2

Parent2 - > Child1

Answer 1

使用Postgres,通过收集数组中的所有访问节点可以很容易地防止这种情况.

建立:

create table hierarchy (id integer, parent_id integer);

insert into hierarchy
values
(1, null), -- root element
(2, 1), -- first child
(3, 1), -- second child
(4, 3), 
(5, 4), 
(3, 5); -- endless loop

递归查询:

with recursive tree as (
  select id, 
         parent_id, 
         array[id] as all_parents
  from hierarchy
  where parent_id is null

  union all

  select c.id, 
         c.parent_id,
         p.all_parents||c.id
  from hierarchy c
     join tree p
      on c.parent_id = p.id 
     and c.id <> ALL (p.all_parents) -- this is the trick to exclude the endless loops
)
select *
from tree;

Answer 2

您尚未指定方言或列名，因此很难做出完美的示例...

-- Some random data
IF OBJECT_ID('tempdb..#MyTable') IS NOT NULL
    DROP TABLE #MyTable

CREATE TABLE #MyTable (ID INT PRIMARY KEY, ParentID INT NULL, Description VARCHAR(100))
INSERT INTO #MyTable (ID, ParentID, Description) VALUES
(1, NULL, 'Parent'), -- Try changing the second value (NULL) to 1 or 2 or 3
(2, 1, 'Child'), -- Try changing the second value (1) to 2 
(3, 2, 'SubChild')
-- End random data

;WITH RecursiveCTE (StartingID, Level, Parents, Loop, ID, ParentID, Description) AS
(
    SELECT ID, 1, '|' + CAST(ID AS VARCHAR(MAX)) + '|', 0, * FROM #MyTable
    UNION ALL
    SELECT R.StartingID, R.Level + 1, 
        R.Parents + CAST(MT.ID AS VARCHAR(MAX)) + '|',
        CASE WHEN R.Parents LIKE '%|' + CAST(MT.ID AS VARCHAR(MAX)) + '|%' THEN 1 ELSE 0 END,
        MT.*
        FROM #MyTable MT
        INNER JOIN RecursiveCTE R ON R.ParentID = MT.ID AND R.Loop = 0
)

SELECT StartingID, Level, Parents, MAX(Loop) OVER (PARTITION BY StartingID) Loop, ID, ParentID, Description 
    FROM RecursiveCTE 
    ORDER BY StartingID, Level

像这样的东西将显示递归 cte 中是否/哪里有循环。看看专栏Loop。使用原样的数据，没有循环。在评论中有关于如何更改值以导致循环的示例。

最后，递归 cteVARCHAR(MAX)以形式|id1|id2|id3|（称为Parents）创建一个id ，然后检查当前ID是否已经在该“列表”中。如果是，则将该Loop列设置为 1。此列在递归连接 (the ABD R.Loop = 0) 中进行检查。

结束查询使用 aMAX() OVER (PARTITION BY ...)将Loop整个“块”链的列设置为 1 。

稍微复杂一点，生成“更好”的报告：

-- Some random data
IF OBJECT_ID('tempdb..#MyTable') IS NOT NULL
    DROP TABLE #MyTable

CREATE TABLE #MyTable (ID INT PRIMARY KEY, ParentID INT NULL, Description VARCHAR(100))
INSERT INTO #MyTable (ID, ParentID, Description) VALUES
(1, NULL, 'Parent'), -- Try changing the second value (NULL) to 1 or 2 or 3
(2, 1, 'Child'), -- Try changing the second value (1) to 2 
(3, 3, 'SubChild')
-- End random data

-- The "terminal" childrens (that are elements that don't have childrens
-- connected to them)
;WITH WithoutChildren AS
(
    SELECT MT1.* FROM #MyTable MT1
        WHERE NOT EXISTS (SELECT 1 FROM #MyTable MT2 WHERE MT1.ID != MT2.ID AND MT1.ID = MT2.ParentID)
)

, RecursiveCTE (StartingID, Level, Parents, Descriptions, Loop, ParentID) AS
(
    SELECT ID, -- StartingID 
        1, -- Level
        '|' + CAST(ID AS VARCHAR(MAX)) + '|', 
        '|' + CAST(Description AS VARCHAR(MAX)) + '|', 
        0, -- Loop
        ParentID
        FROM WithoutChildren
    UNION ALL
    SELECT R.StartingID, -- StartingID
        R.Level + 1, -- Level
        R.Parents + CAST(MT.ID AS VARCHAR(MAX)) + '|',
        R.Descriptions + CAST(MT.Description AS VARCHAR(MAX)) + '|', 
        CASE WHEN R.Parents LIKE '%|' + CAST(MT.ID AS VARCHAR(MAX)) + '|%' THEN 1 ELSE 0 END,
        MT.ParentID
        FROM #MyTable MT
        INNER JOIN RecursiveCTE R ON R.ParentID = MT.ID AND R.Loop = 0
)

SELECT * FROM RecursiveCTE 
    WHERE ParentID IS NULL OR Loop = 1

此查询应返回所有“最后一个子”行，以及完整的父链。列Loop是0如果没有循环，1如果有循环。

Answer 3

id这是一种用于检测邻接列表（父/子关系）中循环的替代方法，其中节点只能有一个父级，可以通过对子列（在下表中）的唯一约束来强制执行。这是通过递归查询计算邻接表的闭包表来实现的。它首先将每个节点添加到闭包表中作为其自己的 0 级祖先，然后迭代遍历邻接表以扩展闭包表。当新记录的子记录和祖先记录在除原始零级 (0) 之外的任何级别上都相同时，就会检测到循环：

-- For PostgreSQL and MySQL 8 use the Recursive key word in the CTE code:
-- with RECURSIVE cte(ancestor, child, lev, cycle) as (

with cte(ancestor, child, lev, cycle) as (
  select id, id, 0, 0 from Table1
  union all
  select cte.ancestor
       , Table1.id
       , case when cte.ancestor = Table1.id then 0 else cte.lev + 1 end
       , case when cte.ancestor = Table1.id then cte.lev + 1 else 0 end
    from Table1
    join cte
      on cte.child = Table1.PARENT_ID
   where cte.cycle = 0
) -- In oracle uncomment the next line
-- cycle child set isCycle to 'Y' default 'N'
select distinct
       ancestor
     , child
     , lev
     , max(cycle) over (partition by ancestor) cycle
  from cte

给定表 1 的以下邻接表：

| parent_id | id |
|-----------|----|
|    (null) |  1 |
|    (null) |  2 |
|         1 |  3 |
|         3 |  4 |
|         1 |  5 |
|         2 |  6 |
|         6 |  7 |
|         7 |  8 |
|         9 | 10 |
|        10 | 11 |
|        11 |  9 |

上述查询适用于 SQL Sever（以及按指示修改后的 Oracle、PostgreSQL 和 MySQL 8），正确检测到节点 9、10 和 11 参与长度为 3 的循环。

SQL(/DB) Fiddles 在各种数据库中演示了这一点，如下所示：

• 甲骨文11gR2
• SQL Server 2017
• PostgeSQL 9.5
• MySQL 8

Answer 4

您可以使用 Knuth 描述的相同方法在此处检测链表中的循环。在一个列中，跟踪孩子，孩子的孩子，孩子的孩子的孩子等。 在另一列中，跟踪孙子，孙子的孙子，孙子的孙子孙子等。

对于初始选择，列Child与Grandchild列之间的距离为1。从每选择一次union all，深度增加Child1，深度增加Grandchild2。它们之间的距离增加1。

如果你有任何循环，由于距离每次只增加 1，在Child循环之后的某个点，距离将是循环长度的倍数。发生这种情况时，Child和Grandchild列是相同的。将其用作停止递归的附加条件，并在其余代码中将其检测为错误。

SQL Server 示例：

declare @LinkTable table (Parent int, Child int);
insert into @LinkTable values (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (7, 1);

with cte as (
    select lt1.Parent, lt1.Child, lt2.Child as Grandchild
    from @LinkTable lt1
    inner join @LinkTable lt2 on lt2.Parent = lt1.Child
    union all
    select cte.Parent, lt1.Child, lt3.Child as Grandchild
    from cte
    inner join @LinkTable lt1 on lt1.Parent = cte.Child
    inner join @LinkTable lt2 on lt2.Parent = cte.Grandchild
    inner join @LinkTable lt3 on lt3.Parent = lt2.Child
    where cte.Child <> cte.Grandchild
)
select Parent, Child
from cte
where Child = Grandchild;

删除LinkTable导致循环的记录之一，您会发现select不再返回任何数据。