20

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

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

クエリが既に記述されているサブグラフに再帰するのを防ぐにはどうすればよいですか? クエリの「再帰メンバー」部分で、これまでに再帰 CTE によって取得されたすべてのデータを参照できれば、これを実現できます(そして、既にアクセスしたノードを除く再帰メンバーを示す述語を提供できます)。ただし、再帰メンバーの最後の繰り返しで返されたデータにのみアクセスできると思います。

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

ステートメントの最後の行で「個別選択」を使用して目的の結果を得ることができることに注意してください。

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

4

6 に答える 6

8

は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です。

于 2009-05-06T13:26:16.153 に答える
7

これが私が使用したアプローチです。それはいくつかの方法に対してテストされており、最もパフォーマンスが良かった。これは、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
于 2010-03-18T07:27:07.187 に答える
1

（私はグラフの専門家ではなく、少し調べているだけです）

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'
于 2009-05-06T14:24:31.600 に答える
1

これはあなたがやりたいことですか？

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ではサポートされていません）。私のアプローチはサポートされており、オリジナルへの唯一の変更は、再帰メンバーの述語にあり、開始セットに明示的に含まれていた再帰的なダウンパスを除外します。1つの場所で開始parent_idsを定義するために、テーブル変数を追加しただけです。元のクエリでこの述語を簡単に使用できます。

where foo.child_id not in (1,3)
于 2009-05-06T14:25:10.413 に答える
1

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

于 2011-03-11T23:48:36.987 に答える
1

2 つのエッジのどちらがツリーのより深いレベルにあるか知っていますか? その場合、 edge3->4をアンカー メンバーにして、 edge が見つかるまでツリーを上っていくことができるからです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
于 2009-05-06T13:27:07.620 に答える