8

リンクを含むこのようなテーブルがあります：

key_a    key_b
--------------
a        b        
b        c
g        h     
a        g       
c        a
f        g

本当に整頓されていない＆無限再帰...

key_a = 親 key_b = 子

各階層グループ (親 + 直接の子 + 間接の子) の番号を再構成して属性を付与するクエリが必要です。

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**

私たちが持っているので

ABCA

-> 示されているように、単にリンクを表示したいだけです。

何か案が ？

前もって感謝します

4

4 に答える 4

5

問題は、厳密な階層を実際に扱っていないことです。一部のグラフにサイクルがある有向グラフを扱っています。nbgroup #1 には正準ルートがないことに注意してください。ca からの循環参照により、a、b、または c になる可能性があります。

これに対処する基本的な方法は、再帰ではなく、グラフ手法の観点から考えることです。実際、反復的なアプローチ (CTE を使用しない) は、SQL で考えられる唯一のソリューションです。ここでは、基本的なアプローチについて説明します。

これは、サイクルと共有リーフの両方のケースに対処するソリューションを備えた SQL Fiddleです。反復処理 (プロセスの暴走を防止するためのフェイルセーフ機能付き) とテーブル変数を使用して操作していることに注意してください。これを回避する方法はないと思います。変更されたサンプル データにも注意してください (ag が ah に変更されました。以下で説明します)。

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

これが、サンプル データで ag を ah に変更した理由の核心になります。リーフ ノードのみが共有されている場合、問題の仕様は簡単です。それが私がコーディングした仕様です。この場合、ah と gh はどちらも問題なく適切なコンポーネントにバンドルできます。これは、親からの到達可能性 (サイクルが与えられていても) が懸念されるためです。

ただし、ブランチを共有していると、何を表示したいのか明確ではありません。ag リンクを考えてみましょう。これを考えると、gh はいずれかのコンポーネント (agh または fgh) に存在する可能性があります。あなたはそれを2番目に入れましたが、代わりに1番目にあった可能性がありますよね? このあいまいさが、このソリューションで対処しようとしなかった理由です。

編集：明確にするために、上記の私のソリューションでは、共有ブランチが発生した場合、セット全体を単一のコンポーネントとして扱います。上記で説明したものではありませんが、問題が明確になった後に変更する必要があります。うまくいけば、これはあなたを近づけます。

于 2013-08-01T15:34:30.453 に答える
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 デモ

于 2013-07-30T13:40:58.260 に答える
0

再帰的 CTE を使用したグラフ ウォーキングの痛ましい問題。これは、グラフ内で接続されたサブグラフを見つける問題です。再帰 CTE を使用する際の課題は、不当な再帰、つまり無限ループを防ぐことです。SQL Server では、これは通常、それらを文字列に格納することを意味します。

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

もう 1 つのアイデアは、ノードから両方向にグラフをたどることです。これにより、すべての可能なノードが訪問されることが保証されます。以下は、これを実現するクエリです。

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

于 2013-08-03T19:23:11.110 に答える