पंक्तियों को एक नियम के

Question

मैं एक बड़ी मेज (1M पंक्तियां) निम्नलिखित कॉलम के साथ है का पालन की जोड़ी का चयन करें। प्रत्येक पंक्ति एक लिंक को परिभाषित करती है (ए से बी तक)।

मुझे एनोटर नोड का उपयोग करके एक जोड़ी के बीच दूरी खोजने की आवश्यकता है। एक उदाहरण: तो अगर मैं एक नोड एक्स खोजने के लिए और है ए और बी, के बीच की दूरी को खोजने के लिए चाहते हैं: एक्स -> एक एक्स -> बी मैं इन दूरियों को जोड़ने और ए और बी beetween दूरी हो सकता है मेरा प्रश्न: मैं सभी नोड्स (जैसे एक्स) कैसे ढूंढ सकता हूं और उनकी दूरी (ए और बी) प्राप्त कर सकता हूं? मेरा उद्देश्य दूरी के न्यूनतम मूल्य का चयन करना है।

पी.एस: ए और बी सिर्फ एक कनेक्शन (मैं 100K कनेक्शन के लिए यह सब करने की ज़रूरत) कर रहे हैं। धन्यवाद!

Answer 1

मान लिया जाये कि आप कई मध्यवर्ती चरणों के साथ एक-बी से पथ प्राप्त करना चाहते हैं यह कदम की एक अनिश्चित संख्या के लिए सादे एसक्यूएल में यह करने के लिए असंभव है। सीधे शब्दों में कहें, इसमें अभिव्यक्ति शक्ति की कमी है, http://en.wikipedia.org/wiki/Expressive_power#Expressive_power_in_database_theory देखें। जैसा कि एंडोमर ने कहा, डेटा को एक प्रक्रिया में लोड करें और हमें Djikstra के एल्गोरिदम।

Answer 2

यह traveling salesman problem तरह लगता है।

एक एसक्यूएल सिंटैक्स दृष्टिकोण से: connect by prior शुरुआत के उपयोग के बाद पेड़ का निर्माण करेगा और परतों की संख्या को सीमित कर देगा; हालांकि, न्यूनतम गारंटी की गारंटी नहीं होगी।

Answer 3

मैं इसके लिए downvoted हो सकता है, लेकिन मैं यह एक दिलचस्प समस्या पाते हैं। मेरी इच्छा है कि यह एक और अधिक खुली चर्चा हो सकती है, क्योंकि मुझे लगता है कि मैं इससे बहुत कुछ सीख सकता हूं।

ऐसा लगता है कि यह कई चुनिंदा बयान करने से इस लक्ष्य को हासिल करने के लिए संभव होना चाहिए - SELECT id FROM mytable WHERE source="A" ORDER BY distance ASC LIMIT 1 की तरह कुछ। थोड़ी देर में इस तरह कुछ लपेटना, और एक आईडी चर के साथ "ए" को बदलना, चाल करेगा, नहीं?

उदाहरण के लिए (एक सूत्र है, बी अंतिम गंतव्य है):

DECLARE var_id as INT 
WHILE var_id != 'B' 
    BEGIN 
    SELECT id INTO var_id FROM mytable WHERE source="A" ORDER BY distance ASC LIMIT 1 
    SELECT var_id 
    END 

नहीं चाहेंगे इस काम की तरह कुछ? (कोड मैला है, लेकिन विचार ध्वनि लगता है।) टिप्पणियाँ स्वागत से अधिक हैं।

Answer 4

स्रोत में शामिल गंतव्य के साथ तालिका में शामिल हों। दो लिंक से दूरी जोड़ें। बाएं तरफ स्रोत के साथ एक नए लिंक के रूप में डालें, दाएं तरफ गंतव्य और कुल दूरी यदि वह पहले से ही तालिका में नहीं है। यदि वह तालिका में है लेकिन कम दूरी के साथ, तो छोटी दूरी के साथ मौजूदा पंक्ति को अद्यतन करें।

तब तक दोहराएं जब तक आपको तालिका में कोई नया लिंक नहीं जोड़ा जाता है और कम दूरी के साथ कोई अपडेट नहीं मिलता है। आपकी तालिका में अब स्रोत और गंतव्य के हर संभावित संयोजन के लिए उनके बीच न्यूनतम दूरी के साथ एक लिंक शामिल है। यह देखना दिलचस्प होगा कि यह कितनी बार दोहराएगा।

यह स्रोत और गंतव्य के बीच मध्यवर्ती पथ को ट्रैक नहीं करेगा बल्कि केवल सबसे छोटी दूरी प्रदान करेगा।

Answer 5

रूप Andomar कहा, तुम डिज्कस्ट्रा एल्गोरिथ्म की आवश्यकता होगी, यहाँ T-SQL में है कि एल्गोरिथ्म के लिए एक लिंक है: T-SQL Dijkstra's Algorithm

Answer 6

IIUC ऐसा करने चाहिए, लेकिन मुझे यकीन है कि अगर यह वास्तव में व्यवहार्य है नहीं कर रहा हूँ (प्रदर्शन वार) शामिल पंक्तियों की बड़ी राशि के लिए और पार की वजह से शामिल हों

SELECT 
    t1.src AS A, 
    t1.dest AS x, 
    t2.dest AS B, 
    t1.distance + t2.distance AS total_distance 
FROM 
    big_table AS t1 
CROSS JOIN 
    big_table AS t2 ON t1.dst = t2.src 
WHERE 
    A = 'insert source (A) here' AND 
    B = 'insert destination (B) here' 
ORDER BY 
    total_distance ASC 
LIMIT 
    1 

ऊपर टुकड़ा मामला है जिसमें आप के रूप में दो पंक्तियों है A-> एक्स और x-> बी लेकिन के लिए काम करेंगे अन्य संयोजनों के लिए नहीं (उदाहरण के लिए ए-> एक्स और बी-> एक्स)। सभी चार संयोजनों को कवर करने के लिए इसे विस्तारित करना छोटा होना चाहिए (उदा। एक दृश्य बनाएं जो प्रत्येक पंक्ति को डुप्लिकेट करता है और src और dest swaps)।