Finde das niedrigste gemeinsame Elternteil in der rekursiven SQL-Tabelle

Question

Angenommen, ich habe eine rekursive Tabelle (z. B. Mitarbeiter mit Managern) und eine Liste der Größe 0..n von ids. Wie kann ich die niedrigsten gemeinsamen Eltern für diese IDs finden?

Zum Beispiel, wenn meine Tabelle wie folgt aussieht:

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

Dann gelten die folgenden Sätze von IDs zu folgenden Ergebnissen führen (die erste ist eine Ecke Fall):

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

Wie um dies zu tun?

EDIT: Beachten Sie, dass Eltern nicht der richtige Begriff in allen Fällen ist. Es ist der niedrigste gemeinsame Knoten in allen Pfaden auf dem Baum. Der niedrigste gemeinsame Knoten kann auch ein Knoten selbst sein (zum Beispiel im Fall [1,8] => 1 ist der Knoten 1 kein Elternteil des Knotens 1 sondern Knoten 1 selbst).

Mit freundlichen Grüßen, Ronald

Answer 1

Nach einigem tun Denken und ein paar Hinweise in die richtige Richtung von Marc's Antwort (danke), ich selbst habe eine andere Lösung gefunden:

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 

Es gibt nun den gesamten Weg von dem kleinsten gemeinsamen Elternteil zu dem Wurzelknoten, aber das ist eine Frage des ein TOP 1 zum Auswählen hinzuzufügen.

Answer 2

Hier ist eine Möglichkeit, es zu tun; Es verwendet einen rekursiven CTE, um die Herkunft eines Knotens zu finden, und verwendet "CROSS APPLY" über die Eingabewerte, um die gemeinsame Herkunft zu erhalten. Sie nur die Werte in @ids ändern (Tabellenvariable):

----------------------------------------- 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 

---

aktualisieren, wenn die Knoten nicht unbedingt aufsteigen:

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 

und

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