los padres múltiples árbol (o dígrafo) servidor de aplicación SQL 2005

Question

Necesito implementar un árbol de múltiples emparentado (o dígrafo) en SQL Server 2005. He leído varios artículos, pero la mayoría de ellos utiliza árboles contacto materno individuales con una raíz única como la siguiente.

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

En éste, todo lo que se deriva de un elemento raíz (Mi PC).

En mi caso, un niño podría tener más de 1 padre, como la siguiente:

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

Así que tengo el siguiente 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 devuelve el siguiente 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

Tenga en cuenta que la relación G> B no está presente, ya que pide un objeto de partida (que no funciona para mí también, porque no conozco el objeto de raíz desde el principio) y el uso de A como el inicio punto ignorará el G-> relación B.

Por lo tanto, este código no funciona en mi caso, ya que pide un objeto de partida, que es evidente en un árbol de un solo padre (siempre será el objeto de raíz). Pero en el árbol de varios padres, usted podría tener más de 1 objeto "raíz" (como en el ejemplo, G y A son los objetos "raíz", donde root es un objeto que no tiene un padre (antepasado)).

Así que soy una especie de stucked aquí ... tengo que modificar la consulta para no pedir un objeto de partida y de forma recursiva atravesar todo el árbol. No sé si eso es posible con la (Id, NextID) aplicación ... puede ser que necesito para almacenarla como un gráfico utilizando algún tipo de matriz de incidencia, matriz de adyacencia o lo que sea (véase http://willets.org/sqlgraphs.html ).

Cualquier ayuda? ¿Qué piensan chicos? Muchas gracias por su tiempo =)

Saludos!

Fuentes: Fuente 1 Fuente 2 Fuente 3

Answer 1

Bueno, finalmente ocurrió con la siguiente solución. Es la manera que encontré para soportar múltiples árboles de raíz y dígrafos también en bicicleta.

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

Podría ser útil para alguien. Es para mí = P Gracias

Answer 2

Si desea utilizar todos los objetos raíz como objetos de partida, debe actualizar primero sus datos para incluir información acerca de los objetos raíz (y las hojas). Usted debe agregar las siguientes inserciones:

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

Por supuesto, también puede escribir su consulta anclaje de tal manera que seleccione como root nodos de los registros que tienen un Id que no se presenta como un NextId, pero esto es más fácil.

A continuación, modificar la consulta de anclaje a tener este aspecto:

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

Si se ejecuta esta consulta, se verá que se obtiene una gran cantidad de duplicados, una gran cantidad de arcos se producen varias veces. Esto se debe a que ahora tiene dos resultados de la consulta de anclaje y por lo tanto es atravesado dos veces el árbol.

Esto se puede solucionar cambiando la instrucción de selección a este (nótese el DISTINCT):

SELECT DISTINCT o.*
FROM   Objects o

Answer 3

Si usted no quiere hacer las inserciones sugeridas por Ronald, esto haría !.

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