डेटाबेस में कार्यात्मक निर्भरताएँ कुशलतापूर्वक खोजें

डेटा में कार्यात्मक निर्भरता खोजने का उपयोग डेटा विश्लेषण के विभिन्न क्षेत्रों में किया जाता है: डेटाबेस प्रबंधन, डेटा सफाई, डेटाबेस रिवर्स इंजीनियरिंग और डेटा अन्वेषण। निर्भरताओं के बारे में हम पहले ही प्रकाशित कर चुके हैं लेख अनास्तासिया बिरिलो और निकिता बोब्रोव। इस बार, इस साल के कंप्यूटर साइंस सेंटर से स्नातक अनास्तासिया ने इस काम के विकास को उस शोध कार्य के हिस्से के रूप में साझा किया है जिसका उन्होंने केंद्र में बचाव किया था।

कार्य चयन

सीएस केंद्र में अध्ययन के दौरान, मैंने डेटाबेस का गहराई से अध्ययन करना शुरू किया, अर्थात् कार्यात्मक और अंतर निर्भरता की खोज। यह विषय विश्वविद्यालय में मेरे पाठ्यक्रम के विषय से संबंधित था, इसलिए पाठ्यक्रम पर काम करते समय, मैंने डेटाबेस में विभिन्न निर्भरताओं के बारे में लेख पढ़ना शुरू किया। मैंने इस क्षेत्र की समीक्षा लिखी - मेरी पहली समीक्षा में से एक सामग्री अंग्रेजी में और इसे SEIM-2017 सम्मेलन में प्रस्तुत किया। जब मुझे पता चला कि आखिरकार उसे स्वीकार कर लिया गया है तो मुझे बहुत खुशी हुई और मैंने इस विषय पर गहराई से विचार करने का फैसला किया। यह अवधारणा अपने आप में नई नहीं है - इसका उपयोग 90 के दशक में शुरू हुआ था, लेकिन अब भी इसका उपयोग कई क्षेत्रों में किया जाता है।

केंद्र में अपने दूसरे सेमेस्टर के दौरान, मैंने कार्यात्मक निर्भरता खोजने के लिए एल्गोरिदम में सुधार करने के लिए एक शोध परियोजना शुरू की। उन्होंने जेटब्रेन्स रिसर्च में सेंट पीटर्सबर्ग स्टेट यूनिवर्सिटी की स्नातक छात्रा निकिता बोब्रोव के साथ मिलकर इस पर काम किया।

कार्यात्मक निर्भरताओं की खोज की कम्प्यूटेशनल जटिलता

मुख्य समस्या कम्प्यूटेशनल जटिलता है. संभावित न्यूनतम और गैर-तुच्छ निर्भरताओं की संख्या उपरोक्त मूल्य द्वारा सीमित है जहां - तालिका विशेषताओं की संख्या. एल्गोरिदम का संचालन समय न केवल विशेषताओं की संख्या पर निर्भर करता है, बल्कि पंक्तियों की संख्या पर भी निर्भर करता है। 90 के दशक में, एक नियमित डेस्कटॉप पीसी पर संघीय कानून खोज एल्गोरिदम कई घंटों तक 20 विशेषताओं और हजारों पंक्तियों वाले डेटा सेट को संसाधित कर सकता था। मल्टी-कोर प्रोसेसर पर चलने वाले आधुनिक एल्गोरिदम लगभग एक ही समय में सैकड़ों विशेषताओं (200 तक) और सैकड़ों हजारों पंक्तियों वाले डेटा सेट के लिए निर्भरता का पता लगाते हैं। हालाँकि, यह पर्याप्त नहीं है: ऐसा समय अधिकांश वास्तविक दुनिया के अनुप्रयोगों के लिए अस्वीकार्य है। इसलिए, हमने मौजूदा एल्गोरिदम को तेज़ करने के लिए दृष्टिकोण विकसित किए।

विभाजन चौराहों के लिए कैशिंग योजनाएँ

कार्य के पहले भाग में, हमने एल्गोरिदम के एक वर्ग के लिए कैशिंग योजनाएं विकसित कीं जो विभाजन प्रतिच्छेदन विधि का उपयोग करती हैं। किसी विशेषता के लिए विभाजन सूचियों का एक सेट है, जहां प्रत्येक सूची में किसी दिए गए विशेषता के लिए समान मान वाली पंक्ति संख्याएं होती हैं। ऐसी प्रत्येक सूची को क्लस्टर कहा जाता है। कई आधुनिक एल्गोरिदम यह निर्धारित करने के लिए विभाजन का उपयोग करते हैं कि निर्भरता कायम है या नहीं, अर्थात्, वे लेम्मा का पालन करते हैं: निर्भरता आयोजित यदि । यहां एक विभाजन नामित किया गया है और विभाजन आकार की अवधारणा का उपयोग किया जाता है - इसमें समूहों की संख्या। विभाजन का उपयोग करने वाले एल्गोरिदम, जब निर्भरता का उल्लंघन होता है, तो निर्भरता के बाईं ओर अतिरिक्त विशेषताएँ जोड़ते हैं, और फिर विभाजन के प्रतिच्छेदन का संचालन करते हुए इसकी पुनर्गणना करते हैं। इस ऑपरेशन को लेखों में विशेषज्ञता कहा जाता है। लेकिन हमने देखा कि निर्भरता के लिए विभाजन जो विशेषज्ञता के कुछ दौरों के बाद ही बरकरार रहेंगे, उन्हें सक्रिय रूप से पुन: उपयोग किया जा सकता है, जो एल्गोरिदम के चलने के समय को काफी कम कर सकता है, क्योंकि इंटरसेक्शन ऑपरेशन महंगा है।

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

यहां — हाल ही में गणना किए गए विभाजन की विशिष्टता की डिग्री और व्यक्तिगत विशेषताओं के लिए विशिष्टता की डिग्री का माध्यिका है। ऊपर वर्णित सभी तीन मेट्रिक्स का परीक्षण विशिष्टता मेट्रिक के रूप में किया गया था। आप यह भी देख सकते हैं कि अनुमान में दो संशोधक हैं। पहला इंगित करता है कि वर्तमान विभाजन प्राथमिक कुंजी के कितना करीब है और आपको उन विभाजनों को अधिक हद तक कैश करने की अनुमति देता है जो संभावित कुंजी से बहुत दूर हैं। दूसरा संशोधक आपको कैश अधिभोग की निगरानी करने की अनुमति देता है और इस तरह खाली स्थान उपलब्ध होने पर कैश में अधिक विभाजन जोड़ने को प्रोत्साहित करता है। इस समस्या के सफल समाधान ने हमें डेटासेट के आधार पर PYRO एल्गोरिदम को 10-40% तक तेज़ करने की अनुमति दी। यह ध्यान देने योग्य है कि PYRO एल्गोरिथ्म इस क्षेत्र में सबसे सफल है।

नीचे दिए गए चित्र में आप बुनियादी सिक्का-फ्लिप कैशिंग दृष्टिकोण की तुलना में प्रस्तावित अनुमान को लागू करने के परिणाम देख सकते हैं। एक्स अक्ष लघुगणकीय है.

विभाजनों को संग्रहीत करने का एक वैकल्पिक तरीका

फिर हमने विभाजनों को संग्रहीत करने का एक वैकल्पिक तरीका प्रस्तावित किया। विभाजन समूहों का एक समूह है, जिनमें से प्रत्येक कुछ विशेषताओं के लिए समान मान वाले टुपल्स की संख्या संग्रहीत करता है। इन समूहों में टुपल संख्याओं के लंबे अनुक्रम हो सकते हैं, उदाहरण के लिए यदि किसी तालिका में डेटा क्रमबद्ध है। इसलिए, हमने विभाजनों को संग्रहीत करने के लिए एक संपीड़न योजना प्रस्तावित की, अर्थात् विभाजनों के समूहों में मूल्यों का अंतराल भंडारण:

$$display$$pi(X) = {{अंडरब्रेस{1, 2, 3, 4, 5}_{पहला अंतराल}, अंडरब्रेस{7, 8}_{दूसरा अंतराल}, 10}}\ डाउनएरो{ संपीड़न} \ pi(X) = {{अंडरब्रेस{$, 1, 5}_{पहला~अंतराल}, अंडरब्रेस{7, 8}_{दूसरा~अंतराल}, 10}}$$display$$

यह विधि TANE एल्गोरिथम के संचालन के दौरान मेमोरी खपत को 1 से 25% तक कम करने में सक्षम थी। TANE एल्गोरिथ्म संघीय कानूनों की खोज के लिए एक क्लासिक एल्गोरिदम है, यह अपने काम के दौरान विभाजन का उपयोग करता है। अभ्यास के भाग के रूप में, TANE एल्गोरिथ्म को चुना गया था, क्योंकि प्रस्तावित दृष्टिकोण काम करता है या नहीं, इसका मूल्यांकन करने के लिए, उदाहरण के लिए, PYRO की तुलना में इसमें अंतराल भंडारण को लागू करना बहुत आसान था। प्राप्त परिणाम नीचे दिए गए चित्र में प्रस्तुत किए गए हैं। एक्स अक्ष लघुगणकीय है.

सम्मेलन ADBIS-2019

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

स्रोत: www.habr.com