Mehrere Eltern Baum (oder Digraph) Implementierung von SQL Server 2005

Question

Ich brauche einen Multi-parented Baum (oder Digraph) auf SQL Server 2005 zu implementieren. Ich habe mehrere Artikel gelesen, aber die meisten von ihnen verwenden Single-parented Bäume mit einer einzigartigen Wurzel wie die folgenden.

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

In diesem leitet sich alles von einem Wurzelelement (Mein PC).

In meinem Fall ein Kind könnte mehr als 1 Elternteil haben, wie folgt aus:

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

So habe ich den folgenden Code:

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

---

Welche gibt die folgende SET:

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

Erwartetes Ergebnis SET:

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

Beachten Sie, dass die Beziehung G> B fehlt, weil es für einen Startobjekt fragt (was nicht für mich auch nicht funktioniert, weil ich von Anfang an das Wurzelobjekt nicht kennen) und mit A als Start Punkt wird die G-> B Beziehung ignorieren.

Also, dieser Code nicht in meinem Fall nicht funktioniert, weil es für einen Start Objekt fragt, die in einem Ein-Eltern-Baum offensichtlich ist (wird immer das Stammobjekt sein). Aber in Multi-Elternteilbaum, man könnte mehr haben als 1 „root“ Objekt (wie im Beispiel G und A sind die „root“ Objekte, wo root ein Objekt ist, das nicht einen Elternteil (Vorfahren hat)).

So ich hier Art von stucked bin ... Ich brauche die Abfrage zu verändern für einen Startobjekt nicht zu fragen, und rekursiv den gesamten Baum durchlaufen. Ich weiß nicht, ob das möglich ist, mit dem (Id, NextID) Implementierung ... kann ich es wie ein Diagramm zu speichern, eine Art von Incidence Matrix, Adjazenzmatrix oder was auch immer (siehe http://willets.org/sqlgraphs.html ).

Jede Hilfe? Was denkt ihr Leute? Vielen Dank für Ihre Zeit =)

Cheers!

Quellen: Quelle 1 Quelle 2 Quelle 3

Answer 1

Nun, ich kam schließlich mit der folgenden Lösung auf. Es ist die Art, wie ich mit mehreren Wurzelbäumen und auch Radfahren Digraphe zur Unterstützung gefunden.

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

Könnte für jemanden nützlich sein. Es ist für mich = P Dank

Answer 2

Wenn Sie alle Stammobjekte als Ausgangsobjekte verwenden möchten, sollten Sie zunächst Ihre Daten aktualisieren Informationen über die Root-Objekte enthalten (und die Blätter). Sie sollten die folgenden Einsätze hinzufügen:

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

Natürlich können Sie auch Ihre Anker Abfrage so schreiben könnte, die Sie als root wählen die Datensätze die Knoten, die eine Id haben, die nicht als NextId auftritt, aber das ist einfacher.

Als nächstes ändern Sie Ihre Anker-Abfrage wie folgt aussehen:

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

Wenn Sie diese Abfrage ausführen, werden Sie sehen, dass Sie eine Menge von Duplikaten erhalten, treten viele Bögen mehrmals. Dies liegt daran, dass Sie nun zwei Ergebnisse aus Ihrer Anker-Abfrage und daher wird der Baum zweimal durchlaufen.

Dies kann durch Änderung Ihrer select-Anweisung zu diesem (man beachte die DISTINCT) festgelegt werden:

SELECT DISTINCT o.*
FROM   Objects o

Answer 3

Wenn Sie nicht wollen, um die Einsätze von Ronald vorgeschlagen zu tun, würde dies tun !.

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