क्या यह एक रिलेशनल डेटाबेस में ग्राफ डेटा-संरचना को मैप करने के लिए समझ में आता है?

Question

विशेष रूप से Multigraph।

कुछ सहयोगी ने इसका सुझाव दिया और मैं पूरी तरह से परेशान हूं।

इस पर कोई अंतर्दृष्टि?

Answer 1

डेटाबेस में ग्राफ को स्टोर करने के लिए यह बहुत सरल है: आपके पास नोड्स के लिए एक टेबल है, और किनारों के लिए एक टेबल है, जो नोड्स तालिका और स्वयं के बीच कई से अधिक रिश्ते तालिका के रूप में कार्य करती है। इस तरह:

create table node (
    id integer primary key 
); 

create table edge (
    start_id integer references node, 
    end_id integer references node, 
    primary key (start_id, end_id) 
); 

हालांकि, इस तरह ग्राफ को संग्रहीत करने के बारे में कुछ चिपचिपा बिंदु हैं।

सबसे पहले, इस योजना के किनारों को स्वाभाविक रूप से निर्देशित किया जाता है - शुरुआत और अंत अलग-अलग होते हैं। यदि आपके किनारों को अप्रत्यक्ष किया गया है, तो आपको या तो प्रश्नों को लिखने में सावधान रहना होगा, या प्रत्येक किनारे के लिए तालिका में दो प्रविष्टियों को स्टोर करना होगा, एक दिशा में एक (और फिर सावधानीपूर्वक प्रश्न पूछना चाहिए!)। यदि आप एक किनारे को स्टोर करते हैं, तो मैं संग्रहीत रूप को सामान्यीकृत करने का सुझाव दूंगा - शायद हमेशा निम्नतम आईडी के साथ नोड को शुरू करने के लिए विचार करें (और इसे लागू करने के लिए तालिका में चेक बाधा जोड़ें)। किनारों को नोड्स का संदर्भ नहीं देकर आप वास्तव में अनियंत्रित प्रतिनिधित्व कर सकते हैं, बल्कि उनके बीच एक टेबल शामिल कर सकते हैं, लेकिन यह मेरे लिए एक अच्छा विचार नहीं लग रहा है।

दूसरा, उपरोक्त स्कीमा में एक मल्टीग्राफ का प्रतिनिधित्व करने का कोई तरीका नहीं है।आप इसे करने के लिए आसानी से पर्याप्त विस्तार कर सकते हैं; यदि किसी दिए गए जोड़ी के नोड्स के बीच किनारे अलग-अलग हैं, तो सबसे आसान बात यह है कि प्रत्येक किनारे की पंक्ति में गिनती जोड़नी होगी, यह कहकर कि निर्दिष्ट-नोड्स के बीच कितने किनारे हैं। यदि वे अलग-अलग हैं, तो आपको नोड तालिका में कुछ जोड़ने की आवश्यकता होगी ताकि उन्हें प्रतिष्ठित किया जा सके - एक स्वत: जेनरेटेड एज आईडी सबसे सरल चीज हो सकती है।

हालांकि, स्टोरेज को हल करने के बावजूद, आपको ग्राफ के साथ काम करने की समस्या है। यदि आप स्मृति में ऑब्जेक्ट्स पर अपनी सभी प्रोसेसिंग करना चाहते हैं, और डेटाबेस पूरी तरह से स्टोरेज के लिए है, तो कोई समस्या नहीं है। लेकिन यदि आप डेटाबेस में आलेख पर प्रश्न पूछना चाहते हैं, तो आपको यह पता लगाना होगा कि उन्हें SQL में कैसे करना है, जिसमें ग्राफ़ के लिए कोई अंतर्निहित समर्थन नहीं है, और जिनके मूल संचालन आसानी से अनुकूलित नहीं किए जाते हैं ग्राफ के साथ काम करते हैं। यह किया जा सकता है, खासकर यदि आपके पास रिकर्सिव एसक्यूएल सपोर्ट (पोस्टग्रेएसक्यूएल, फायरबर्ड, कुछ स्वामित्व डेटाबेस) के साथ डेटाबेस है, लेकिन इसमें कुछ विचार लगता है। यदि आप ऐसा करना चाहते हैं, तो मेरा सुझाव विशिष्ट प्रश्नों के बारे में और प्रश्न पोस्ट करना होगा।

Answer 2

ठीक है, जानकारी कहीं भी संग्रहीत की जानी है, एक संबंधपरक डेटाबेस एक बुरा विचार नहीं है।

यह बहुत से रिश्तों, नोड्स की एक सूची की एक तालिका, और किनारों/कनेक्शन की सूची की तालिका होगी।

Answer 3

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

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

Answer 4

यह एक स्वीकार्य दृष्टिकोण है। आपको यह समझने की जरूरत है कि उस जानकारी को कैसे छेड़छाड़ की जाएगी। संभावना से अधिक आपको इस प्रकार के डेटा का तात्पर्य है, इस तरह के ग्राफ़ से संबंधित कंप्यूटेशंस के प्रकार के लिए आपको अपने डेटाबेस से अलग एक भाषा की आवश्यकता होगी। Skiena's Algorithm Design Manual में एक विस्तृत खंड ग्राफ डेटा संरचनाएं और उनके हेरफेर हैं।

इस बात पर विचार किए बिना कि आप किस प्रकार के प्रश्न निष्पादित कर सकते हैं, दो टेबल vertices और edges से शुरू करें। वर्टिसेस सरल, पहचानकर्ता और नाम हैं। किनारों को मल्टीग्राफ दिया गया जटिल है। किनारों को दो अक्षरों (यानी विदेशी कुंजी) और कुछ अतिरिक्त जानकारी के संयोजन द्वारा विशिष्ट रूप से पहचाना जाना चाहिए। अतिरिक्त जानकारी उस समस्या पर निर्भर है जिसे आप हल कर रहे हैं। उदाहरण के लिए, यदि उड़ान की जानकारी, प्रस्थान और आगमन के समय और एयरलाइन। इसके अलावा आपको यह तय करने की आवश्यकता होगी कि किनारे को निर्देशित किया गया है (यानी एक तरफ) या नहीं और उस जानकारी को ट्रैक करते रहें।

गणना के आधार पर आप किसी समस्या के साथ समाप्त हो सकते हैं जो किसी प्रकार की कृत्रिम बुद्धि/मशीन लर्निंग एल्गोरिदम के साथ बेहतर हल हो जाती है। उदाहरण के लिए, इष्टतम उड़ानें। इस उद्देश्य के लिए Programming Collective Intelligence पुस्तक में कुछ उपयोगी एल्गोरिदम हैं। लेकिन जहां डेटा रखा जाता है, वह एल्गोरिदम स्वयं नहीं बदलता है।