arbre plusieurs parents (ou digraphe) serveur SQL de mise en œuvre 2005

Question

Je dois mettre en œuvre un arbre multi-parented (ou digraphe) sur SQL Server 2005. Je l'ai lu plusieurs articles, mais la plupart d'entre eux utilise des arbres à un seul parented avec une racine unique comme celle qui suit.

-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 (Mon PC).

Dans mon cas, un enfant pourrait avoir plus de 1 parent, comme 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

---

Ce qui renvoie le SET suivant:

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

Résultat attendu 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 (ce qui ne fonctionne pas pour moi aussi, parce que je ne sais pas l'objet racine dès le début) et l'utilisation de A comme début le point ignorera la G-> relation B.

Alors, ce code ne fonctionne pas dans mon cas car il demande un objet de départ, ce qui est évident dans un arbre monoparental (sera toujours l'objet racine). Mais dans l'arbre multi-parent, vous pourriez avoir l'objet de plus de 1 « root » (comme dans l'exemple, G et A sont les objets « root », où la racine est un objet qui ne dispose pas d'un parent (ancêtre)).

Je suis un peu stucked ici ... Je dois modifier la requête pour ne pas demander un objet à partir et traverser récursive l'arbre entier. Je ne sais pas si cela est possible avec le (Id, NextID) la mise en œuvre ... peut-être que je dois stocker comme un graphique en utilisant une sorte de matrice d'incidence, matrice de contiguïté ou tout autre (voir http://willets.org/sqlgraphs.html ).

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

Vive!

Sources: Source 1 Source 2 Source 3

Answer 1

Eh bien, je suis finalement arrivé avec la solution suivante. C'est la manière que je trouvais pour soutenir les arbres multi-racines et aussi à vélo digraphs.

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

pourrait être utile pour quelqu'un. Il 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 qui ne se Id 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, un grand nombre d'arcs se produisent plusieurs fois. Ceci 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 inserts proposés par Ronald, ce serait faire !.

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