2013-07-30 14 views
8

を階層グループを取得します。は、私はリンクが含まれています。このようなテーブルをした無限再帰と...

各階層グループ(親+直接の子供+間接的な子供)の番号を再構成して属性付けするクエリを要求します。

key_a key_b nb_group 
-------------------------- 
a  b  1 
a  g  1 
b  c  1 
**c  a**  1 
f  g  2 
g  h  2 

**link responsible of infinite loop** 

我々が持っているので

A-B-C-

- >のみ示すように、単純にリンクを表示したいです。

ありがとうございます。

+0

更新に確認することがあります:無限再帰の問題 –

+0

「無限再帰」とは何を意味するのでしょうか?階層に理論上の制限はないということですか?または、階層が、ある時点で文字通り、いくつかのブランチ上に子ノードがないようにループすることはありますか? - 編集:後者のように見えるので、ループに達したときに何が起こりたいですか? –

+0

親が子供の場合もあるので、 –

答えて

5

問題は、あなたが本当に厳しい階層を扱っていないということです。いくつかのグラフにサイクルがある有向グラフを扱っています。あなたのnbgroup#1には、c-aからの循環参照のために、a、b、またはcのいずれかの標準的なルートがないことに注意してください。

これに対処する基本的な方法は、再帰ではなくグラフ手法で考えることです。実際、SQLで考えることができる唯一の解決策は、反復的なアプローチ(CTEを使用しない)です。基本的なアプローチはexplained hereです。

Here is a SQL Fiddleを、サイクルと共有リーフケースの両方に対処するソリューションで置き換えます。反復(暴走プロセスを防ぐためのフェールセーフ付き)とテーブル変数を使用していることに注意してください。私はこれを回避するものはないと思う。変更されたサンプルデータ(a-gがa-hに変更された、以下で説明する)にも注意してください。

SQLを掘り下げてみると、リンクにある解決策からいくつかの重要なことが変更されていることがわかります。その解決策は、無向エッジを扱っていましたが、エッジは指向されていました(無向エッジを使用した場合、a-g接続のためサンプルセット全体が単一のコンポーネントになります)。

これは、私のサンプルデータでa-gをa-hに変更した理由の中心になっています。葉ノードのみが共有されている場合、問題の指定は簡単です。それは私がコード化した仕様です。この場合、a-hとg-hは問題なく問題なく適切なコンポーネントにバンドルできます。これは、親からの到達可能性が懸念されているためです。

ただし、ブランチを共有している場合は、表示する内容が明確ではありません。 a-gリンクを考えてみましょう。これを仮定すると、g-hはどちらかのコンポーネント(a-g-hまたはf-g-h)に存在する可能性があります。あなたはそれを2番目に入れますが、代わりに1番に入っていた可能性があります。この曖昧さは、私がこの解決策でそれに対処しようとしなかった理由です。

編集:上記の私の解決策では、明らかにするために、共有されている枝に遭遇した場合、全体のセットを単一のコンポーネントとして扱います。あなたが上で説明したものではありませんが、問題が明らかになった後に変更する必要があります。うまくいけば、これはあなたを近づけます。

2

再帰的なクエリを使用する必要があります。最初の部分では、最上位ノード(親を持たない)であるすべてのレコードを選択し、ROW_NUMBER()を使用してグループID番号を割り当てます。再帰的な部分では、子どもたちに1つずつ追加し、親のグループID番号を使用します。

with CTE as 
(

select t1.parent,t1.child, 
     ROW_NUMBER() over (order by t1.parent) rn 

from t t1 where 
not exists (select 1 from t where child=t1.parent) 
union all 
select t.parent,t.child, CTE.rn 
from t 
join CTE on t.parent=CTE.Child 
) 
select * from CTE 
order by RN,parent 

SQLFiddle demo

+0

完璧だと思いますが、別の問題があると思います...いくつかのグループは無限の再帰を持つことができます –

+0

@ViséeMaxence:再帰を制限するために、子どもとの結合をチェックする必要があります。 http://stackoverflow.com/a/660145/128217 – zimdanen

0

再帰的CTEを使用したグラフウォーキングの苦しい問題。これは、グラフ内の接続された部分グラフを見つける問題です。再帰的なCTEを使用することの課題は、無関係な再帰、つまりSQL Serverの無限ループ(通常は文字列に格納すること)を防ぐことです。

考えられるのは、接続されている(ノードが自分自身に接続されている)ノードのすべてのペアのリストを取得することです。次に、接続されたノードのリストから最小値を取り出し、これを接続されたサブグラフのIDとして使用します。

他の考え方は、ノードから両方向にグラフを歩くことです。これにより、すべての可能なノードが確実に訪問されます。これを行うクエリは次のとおりです。

with fullt as (
     select keyA, keyB 
     from t 
     union 
     select keyB, keyA 
     from t 
    ), 
    CTE as (
     select t.keyA, t.keyB, t.keyB as last, 1 as level, 
      ','+cast(keyA as varchar(max))+','+cast(keyB as varchar(max))+',' as path 
     from fullt t 
     union all 
     select cte.keyA, cte.keyB, 
      (case when t.keyA = cte.last then t.keyB else t.keyA 
       end) as last, 
      1 + level, 
      cte.path+t.keyB+',' 
     from fullt t join 
      CTE 
      on t.keyA = CTE.last or 
       t.keyB = cte.keyA 
     where cte.path not like '%,'+t.keyB+',%' 
    ) -- select * from cte where 'g' in (keyA, keyB) 
select t.keyA, t.keyB, 
     dense_rank() over (order by min(cte.Last)) as grp, 
     min(cte.Last) 
from t join 
    CTE 
    on (t.keyA = CTE.keyA and t.keyB = cte.keyB) or 
     (t.keyA = CTE.keyB and t.keyB = cte.keyA) 
where cte.path like '%,'+t.keyA+',%' or 
     cte.path like '%,'+t.keyB+',%' 
group by t.id, t.keyA, t.keyB 
order by t.id; 

SQLFiddleはhereです。

+0

私はあなたのソリューションが共有ブランチに関して私と同じ問題を抱えていることに気付きました。 Mineは(2つの別々のコンポーネントの一部として)共有リーフノードを尊重しますが、あなたのものと同じように、より多くのものが共有されると、2つのコンポーネントをマージします。それでも、私はCTEの実装を見てみたいと思っていました。 –

関連する問題