Abrufen hierarchische Gruppen ... mit unendlicher Rekursion

Question

ich eine Tabelle wie folgt habe, die Links enthält:

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

nicht wirklich ordentlich & unendliche Rekursion ...

key_a = Mutter key_b = Kind

Erfordern eine Abfrage, die neu zusammensetzt und eine Nummer für jede hierarchische Gruppe (Eltern + direkte Kinder + indirekte Kinder):

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

Weil wir

A-B-C-A

haben -> wollen nur zeigen, einfach auf den Link, wie dargestellt.

Irgendeine Idee?

Vielen Dank im Voraus

Answer 1

Das Problem ist, dass Sie nicht wirklich mit strengen Hierarchien zu tun; Sie haben es mit gerichteten Graphen zu tun, in denen einige Graphen Zyklen haben. Beachten Sie, dass Ihre nbgroup # 1 keine kanonische Wurzel hat - sie könnte a, b oder c aufgrund der zyklischen Referenz von c-a sein.

Der grundlegende Weg, damit umzugehen, ist in Graphtechniken zu denken, nicht in Rekursion. In der Tat ist ein iterativer Ansatz (ohne Verwendung eines CTE) die einzige Lösung, die ich mir in SQL vorstellen kann. Der grundlegende Ansatz ist explained here.

Here is a SQL Fiddle mit einer Lösung, die sowohl die Zyklen als auch den gemeinsamen Blattfall anspricht. Beachten Sie, dass es eine Iteration (mit einer Failsafe-Funktion zum Verhindern von Runaway-Prozessen) und Tabellenvariablen verwendet; Ich denke nicht, dass da irgendwas passiert. Beachten Sie auch die geänderten Probendaten (a-g wurde in a-h geändert; siehe unten).

Wenn Sie sich in SQL vertiefen, werden Sie bemerken, dass ich einige wichtige Dinge von der Lösung geändert habe, die in dem Link angegeben ist. Diese Lösung hat sich mit ungerichteten Kanten beschäftigt, während Ihre Kanten gerichtet sind (wenn Sie ungerichtete Kanten verwendet haben, ist der gesamte Probensatz wegen der a-g-Verbindung eine einzelne Komponente).

Dies führt zu dem Grund, warum ich a-g zu a-h in meinen Beispieldaten geändert habe. Ihre Spezifikation des Problems ist einfach, wenn nur Blattknoten gemeinsam genutzt werden. Das ist die Spezifikation, die ich programmiert habe. In diesem Fall können a-h und g-h beide problemlos zu ihren richtigen Komponenten gebündelt werden, da wir uns Sorgen um die Erreichbarkeit von den Eltern machen (selbst bei bestimmten Zyklen).

Wenn Sie jedoch Zweige geteilt haben, ist nicht klar, was Sie anzeigen möchten. Betrachten Sie die a-g-Verknüpfung: Gegeben davon könnte g-h in jeder Komponente (a-g-h oder f-g-h) existieren. Du hast es in die Sekunde gelegt, aber es könnte stattdessen in der ersten sein, oder? Diese Zweideutigkeit ist der Grund, warum ich nicht versucht habe, es in dieser Lösung anzusprechen.

Edit: Um klar zu sein, in meiner obigen Lösung, wenn Shared braches angetroffen werden, behandelt es den gesamten Satz als eine einzelne Komponente. Nicht das, was Sie oben beschrieben haben, aber es muss geändert werden, nachdem das Problem geklärt ist. Hoffentlich kommt dir das nahe.

Answer 2

Sie sollten eine rekursive Abfrage verwenden. Im ersten Teil wählen wir alle Datensätze aus, die Knoten auf oberster Ebene sind (haben keine Eltern), und verwenden ROW_NUMBER(), um ihnen Gruppen-ID-Nummern zuzuweisen. Dann fügen wir ihnen im rekursiven Teil nacheinander die Kinder hinzu und verwenden die ID-Nummern der Elterngruppen.

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

Schmerzhaftes Problem des Graph Walking mit rekursiven CTEs. Dies ist das Problem, zusammenhängende Teilgraphen in einem Graphen zu finden. Die Herausforderung bei der Verwendung von rekursiven CTEs besteht darin, eine ungerechtfertigte Rekursion zu verhindern - also Endlosschleifen. In SQL Server bedeutet dies normalerweise, dass sie in einer Zeichenfolge gespeichert werden.

Die Idee ist, eine Liste aller Paare von Knoten zu erhalten, die verbunden sind (und ein Knoten ist mit sich selbst verbunden). Nehmen Sie dann das Minimum aus der Liste der verbundenen Knoten und verwenden Sie diese als ID für den verbundenen Teilgraphen.

Die andere Idee ist, den Graphen in beiden Richtungen von einem Knoten zu gehen. Dies stellt sicher, dass alle möglichen Knoten besucht werden. Hier finden Sie Abfrage, die dies leistet:

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; 

Die SQLFiddle ist here.

Answer 4

Sie könnten mit COMMON TABLE überprüfen möchten AUSDRÜCKEN

here's the link