ejemplo - sql server query recursive table

Prevenir los nodos de visita CTE recursivos varias veces

Question

Considere el siguiente DAG simple:

  1->2->3->4

Y una tabla, #bar, que describe esto (estoy usando SQL Server 2005):

parent_id   child_id
1           2
2           3
3           4
//... other edges, not connected to the subgraph above

Ahora imagine que tengo otros criterios arbitrarios que seleccionan el primer y último borde, es decir, 1-> 2 y 3-> 4. Quiero usar estos para encontrar el resto de mi gráfica.

Puedo escribir un CTE recursivo de la siguiente manera (estoy usando terminología de MSDN ):

with foo(parent_id,child_id) as (
// anchor member that happens to select first and last edges:
select parent_id,child_id from #bar where parent_id in (1,3)
union all
// recursive member:
select #bar.* from #bar
join foo on #bar.parent_id = foo.child_id
)
select parent_id,child_id from foo

Sin embargo, esto hace que el borde 3> 4 se seleccione dos veces:

parent_id  child_id
1          2
3          4
2          3
3          4    // 2nd appearance!

¿Cómo puedo evitar que la consulta se convierta en subgrafos que ya se han descrito? Podría lograrlo si, en mi parte "recursiva" de la consulta, pudiera hacer referencia a todos los datos recuperados por el CTE recursivo hasta el momento (y proporcionar un predicado que indique en el miembro recursivo excluyendo los nodos ya visitados). Sin embargo, creo que solo puedo acceder a los datos devueltos por la última iteración del miembro recursivo.

Esto no se escalará bien cuando haya mucha repetición. ¿Hay alguna manera de prevenir esta recursión adicional innecesaria?

Tenga en cuenta que podría usar "seleccionar distinto" en la última línea de mi declaración para lograr los resultados deseados, pero parece que esto se aplica después de que se haga toda la recursión (repetida), por lo que no creo que esta sea una solución ideal.

Editar : hainstech sugiere detener la recursión agregando un predicado para excluir las rutas recursivas hacia abajo que estaban explícitamente en el conjunto de inicio, es decir, repetir solo where foo.child_id not in (1,3) . Eso funciona para el caso anterior solo porque es simple: todas las secciones repetidas comienzan dentro del conjunto de nodos de anclaje. No resuelve el caso general donde pueden no estar. por ejemplo, considere agregar los bordes 1-> 4 y 4-> 5 al conjunto anterior. El borde 4-> 5 se capturará dos veces, incluso con el predicado sugerido. :(

Answer 1

¿Es esto lo que quieres hacer?

create table #bar (parent_id int, child_id int)
insert #bar values (1,2)
insert #bar values (2,3)
insert #bar values (3,4)

declare @start_node table (parent_id int)
insert @start_node values (1)
insert @start_node values (3)

;with foo(parent_id,child_id) as (
    select
        parent_id
        ,child_id
    from #bar where parent_id in (select parent_id from @start_node)

    union all

    select
        #bar.*
    from #bar
        join foo on #bar.parent_id = foo.child_id
    where foo.child_id not in (select parent_id from @start_node)
)
select parent_id,child_id from foo

Editar - @bacar - No creo que esta sea la solución de tabla temporal que propuso Quasnoi. Creo que sugirieron básicamente duplicar el contenido completo de los miembros de la recursión durante cada recursión, y usarlo como una combinación para evitar el reprocesamiento (y que esto no se admite en ss2k5). Mi enfoque es compatible, y el único cambio en su original está en el predicado en el miembro de recursión para excluir las rutas recursivas hacia abajo que estaban explícitamente en su conjunto de inicio. Solo agregué la variable de la tabla para que definieras los parent_ids iniciales en una ubicación, podrías haber utilizado este predicado con tu consulta original con la misma facilidad:

where foo.child_id not in (1,3)

Answer 2

¿Sabes cuál de los dos bordes está en un nivel más profundo en el árbol? Porque en ese caso, podría hacer que el borde 3->4 el miembro de anclaje y comenzar a subir por el árbol hasta que encuentre el borde 1->2 .

Algo como esto:

with foo(parent_id, child_id)
as
(
    select parent_id, child_id
    from #bar
    where parent_id = 3

    union all

    select parent_id, child_id
    from #bar b
    inner join foo f on b.child_id = f.parent_id
    where b.parent_id <> 1
)
select *
from foo

Answer 3

(No soy un experto en gráficos, solo explorando un poco)

DISTINCT garantizará que cada fila sea distinta, pero no eliminará las rutas gráficas que no terminen en su último borde. Toma este gráfico:

insert into #bar (parent_id,child_id) values (1,2)
insert into #bar (parent_id,child_id) values (1,5)
insert into #bar (parent_id,child_id) values (2,3)
insert into #bar (parent_id,child_id) values (2,6)
insert into #bar (parent_id,child_id) values (6,4)

Los resultados de la consulta aquí incluyen (1,5), que no forma parte de la ruta desde el primer borde (1,2) hasta el último borde (6,4).

Puedes intentar algo como esto, para encontrar solo las rutas que comienzan con (1,2) y terminan con (6,4):

with foo(parent_id, child_id, route) as (
    select parent_id, child_id, 
        cast(cast(parent_id as varchar) + 
        cast(child_id as varchar) as varchar(128))
    from #bar
    union all
    select #bar.parent_id, #bar.child_id, 
        cast(route + cast(#bar.child_id as varchar) as varchar(128)) 
    from #bar
    join foo on #bar.parent_id = foo.child_id
)
select * from foo where route like ''12%64''

Answer 4

EDITAR - Esto no funciona en absoluto. Este es un método para dejar de perseguir rutas de triángulos. No hace lo que quería el OP.

O puede utilizar una cadena separada por token recursiva.

Estoy en casa en mi computadora portátil (no hay un servidor SQL) así que puede que no sea del todo correcto pero aquí va .....

; WITH NodeNetwork AS (
  -- Anchor Definition
  SELECT
     b.[parent_Id] AS [Parent_ID]
     , b.[child_Id] AS [Child_ID]
     , CAST(b.[Parent_Id] AS VARCHAR(MAX)) AS [NodePath]
  FROM
     #bar AS b

  -- Recursive Definition
  UNION ALL SELECT
     b.[Parent_Id]
     , b.[child_Id]
     , CAST(nn.[NodePath] + ''-'' + CAST(b.[Parent_Id] AS VARCHAR(MAX)) AS VARCHAR(MAX))
  FROM
     NodeNetwork AS nn
     JOIN #bar AS b ON b.[Parent_Id] = nn.[Child_ID]
  WHERE
     nn.[NodePath] NOT LIKE ''%[-]'' + CAST(b.[Parent_Id] AS VARCHAR(MAX)) + ''%''
  )
  SELECT * FROM NodeNetwork

O similar. Lo siento, es tarde y no puedo probarlo. Lo comprobaré el lunes por la mañana. El crédito para esto debe ir a Peter Larsson (Peso)

La idea se generó aquí: http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290

Answer 5

Este es el enfoque que utilicé. Ha sido probado contra varios métodos y fue el más eficaz. Combina la idea de la tabla temporal sugerida por Quassnoi y el uso de una combinación distinta y una izquierda para eliminar las rutas redundantes a la recursión. El nivel de la recursión también se incluye.

Dejé el enfoque de CTE fallido en el código para que pueda comparar los resultados.

Si alguien tiene una idea mejor, me encantaría saberlo.

create table #bar (unique_id int identity(10,10), parent_id int, child_id int)
insert #bar  (parent_id, child_id)
SELECT 1,2 UNION ALL
SELECT 2,3 UNION ALL
SELECT 3,4 UNION ALL
SELECT 2,5 UNION ALL
SELECT 2,5 UNION ALL
SELECT 5,6

SET NOCOUNT ON

;with foo(unique_id, parent_id,child_id, ord, lvl) as (
    -- anchor member that happens to select first and last edges:
    select unique_id, parent_id, child_id, row_number() over(order by unique_id), 0
    from #bar where parent_id in (1,3)
union all
-- recursive member:
select b.unique_id, b.parent_id, b.child_id, row_number() over(order by b.unique_id), foo.lvl+1
    from #bar b
    join foo on b.parent_id = foo.child_id
)
select unique_id, parent_id,child_id, ord, lvl from foo

/***********************************
    Manual Recursion
***********************************/
Declare @lvl as int
Declare @rows as int
DECLARE @foo as Table(
    unique_id int,
    parent_id int,
    child_id int,
    ord int,
    lvl int)

--Get anchor condition
INSERT @foo (unique_id, parent_id, child_id, ord, lvl)
select unique_id, parent_id, child_id, row_number() over(order by unique_id), 0
    from #bar where parent_id in (1,3)

set @rows=@@ROWCOUNT
set @lvl=0

--Do recursion
WHILE @rows > 0
BEGIN
    set @lvl = @lvl + 1

    INSERT @foo (unique_id, parent_id, child_id, ord, lvl)
    SELECT DISTINCT b.unique_id, b.parent_id, b.child_id, row_number() over(order by b.unique_id), @lvl
    FROM #bar b
     inner join @foo f on b.parent_id = f.child_id
     --might be multiple paths to this recursion so eliminate duplicates
     left join @foo dup on dup.unique_id = b.unique_id
    WHERE f.lvl = @lvl-1 and dup.child_id is null

    set @rows=@@ROWCOUNT 
END

SELECT * from @foo

DROP TABLE #bar

Answer 6

Los CTE son recursivos.

Cuando sus CTE tienen múltiples condiciones iniciales, eso significa que también tienen diferentes pilas de recursión, y no hay manera de usar la información de una pila en otra pila.

En su ejemplo, las pilas de recursión serán las siguientes:

(1) - first IN condition
(1, 2)
(1, 2, 3)
(1, 2, 3, 4)
(1, 2, 3) - no more children
(1, 2) - no more children
(1) - no more children, going to second IN condition

(3) - second condition
(3, 4)
(3) - no more children, returning

Como puede ver, estas pilas de recursión no se intersecan.

Probablemente podría registrar los valores visitados en una tabla temporal, JOIN cada valor con el temptable y no siga este valor si se encuentra, pero SQL Server no admite estas cosas.

Entonces solo usas SELECT DISTINCT .