Найти наименьшего общего родителя в рекурсивной таблице SQL - PullRequest
Новая
       10

Найти наименьшего общего родителя в рекурсивной таблице SQL

3 голосов
/ 17 июня 2009

Предположим, у меня есть рекурсивная таблица (например, сотрудники с менеджерами) и список идентификаторов размером 0..n. Как найти наименьшего общего родителя для этих идентификаторов?

Например, если моя таблица выглядит так: 

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

Тогда следующие наборы идентификаторов приводят к следующим результатам (первый - угловой случай): 

[]      => 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).

С уважением, Рональд

Ответы [ 2 ]

5 голосов
/ 17 июня 2009

Вот один из способов сделать это; он использует рекурсивный 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
4 голосов
/ 17 июня 2009

Подумав и подумав в правильном направлении из ответа Марка (спасибо), я сам нашел другое решение: 

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 к выбору.

...