Implémentation de l'arbre parent (ou du digraphe) de SQL Server SQL Server 2005

Question

J'ai besoin d'implémenter un arbre multi-parenté (ou digraphe) sur SQL Server 2005. J'ai lu plusieurs articles, mais la plupart d'entre eux utilisent des arbres monoparentaux avec une racine unique comme la suivante.

-My PC 
    -Drive C 
     -Documents and Settings 
     -Program Files 
     -Adobe 
     -Microsoft 
     -Folder X 
    -Drive D 
     -Folder Y 
     -Folder Z 

Dans celui-ci, tout dérive d'un élément racine (My PC).

Dans mon cas, un enfant pourrait avoir plus de 1 parent, comme ce qui suit:

G A 
\/
    B 
/\ 
X C 
/\ 
    D E 
    \/
    F 

J'ai le code suivant:

create table #ObjectRelations 
(
    Id varchar(20), 
    NextId varchar(20) 
) 

insert into #ObjectRelations values ('G', 'B') 
insert into #ObjectRelations values ('A', 'B') 
insert into #ObjectRelations values ('B', 'C') 
insert into #ObjectRelations values ('B', 'X') 
insert into #ObjectRelations values ('C', 'E') 
insert into #ObjectRelations values ('C', 'D') 
insert into #ObjectRelations values ('E', 'F') 
insert into #ObjectRelations values ('D', 'F') 

declare @id varchar(20) 
set @id = 'A'; 

WITH Objects (Id, NextId) AS 
(-- This is the 'Anchor' or starting point of the recursive query 
    SELECT rel.Id, 
     rel.NextId 
    FROM #ObjectRelations rel 
    WHERE rel.Id = @id 
    UNION ALL -- This is the recursive portion of the query 
    SELECT rel.Id, 
     rel.NextId 
    FROM #ObjectRelations rel 
    INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join) 
     ON rel.Id = Objects.NextId 
) 
SELECT o.* 
FROM Objects o 

drop table #ObjectRelations 

---

qui renvoie le SET suivant :

Id     NextId 
-------------------- -------------------- 
A     B 
B     C 
B     X 
C     E 
C     D 
D     F 
E     F 

Attendu Sult SET:

Id     NextId 
-------------------- -------------------- 
G     B 
A     B 
B     C 
B     X 
C     E 
C     D 
D     F 
E     F 

Notez que la relation G-> B est absent, car il demande un objet de départ (qui ne fonctionne pas pour moi aussi, parce que je ne sais pas l'objet racine dès le début) et en utilisant A comme point de départ ignorera la relation G-> B. Donc, ce code ne fonctionne pas dans mon cas car il demande un objet de départ, ce qui est évident dans un arbre SINGLE-parent (sera toujours l'objet racine). Mais dans l'arbre multi-parent, vous pouvez avoir plus d'un objet "root" (comme dans l'exemple, G et A sont les objets "root", où root est un objet qui n'a pas de parent (ancêtre)).

Donc, je suis coincé ici ... J'ai besoin de modifier la requête pour ne pas demander un objet de départ et parcourir récursivement l'arbre entier. Je ne sais pas si c'est possible avec l'implémentation (Id, NextId) ... peut-être dois-je le stocker comme un graphe en utilisant une sorte de matrice d'Incidence, de matrice d'adjacence ou autre (voir http://willets.org/sqlgraphs.html).

Une aide? Que pensez-vous les gars? Merci beaucoup pour votre temps =)

Cheers!

Sources: Source 1 Source 2 Source 3

Answer 1

Eh bien, je me suis finalement venu avec la solution suivante. C'est comme ça que j'ai trouvé pour supporter les arbres à racines multiples et aussi les digraphes à vélo.

create table #ObjectRelations 
(
    Id varchar(20), 
    NextId varchar(20) 
) 

/* Cycle */ 
/* 
insert into #ObjectRelations values ('A', 'B') 
insert into #ObjectRelations values ('B', 'C') 
insert into #ObjectRelations values ('C', 'A') 
*/ 

/* Multi root */ 

insert into #ObjectRelations values ('G', 'B') 
insert into #ObjectRelations values ('A', 'B') 
insert into #ObjectRelations values ('B', 'C') 
insert into #ObjectRelations values ('B', 'X') 
insert into #ObjectRelations values ('C', 'E') 
insert into #ObjectRelations values ('C', 'D') 
insert into #ObjectRelations values ('E', 'F') 
insert into #ObjectRelations values ('D', 'F') 


declare @startIds table 
(
    Id varchar(20) primary key 
) 

;WITH 
    Ids (Id) AS 
    (
     SELECT Id 
     FROM #ObjectRelations 
    ), 
    NextIds (Id) AS 
    (
     SELECT NextId 
     FROM #ObjectRelations 
    ) 
INSERT INTO @startIds 
/* This select will not return anything since there are not objects without predecessor, because it's a cyclic of course */ 
SELECT DISTINCT 
    Ids.Id 
FROM 
    Ids 
LEFT JOIN 
    NextIds on Ids.Id = NextIds.Id 
WHERE 
    NextIds.Id IS NULL 
UNION 
/* So let's just pick anyone. (the way I will be getting the starting object for a cyclic doesn't matter for the regarding problem)*/ 
SELECT TOP 1 Id FROM Ids 

;WITH Objects (Id, NextId, [Level], Way) AS 
(-- This is the 'Anchor' or starting point of the recursive query 
    SELECT rel.Id, 
     rel.NextId, 
     1, 
     CAST(rel.Id as VARCHAR(MAX)) 
    FROM #ObjectRelations rel 
    WHERE rel.Id IN (SELECT Id FROM @startIds) 

    UNION ALL -- This is the recursive portion of the query 

    SELECT rel.Id, 
     rel.NextId, 
     [Level] + 1, 
     RecObjects.Way + ', ' + rel.Id 
    FROM #ObjectRelations rel 
    INNER JOIN Objects RecObjects -- Note the reference to CTE table name (Recursive Join) 
     ON rel.Id = RecObjects.NextId 
    WHERE RecObjects.Way NOT LIKE '%' + rel.Id + '%' 

) 
SELECT DISTINCT 
     Id, 
     NextId, 
     [Level] 
FROM Objects 
ORDER BY [Level] 

drop table #ObjectRelations 

Peut être utile pour quelqu'un C'est pour moi = P Merci

Answer 2

Si vous souhaitez utiliser tous les objets racine comme des objets à partir, vous devez d'abord mettre à jour vos données pour inclure des informations sur les objets racine (et les feuilles). Vous devez ajouter les inserts suivants:

insert into #ObjectRelations values (NULL, 'G') 
insert into #ObjectRelations values (NULL, 'A') 
insert into #ObjectRelations values ('X', NULL) 
insert into #ObjectRelations values ('F', NULL) 

Bien sûr, vous pouvez également écrire votre requête d'ancrage de telle sorte que vous sélectionnez en tant que root nœuds les enregistrements qui ont un Id qui ne se produit pas comme NextId, mais cela est Plus facile.

Ensuite, modifiez votre requête d'ancrage pour ressembler à ceci:

SELECT rel.Id, 
     rel.NextId 
FROM #ObjectRelations rel 
WHERE rel.Id IS NULL 

Si vous exécutez cette requête, vous verrez que vous obtenez beaucoup de doublons, beaucoup d'arcs se produisent plusieurs fois.C'est parce que vous avez maintenant deux résultats de votre requête d'ancrage et donc l'arbre est traversé deux fois.

Cela peut être corrigé en changeant votre instruction select à cette (notez le DISTINCT):

SELECT DISTINCT o.* 
FROM Objects o 

Answer 3

Si vous ne voulez pas faire les insertions suggérées par Ronald, cela ferait !.

WITH CTE_MultiParent (ID, ParentID) 
AS 
(
    SELECT ID, ParentID FROM #ObjectRelations 
    WHERE ID NOT IN 
    (
     SELECT DISTINCT ParentID FROM #ObjectRelations 
    ) 
    UNION ALL 
    SELECT ObjR.ID, ObjR.ParentID FROM #ObjectRelations ObjR INNER JOIN CTE_MultiParent 
    ON CTE_MultiParent.ParentID = ObjR.Id 
) 

SELECT DISTINCT * FROM CTE_MultiParent