Récupérer tous les enfants et leurs enfants, SQL

Question

récursive Tenir compte les lignes suivantes dans une base de données:

Id  | Parent 
__________________ 
1   null 
2   1 
3   2 
4   3 
5   null 
6   5 

Chaque Id qui a une nullParent est le "propriétaire"/"super Parent".

Quelle serait la meilleure approche, en termes de performance, pour recueillir les parents et leurs enfants? Dois-je utiliser LINQ ou Procédures stockées? Je veux que le résultat final soit IEnumerable<IEnumerable<int>>.

Answer 1

En SQL, vous pouvez effectuer une requête à l'aide d'un CTE. Par exemple, pour récupérer une liste de noeuds avec leurs parents et le plus haut parent dans leur arbre:

declare @t table (id int, parent int) 
insert @t (id, parent) values (1, null), (2,1), (3,2), (4,3), (5,null), (6,5) 

; with cte as (
    select id, parent, id as head 
    from @t 
    where parent is null 
    union all 
    select child.id, child.parent, parent.head 
    from @t child 
    join cte parent 
    on  parent.id = child.parent 
) 
select * 
from cte 

Cela donne:

id parent head 
1 NULL 1 
2 1  1 
3 2  1 
4 3  1 
5 NULL 5 
6 5  5 

Notez que j'ai changé vos données d'exemple ligne afin 2 ne soit plus un enfant de lui-même, mais un enfant de rang 1.

Answer 2

Si la table est pas trop grand votre meilleur pari serait de retourner toute la table en faisant cette db.Categories

Une fois que la table des catégories entière est récupérée dans Entity Framework, EF utilisera la relation span pour fixer le gabarit objectGraph alors quand vous faites category.SubCategories vous obtiendrez tous les enfants. L'avantage de ceci est, vous sql ne serait pas complexe, car il serait essentiellement sélectionner * à partir des catégories. Une grande partie du dur labeur serait faite par EF dans la fixation du graphe d'objets afin que tous les enfants s'alignent correctement avec leurs parents.

Vous pouvez également utiliser ce que quelqu'un d'autre a mentionné à propos de l'utilisation de l'expression de table commune.

Je couvre deux de ces concepts dans mon livre.

5-11 En utilisant la relation Span 5-2 Chargement d'un objet complet Graphique (CTE)

Answer 3

Vous pouvez également utiliser une solution pure SQL; Voici un exemple pour SQL Server. Il ne serait pas difficile de le réécrire pour un autre gestionnaire de base de données:

/* Create table */ 
CREATE TABLE dbo.Nodes (ID int NOT NULL PRIMARY KEY, Parent int) 

/* Insert sample data */ 
INSERT INTO Nodes VALUES (1,NULL) 
INSERT INTO Nodes VALUES (2,1) 
INSERT INTO Nodes VALUES (3,2) 
INSERT INTO Nodes VALUES (4,3) 
INSERT INTO Nodes VALUES (5,NULL) 
INSERT INTO Nodes VALUES (6,5) 

/* Create recursive function */ 
CREATE function dbo.fn_Root(@ID int) returns int 
AS BEGIN 
    DECLARE @R int 

    SELECT @R = CASE WHEN Parent IS NULL THEN ID 
        ELSE dbo.fn_Root(Parent) 
       END 
      FROM Nodes 
      WHERE id = @id 

    RETURN @R 
END 

/* Query the table */ 
SELECT ID, Parent, dbo.fn_Root(ID) AS Root 
    FROM Nodes 

/* Also, in SQL Server you can create a calculated column */ 
ALTER TABLE Nodes ADD Root AS dbo.fn_Root(id) 

Ceci est la version de base. Mais celui-ci échouerait si vos données avaient des boucles fermées (pas une arborescence). Pour empêcher le code d'entrer dans une boucle sans fin, la fonction pourrait être améliorée comme ceci:

CREATE function dbo.fn_Root(@ID int, @Initial int) returns int 
AS BEGIN 
    DECLARE @R int 

    DECLARE @Parent int 
    SELECT @Parent = Parent FROM Nodes WHERE ID = @ID 

    IF @Parent IS NULL 
     SELECT @R = @ID /* No parent, the root is the node itself */ 
    ELSE 
     IF @Parent = @Initial 
     /* We have returned to initial node: endless loop. We return NULL to indicate no root exists */ 
     SELECT @R = NULL 
     ELSE 
     /* The root will be the root of the parent node */ 
     SELECT @R = dbo.fn_Root(@Parent,@Initial) 

    RETURN @R 

END 

/* Query the table */ 
SELECT ID, Parent, dbo.fn_Root(ID,ID) AS Root FROM Nodes 

Avec cette modification, si la fonction retourne NULL, il indique que le nœud fait partie d'une boucle, et il n'a pas Noeud principal.

Answer 4

Les bases de données ne sont pas vraiment destinées à effectuer une récursion de profondeur arbitraire. Voici l'opération souhaitée effectuée localement.

List<Item> items = context.Items.ToList(); 

Dictionary<int, Item> itemsById = items.ToDictionary(item => item.Id); 

Dictionary<int, List<Item>> itemsByRoot = new Dictionary<int, List<Item>>(); 
List<Item> cyclicals = new List<Item>(); 

foreach(Item item in items) 
{ 
    HashSet<int> seenIt = new HashSet<int>(); 
    Item parent = item; 
    while (parent.ParentId != null && !seenIt[parent.Id]) 
    { 
    seenIt.Add(parent.Id); 
    parent = itemsById[parent.ParentId]; 
    } 

    if (parent.ParentId == null) 
    { 
    if (!itemsByRoot.ContainsKey(parent.Id)) 
    { 
     itemsByRoot[parent.Id] = new List<Item>(); 
    } 
    itemsByRoot[parent.Id].Add(item); 
    } 
    else 
    { 
    cyclicals.Add(item); 
    } 
}