3

再帰テーブル（たとえば、マネージャーを持つ従業員）と0..nIDのサイズのリストがあるとします。これらのIDの最も低い共通の親を見つけるにはどうすればよいですか？

たとえば、私のテーブルが次のようになっている場合：

Id | ParentId
---|---------
 1 |     NULL
 2 |        1
 3 |        1
 4 |        2
 5 |        2
 6 |        3
 7 |        3
 8 |        7

次に、次のIDのセットにより、次の結果が得られます（最初のIDはコーナーケースです）。

[]      => 1 (or NULL, doesn't really matter)
[1]     => 1
[2]     => 2
[1,8]   => 1
[4,5]   => 2
[4,6]   => 1
[6,7,8] => 3

これを行う方法？

編集：すべての場合において、親は正しい用語ではないことに注意してください。これは、ツリーの上のすべてのパスの中で最も低い共通ノードです。最も低い共通ノードは、ノード自体にすることもできます（たとえば、この場合[1,8] => 1、ノード1はノードの親ではなく、1ノード1自体です）。

よろしく、ロナルド

4

2 に答える 2

5

これを行う1つの方法があります。再帰CTEを使用してノードの祖先を検索し、入力値に対して「CROSSAPPLY」を使用して共通の祖先を取得します。@ids（テーブル変数）の値を変更するだけです。

----------------------------------------- SETUP
CREATE TABLE MyData (
   Id int NOT NULL,
   ParentId int NULL)

INSERT MyData VALUES (1,NULL)
INSERT MyData VALUES (2,1)
INSERT MyData VALUES (3,1)
INSERT MyData VALUES (4,2)
INSERT MyData VALUES (5,2)
INSERT MyData VALUES (6,3)
INSERT MyData VALUES (7,3)
INSERT MyData VALUES (8,7)

GO
CREATE FUNCTION AncestorsUdf (@Id int)
RETURNS TABLE
AS
RETURN (
    WITH Ancestors (Id, ParentId)
    AS (
        SELECT Id, ParentId
        FROM MyData
        WHERE Id = @Id
        UNION ALL
        SELECT md.Id, md.ParentId
        FROM MyData md
        INNER JOIN Ancestors a
          ON md.Id = a.ParentId
    )
    SELECT Id FROM Ancestors
);
GO
----------------------------------------- ACTUAL QUERY
DECLARE @ids TABLE (Id int NOT NULL)
DECLARE @Count int
-- your data (perhaps via a "split" udf)
INSERT @ids VALUES (6)
INSERT @ids VALUES (7)
INSERT @ids VALUES (8)

SELECT @Count = COUNT(1) FROM @ids
;
SELECT TOP 1 a.Id
FROM @ids
CROSS APPLY AncestorsUdf(Id) AS a
GROUP BY a.Id
HAVING COUNT(1) = @Count
ORDER BY a.ID DESC

ノードが厳密に昇順でない場合は更新します。

CREATE FUNCTION AncestorsUdf (@Id int)
RETURNS @result TABLE (Id int, [Level] int)
AS
BEGIN
    WITH Ancestors (Id, ParentId, RelLevel)
    AS (
        SELECT Id, ParentId, 0
        FROM MyData
        WHERE Id = @Id
        UNION ALL
        SELECT md.Id, md.ParentId, a.RelLevel - 1
        FROM MyData md
        INNER JOIN Ancestors a
          ON md.Id = a.ParentId
    )

    INSERT @result
    SELECT Id, RelLevel FROM Ancestors

    DECLARE @Min int
    SELECT @Min = MIN([Level]) FROM @result

    UPDATE @result SET [Level] = [Level] - @Min

    RETURN
END
GO

と

SELECT TOP 1 a.Id
FROM @ids
CROSS APPLY AncestorsUdf(Id) AS a
GROUP BY a.Id, a.[Level]
HAVING COUNT(1) = @Count
ORDER BY a.[Level] DESC
于 2009-06-17T09:11:25.827 に答える
4

マークの答え（ありがとう）から正しい方向にいくつかの考えといくつかのヒントをした後、私は自分で別の解決策を思いつきました：

DECLARE @parentChild TABLE (Id INT NOT NULL, ParentId INT NULL);
INSERT INTO @parentChild VALUES (1, NULL);
INSERT INTO @parentChild VALUES (2, 1);
INSERT INTO @parentChild VALUES (3, 1);
INSERT INTO @parentChild VALUES (4, 2);
INSERT INTO @parentChild VALUES (5, 2);
INSERT INTO @parentChild VALUES (6, 3);
INSERT INTO @parentChild VALUES (7, 3);
INSERT INTO @parentChild VALUES (8, 7);

DECLARE @ids TABLE (Id INT NOT NULL);
INSERT INTO @ids VALUES (6);
INSERT INTO @ids VALUES (7);
INSERT INTO @ids VALUES (8);

DECLARE @count INT;
SELECT @count = COUNT(1) FROM @ids;

WITH Nodes(Id, ParentId, Depth) AS
(
    -- Start from every node in the @ids collection.
    SELECT pc.Id , pc.ParentId , 0 AS DEPTH
    FROM @parentChild pc
    JOIN @ids i ON pc.Id = i.Id

    UNION ALL

    -- Recursively find parent nodes for each starting node.
    SELECT pc.Id , pc.ParentId , n.Depth - 1
    FROM @parentChild pc
    JOIN Nodes n ON pc.Id = n.ParentId
)
SELECT n.Id
FROM Nodes n
GROUP BY n.Id
HAVING COUNT(n.Id) = @count
ORDER BY MIN(n.Depth) DESC

これで、最も低い共通の親からルートノードまでのパス全体が返されますが、これはTOP 1selectにを追加するだけの問題です。

于 2009-06-17T11:44:40.340 に答える