Verhindern, dass rekursive CTE Besuch Knoten mehrere Male

StackOverflow https://stackoverflow.com/questions/829514

Frage

Betrachten Sie die folgende einfache DAG: 

  1->2->3->4

Und eine Tabelle, #bar, beschreibt dieser (ich bin mit SQL Server 2005): 

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

Nun stell dir vor, dass ich einige andere beliebige Kriterien, die die ersten und letzten Kanten wählen, das heißt 1-> 2 und 3-> 4. Ich möchte diese verwenden den Rest meines Graphen zu finden.

Ich kann einen rekursiven CTE wie folgt schreiben (ich bin mit der Terminologie von 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

Dies führt jedoch in Kante 3-> 4 zweimal ausgewählt ist: 

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

Wie kann ich die Abfrage von Rekursion in Subgraphen verhindern, die bereits beschrieben worden sind? Ich könnte dies erreichen, wenn in meinem „rekursive Mitglied“ Teil der Abfrage, ich verweisen könnte alle Daten, die bisher von der rekursiven CTE abgerufen wurden, (und ein Prädikat liefert in dem rekursiven Elemente angibt, mit Ausnahme von Knoten bereits besucht). Aber ich denke, ich kann auf Daten zugreifen, die nur von die letzte Iteration des rekursiven Element zurückgegeben wurde.

Das wird nicht gut skalieren, wenn es eine Menge solchen Wiederholung ist. Gibt es eine Möglichkeit, diese unnötige zusätzliche Rekursion zu verhindern?

Beachten Sie, dass ich „select distinct“ in der letzten Zeile meiner Anweisung könnte die gewünschten Ergebnisse zu erzielen, aber dies scheint angewendet werden nach alle (Wiederholung) Rekursion erfolgt, so dass ich glaube nicht, dass dies eine ideale Lösung.

Bearbeiten - hainstech schlägt vor, durch Hinzufügen eines Prädikats Rekursion Anhalte auszuschließen Pfade Rekursion nach unten, die explizit in dem Startsatz waren, das heißt recurse nur where foo.child_id not in (1,3). Das funktioniert für den Fall oben nur, weil es einfach - alle wiederholten Abschnitte beginnen innerhalb des Ankers Satz von Knoten. Es muss nicht den allgemeinen Fall lösen, wo sie nicht sein. Beispiel betrachten Kanten Zugabe 1-> 4 und 4-> 5 zu den oben Ausgeführten. Edge-4-> 5 wird zweimal, auch mit dem vorgeschlagenen Prädikat erfaßt. : (

War es hilfreich?

Lösung

Die CTE die sind rekursiv.

Wenn Sie CTE die mehrere Anfangsbedingungen haben, bedeutet, dass sie auch andere Rekursion Stapel haben, und es gibt keine Möglichkeit, Informationen von einem Stapel in einem anderen Stapel zu verwenden.

In Ihrem Beispiel die Rekursion Stapel gehen Sie wie folgt vor: 

(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

Wie Sie sehen können, diese Rekursion Stack nicht schneiden.

Sie könnten wahrscheinlich die besuchten Werte in einer temporären Tabelle notieren, JOIN jeden Wert mit dem temptable und Sie diesem Wert nicht folgen, wenn es gefunden wird, aber SQL Server nicht, diese Dinge nicht unterstützt.

So einfach SELECT DISTINCT verwenden.

Andere Tipps

Dies ist der Ansatz, den ich verwenden. Es wurde gegen mehrere Methoden getestet und war die performant. Es kombiniert die Idee temporäre Tabelle vorgeschlagen von Quassnoi und der Verwendung von sowohl unterschiedlichen und einem linken verbinden redundante Pfade zur Rekursion zu beseitigen. Die Höhe der Rekursion ist ebenfalls enthalten.

Ich ließ den ausgefallenen CTE Ansatz im Code, so dass Sie Ergebnisse vergleichen können.

Wenn jemand eine bessere Idee hat, würde ich lieben, es zu wissen. 

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

Sie passieren Sie wissen, welche der beiden Kanten auf einer tieferen Ebene ist im Baum? Denn in diesem Fall könnten Sie Rand des Ankerelement machen 3->4 und starten Sie den Baum gehen, bis Sie Rand 1->2 finden.

So etwas wie folgt aus: 

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

Ist das, was Sie tun möchten? 

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

Bearbeiten - @bacar - ich glaube nicht, das die temporäre Tabelle ist Lösung Quasnoi vorschlägt. Ich glaube, sie waren darauf hindeutet, im Grunde duplizieren den gesamten Rekursion Mitglied Inhalt bei jeder Rekursion, und verwende, die als Join Wiederaufbereitung zu verhindern (und dass dies nicht in ss2k5 unterstützt). Mein Ansatz wird unterstützt, und die einzige Änderung Ihrer Vorlage ist in dem Prädikat in dem Rekursion Mitglied Rekursion Down-Pfade auszuschließen, die explizit in Ihrem Ausgang Set waren. Ich habe nur die Tabellenvariable, so dass Sie den Start parent_ids an einer Stelle definieren würden, könnte man genauso gut dieses Prädikat mit Ihrer ursprünglichen Abfrage verwendet hat: 

where foo.child_id not in (1,3)

EDIT - Dies gilt nicht bei allen. Dies ist eine Methode zu stoppen Dreieck Strecken jagen. Es ist nicht das tun, was die OP wollte.

Sie können auch eine rekursive Token getrennte Zeichenfolge verwendet werden.

Ich bin zu Hause auf meinem Laptop (kein SQL-Server), so könnte dies nicht ganz richtig sein, aber hier geht ..... 

; 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

oder ähnliches. Traurig ist es spät, und ich kann es nicht testen. Ich werde am Montagmorgen überprüfen. Kredit für diese muss gehen zu Peter Larsson (Peso)

Die Idee wurde hier erzeugt: http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290

(Ich bin kein Experte auf Graphen, nur ein wenig zu erkunden)

Die DISTINCT garantiert jede Reihe unterschiedlich ist, aber es wird nicht Graph Routen beseitigen, die in der letzten Kante am Ende nicht. Nehmen Sie dieses Diagramm: 

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)

Die Ergebnisse der Abfrage hier enthalten (1,5), die nicht Teil der Strecke von der ersten Kante (1,2) zur letzten Kante (6,4).

Sie könnte so etwas wie diese versuchen, finden nur Routen, die mit (1,2) und enden mit (6,4) zu starten: 

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'
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top