डेटाबेसहरूमा कार्यात्मक निर्भरताहरू कुशलतापूर्वक फेला पार्नुहोस्

डाटामा कार्यात्मक निर्भरताहरू पत्ता लगाउने डाटा विश्लेषणका विभिन्न क्षेत्रहरूमा प्रयोग गरिन्छ: डाटाबेस व्यवस्थापन, डाटा क्लीनिङ, डाटाबेस रिभर्स इन्जिनियरिङ र डाटा अन्वेषण। हामीले पहिले नै निर्भरताहरू बारे प्रकाशित गरिसकेका छौं लेख Anastasia Birillo र निकिता Bobrov। यस पटक, अनास्तासिया, यस वर्ष कम्प्यूटर विज्ञान केन्द्रको स्नातक, अनुसन्धान कार्यको भागको रूपमा यस कार्यको विकास साझा गर्छिन् जुन उनले केन्द्रमा रक्षा गरे।

कार्य चयन

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

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

कार्यात्मक निर्भरताहरू खोज्ने कम्प्युटेसनल जटिलता

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

विभाजन प्रतिच्छेदनका लागि क्यासिङ योजनाहरू

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

तसर्थ, हामीले श्यानन एन्ट्रोपी र गिनी अनिश्चितता, साथै हाम्रो मेट्रिक, जसलाई हामीले रिभर्स एन्ट्रोपी भनिन्छ, मा आधारित एक ह्युरिस्टिक प्रस्ताव गर्यौं। यो Shannon Entropy को एक सानो परिमार्जन हो र डेटा सेटको विशिष्टता बढ्दै जाँदा बढ्छ। प्रस्तावित ह्युरिस्टिक निम्नानुसार छ:

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

तलको चित्रमा तपाईले आधारभूत सिक्का-फ्लिप क्यासिङ दृष्टिकोणको तुलनामा प्रस्तावित हेरिस्टिक लागू गर्ने परिणामहरू देख्न सक्नुहुन्छ। X अक्ष लघुगणकीय छ।

विभाजन भण्डारण गर्न वैकल्पिक तरिका

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

$$display$$pi(X) = {{अन्डरब्रेस{1, 2, 3, 4, 5}_{प्रथम अन्तराल}, अन्डरब्रेस{7, 8}_{दोस्रो अन्तराल}, 10}}\ डाउनएरो{ कम्प्रेसन} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{सेकेन्ड~interval}, 10}}$$display$$

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

सम्मेलन ADBIS-2019

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

स्रोत: www.habr.com