Finden niedrigsten gemeinsamen übergeordneten in rekursiven SQL-Tabelle

Question

Angenommen, ich habe eine rekursive Tabelle (zum Beispiel Mitarbeiter mit Managern) und eine Liste der Größe 0..n von ids. Wie kann ich die kleinst gemeinsam 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 den 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 dies zu tun?

EDIT: Beachten Sie, dass Eltern nicht der richtige Begriff ist in allen Fällen. Es ist der niedrigste gemeinsame Knoten in allen Pfaden auf den Baum. Der kleinste gemeinsame Knoten kann auch ein Knoten selbst sein (zum Beispiel im Fall [1,8] => 1, Knoten 1 ist keine übergeordnete Knoten 1 aber Knoten 1 selbst).

Mit freundlichen Grüßen, Ronald

Answer 1

einige denken und einige Hinweise in der richtigen Richtung von Marc Antwort Nachdem ich (danke), kam ich mit einer anderen Lösung auf mich:

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 eine TOP 1 zum Auswählen hinzuzufügen.

Answer 2

Hier ist eine Art und Weise, es zu tun; es verwendet eine rekursive CTE die Abstammung eines Knotens zu finden und verwendet über die Eingabewerte „CROSS APPLY“, um die gemeinsamen Vorfahren zu erhalten; Sie ändern nur die Werte in @ids (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 streng steigend:

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