sql-server - SQL Server：CTE再帰を再帰的に追加された行に制限するにはどうすればよいですか？

Question

より簡単な例

より簡単な例を試してみましょう。そうすれば、人々は概念に頭を悩ませることができ、SQLクエリアナライザーにコピーアンドペーストできる実用的な例があります。

階層を持つNodesテーブルを想像してみてください。

A
 - B
    - C

クエリアナライザーでテストを開始できます。

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 Server2005†CTEが2000年以前に行っていたことを実行できない場合‡、それは問題ありません。それが答えです。そして、答えが賞金を獲得するので、「それは不可能です」と与える人は誰でも。しかし、私は数日待って、私の問題の解決策がないことで250の評判を取り返しのつかないほど与える前に、それが不可能であることに全員が同意することを確認します。

Nitpickersコーナー

†2008年ではない

‡UDF*に頼ることなく、これはすでに解決策です

*元の質問でUDFのパフォーマンスを改善する方法がわからない場合

元の質問

ノードのテーブルがあり、それぞれに別のノード（またはnull）を指す親があります。

説明のために：

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が永久に再帰するのをどのように防ぎますか？

score 0 · Accepted Answer

CTEでパスを作成し、それを使用して祖先を識別しようとしましたか？

次に、祖先ノードの深さから子孫ノードの深さを差し引いて、GenerationsRemoved列を計算できます。

DECLARE @Nodes TABLE
(
    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')

DECLARE @Hierarchy TABLE
(
    NodeId varchar(50) PRIMARY KEY NOT NULL,
    ParentNodeId varchar(50) NULL,
    Depth int NOT NULL,
    [Path] varchar(2000) NOT NULL
)

WITH Hierarchy AS
(
    --initialization
    SELECT NodeId, ParentNodeId, 0 AS Depth, CONVERT(varchar(2000), NodeId) AS [Path]
    FROM @Nodes
    WHERE ParentNodeId IS NULL

    UNION ALL

    --recursive execution
    SELECT n.NodeId, n.ParentNodeId, p.Depth + 1, CONVERT(varchar(2000), p.[Path] + '/' + n.NodeId)
    FROM Hierarchy AS p
    INNER JOIN @Nodes AS n
    ON p.NodeId = n.ParentNodeId
)
INSERT INTO @Hierarchy
SELECT *
FROM Hierarchy

SELECT parent.NodeId AS AncestorNodeId, child.NodeId AS DescendantNodeId, child.Depth - parent.Depth AS GenerationsRemoved
FROM @Hierarchy AS parent
INNER JOIN @Hierarchy AS child
ON child.[Path] LIKE parent.[Path] + '/%'

score 0 · Accepted Answer

余談ですが、SQL Server 2008はありますか？hierarchyidこれは、データ型に適している可能性があります。

score 0 · Accepted Answer

私があなたの意図を理解したら、次のようなことを行うことで結果を得ることができます:

DECLARE @StartID INT;
SET @StartID = 1;
WITH CTE (ChildNodeID, ParentNodeID, [Level]) AS
(
  SELECT  t1.ChildNodeID, 
          t1.ParentNodeID, 
          0
  FROM tblNodes AS t1
  WHERE ChildNodeID = @StartID
  UNION ALL
  SELECT  t1.ChildNodeID, 
          t1.ParentNodeID, 
          t2.[Level]+1
  FROM tblNodes AS t1
    INNER JOIN CTE AS t2 ON t1.ParentNodeID = t2.ChildNodeID    
)
SELECT t1.ChildNodeID, t2.ChildNodeID, t1.[Level]- t2.[Level] AS GenerationsDiff
FROM CTE AS t1
  CROSS APPLY CTE t2

これにより、すべてのノード間の世代差が返されます。正確なニーズに合わせて変更できます。

score 0 · Accepted Answer

まあ、あなたの答えはそれほど明白ではありません:-)

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

この部分は、再帰 CTE の「アンカー」部分と呼ばれますが、実際には、テーブルから 1 つまたはいくつかの行のみを選択する必要があります。これにより、すべてが選択されます。

ここで見逃しているのは、単に適切な WHERE 句だと思います。

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

ただし、「まっすぐな」階層だけでなく、祖父母と子の行も必要とする要件を満たすのは簡単ではないかもしれません....通常、再帰的なCTEは、1つのレベルとその直接の下位階層のみを表示します(もちろん、それは階層を下ります）-通常、1つ、2つ、またはそれ以上のレベルをスキップしません。

これが少し役立つことを願っています。

マルク

sql-server - SQL Server：CTE再帰を再帰的に追加された行に制限するにはどうすればよいですか？

より簡単な例

元の質問

8 に答える 8

Related

Reference