Multiple árvore pais (ou dígrafo) servidor implementação SQL 2005

Question

Eu preciso implementar uma árvore multi-parented (ou dígrafo) para SQL Server 2005. Já li vários artigos, mas a maioria deles usa árvores single-parent com uma raiz única como a seguinte.

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

Neste, tudo deriva de um elemento de raiz (Meu PC).

No meu caso, uma criança poderia ter mais de 1 pai, como o seguinte:

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

Então, eu tenho o seguinte código:

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

---

Que retorna o seguinte conjunto:

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

Resultado esperado SET:

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

Note que o G- relação> B está faltando, porque ele pede um objeto inicial (que não funciona para mim também, porque eu não sei o objeto raiz desde o início) e usando um como o início ponto irá ignorar o G-> relacionamento B.

Assim, este código não funciona no meu caso, porque ele pede um objeto partida, o que é óbvio em uma árvore monoparentais (sempre será o objeto de raiz). Mas na árvore multi-pai, você poderia ter mais de 1 objeto "root" (como no exemplo, G e A são os objetos "raiz", onde root é um objeto que não tem um pai (ancestral)).

Então, eu sou o tipo de stucked aqui ... eu preciso modificar a consulta para não pedir um objeto inicial e recursivamente percorrer a árvore inteira. Eu não sei se isso é possível com o (Id, NextID) implementação ... pode ser que eu preciso para armazená-lo como um gráfico usando algum tipo de matriz de incidência, matriz de adjacência ou o que quer (veja http://willets.org/sqlgraphs.html ).

Qualquer ajuda? O que vocês acham pessoal? Muito obrigado pelo seu tempo =)

Felicidades!

Fontes: Fonte 1 Fonte 2 Fonte 3

Answer 1

Bem, eu finalmente veio com a seguinte solução. É a maneira que eu encontrei para apoiar árvores multi-raiz e dígrafos também ciclismo.

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

Pode ser útil para alguém. É para mim = P Graças

Answer 2

Se você quiser usar todos os objetos raiz como objetos de partida, você primeiro deve atualizar seus dados para incluir informações sobre os objetos da raiz (e as folhas). Você deve adicionar as seguintes inserções:

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

É claro que você também pode escrever sua consulta âncora de tal forma que você selecionar como root nodos os registros que têm um Id que não ocorre como um NextId, mas isso é mais fácil.

Em seguida, modificar sua consulta âncora para esta aparência:

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

Se você executar essa consulta, você verá que você terá um monte de duplicatas, um monte de arcos ocorrer várias vezes. Isto é porque agora você tem dois resultados de sua consulta âncora e, portanto, a árvore é atravessado duas vezes.

Isso pode ser corrigido alterando sua instrução select a este (note a DISTINCT):

SELECT DISTINCT o.*
FROM   Objects o

Answer 3

Se você não quer fazer as inserções sugeridos por Ronald, este faria !.

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