檢索層級組...有無限遞歸

Question

我有一個表像這裏麪包含的鏈接：

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

因爲我們有

A-B-C-A

- >只想簡單地顯示鏈接，如圖所示。

有什麼想法？

在此先感謝

Answer 1

的問題是，你並沒有真正處理嚴格的等級制度;你正在處理有向圖，其中一些圖有周期。請注意，您的nbgroup＃1沒有任何規範的根 - 由於來自c-a的循環引用，它可能是a，b或c。

處理這個問題的基本方法是用圖形技術而不是遞歸來思考。實際上，迭代方法（不使用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）中。你把它放在第二位，但它可能在第一位，對吧？這種含糊不清的原因是我沒有試圖在這個解決方案中解決它。

編輯：爲了清楚起見，在我上面的解決方案中，如果遇到共享分支，它會將整個集合視爲單個組件。不是你上面所描述的，但是在問題得到澄清之後它將不得不被改變。希望這會讓你接近。

Answer 2

您應該使用遞歸查詢。在第一部分中，我們選擇所有記錄是頂級節點（沒有父母），並使用ROW_NUMBER()爲其分配組ID號碼。然後在遞歸部分中，我們爲他們添加一個孩子，並使用父母組的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

Answer 3

使用遞歸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。

Answer 4

你可能要檢查與公共表表達式

here's the link