Evitar recursiva CTE visitar nós várias vezes

Question

Considere o seguinte DAG simples:

  1->2->3->4

E uma mesa, #bar, descrevendo esta (estou usando o SQL Server 2005):

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

Agora imagine que eu tenho alguns outros critérios arbitrários que selecionam as primeiras e últimas arestas, ou seja 1-> 2 e 3> 4. Quero usá-los para encontrar o resto da minha gráfico.

Eu posso escrever uma CTE recursiva como segue (estou usando a terminologia 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

No entanto, isto resulta numa aresta 3-> 4 ser seleccionado duas vezes:

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

Como posso evitar a consulta de recursão em subgrafos que já foram descritos? Eu poderia fazer isto, caso, na minha parte "membro recursivo" da consulta, eu poderia referência todos os dados que foram recuperados pelo CTE recursiva até agora (e fornecer um predicado indicando no membro recursivo excluindo nós já visitamos). No entanto, eu acho que eu posso acessar os dados que foram retornados por a última iteração do membro recursivo somente.

Esta não escala bem quando há um monte de tal repetição. Existe uma maneira de prevenir esta recursão adicional desnecessário?

Note que eu poderia usar "select distinct" na última linha da minha afirmação para alcançar os resultados desejados, mas este parece ser aplicado após toda a (repetida) recursão é feito, então eu não acho que esta é uma solução ideal.

Editar - hainstech sugere parar recursão adicionando um predicado para excluir recursão por caminhos que foram explicitamente no conjunto de partida, ou seja, recurse única where foo.child_id not in (1,3). Que funciona para o caso acima só porque o simples - todas as seções repetidas começam dentro do conjunto de âncora de nós. Não resolve o caso geral onde eles não podem ser. por exemplo, considere a adição de bordas 1-> 4 e 4> 5 para o conjunto acima. Borda 4> 5 será capturado duas vezes, mesmo com o predicado sugeriu. : (

Answer 1

As do CTE são recursiva.

Quando seus de CTE ter várias condições iniciais, isso significa que eles também têm diferentes pilhas de recursão, e não há maneira de informações utilização de uma pilha em outra pilha.

No seu exemplo, as pilhas de recursão vão da seguinte forma:

(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 você pode ver, estes pilha recursão não se cruzam.

Você provavelmente poderia gravar os valores visitou em uma tabela temporária, JOIN cada valor com o temptable e não seguem este valor-lo se ele é encontrado, mas SQL Server não suporta essas coisas.

Assim que você acabou de usar SELECT DISTINCT.

Answer 2

Esta é a abordagem que eu usei. Foi testado contra vários métodos e foi a mais elevada performance. Ele combina a idéia tabela temporária sugerida por Quassnoi eo uso de ambos distinta e uma esquerda se unem para eliminar caminhos redundantes para a recursividade. O nível de recursividade também está incluído.

Eu deixei a abordagem CTE falhou no código para que você possa comparar os resultados.

Se alguém tem uma idéia melhor, eu adoraria conhecê-lo.

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 3

Por acaso você sabe qual das duas bordas está em um nível mais profundo na árvore? Porque, nesse caso, você poderia fazer borda 3->4 o membro de ancoragem e começar a caminhar até a árvore até encontrar 1->2 borda.

Algo parecido com isto:

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 4

É isso que você quer fazer?

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

Edit - @bacar - Eu não acho que esta é a solução tabela temporária Quasnoi estava propondo. Eu acredito que eles estavam sugerindo basicamente duplicar todo o conteúdo membros recursão durante cada recursão, e usar isso como uma junção para evitar o reprocessamento (e que este não é suportado no ss2k5). Minha abordagem é suportado, e a única mudança para o seu original está no predicado no membro recursão para excluir recursão por caminhos que foram explicitamente em seu set de partida. Eu só acrescentou a variável de tabela para que você definiria os parent_ids começando em um único local, você poderia facilmente ter usado esse predicado com a sua consulta original:

where foo.child_id not in (1,3)

Answer 5

EDIT - Isto não funciona em todos. Este é um método para parar de perseguir rotas triângulo. Ele não faz o que o OP queria.

Ou você pode usar uma string separada simbólico recursiva.

Eu estou em casa no meu laptop (sem sql server) de modo que este pode não ser totalmente certo, mas aqui vai .....

; 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

ou similar. Desculpe É tarde e eu não posso testá-lo. Vou verificar na segunda-feira de manhã. Crédito para este deve ir para Peter Larsson (Peso)

A idéia foi gerado aqui: http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290

Answer 6

(Não sou especialista em gráficos, apenas explorar um pouco)

O DISTINCT irá garantir cada linha é distinto, mas não vai eliminar rotas gráfico que não acabam em sua última borda. Tome 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)

Os resultados da consulta aqui incluem (1,5), que não faz parte do percurso a partir da primeira borda (1,2) para o último borda (6,4).

Você poderia tentar algo como isto, para encontrar apenas as rotas que começam com (1,2) e terminam com (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'