Предотвратите рекурсивный CTE посещение узлов многократно

Вы случайно не знаете, какой из двух ребер находится на более глубоком уровне дерева? Потому что в этом случае вы могли бы сделать edge 3-> 4 якорным элементом и начать подниматься по дереву, пока не найдете edge 1-> 2 .

Что-то вроде этого:

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

Это то, что вы хотите сделать?

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 - я не думаю, что это решение для временных таблиц, которое предлагал Quasnoi. Я полагаю, что они предлагали в основном дублировать все содержимое элемента рекурсии во время каждой рекурсии и использовать это как объединение, чтобы предотвратить повторную обработку (и что это не поддерживается в ss2k5). Мой подход поддерживается, и единственное изменение в вашем оригинале - предикат в элементе рекурсии, чтобы исключить повторяющиеся пути вниз, которые были явно в вашем начальном наборе. Я только добавил переменную таблицы, чтобы вы могли определить начальные parent_ids в одном месте, вы могли бы так же легко использовать этот предикат с вашим исходным запросом:

where foo.child_id not in (1,3)

(я не специалист по графам, просто немного разбираюсь)

DISTINCT гарантирует, что каждая строка различна, но не устраняет маршруты к графам, которые не заканчиваются в вашем последнем крае. Возьмем этот график:

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)

Результаты запроса здесь включают (1,5), который не является частью маршрута от первого ребра (1,2) до последнего ребра (6,4).

Вы можно попробовать что-то вроде этого, чтобы найти только маршруты, которые начинаются с (1,2) и заканчиваются (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'

Это подход, который я использовал. Он был протестирован с использованием нескольких методов и оказался наиболее эффективным. Он сочетает в себе идею временной таблицы, предложенную Квассной, и использование как отдельного, так и левого соединения для устранения избыточных путей к рекурсии. Также включен уровень рекурсии.

Я оставил неудачный подход CTE в коде, чтобы вы могли сравнить результаты.

Если у кого-то есть идея получше, я бы хотел ее узнать.

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