डेटाबेसमध्ये कार्यक्षम अवलंबित्व शोधा

डेटा विश्लेषणाच्या विविध क्षेत्रांमध्ये डेटामध्ये कार्यात्मक अवलंबित्वे शोधणे वापरले जाते: डेटाबेस व्यवस्थापन, डेटा साफ करणे, डेटाबेस रिव्हर्स इंजिनिअरिंग आणि डेटा एक्सप्लोरेशन. आम्ही आधीच अवलंबित्वे बद्दल प्रकाशित केले आहे. एक लेख अनास्तासिया बिरिलो आणि निकिता बोब्रोव्ह. यावेळी, या वर्षी संगणक विज्ञान केंद्राची पदवीधर असलेली अनास्तासिया, या संशोधन प्रकल्पाच्या विकासाबद्दल माहिती देते, ज्याचा तिने केंद्रात बचाव केला होता.

कार्य निवड

सीएस सेंटरमध्ये शिकत असताना, मी डेटाबेसचा सखोल अभ्यास करायला सुरुवात केली, विशेषतः, कार्यात्मक आणि भिन्न अवलंबित्वे शोधणे. हा विषय माझ्या विद्यापीठाच्या अभ्यासक्रमाशी संबंधित होता, म्हणून त्यावर काम करत असताना, मी डेटाबेसमधील विविध अवलंबित्वेंबद्दलचे लेख वाचायला सुरुवात केली. मी या क्षेत्राचा आढावा लिहिला - माझ्या पहिल्यापैकी एक लेख इंग्रजीमध्ये लिहिले आणि ते SEIM-२०१७ परिषदेत सादर केले. ते स्वीकारले गेल्यावर मला खूप आनंद झाला आणि मी या विषयात खोलवर जाण्याचा निर्णय घेतला. ही संकल्पना स्वतःच नवीन नाही - ती १९९० पासून अस्तित्वात आहे - परंतु आजही ती अनेक क्षेत्रांमध्ये वापरली जात आहे.

केंद्रातील माझ्या दुसऱ्या सत्रात, मी कार्यात्मक अवलंबित्वे शोधण्यासाठी अल्गोरिदम सुधारण्यासाठी एक संशोधन प्रकल्प सुरू केला. मी सेंट पीटर्सबर्ग स्टेट युनिव्हर्सिटीमधील जेटब्रेन्स रिसर्चमधील पदवीधर विद्यार्थिनी निकिता बोब्रोव्ह यांच्यासोबत त्यावर काम केले.

कार्यात्मक अवलंबित्वे शोधण्याची संगणकीय जटिलता

मुख्य समस्या म्हणजे संगणकीय जटिलता. शक्य किमान आणि क्षुल्लक नसलेल्या अवलंबित्वांची संख्या वरून मर्यादित आहे कुठे — टेबल अॅट्रिब्यूट्सची संख्या. अल्गोरिदमचा चालू वेळ केवळ अॅट्रिब्यूट्सच्या संख्येवरच नाही तर ओळींच्या संख्येवर देखील अवलंबून असतो. १९९० च्या दशकात, एका सामान्य डेस्कटॉप पीसीवर संघीय कायदा शोधण्यासाठी अल्गोरिदम २० पर्यंत अॅट्रिब्यूट्स आणि हजारो ओळी असलेल्या डेटासेटवर अनेक तासांपर्यंत प्रक्रिया करू शकत होते. मल्टी-कोर प्रोसेसरवर चालणारे आधुनिक अल्गोरिदम अंदाजे एकाच वेळी शेकडो अॅट्रिब्यूट्स (२०० पर्यंत) आणि शेकडो हजारो ओळी असलेल्या डेटासेटसाठी अवलंबित्वे शोधतात. तथापि, हे अपुरे आहे: बहुतेक वास्तविक-जगातील अनुप्रयोगांसाठी असा वेळ अस्वीकार्य आहे. म्हणून, आम्ही विद्यमान अल्गोरिदमला गती देण्यासाठी दृष्टिकोन विकसित केले.

विभाजन छेदनबिंदूसाठी कॅशिंग योजना

पेपरच्या पहिल्या भागात, आम्ही विभाजन छेदनबिंदू पद्धतीचा वापर करून अल्गोरिदमच्या वर्गासाठी कॅशिंग योजना विकसित केल्या. विशेषतेसाठी विभाजन म्हणजे सूचींचा संच असतो, जिथे प्रत्येक यादीमध्ये दिलेल्या गुणधर्मासाठी समान मूल्यांसह पंक्ती क्रमांक असतात. अशा प्रत्येक यादीला क्लस्टर म्हणतात. अनेक आधुनिक अल्गोरिदम अवलंबित्व टिकवून ठेवतात की नाही हे निर्धारित करण्यासाठी विभाजने वापरतात, म्हणजेच, ते खालील लेमाचे पालन करतात: अवलंबित्व जर ठेवला तर . येथे विभाजन हे द्वारे दर्शविले जाते, आणि विभाजन आकाराची संकल्पना - त्यातील क्लस्टर्सची संख्या - वापरली जाते. विभाजने वापरणारे अल्गोरिदम जेव्हा अवलंबित्वाचे उल्लंघन होते तेव्हा अवलंबित्वाच्या डाव्या बाजूला अतिरिक्त गुणधर्म जोडतात, नंतर विभाजन छेदनबिंदू ऑपरेशन करून ते पुन्हा मोजतात. या ऑपरेशनला लेखांमध्ये स्पेशलायझेशन म्हणून संबोधले जाते. तथापि, आम्ही असे नोंदवले आहे की स्पेशलायझेशनच्या अनेक फेऱ्यांनंतरच राखले जाणारे अवलंबित्वांसाठी विभाजने सक्रियपणे पुन्हा वापरली जाऊ शकतात, ज्यामुळे अल्गोरिदमचा चालू वेळ लक्षणीयरीत्या कमी होऊ शकतो, कारण छेदनबिंदू ऑपरेशन महाग आहे.

म्हणून, आम्ही शॅनन एन्ट्रॉपी आणि गिनी अनिश्चितता, तसेच आमच्या स्वतःच्या मेट्रिकवर आधारित एक ह्युरिस्टिक प्रस्तावित केला, ज्याला आम्ही इन्व्हर्स एन्ट्रॉपी म्हणतो. हे शॅनन एन्ट्रॉपीचे थोडेसे बदल आहे आणि डेटासेटची विशिष्टता वाढत असताना ते वाढते. प्रस्तावित ह्युरिस्टिक खालीलप्रमाणे आहे:

तो आहे — अलिकडेच गणना केलेल्या विभाजनाच्या विशिष्टतेची डिग्री आणि वैयक्तिक गुणधर्मांसाठी विशिष्टता अंशांचा मध्यक आहे. वर वर्णन केलेले तिन्ही मेट्रिक्स विशिष्टता मेट्रिक्स म्हणून तपासले गेले. हे देखील लक्षात घेतले जाऊ शकते की ह्युरिस्टिकमध्ये दोन मॉडिफायर्स समाविष्ट आहेत. पहिले दर्शवते की वर्तमान विभाजन प्राथमिक कीच्या किती जवळ आहे आणि उमेदवार कीपासून दूर असलेल्या विभाजनांचे अधिक कॅशिंग करण्यास अनुमती देते. दुसरा मॉडिफायर कॅशे ऑक्युपन्सीचे निरीक्षण करतो, ज्यामुळे जागा उपलब्ध असताना कॅशेमध्ये अधिक विभाजने जोडण्यास प्रोत्साहन मिळते. या समस्येचे यशस्वीरित्या निराकरण केल्याने डेटासेटवर अवलंबून PYRO अल्गोरिथमला 10-40% ने गती मिळू शकली. हे लक्षात घेण्यासारखे आहे की PYRO अल्गोरिथम या क्षेत्रात सर्वात यशस्वी आहे.

खालील आकृती नाणे उलगडण्यावर आधारित बेसलाइन कॅशिंग दृष्टिकोनाच्या तुलनेत प्रस्तावित ह्युरिस्टिक लागू करण्याचे परिणाम दर्शवते. x-अक्ष लॉगरिदमिक आहे.

विभाजने साठवण्याचा पर्यायी मार्ग

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

$$display$$pi(X) = {{अंडरब्रेस{1, 2, 3, 4, 5}_{पहिला~अंतराल}, अंडरब्रेस{7, 8}_{दुसरा~अंतराल}, 10}}\डाउनअ‍ॅरो{कम्प्रेशन}\pi(X) = {{अंडरब्रेस{$, 1, 5}_{पहिला~अंतराल}, अंडरब्रेस{7, 8}_{दुसरा~अंतराल}, 10}}$$डिस्प्ले$$

या पद्धतीमुळे TANE अल्गोरिथमच्या अंमलबजावणीदरम्यान मेमरीचा वापर १ ते २५% कमी झाला. TANE अल्गोरिथम हा लॉजिकल झोन शोधण्यासाठी एक क्लासिक अल्गोरिथम आहे; तो त्याच्या ऑपरेशन दरम्यान विभाजनांचा वापर करतो. व्यावहारिक हेतूंसाठी, TANE अल्गोरिथम निवडण्यात आला कारण प्रस्तावित दृष्टिकोनाची व्यवहार्यता मूल्यांकन करण्यासाठी PYRO पेक्षा मध्यांतर स्टोरेज लागू करणे खूपच सोपे होते. परिणाम खालील आकृतीमध्ये सादर केले आहेत. x-अक्ष लॉगरिथमिक आहे.

परिषद ADBIS-२०१९

संशोधनाच्या निकालांवर आधारित, मी सप्टेंबर २०१९ मध्ये एक लेख प्रकाशित केला. कार्यक्षम कार्यात्मक अवलंबित्व शोधासाठी स्मार्ट कॅशिंग डेटाबेस आणि माहिती प्रणालींमधील प्रगतीवरील २३ व्या युरोपियन परिषदेत (ADBIS-२०१९) डेटाबेस क्षेत्रातील एक प्रमुख व्यक्ती बर्नहार्ड थॅलहेम यांनी या कामाची दखल घेतली. सेंट पीटर्सबर्ग स्टेट युनिव्हर्सिटीमधील गणित आणि यांत्रिकी विद्याशाखेतील पदव्युत्तर अभ्यासक्रमासाठी माझ्या प्रबंधाचा आधार या संशोधन निकालांनी घेतला, ज्या दरम्यान प्रस्तावित दृष्टिकोन (कॅशिंग आणि कॉम्प्रेशन) दोन्ही अल्गोरिदममध्ये लागू केले गेले: TANE आणि PYRO. निकालांवरून असे दिसून आले की प्रस्तावित दृष्टिकोन सार्वत्रिक आहेत, कारण दोन्ही अल्गोरिदमने मेमरी वापरात लक्षणीय घट आणि अंमलबजावणी वेळेत लक्षणीय घट दर्शविली.

स्त्रोत: www.habr.com