3

假设我有一个递归表（例如，有经理的员工）和一个0..nID 大小的列表。如何找到这些 id 的最低共同父级？

例如，如果我的表如下所示：

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

那么下面这组 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

这是一种方法；它使用递归 CTE 来查找节点的祖先，并在输入值上使用“CROSS APPLY”来获取共同祖先；您只需更改@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

在从 Marc 的回答（谢谢）中对正确方向进行了一些思考和一些提示之后，我自己想出了另一个解决方案：

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 1在选择中添加 a 的问题。

于 2009-06-17T11:44:40.340 回答