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

Question

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

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

In diesem Fall stammt alles von einem Wurzelelement (My PC).

In meinem Fall könnte ein Kind 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 

---

, die die folgenden SET zurück :

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

Erwartete re Sult 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 ein Start-Ziel fragt (was nicht für mich auch nicht funktioniert, weil ich von Anfang an das Wurzelobjekt nicht kennen) und die Verwendung von A als Startpunkt ignoriert die G-> B-Beziehung.

Also funktioniert dieser Code in meinem Fall nicht, weil er nach einem Startobjekt fragt, was in einem EINZEL-Elternbaum offensichtlich ist (wird immer das Wurzelobjekt sein). Aber in einem Baum mit mehreren Elternteilen könnten Sie mehr als 1 "root" -Objekt haben (wie im Beispiel, G und A sind die "root" -Objekte, wobei root ein Objekt ist, das kein Elternteil (Vorfahre) hat).

Also bin ich irgendwie hier stecken geblieben ... Ich muss die Abfrage ändern, um nicht nach einem Startobjekt zu fragen und rekursiv den gesamten Baum zu durchlaufen. Ich weiß nicht, ob das mit der (Id, NextId) Implementierung möglich ist ... vielleicht muss ich es wie ein Diagramm speichern, indem ich irgendeine Art von Inzidenzmatrix, Adjazenzmatrix oder was auch immer verwende (siehe http://willets.org/sqlgraphs.html).

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

Prost!

Quellen: Source 1 Source 2 Source 3

Answer 1

Nun, ich mit der folgenden Lösung schließlich kam. Es ist die Art, wie ich gefunden habe, um mehrwurzelnde Bäume und auch Fahrrad-Digraphen zu unterstützen.

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 Danke

Answer 2

Wenn Sie alle Stammobjekte als Ausgangsobjekte verwenden möchten, sollten Sie zunächst Ihre Daten aktualisieren Informationen über die Root-Objekte (und die Blätter) aufzunehmen. 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 auswählen als root die Datensätze die Knoten, die eine Id haben, die nicht als NextId auftritt, aber dies 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 jetzt zwei Ergebnisse von Ihrer Ankerabfrage haben und daher der Baum zwei Mal durchlaufen wird.

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

SELECT DISTINCT o.* 
FROM Objects o 

Answer 3

Wenn Sie nicht die Einsätze von Ronald vorgeschlagen tun möchten, 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