le plus bas parent commun dans le tableau SQL récursif

Question

Supposons que j'ai une table récursive (par exemple, des employés avec les gestionnaires) et une liste de taille 0..n de ids. 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 de ids suivants conduisent aux résultats suivants (le premier est un cas d'angle):

[]  => 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 pour faire ça?

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 de l'arbre. Le plus bas noeud commun peut aussi être un nœud lui-même (par exemple dans le cas [1,8] => 1, noeud 1 est pas un parent du noeud 1 mais noeud 1 lui-même).

Meilleures salutations, Ronald

Answer 1

Après avoir fait quelques En réfléchissant à la réponse de Marc (merci), j'ai trouvé 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 retourne maintenant tout le chemin du plus bas parent commun au nœud racine mais qui est une question d'ajouter un TOP 1 à la sélection.

Answer 2

Voici une façon de le faire; il utilise un CTE récursif pour trouver 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 

---

mise à jour si les nœuds ne sont pas strictement ascendantes:

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