Найдите наименьший общий родительский элемент в рекурсивной таблице SQL
-
05-07-2019 - |
Вопрос
Предположим, у меня есть рекурсивная таблица (например,сотрудники с менеджерами) и список размеров 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
Как это сделать?
Редактировать:Обратите внимание, что parent - это неправильный термин не во всех случаях.Это самый низкий общий узел во всех путях вверх по дереву.Наименьший общий узел также может быть самим узлом (например, в случае [1,8] => 1
, узел 1
не является родительским элементом node 1
но узел 1
сам по себе).
С уважением, Рональд
Решение 2
После некоторого размышления и некоторых подсказок в правильном направлении от ответа Марка (спасибо) я сам нашел другое решение:
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
в выборку.
Другие советы
Вот один из способов сделать это;он использует рекурсивный CTE для поиска родословной узла и использует "ПЕРЕКРЕСТНОЕ ПРИМЕНЕНИЕ" к входным значениям, чтобы получить общую родословную;вы просто меняете значения в @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