Предотвращение рекурсивного посещения узлов CTE несколько раз

Ответ 1

CTE являются рекурсивными.

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

В вашем примере стеки рекурсии будут выглядеть следующим образом:

(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

Как вы можете видеть, эти рекурсионные стеки не пересекаются.

Возможно, вы могли бы записать посещенные значения во временную таблицу, JOIN каждое значение с помощью соблазнительного и не следовать этому значению, если оно найдено, но SQL Server не поддерживает эти вещи.

Итак, вы просто используете SELECT DISTINCT.

Ответ 2

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

Я оставил неудачный подход 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 @[email protected]@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 @[email protected]@ROWCOUNT 
END

SELECT * from @foo

DROP TABLE #bar

Ответ 3

Вам известно, какой из двух ребер находится на более глубоком уровне в дереве? Поскольку в этом случае вы можете сделать ребро 3->4 элементом привязки и начать движение по дереву, пока не найдете край 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

Ответ 4

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

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

Изменить - @bacar - Я не думаю, что это предложение временного стола, предложенное Квасьным. Я считаю, что они предлагали в основном дублировать содержимое всех членов рекурсии во время каждой рекурсии и использовать это как соединение для предотвращения повторной обработки (и что это не поддерживается в ss2k5). Мой подход поддерживается, и единственное изменение в вашем оригинале заключается в предикате в элементе рекурсии, чтобы исключить рекурсивные пути, которые были явно указаны в вашем стартовом наборе. Я только добавил переменную таблицы, чтобы вы определяли начальные parent_ids в одном месте, вы могли бы так же легко использовать этот предикат с исходным запросом:

where foo.child_id not in (1,3)

Ответ 5

EDIT - это совсем не работает. Это метод прекращения преследования маршрутов треугольника. Он не делает то, что хотел OP.

Или вы можете использовать рекурсивную строку, разделенную на токены.

Я дома на своем ноутбуке (без сервера sql), так что это может быть не совсем правильно, но здесь идет.....

; 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

Или аналогично. Простите, и я не могу это проверить. Я проверю в понедельник утром. Кредит для этого должен пойти к Питеру Ларссону (Песо)

Идея была создана здесь: http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290

Ответ 6

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

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'