कार्यात्मक अवलंबनांचा परिचय

या लेखात आम्ही डेटाबेसमधील कार्यात्मक अवलंबनांबद्दल बोलू - ते काय आहेत, ते कुठे वापरले जातात आणि त्यांना शोधण्यासाठी कोणते अल्गोरिदम अस्तित्वात आहेत.

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

उदाहरणार्थ, वरील तक्त्यामध्ये, (बेन्सन, एम, एम ऑर्गन) गुणधर्मांचा एक टपल आहे (रुग्ण, पॉल, डॉक्टर).
अधिक औपचारिकपणे, हे खालीलप्रमाणे लिहिले आहे: [रुग्ण, लिंग, डॉक्टर] = (बेन्सन, एम, एम ऑर्गन).
आता आपण कार्यात्मक अवलंबन (FD) ची संकल्पना सादर करू शकतो:

व्याख्या १. संबंध R फेडरल कायद्याचे समाधान करतो X → Y (जेथे X, Y ⊆ R) जर आणि फक्त कोणत्याही ट्युपल्ससाठी , ∈ R धारण करतो: जर [X] = [X], नंतर [Y] = [वाय]. या प्रकरणात, आम्ही म्हणतो की X (निर्धारक, किंवा गुणधर्मांचा परिभाषित संच) कार्यात्मकपणे Y (आश्रित संच) निर्धारित करतो.

दुसऱ्या शब्दांत, फेडरल कायद्याची उपस्थिती X → Y याचा अर्थ असा की जर आपल्याकडे दोन टपल्स असतील R आणि ते गुणधर्मांमध्ये जुळतात X, नंतर ते गुणधर्मांमध्ये एकरूप होतील Y.
आणि आता क्रमाने. चला गुणधर्म पाहू एक रुग्ण и पॉल ज्यासाठी आम्हाला त्यांच्यामध्ये अवलंबित्व आहे की नाही हे शोधायचे आहे. अशा गुणधर्मांच्या संचासाठी, खालील अवलंबित्व अस्तित्वात असू शकतात:

1. रुग्ण → लिंग
2. लिंग → रुग्ण

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

अशा प्रकारे, कार्यात्मक अवलंबित्व सारणी गुणधर्मांच्या संचामधील विद्यमान संबंध निर्धारित करणे शक्य करते. येथून पुढे आम्ही सर्वात मनोरंजक कनेक्शन किंवा त्याऐवजी अशा गोष्टींचा विचार करू X → Yते काय आहेत:

• गैर-क्षुल्लक, म्हणजे, अवलंबनाची उजवी बाजू डावीकडील उपसंच नाही (Y ̸⊆ X);
• किमान, म्हणजे, असे कोणतेही अवलंबित्व नाही Z → Y, की Z ⊂ X.

या बिंदूपर्यंत विचारात घेतलेली अवलंबित्व कठोर होती, म्हणजेच त्यांनी टेबलवर कोणत्याही उल्लंघनाची तरतूद केली नाही, परंतु त्याव्यतिरिक्त, असे देखील आहेत जे ट्यूपल्सच्या मूल्यांमध्ये काही विसंगती निर्माण करण्यास परवानगी देतात. अशा अवलंबित्वांना एका वेगळ्या वर्गात ठेवले जाते, ज्याला अंदाजे म्हणतात, आणि विशिष्ट संख्येच्या ट्यूपल्ससाठी त्यांचे उल्लंघन करण्याची परवानगी आहे. ही रक्कम कमाल त्रुटी निर्देशक emax द्वारे नियंत्रित केली जाते. उदाहरणार्थ, त्रुटी दर = 0.01 चा अर्थ असा असू शकतो की गुणधर्मांच्या विचारात घेतलेल्या संचावरील उपलब्ध ट्युपल्सच्या 1% द्वारे अवलंबित्वाचे उल्लंघन केले जाऊ शकते. म्हणजेच, 1000 रेकॉर्डसाठी, जास्तीत जास्त 10 ट्यूपल्स फेडरल कायद्याचे उल्लंघन करू शकतात. तुलना केल्या जाणार्‍या ट्युपल्सच्या जोडीनुसार भिन्न मूल्यांवर आधारित आम्ही थोड्या वेगळ्या मेट्रिकचा विचार करू. व्यसनासाठी X → Y वृत्तीवर r हे असे मानले जाते:

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

आता या प्रश्नाचे उत्तर देण्याचा प्रयत्न करूया: "हे सर्व कशासाठी आहे?" खरं तर, फेडरल कायदे वेगळे आहेत. पहिला प्रकार म्हणजे डेटाबेस डिझाइन स्टेजवर प्रशासकाद्वारे निर्धारित केलेल्या अवलंबित्वांचा. ते सहसा संख्येने कमी, कठोर असतात आणि मुख्य अनुप्रयोग म्हणजे डेटा सामान्यीकरण आणि रिलेशनल स्कीमा डिझाइन.

दुसरा प्रकार म्हणजे अवलंबित्व, जे "लपवलेले" डेटा आणि विशेषतांमधील पूर्वीचे अज्ञात संबंध दर्शवतात. म्हणजेच, डिझाइनच्या वेळी अशा अवलंबनांचा विचार केला गेला नाही आणि ते विद्यमान डेटा सेटसाठी आढळले, जेणेकरून नंतर, अनेक ओळखल्या गेलेल्या फेडरल कायद्यांच्या आधारे, संग्रहित माहितीबद्दल कोणतेही निष्कर्ष काढले जाऊ शकतात. तंतोतंत या अवलंबनांवरच आपण काम करतो. त्यांच्या आधारे तयार केलेल्या विविध शोध तंत्रे आणि अल्गोरिदमसह डेटा मायनिंगच्या संपूर्ण क्षेत्राद्वारे ते हाताळले जातात. कोणत्याही डेटामध्ये सापडलेल्या कार्यात्मक अवलंबित्व (अचूक किंवा अंदाजे) कसे उपयुक्त ठरू शकतात ते शोधू या.

आज, अवलंबनांच्या मुख्य अनुप्रयोगांपैकी एक म्हणजे डेटा साफ करणे. यात "घाणेरडा डेटा" ओळखण्यासाठी आणि नंतर दुरुस्त करण्यासाठी प्रक्रिया विकसित करणे समाविष्ट आहे. “डर्टी डेटा” ची प्रमुख उदाहरणे म्हणजे डुप्लिकेट, डेटा एरर किंवा टायपो, गहाळ मूल्ये, कालबाह्य डेटा, अतिरिक्त जागा आणि यासारखे.

डेटा त्रुटीचे उदाहरण:

डेटामधील डुप्लिकेटचे उदाहरण:

उदाहरणार्थ, आमच्याकडे एक टेबल आणि फेडरल कायद्यांचा संच आहे ज्याची अंमलबजावणी करणे आवश्यक आहे. या प्रकरणात डेटा क्लीनिंगमध्ये डेटा बदलणे समाविष्ट आहे जेणेकरून फेडरल कायदे योग्य होतील. या प्रकरणात, सुधारणांची संख्या कमीतकमी असावी (या प्रक्रियेचे स्वतःचे अल्गोरिदम आहेत, ज्यावर आम्ही या लेखात लक्ष केंद्रित करणार नाही). खाली अशा डेटा ट्रान्सफॉर्मेशनचे उदाहरण आहे. डावीकडे मूळ संबंध आहे, ज्यामध्ये, स्पष्टपणे, आवश्यक FLs पूर्ण केले जात नाहीत (FLs पैकी एकाच्या उल्लंघनाचे उदाहरण लाल रंगात हायलाइट केले आहे). उजवीकडे अद्ययावत संबंध आहे, हिरव्या पेशी बदललेली मूल्ये दर्शवित आहेत. या प्रक्रियेनंतर, आवश्यक अवलंबित्व राखले जाऊ लागले.

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

खालील चित्रातील चार सामान्य फॉर्मसाठी त्यांच्या अर्जाचा विचार करूया. लक्षात ठेवा की Boyce-Codd सामान्य स्वरूप तिसऱ्या स्वरूपापेक्षा अधिक कठोर आहे, परंतु चौथ्यापेक्षा कमी कठोर आहे. आम्ही आत्तासाठी नंतरचा विचार करत नाही, कारण त्याच्या निर्मितीसाठी बहु-मौल्यवान अवलंबनांची समज आवश्यक आहे, जी या लेखात आमच्यासाठी मनोरंजक नाही.

आणखी एक क्षेत्र ज्यामध्ये अवलंबित्वांना त्यांचा अनुप्रयोग सापडला आहे ते म्हणजे निष्कलंक बेयस क्लासिफायर तयार करणे, महत्त्वपूर्ण वैशिष्ट्ये ओळखणे आणि प्रतिगमन मॉडेलचे पुनर्परिमाणीकरण करणे यासारख्या कार्यांमध्ये वैशिष्ट्य स्पेसची आयामीता कमी करणे. मूळ लेखांमध्ये, या कार्याला निरर्थक आणि वैशिष्ट्य प्रासंगिकतेचे निर्धारण असे म्हणतात [5, 6], आणि डेटाबेस संकल्पनांच्या सक्रिय वापराने त्याचे निराकरण केले जाते. अशा कामांच्या आगमनाने, आम्ही असे म्हणू शकतो की आज अशा उपायांची मागणी आहे जी आम्हाला वरील ऑप्टिमायझेशन समस्यांचे डेटाबेस, विश्लेषणे आणि अंमलबजावणी एका साधनामध्ये एकत्रित करण्याची परवानगी देतात [7, 8, 9].

डेटा सेटमध्ये फेडरल कायदे शोधण्यासाठी अनेक अल्गोरिदम (आधुनिक आणि इतके आधुनिक नाही दोन्ही) आहेत. अशा अल्गोरिदम तीन गटांमध्ये विभागल्या जाऊ शकतात:

• बीजगणितीय जाळींचा ट्रॅव्हर्सल वापरून अल्गोरिदम (लॅटिस ट्रॅव्हर्सल अल्गोरिदम)
• सहमत मूल्यांच्या शोधावर आधारित अल्गोरिदम (फरक- आणि सहमत-सेट अल्गोरिदम)
• जोडीनुसार तुलनांवर आधारित अल्गोरिदम (अवलंबन इंडक्शन अल्गोरिदम)

प्रत्येक प्रकारच्या अल्गोरिदमचे संक्षिप्त वर्णन खालील तक्त्यामध्ये सादर केले आहे:


आपण या वर्गीकरणाबद्दल अधिक वाचू शकता [4]. खाली प्रत्येक प्रकारासाठी अल्गोरिदमची उदाहरणे आहेत:

सध्या, नवीन अल्गोरिदम दिसून येत आहेत जे कार्यात्मक अवलंबित्व शोधण्यासाठी अनेक दृष्टिकोन एकत्र करतात. अशा अल्गोरिदमची उदाहरणे पायरो [२] आणि हायएफडी [३] आहेत. या मालिकेच्या पुढील लेखांमध्ये त्यांच्या कार्याचे विश्लेषण अपेक्षित आहे. या लेखात आम्ही फक्त मूलभूत संकल्पना आणि लेमा तपासू ज्या अवलंबित्व शोध तंत्र समजून घेण्यासाठी आवश्यक आहेत.

दुसर्‍या प्रकारच्या अल्गोरिदममध्ये वापरल्या जाणार्‍या एका साध्या - फरक- आणि सहमत-सेटसह प्रारंभ करूया. डिफरन्स-सेट हा ट्युपल्सचा एक संच आहे ज्यात समान मूल्ये नसतात, तर सहमत-सेट, त्याउलट, समान मूल्ये असलेले ट्यूपल्स असतात. हे लक्षात घेण्यासारखे आहे की या प्रकरणात आम्ही केवळ अवलंबनाच्या डाव्या बाजूचा विचार करीत आहोत.

दुसरी महत्त्वाची संकल्पना जी वर आली ती म्हणजे बीजगणितीय जाळी. अनेक आधुनिक अल्गोरिदम या संकल्पनेवर कार्य करत असल्याने, आम्हाला ते काय आहे याची कल्पना असणे आवश्यक आहे.

जाळीची संकल्पना सादर करण्यासाठी, अंशतः ऑर्डर केलेला संच (किंवा अंशतः ऑर्डर केलेला संच, पोसेट म्हणून संक्षिप्त) परिभाषित करणे आवश्यक आहे.

व्याख्या १. जर सर्व a, b, c ∈ S साठी खालील गुणधर्म समाधानी असतील तर एक संच S हा बायनरी संबंध ⩽ द्वारे अंशतः क्रमबद्ध केला जातो असे म्हटले जाते:

1. रिफ्लेक्सिव्हिटी, म्हणजे, a ⩽ a
2. प्रतिसममिती, म्हणजे, जर a ⩽ b आणि b ⩽ a असेल, तर a = b
3. संक्रमण, म्हणजे, a ⩽ b आणि b ⩽ c साठी ते a ⩽ c चे अनुसरण करते

अशा संबंधाला (लूज) आंशिक ऑर्डर रिलेशन म्हणतात आणि सेटलाच आंशिक ऑर्डर केलेला सेट म्हणतात. औपचारिक नोटेशन: ⟨S, ⩽⟩.

अंशतः क्रमबद्ध केलेल्या संचाचे सर्वात सोपे उदाहरण म्हणून, आपण नेहमीच्या क्रम संबंध ⩽ सह सर्व नैसर्गिक संख्या N चा संच घेऊ शकतो. सर्व आवश्यक स्वयंसिद्धी समाधानी आहेत हे सत्यापित करणे सोपे आहे.

अधिक अर्थपूर्ण उदाहरण. सर्व उपसमूहांचा संच विचारात घ्या {1, 2, 3}, समावेशन संबंध ⊆ द्वारे क्रमाने. खरंच, हा संबंध सर्व आंशिक क्रम स्थिती पूर्ण करतो, म्हणून ⟨P ({1, 2, 3}), ⊆⟩ हा अंशतः क्रमबद्ध संच आहे. खालील आकृती या संचाची रचना दर्शवते: जर एका घटकाला बाणांनी दुसर्‍या घटकापर्यंत पोहोचवता आले, तर ते क्रमाने नातेसंबंधात आहेत.

आपल्याला गणिताच्या क्षेत्रातील आणखी दोन सोप्या व्याख्यांची आवश्यकता असेल - सर्वोच्च आणि इन्फिमम.

व्याख्या १. ⟨S, ⩽⟩ अंशतः क्रमबद्ध संच असू द्या, A ⊆ S. A ची वरची सीमा u ∈ S असा घटक आहे की ∀x ∈ S: x ⩽ u. U हा S च्या सर्व वरच्या सीमांचा संच असू द्या. जर U मध्ये सर्वात लहान घटक असेल तर त्याला सर्वोच्च म्हणतात आणि त्याला sup A दर्शविले जाते.

तंतोतंत लोअर बाउंडची संकल्पना त्याच प्रकारे सादर केली गेली आहे.

व्याख्या १. ⟨S, ⩽⟩ अंशतः क्रमबद्ध संच असू द्या, A ⊆ S. A चा infimum हा घटक l ∈ S असा आहे की ∀x ∈ S: l ⩽ x. L हा S च्या सर्व खालच्या सीमांचा संच असू द्या. जर L मध्ये सर्वात मोठा घटक असेल, तर त्याला इन्फिमम म्हणतात आणि inf A म्हणून दर्शविले जाते.

उदाहरण म्हणून वरील अर्धवट क्रमाने दिलेला संच ⟨P ({1, 2, 3}), ⊆⟩ विचारात घ्या आणि त्यात सर्वोच्च आणि infimum शोधा:

आता आपण बीजगणितीय जाळीची व्याख्या तयार करू शकतो.

व्याख्या १. ⟨P,⩽⟩ अंशतः क्रमबद्ध संच असू द्या की प्रत्येक दोन-घटकांच्या उपसंचाला वरच्या आणि खालच्या सीमा असतात. मग P ला बीजगणितीय जाळी म्हणतात. या प्रकरणात, sup{x, y} हे x ∨ y, आणि inf {x, y} x ∧ y असे लिहिले आहे.

चला तपासूया की आमचे कार्यरत उदाहरण ⟨P ({1, 2, 3}), ⊆⟩ एक जाळी आहे. खरंच, कोणत्याही a, b ∈ P ({1, 2, 3}), a∨b = a∪b, आणि a∧b = a∩b साठी. उदाहरणार्थ, {1, 2} आणि {1, 3} संच विचारात घ्या आणि त्यांचे इन्फिमम आणि सर्वोच्च शोधा. जर आपण त्यांना छेदले तर आपल्याला {1} हा संच मिळेल, जो इन्फिमम असेल. त्यांना एकत्र करून आपल्याला सर्वोच्च मिळते - {1, 2, 3}.

भौतिक समस्या ओळखण्यासाठी अल्गोरिदममध्ये, शोध जागा बर्‍याचदा जाळीच्या स्वरूपात दर्शविली जाते, जिथे एका घटकाचे संच (शोध जाळीचा पहिला स्तर वाचा, जिथे अवलंबनांच्या डाव्या बाजूला एक विशेषता असते) प्रत्येक विशेषता दर्शवते. मूळ नात्याचे.
प्रथम, आम्ही ∅ → फॉर्मच्या अवलंबनांचा विचार करतो एकल विशेषता. ही पायरी तुम्हाला कोणती विशेषता प्राथमिक की आहेत हे निर्धारित करण्यास अनुमती देते (अशा विशेषतांसाठी कोणतेही निर्धारक नाहीत आणि म्हणून डावी बाजू रिकामी आहे). पुढे, असे अल्गोरिदम जाळीच्या बाजूने वरच्या दिशेने जातात. हे लक्षात घेण्यासारखे आहे की संपूर्ण जाळी पार केली जाऊ शकत नाही, म्हणजे, जर डाव्या बाजूचा इच्छित कमाल आकार इनपुटवर पास केला गेला तर अल्गोरिदम त्या आकाराच्या पातळीपेक्षा पुढे जाणार नाही.

खालील आकृती FZ शोधण्याच्या समस्येमध्ये बीजगणितीय जाळी कशी वापरली जाऊ शकते हे दर्शविते. येथे प्रत्येक धार (X, XY) अवलंबित्व दर्शवते X → Y. उदाहरणार्थ, आपण प्रथम स्तर उत्तीर्ण केला आहे आणि व्यसन राखले आहे हे माहित आहे A → B (आम्ही हे शिरोबिंदूंमधील हिरवे कनेक्शन म्हणून दाखवू A и B). याचा अर्थ असा की पुढे, जेव्हा आपण जाळीच्या बाजूने वर जातो तेव्हा आपण अवलंबित्व तपासू शकत नाही A, C → B, कारण ते यापुढे किमान राहणार नाही. त्याचप्रमाणे, अवलंबित्व धारण केले असल्यास आम्ही ते तपासणार नाही C → B.

याव्यतिरिक्त, एक नियम म्हणून, फेडरल कायदे शोधण्यासाठी सर्व आधुनिक अल्गोरिदम डेटा संरचना वापरतात जसे की विभाजन (मूळ स्त्रोतामध्ये - स्ट्रिप्ड विभाजन [1]). विभाजनाची औपचारिक व्याख्या खालीलप्रमाणे आहे:

व्याख्या १. X ⊆ R हा संबंध r साठी गुणधर्मांचा संच असू द्या. क्लस्टर हा r मधील ट्युपल्सच्या निर्देशांकांचा एक संच आहे ज्याचे मूल्य X साठी समान आहे, म्हणजेच c(t) = {i|ti[X] = t[X]}. विभाजन हे एकक लांबीचे क्लस्टर्स वगळता क्लस्टर्सचा संच आहे:

सोप्या शब्दात, विशेषतासाठी विभाजन X सूचीचा एक संच आहे, जेथे प्रत्येक सूचीमध्ये समान मूल्यांसह रेखा क्रमांक असतात X. आधुनिक साहित्यात, विभाजनांचे प्रतिनिधित्व करणाऱ्या संरचनेला स्थिती सूची निर्देशांक (PLI) म्हणतात. युनिट-लांबीच्या क्लस्टर्सना PLI कॉम्प्रेशनच्या उद्देशाने वगळण्यात आले आहे कारण ते असे क्लस्टर आहेत ज्यात फक्त एक अद्वितीय मूल्य असलेली रेकॉर्ड संख्या असते जी ओळखणे नेहमीच सोपे असते.

एक उदाहरण पाहू. चला रुग्णांसह त्याच टेबलवर परत येऊ आणि स्तंभांसाठी विभाजने तयार करू एक रुग्ण и पॉल (डावीकडे एक नवीन स्तंभ दिसला आहे, ज्यामध्ये सारणी पंक्ती क्रमांक चिन्हांकित आहेत):

शिवाय, परिभाषानुसार, स्तंभासाठी विभाजन एक रुग्ण विभाजनातून एकल क्लस्टर्स वगळण्यात आल्याने प्रत्यक्षात रिकामे असेल.

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

सोप्या शब्दात, उदाहरणार्थ, स्तंभांद्वारे विभाजन मिळवणे ABC, तुम्ही यासाठी विभाजने घेऊ शकता AC и B (किंवा डिसजॉइंट सबसेटचा इतर कोणताही संच) आणि त्यांना एकमेकांशी छेदतात. दोन विभाजनांच्या छेदनबिंदूचे ऑपरेशन दोन्ही विभाजनांसाठी सामान्य असलेल्या सर्वात मोठ्या लांबीचे क्लस्टर निवडते.

चला एक उदाहरण पाहू:

पहिल्या प्रकरणात, आम्हाला रिक्त विभाजन प्राप्त झाले. आपण सारणीकडे बारकाईने पाहिल्यास, दोन गुणधर्मांसाठी कोणतीही समान मूल्ये नाहीत. जर आपण टेबलमध्ये (उजवीकडील केस) किंचित बदल केले तर, आपल्याला आधीच एक नॉन-रिक्त छेदनबिंदू मिळेल. शिवाय, ओळी 1 आणि 2 मध्ये गुणधर्मांसाठी समान मूल्ये आहेत पॉल и डॉक्टर.

पुढे, आपल्याला विभाजन आकारासारख्या संकल्पनेची आवश्यकता असेल. औपचारिकपणे:

सोप्या भाषेत सांगायचे तर, विभाजन आकार म्हणजे विभाजनामध्ये समाविष्ट केलेल्या क्लस्टर्सची संख्या (लक्षात ठेवा की विभाजनामध्ये एकल क्लस्टर समाविष्ट नाहीत!):

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

लेमा १. अवलंबित्व A, B → C जर आणि फक्त असेल तर

लेमानुसार, अवलंबित्व आहे की नाही हे निर्धारित करण्यासाठी, चार पायऱ्या केल्या पाहिजेत:

1. अवलंबित्वाच्या डाव्या बाजूसाठी विभाजनाची गणना करा
2. अवलंबित्वाच्या उजव्या बाजूसाठी विभाजनाची गणना करा
3. पहिल्या आणि दुसऱ्या पायरीच्या उत्पादनाची गणना करा
4. पहिल्या आणि तिसर्‍या चरणांमध्ये मिळालेल्या विभाजनांच्या आकारांची तुलना करा

या लेमानुसार अवलंबित्व आहे की नाही हे तपासण्याचे एक उदाहरण खाली दिले आहे:

या लेखात, आम्ही फंक्शनल अवलंबित्व, अंदाजे कार्यात्मक अवलंबित्व यासारख्या संकल्पनांचे परीक्षण केले, ते कुठे वापरले जातात ते पाहिले, तसेच भौतिक कार्ये शोधण्यासाठी कोणते अल्गोरिदम अस्तित्वात आहेत. आम्ही फेडरल कायदे शोधण्यासाठी आधुनिक अल्गोरिदममध्ये सक्रियपणे वापरल्या जाणार्‍या मूलभूत परंतु महत्त्वाच्या संकल्पनांचे देखील तपशीलवार परीक्षण केले.

संदर्भ:

1. हुहताला वाय. वगैरे. TANE: कार्यात्मक आणि अंदाजे अवलंबित्व शोधण्यासाठी एक कार्यक्षम अल्गोरिदम // संगणक जर्नल. - 1999. - टी. 42. - नाही. 2. – पृ. 100-111.
2. क्रुस एस., नौमन एफ. अंदाजे अवलंबनांचा कार्यक्षम शोध // VLDB एंडोमेंटची कार्यवाही. – 2018. – टी. 11. – नाही. 7. – pp. 759-772.
3. पापनब्रॉक टी., नौमन एफ. फंक्शनल डिपेंडेंसी डिस्कवरीसाठी एक संकरित दृष्टीकोन // डेटा मॅनेजमेंट ऑन 2016 इंटरनॅशनल कॉन्फरन्सची कार्यवाही. – ACM, 2016. – pp. 821-833.
4. Papenbrock T. et al. कार्यात्मक अवलंबन शोध: सात अल्गोरिदमचे प्रायोगिक मूल्यमापन //व्हीएलडीबी एंडोमेंटची कार्यवाही. - 2015. - टी. 8. - नाही. १०. – पृ. १०८२-१०९३.
5. कुमार ए. आणि इतर. सामील होण्यासाठी किंवा न सामील होण्यासाठी?: वैशिष्ट्य निवडीपूर्वी सामील होण्याबद्दल दोनदा विचार करणे // डेटा व्यवस्थापनावरील 2016 आंतरराष्ट्रीय परिषदेची कार्यवाही. – ACM, 2016. – pp. 19-34.
6. Abo Khamis M. et al. स्पार्स टेन्सर्ससह इन-डेटाबेस लर्निंग //डेटाबेस सिस्टम्सच्या तत्त्वांवरील 37व्या ACM SIGMOD-SIGACT-SIGAI सिम्पोजियमची कार्यवाही. – ACM, 2018. – pp. 325-340.
7. Hellerstein JM et al. MADlib विश्लेषण लायब्ररी: किंवा MAD कौशल्य, SQL // VLDB एंडोमेंटची कार्यवाही. – २०१२. – टी. ५. – क्र. 2012. – pp. 5-12.
8. किन सी., रुसू एफ. टेरास्केल वितरित ग्रेडियंट डिसेंट ऑप्टिमायझेशनसाठी सट्टा अंदाजे // क्लाउडमधील डेटा विश्लेषणावरील चौथ्या कार्यशाळेची कार्यवाही. – ACM, 2015. – पृष्ठ 1.
9. मेंग X. et al. मिलीब: अपाचे स्पार्कमध्ये मशीन लर्निंग // मशीन लर्निंग रिसर्च जर्नल. - 2016. - टी. 17. - नाही. १. – पृ. १२३५-१२४१.

लेखाचे लेखक: अनास्तासिया बिरिलो, येथील संशोधक जेटब्रेन्स संशोधन, सीएस केंद्राचा विद्यार्थी и निकिता बोब्रोव्ह, येथील संशोधक जेटब्रेन्स संशोधन

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