sql-server-2005 - management - sql server 2008

Implementación del árbol sqls de múltiples padres(o dígrafo) 2005

Question

Necesito implementar un árbol (o dígrafo) multipared en SQL Server 2005. He leído varios artículos, pero la mayoría de ellos usa árboles de un solo padre 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 este caso, todo se deriva de un elemento raíz (Mi PC).

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

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

Entonces 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

Lo cual devuelve el siguiente SET:

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 falta la relación G-> B porque solicita un objeto de inicio (que tampoco funciona para mí, porque no conozco el objeto raíz desde el principio) y el uso de A como punto de inicio ignorará la relación G-> B.

Por lo tanto, este código no funciona en mi caso porque solicita un objeto de inicio, que es obvio en un árbol padre SINGLE (siempre será el objeto raíz). Pero en el árbol multi-parental, podría tener más de 1 objeto "raíz" (como en el ejemplo, G y A son los objetos "raíz", donde raíz es un objeto que no tiene un padre (ancestro)).

Así que estoy algo atrapado aquí ... Necesito modificar la consulta para NO pedir un objeto inicial y atravesar recursivamente todo el árbol. No sé si eso es posible con la implementación (Id, NextId) ... puede ser que necesite almacenarlo como un gráfico usando algún tipo de matriz de incidencia, matriz de adyacencia o lo que sea (ver http://willets.org/ sqlgraphs.html ).

¿Alguna ayuda? ¿Qué piensan chicos? Muchas gracias por tu tiempo =)

¡Aclamaciones!

Fuentes: Fuente 1 Fuente 2 Fuente 3

Answer 1

Si desea utilizar todos los objetos raíz como objetos iniciales, primero debe actualizar sus datos para incluir información sobre los objetos raíz (y las hojas). 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 de anclaje de tal manera que seleccione como nodos raíz los registros que tienen un Id que no aparece como NextId , pero esto es más fácil.

A continuación, modifique su consulta ancla para que se vea así:

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

Si ejecuta esta consulta, verá que obtiene muchos duplicados, muchos arcos ocurren varias veces. Esto se debe a que ahora tiene dos resultados de su consulta de delimitador y, por lo tanto, el árbol se recorre dos veces.

Esto se puede solucionar cambiando su declaración de selección a esta (observe DISTINCT ):

SELECT DISTINCT o.*
FROM   Objects o

Answer 2

Bueno, finalmente se me ocurrió la siguiente solución. Es la forma en que encontré para admitir árboles de múltiples raíces y también cíclicas de dígrafos.

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 3

Si no quieres hacer las inserciones sugeridas por Ronald, ¡esto sería suficiente !.

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