SQL Server:如何将CTE递归限制为只是递归添加的行？

Question

更简单的例子

让我们尝试一个更简单的例子,这样人们可以围绕这些概念,并有一个实际的例子,你可以复制并粘贴到SQL Query Analizer:

想象一个具有层次结构的节点表:

A
 - B
    - C

我们可以在Query Analizer中开始测试:

CREATE TABLE ##Nodes
(
 NodeID varchar(50) PRIMARY KEY NOT NULL,
 ParentNodeID varchar(50) NULL
)

INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('A', null)
INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('B', 'A')
INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('C', 'B')

期望的输出:

ParentNodeID    NodeID    GenerationsRemoved
============    ======    ==================
NULL            A         1
NULL            B         2
NULL            C         3
A               B         1
A               C         2
B               C         1

现在建议的CTE表达式,输出不正确:

WITH NodeChildren AS
(
   --initialization
   SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
   FROM ##Nodes
   WHERE ParentNodeID IS NULL

   UNION ALL

   --recursive execution
   SELECT P.ParentNodeID, N.NodeID, P.GenerationsRemoved + 1
   FROM NodeChildren AS P
      INNER JOIN ##Nodes AS N
      ON P.NodeID = N.ParentNodeID
)
SELECT ParentNodeID, NodeID, GenerationsRemoved
FROM NodeChildren

实际产量:

ParentNodeID    NodeID    GenerationsRemoved
============    ======    ==================
NULL            A         1
NULL            B         2
NULL            C         3

注意:如果SQL Server 2005†CTE无法在2000年之前完成我的工作,那很好,这就是答案.任何给出"不可能"作为答案的人都将赢得赏金.但是我会等几天,以确保每个人都同意这是不可能的,否则我无法在不解决问题的情况下给予250点声望.

Nitpickers角落

†不是2008年

‡不使用UDF*,这是已有的解决方案

*除非您能在原始问题中看到提高UDF性能的方法

---

原始问题

我有一个节点表,每个节点都有一个指向另一个节点的父节点(或为空).

例如:

1 My Computer
    2 Drive C
         4 Users
         5 Program Files
         7 Windows
             8 System32
    3 Drive D
         6 mp3

我想要一个表,它返回所有父子关系,以及它们之间的代数

对于所有直接父母关系:

ParentNodeID  ChildNodeID  GenerationsRemoved
============  ===========  ===================
(null)        1            1
1             2            1
2             4            1
2             5            1
2             7            1
1             3            1
3             6            1
7             8            1

但后来有祖父母的关系:

ParentNodeID  ChildNodeID  GenerationsRemoved
============  ===========  ===================
(null)        2            2
(null)        3            2
1             4            2
1             5            2
1             7            2
1             6            2
2             8            2

那里有曾祖父母的关系:

ParentNodeID  ChildNodeID  GenerationsRemoved
============  ===========  ===================
(null)        4            3
(null)        5            3
(null)        7            3
(null)        6            3
1             8            3

所以我可以弄清楚基本的CTE初始化:

WITH (NodeChildren) AS
{
   --initialization
   SELECT ParentNodeID, NodeID AS ChildNodeID, 1 AS GenerationsRemoved
   FROM Nodes
} 

现在的问题是递归部分.当然,明显的答案是行不通的:

WITH (NodeChildren) AS
{
   --initialization
   SELECT ParentNodeID, ChildNodeID, 1 AS GenerationsRemoved
   FROM Nodes

   UNION ALL

   --recursive execution
   SELECT parents.ParentNodeID, children.NodeID, parents.Generations+1
   FROM NodeChildren parents
    INNER JOIN NodeParents children
    ON parents.NodeID = children.ParentNodeID
} 

Msg 253, Level 16, State 1, Line 1
Recursive member of a common table expression 'NodeChildren' has multiple recursive references.

生成整个递归列表所需的所有信息都存在于初始CTE表中.但如果不允许,我会尝试:

WITH (NodeChildren) AS
{
   --initialization
   SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
   FROM Nodes

   UNION ALL

   --recursive execution
   SELECT parents.ParentNodeID, Nodes.NodeID, parents.Generations+1
   FROM NodeChildren parents
    INNER JOIN Nodes
    ON parents.NodeID = nodes.ParentNodeID
} 

但这失败了,因为它不仅加入了递归元素,而且还一遍又一遍地重复添加相同的行:

Msg 530, Level 16, State 1, Line 1
The statement terminated. The maximum recursion 100 has been exhausted before statement completion.

在SQL Server 2000中,我使用用户定义函数(UDF)模拟了CTE:

CREATE FUNCTION [dbo].[fn_NodeChildren] ()
RETURNS @Result TABLE (
    ParentNodeID int NULL,
    ChildNodeID int NULL,
    Generations int NOT NULL) 
AS  
/*This UDF returns all "ParentNode" - "Child Node" combinations
    ...even multiple levels separated
BEGIN 
    DECLARE @Generations int
    SET @Generations = 1

    --Insert into the Return table all "Self" entries
    INSERT INTO @Result
    SELECT ParentNodeID, NodeID, @Generations
    FROM Nodes
    WHILE @@rowcount > 0 
    BEGIN
        SET @Generations = @Generations + 1
        --Add to the Children table: 
        --  children of all nodes just added 
        -- (i.e. Where @Result.Generation = CurrentGeneration-1)
        INSERT @Result
        SELECT CurrentParents.ParentNodeID, Nodes.NodeID, @Generations
        FROM Nodes
            INNER JOIN @Result CurrentParents
            ON Nodes.ParentNodeID = CurrentParents.ChildNodeID
        WHERE CurrentParents.Generations = @Generations - 1
    END
    RETURN
END

保持它不被炸毁的魔力是限制where子句:WHERE CurrentParents.Generations - @ Generations-1

你如何防止递归CTE永远递归？

Answer 1

试试这个:

WITH Nodes AS
(
   --initialization
   SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
   FROM ##Nodes

   UNION ALL

   ----recursive execution
   SELECT P.ParentNodeID, N.NodeID, P.GenerationsRemoved + 1
   FROM Nodes AS P
      INNER JOIN ##Nodes AS N
      ON P.NodeID = N.ParentNodeID
   WHERE P.GenerationsRemoved <= 10

)
SELECT ParentNodeID, NodeID, GenerationsRemoved
FROM Nodes
ORDER BY ParentNodeID, NodeID, GenerationsRemoved

基本上从初始化查询中删除"只显示我绝对父母"; 这样它就可以从每个结果开始生成结果并从那里下降.我还在"WHERE P.GenerationsRemoved <= 10"中添加了无限递归捕获(将10替换为任何数字,最多100个以满足您的需要).然后添加排序,使其看起来像您想要的结果.