Zapobieganie wielokrotnemu odwiedzaniu węzłów CTE

Takie podejście zastosowałem. Został przetestowany na kilka metod i był najbardziej wydajny. Łączy w sobie ideę tabeli temp sugerowaną przez Quassnoi i użycie zarówno oddzielnego, jak i lewego połączenia w celu wyeliminowania zbędnych ścieżek do rekursji. Uwzględniono również poziom rekurencji.

Zostawiłem nieudane podejście CTE w kodzie, abyś mógł porównać wyniki.

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

Wiesz może, która z dwóch krawędzi znajduje się na głębszym poziomie drzewa? Ponieważ w takim przypadku możesz zrobić edge 3->4 członkiem kotwicy i zacząć chodzić po drzewie, dopóki nie znajdziesz edge 1->2.

Coś takiego:

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

To jest to, co chcesz zrobić?

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 - nie wydaje mi się, aby to było rozwiązanie tabeli temp zaproponowane przez Quasnoi. Wydaje mi się, że sugerowali zasadniczo powielenie całej zawartości rekurencji podczas każdej rekurencji i użycie jej jako łącznika, aby zapobiec ponownemu przetwarzaniu (i że nie jest to obsługiwane w ss2k5). Moje podejście jest obsługiwane, a jedyną zmianą w stosunku do oryginału jest predykat w członie rekurencji, aby wykluczyć rekurencyjne ścieżki, które były wyraźnie w zestawie startowym. Dodałem tylko zmienną table, aby zdefiniować początkowe parent_ids w jednym miejscu, równie łatwo można było użyć tego predykatu z oryginalnym zapytaniem:

where foo.child_id not in (1,3)

EDIT -- to w ogóle nie działa. Jest to metoda, aby przestać gonić trasy trójkąta. Nie robi tego, czego chciała operacja.

Lub możesz użyć rekurencyjnego łańcucha oddzielonego tokenem.

Jestem w domu na moim laptopie (nie SQL server), więc to może nie być całkowicie w porządku, ale tutaj idzie.....

; 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

Lub podobne. Przepraszam za spóźnienie i nie mogę tego przetestować. Sprawdzę w poniedziałek rano. Kredyt na to musi iść do Petera Larssona (Peso)

Pomysł powstał tutaj: http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290

(nie jestem ekspertem od grafów, tylko trochę zgłębiam)

Funkcja DISTINCT gwarantuje, że każdy wiersz jest odrębny, ale nie eliminuje tras wykresu, które nie kończą się na ostatniej krawędzi. Weźmy ten wykres:

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)

Wyniki zapytania obejmują (1,5), który nie jest częścią trasy od pierwszej krawędzi (1,2) do ostatniej krawędzi (6,4).

Możesz spróbować czegoś takiego, aby znaleźć tylko trasy zaczynające się od (1,2) i kończące się na (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'