Rechercher le plus petit parent commun dans une table SQL récursive

Question

Supposons que je dispose d’un tableau récursif (par exemple, des employés avec des responsables) et d’une liste de taille 0..n d’id. Comment puis-je trouver le parent commun le plus bas pour ces identifiants?

Par exemple, si ma table ressemble à ceci:

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

Ensuite, les ensembles d'identifiants suivants mènent aux résultats suivants (le premier est un cas de coin):

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

Comment faire cela?

EDIT: Notez que parent n'est pas le terme correct dans tous les cas. C'est le nœud commun le plus bas dans tous les chemins en haut de l'arbre. Le nœud commun le plus bas peut également être un nœud lui-même (par exemple, dans le cas [1,8] = > 1 , le nœud 1 n'est pas un parent du nœud 1 mais le noeud 1 lui-même).

Cordialement, Ronald

Answer 1

Après avoir réfléchi et fait quelques allusions dans la bonne direction à partir de la réponse de Marc (merci), j'ai proposé moi-même une autre solution:

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

Il renvoie maintenant l'intégralité du chemin du parent commun le plus bas au nœud racine, mais il suffit d'ajouter un TOP 1 à la sélection.

Answer 2

Voici une façon de le faire. il utilise un CTE récursif pour rechercher l'ascendance d'un nœud et utilise "CROSS APPLY". sur les valeurs d'entrée pour obtenir l'ascendance commune; vous venez de changer les valeurs dans @ids (variable de table):

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

Mettre à jour si les nœuds ne sont pas strictement ascendants:

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

et

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