在递归SQL表中查找最低公共父级
https://stackoverflow.com/questions/1005761
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
假设我有一个递归表（例如，有经理的员工）和一个大小为 0..n 的id列表。如何找到这些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] =＆gt; 1 的情况下，节点 1 不是节点 1 本身。）
亲切的问候， 罗纳德
解决方案 2
在从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
它现在返回从最低公共父节点到根节点的整个路径，但这是向
其他提示
这是一种做法;它使用递归CTE来查找节点的祖先，并使用“CROSS APPLY”和“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
不隶属于 StackOverflow
