Trova il genitore comune più basso nella tabella ricorsiva SQL
-
05-07-2019 - |
Domanda
Supponi di avere una tabella ricorsiva (ad es. dipendenti con manager) e un elenco di dimensioni 0..n
di ID. Come posso trovare il genitore comune più basso per questi ID?
Ad esempio, se la mia tabella è simile alla seguente:
Id | ParentId
---|---------
1 | NULL
2 | 1
3 | 1
4 | 2
5 | 2
6 | 3
7 | 3
8 | 7
Quindi i seguenti insiemi di ID portano ai seguenti risultati (il primo è un caso angolare):
[] => 1 (or NULL, doesn't really matter)
[1] => 1
[2] => 2
[1,8] => 1
[4,5] => 2
[4,6] => 1
[6,7,8] => 3
Come farlo?
EDIT: nota che parent non è il termine corretto in tutti i casi. È il nodo comune più basso in tutti i percorsi dell'albero. Il nodo comune più basso può anche essere un nodo stesso (ad esempio nel caso [1,8] = > 1
, il nodo 1
non è un genitore del nodo 1
ma nodo 1
stesso).
Cordiali saluti, Ronald
Soluzione 2
Dopo aver riflettuto e suggerito nella giusta direzione dalla risposta di Marc (grazie), ho trovato anch'io un'altra soluzione:
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
Ora restituisce l'intero percorso dal genitore comune più basso al nodo radice, ma si tratta dell'aggiunta di un TOP 1
alla selezione.
Altri suggerimenti
Ecco un modo per farlo; utilizza un CTE ricorsivo per trovare la progenie di un nodo e usa "CROSS APPLY" sui valori di input per ottenere la progenie comune; devi solo cambiare i valori in @ids
(variabile di tabella):
----------------------------------------- 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
Aggiorna se i nodi non sono strettamente ascendenti:
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
e
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