再帰的なCTE訪問ノードを複数回防止します

https://stackoverflow.com/questions/829514

06-07-2019
|

質問

次の単純な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-＆gt; 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-＆gt; 4が2回選択されます。

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

クエリが既に説明されているサブグラフに再帰するのを防ぐにはどうすればよいですか？私の「再帰メンバー」でこれを達成できました。クエリの一部として、これまでに再帰CTEによって取得されたすべてのデータを参照することができます（そして、既にアクセスしたノードを除く再帰メンバーに示す述語を提供します）。ただし、再帰メンバーの最後の反復によって返されたデータにのみアクセスできると思います。

このような繰り返しが多い場合、これはうまくスケーリングしません。この不必要な追加の再帰を防ぐ方法はありますか？

「select distinct」を使用できることに注意してください。私の声明の最後の行で目的の結果を達成していますが、これはすべての（繰り返し）再帰が行われた後に適用されるようですので、これは理想的な解決策ではないと思います

編集-開始セットに明示的にある再帰ダウンパスを除外する述語を追加して再帰を停止することを提案します。つまり、（1,3）にないfoo.child_idのみを再帰します。これは上記のケースで機能するのは、単純だからです。繰り返されるセクションはすべて、ノードのアンカーセット内で始まります。それができない一般的なケースは解決しません。たとえば、エッジ1-> 4および4> 5を上記のセットに追加することを検討してください。 Edge 4-＆gt; 5は、提案された述語を使用しても、2回キャプチャされます。：（

解決

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

ご覧のとおり、これらの再帰スタックは交差しません。

訪問した値を一時テーブルに記録し、各値をtemptableに JOIN し、見つかった場合はこの値に従わないことができますが、 SQL Server はこれらをサポートしていません。

つまり、 SELECT DISTINCT を使用するだけです。

他のヒント

これは私が使用したアプローチです。いくつかの方法でテストされており、最もパフォーマンスが高かった。 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

2つのエッジのどちらがツリーのより深いレベルにあるかを知っていますか？その場合、エッジ 3-＆gt; 4 をアンカーメンバーにし、エッジ 1-＆gt; 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

編集-@bacar-これがQuasnoiが提案した一時テーブルソリューションではないと思います。私は彼らが基本的に各再帰中に再帰メンバーの内容全体を複製することを提案し、再処理を防ぐための結合としてそれを使用していたと信じています（これはss2k5ではサポートされていません）。私のアプローチはサポートされており、元のセットへの唯一の変更は、再帰セットの述語にあり、開始セットに明示的に含まれている再帰パスを除外することです。テーブル変数を追加したのは、開始parent_idを1つの場所で定義するためだけで、元のクエリでこの述部を簡単に使用できた可能性があります。

where foo.child_id not in (1,3)

編集-これはまったく機能しません。これは、三角形のルートの追跡を停止する方法です。 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

または同様。申し訳ありませんが、遅れてテストできません。月曜日の朝に確認します。この功績はPeter Larsson（Peso）に送らなければなりません

アイデアはここで生成されました： http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290

（私はグラフの専門家ではありません、ちょっと調べてみてください）

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'

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow