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

Question

Рассмотрим следующий простой DAG:

  1->2->3->4

И таблица, #bar, описывающая это (я использую SQL Server 2005):

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

Теперь представьте, что у меня есть некоторые другие произвольные критерии, которые выбирают первое и последнее ребра, то есть 1-> 2 и 3-> 4. Я хочу использовать их, чтобы найти остальную часть моего графика.

Я могу написать рекурсивный CTE следующим образом (я использую терминологию из 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

Однако это приводит к тому, что ребро 3-> 4 выбирается дважды:

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

Как я могу предотвратить повторение запроса в подграфах, которые уже были описаны? Я мог бы добиться этого, если бы в моей части запроса «рекурсивный элемент» я мог ссылаться на все данные, которые были получены рекурсивным CTE до сих пор (и предоставлять предикат, указывающий на рекурсивный член, исключая узлы уже побывал). Однако я думаю, что могу получить доступ к данным, которые были возвращены последней итерацией только рекурсивного члена.

Это не будет хорошо масштабироваться, когда таких повторений много. Есть ли способ предотвратить эту ненужную дополнительную рекурсию?

Обратите внимание, что я мог бы использовать «выбрать отличное» в последней строке моего утверждения, чтобы достичь желаемых результатов, но это, кажется, применимо после , когда вся (повторная) рекурсия выполнена, поэтому я не не думаю, что это идеальное решение.

Редактировать - hainstech предлагает остановить рекурсию, добавив предикат, чтобы исключить рекурсивные нисходящие пути, которые были явно в начальном наборе, т.е. только рекурсия where foo.child_id not in (1,3). Это работает для случая выше только потому, что это просто - все повторяющиеся разделы начинаются внутри якорного набора узлов. Это не решает общий случай, когда они не могут быть. например, рассмотрите добавление ребер 1-> 4 и 4-> 5 к вышеуказанному набору. Край 4-> 5 будет захвачен дважды, даже с предложенным предикатом. (

Answer 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 каждое значение с помощью temptable и не следовать этому значению, если оно найдено, но SQL Server не поддерживает эти вещи.

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

Answer 2

Это подход, который я использовал. Он был протестирован против нескольких методов и был наиболее эффективным. Он объединяет идею временной таблицы, предложенную 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 @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

РЕДАКТИРОВАТЬ - Это не работает вообще. Это метод прекращения погони за треугольными маршрутами. Он не делает то, что хотел ОП.

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

Я дома на своем ноутбуке (без сервера 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

Answer 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

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

where foo.child_id not in (1,3)

Answer 5

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

Answer 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'