श्रेणीबद्ध समूहों को पुनः प्राप्त ... अनंत प्रत्यावर्तन

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

क्योंकि हमारे पास

ए-बी-सी-ए

-> केवल दिखाया गया है, बस उस लिंक दिखाना चाहते हैं।

कोई विचार?

अग्रिम धन्यवाद

Answer 1

समस्या यह है कि क्या तुम सच में सख्त पदानुक्रम के साथ काम नहीं कर रहे हैं; आप निर्देशित ग्राफ से निपट रहे हैं, जहां कुछ ग्राफों में चक्र होते हैं। ध्यान दें कि आपके nbgroup # 1 में कोई कैनोलिक रूट नहीं है - यह सी-ए से चक्रीय संदर्भ के कारण ए, बी, या सी हो सकता है।

इससे निपटने का मूल तरीका ग्राफ तकनीकों के संदर्भ में सोचना है, रिकर्सन नहीं। असल में, एक पुनरावृत्ति दृष्टिकोण (सीटीई का उपयोग नहीं करना) एकमात्र समाधान है जिसे मैं एसक्यूएल में सोच सकता हूं। मूल दृष्टिकोण explained here है।

Here is a SQL Fiddle एक समाधान के साथ जो चक्र और साझा-पत्ते दोनों मामलों को संबोधित करता है। ध्यान दें कि यह पुनरावृत्ति का उपयोग करता है (रनवे प्रक्रियाओं को रोकने के लिए एक असफलता के साथ) और तालिका चर संचालित करने के लिए; मुझे नहीं लगता कि इसके आसपास कोई हो रहा है। ध्यान दें कि परिवर्तित नमूना डेटा (ए-जी बदलकर ए-एच; नीचे समझाया गया है)।

यदि आप एसक्यूएल में खोदते हैं तो आप देखेंगे कि मैंने लिंक में दिए गए समाधान से कुछ महत्वपूर्ण चीजें बदली हैं। वह समाधान अप्रत्यक्ष किनारों से निपट रहा था, जबकि आपके किनारों को निर्देशित किया गया है (यदि आपने अप्रत्यक्ष किनारों का उपयोग किया है तो संपूर्ण नमूना सेट ए-जी कनेक्शन के कारण एक घटक है)।

यह मेरे नमूना डेटा में ए-जी से ए-एच क्यों बदल गया है, इस दिल के लिए यह हो जाता है। समस्या का आपका विनिर्देश सरल है अगर केवल पत्ता नोड्स साझा किए जाते हैं; यह वह विनिर्देश है जिसे मैंने कोड किया था। इस मामले में, ए-एच और जी-एच दोनों बिना किसी समस्या के अपने उचित घटकों तक बंडल हो सकते हैं, क्योंकि हम माता-पिता (यहां तक ​​कि चक्र दिए गए) से पहुंचने के बारे में चिंतित हैं।

हालांकि, जब आपने शाखाएं साझा की हैं, तो यह स्पष्ट नहीं है कि आप क्या दिखाना चाहते हैं। ए-जी लिंक पर विचार करें: यह दिया गया है, जी-एच किसी भी घटक (ए-जी-एच या एफ-जी-एच) में मौजूद हो सकता है। आप इसे दूसरे में डाल देते हैं, लेकिन यह पहले के बजाय पहले हो सकता था, है ना? यह अस्पष्टता इसलिए है कि मैंने इस समाधान में इसे संबोधित करने की कोशिश नहीं की।

संपादित करें: स्पष्ट होने के लिए, ऊपर दिए गए मेरे समाधान में, यदि साझा ब्रैच का सामना करना पड़ता है, तो यह पूरे सेट को एक घटक के रूप में मानता है। आपने ऊपर वर्णित नहीं किया है, लेकिन समस्या को स्पष्ट करने के बाद इसे बदला जाना होगा। उम्मीद है कि यह आपको बंद कर देता है।

Answer 2

आपको एक पुनरावर्ती क्वेरी का उपयोग करना चाहिए। पहले भाग में हम सभी रिकॉर्ड चुनते हैं जो शीर्ष स्तर के नोड्स (कोई माता-पिता नहीं हैं) और ROW_NUMBER() का उपयोग करके उन्हें समूह आईडी नंबर असाइन करें। फिर पुनरावर्ती भाग में हम उन्हें एक-एक करके बच्चों को जोड़ते हैं और माता-पिता के समूह आईडी संख्याओं का उपयोग करते हैं।

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

रिकर्सिव सीटीई का उपयोग कर ग्राफ चलने की दर्दनाक समस्या। ग्राफ में जुड़े सबग्राफ ढूंढने की समस्या यह है। रिकर्सिव सीटीई का उपयोग करने के साथ चुनौती अनचाहे रिकर्सन को रोकने के लिए है - यानी, असीमित लूप एसक्यूएल सर्वर में, जो आम तौर पर उन्हें स्ट्रिंग में संग्रहीत करने का मतलब है।

विचार है कि जुड़े हुए नोड्स के सभी जोड़े की सूची प्राप्त करना है (और एक नोड स्वयं से जुड़ा हुआ है)। फिर, कनेक्टेड नोड्स की सूची से न्यूनतम लें और कनेक्ट किए गए सबग्राफ के लिए इसे आईडी के रूप में उपयोग करें।

दूसरा विचार ग्राफ को दोनों दिशाओं में नोड से चलना है। यह सुनिश्चित करता है कि सभी संभावित नोड्स का दौरा किया जाता है।

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