कार्यात्मक निर्भरता का परिचय

इस लेख में हम डेटाबेस में कार्यात्मक निर्भरताओं के बारे में बात करेंगे - वे क्या हैं, उनका उपयोग कहाँ किया जाता है और उन्हें खोजने के लिए कौन से एल्गोरिदम मौजूद हैं।

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

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

परिभाषा 1. संबंध R संघीय कानून X → Y (जहाँ X, Y ⊆ R) को संतुष्ट करता है यदि और केवल यदि किसी टुपल्स के लिए , ∈ आर मानता है: यदि [एक्स] = [एक्स], फिर [य] = [य]. इस मामले में, हम कहते हैं कि X (निर्धारक, या विशेषताओं का परिभाषित सेट) कार्यात्मक रूप से Y (आश्रित सेट) को निर्धारित करता है।

दूसरे शब्दों में, एक संघीय कानून की उपस्थिति एक्स → वाई इसका मतलब है कि अगर हमारे पास दो टुपल्स हैं R और वे गुणों में मेल खाते हैं X, तो वे गुणों में मेल खाएंगे Y.
और अब, क्रम में. आइए विशेषताओं पर नजर डालें रोगी и लिंग जिसके लिए हम यह पता लगाना चाहते हैं कि उनके बीच निर्भरताएं हैं या नहीं। विशेषताओं के ऐसे सेट के लिए, निम्नलिखित निर्भरताएँ मौजूद हो सकती हैं:

1. रोगी → लिंग
2. लिंग → रोगी

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

इस प्रकार, कार्यात्मक निर्भरताएँ तालिका विशेषताओं के सेट के बीच मौजूदा संबंधों को निर्धारित करना संभव बनाती हैं। यहां से हम सबसे दिलचस्प कनेक्शनों, या यूं कहें कि ऐसे कनेक्शनों पर विचार करेंगे एक्स → वाईवे क्या हैं:

• गैर-तुच्छ, अर्थात्, निर्भरता का दाहिना भाग बाईं ओर का उपसमूह नहीं है (वाई ̸⊆ एक्स);
• न्यूनतम, अर्थात् ऐसी कोई निर्भरता नहीं है जेड → वाईकि जेड ⊂ एक्स.

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

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

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

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

आज, निर्भरता का एक मुख्य अनुप्रयोग डेटा सफ़ाई है। इसमें "गंदे डेटा" की पहचान करने और फिर उसे ठीक करने के लिए प्रक्रियाएं विकसित करना शामिल है। "गंदे डेटा" के प्रमुख उदाहरण डुप्लिकेट, डेटा त्रुटियां या टाइपो, लापता मान, पुराना डेटा, अतिरिक्त स्थान और इसी तरह हैं।

डेटा त्रुटि का उदाहरण:

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

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

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

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

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

डेटा सेट में संघीय कानूनों की खोज के लिए कई एल्गोरिदम (आधुनिक और इतने आधुनिक दोनों नहीं) हैं। ऐसे एल्गोरिदम को तीन समूहों में विभाजित किया जा सकता है:

• बीजगणितीय जालकों के ट्रैवर्सल का उपयोग करने वाले एल्गोरिदम (जाली ट्रैवर्सल एल्गोरिदम)
• सहमत मूल्यों की खोज पर आधारित एल्गोरिदम (अंतर- और सहमत-सेट एल्गोरिदम)
• जोड़ीवार तुलनाओं पर आधारित एल्गोरिदम (निर्भरता प्रेरण एल्गोरिदम)

प्रत्येक प्रकार के एल्गोरिदम का संक्षिप्त विवरण नीचे दी गई तालिका में प्रस्तुत किया गया है:


आप इस वर्गीकरण के बारे में अधिक पढ़ सकते हैं [4]। प्रत्येक प्रकार के लिए एल्गोरिदम के उदाहरण नीचे दिए गए हैं:

वर्तमान में, नए एल्गोरिदम सामने आ रहे हैं जो कार्यात्मक निर्भरता खोजने के लिए कई दृष्टिकोणों को जोड़ते हैं। ऐसे एल्गोरिदम के उदाहरण पायरो [2] और हाईएफडी [3] हैं। इस शृंखला के निम्नलिखित लेखों में उनके कार्य का विश्लेषण अपेक्षित है। इस लेख में हम केवल उन बुनियादी अवधारणाओं और लेम्मा की जांच करेंगे जो निर्भरता का पता लगाने की तकनीकों को समझने के लिए आवश्यक हैं।

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

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

जाली की अवधारणा को पेश करने के लिए, आंशिक रूप से ऑर्डर किए गए सेट (या आंशिक रूप से ऑर्डर किए गए सेट, जिसे पॉसेट के रूप में संक्षिप्त किया गया है) को परिभाषित करना आवश्यक है।

परिभाषा 2. एक सेट एस को बाइनरी रिलेशन ⩽ द्वारा आंशिक रूप से ऑर्डर किया गया कहा जाता है यदि सभी ए, बी, सी ∈ एस के लिए निम्नलिखित गुण संतुष्ट हैं:

1. रिफ्लेक्सिविटी, यानी ए ⩽ ए
2. एंटीसिममेट्री, यानी, यदि ए ⩽ बी और बी ⩽ ए, तो ए = बी
3. परिवर्तनशीलता, अर्थात, a ⩽ b और b ⩽ c के लिए यह इस प्रकार है कि a ⩽ c

ऐसे संबंध को (ढीला) आंशिक क्रम संबंध कहा जाता है, और सेट को आंशिक रूप से ऑर्डर किया गया सेट कहा जाता है। औपचारिक संकेतन: ⟨S, ⩽⟩.

आंशिक रूप से ऑर्डर किए गए सेट के सबसे सरल उदाहरण के रूप में, हम सामान्य ऑर्डर संबंध ⩽ के साथ सभी प्राकृतिक संख्याओं एन का सेट ले सकते हैं। यह सत्यापित करना आसान है कि सभी आवश्यक सिद्धांत संतुष्ट हैं।

एक अधिक सार्थक उदाहरण. समावेशन संबंध ⊆ द्वारा क्रमित सभी उपसमुच्चय {1, 2, 3} के सेट पर विचार करें। दरअसल, यह संबंध सभी आंशिक आदेश शर्तों को संतुष्ट करता है, इसलिए ⟨P ({1, 2, 3}), ⊆⟩ एक आंशिक रूप से आदेशित सेट है। नीचे दिया गया चित्र इस सेट की संरचना को दर्शाता है: यदि एक तत्व को तीरों द्वारा दूसरे तत्व तक पहुँचा जा सकता है, तो वे एक क्रम संबंध में हैं।

हमें गणित के क्षेत्र से दो और सरल परिभाषाओं की आवश्यकता होगी - सर्वोच्च और अनंत।

परिभाषा 3. मान लीजिए ⟨S, ⩽⟩ एक आंशिक रूप से क्रमबद्ध सेट है, A ⊆ S. A की ऊपरी सीमा एक तत्व u ∈ S है जैसे कि ∀x ∈ S: x ⩽ u। मान लीजिए U, S की सभी ऊपरी सीमाओं का समुच्चय है। यदि U में सबसे छोटा तत्व है, तो इसे सर्वोच्च कहा जाता है और इसे शीर्ष A से दर्शाया जाता है।

सटीक निचली सीमा की अवधारणा इसी तरह पेश की गई है।

परिभाषा 4. मान लीजिए ⟨S, ⩽⟩ एक आंशिक रूप से क्रमबद्ध सेट है, A ⊆ S. A का न्यूनतम एक तत्व l ∈ S है जैसे कि ∀x ∈ S: l ⩽ x। मान लीजिए L, S की सभी निचली सीमाओं का समुच्चय है। यदि L में कोई सबसे बड़ा तत्व है, तो इसे infimum कहा जाता है और इसे inf A के रूप में दर्शाया जाता है।

एक उदाहरण के रूप में उपरोक्त आंशिक रूप से क्रमित सेट ⟨P ({1, 2, 3}), ⊆⟩ पर विचार करें और इसमें सर्वोच्च और न्यूनतम खोजें:

अब हम बीजगणितीय जालक की परिभाषा तैयार कर सकते हैं।

परिभाषा 5. मान लीजिए कि ⟨P,⩽⟩ एक आंशिक रूप से ऑर्डर किया गया सेट है, जैसे कि प्रत्येक दो-तत्व उपसमुच्चय में एक ऊपरी और निचली सीमा होती है। तब P को बीजगणितीय जालक कहा जाता है। इस मामले में, su{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 खोजने की समस्या में बीजगणितीय जाली का उपयोग कैसे किया जा सकता है। यहाँ प्रत्येक किनारा (एक्स, एक्सवाई) एक निर्भरता का प्रतिनिधित्व करता है एक्स → वाई. उदाहरण के लिए, हमने पहला स्तर पार कर लिया है और जानते हैं कि लत कायम है ए → बी (हम इसे शीर्षों के बीच हरे कनेक्शन के रूप में प्रदर्शित करेंगे A и B). इसका मतलब यह है कि आगे, जब हम जाली के साथ ऊपर बढ़ते हैं, तो हम निर्भरता की जांच नहीं कर सकते हैं ए, सी → बी, क्योंकि यह अब न्यूनतम नहीं होगा। इसी तरह, यदि निर्भरता बनी हुई थी तो हम इसकी जाँच नहीं करेंगे सी → बी.

इसके अलावा, एक नियम के रूप में, संघीय कानूनों की खोज के लिए सभी आधुनिक एल्गोरिदम एक विभाजन जैसी डेटा संरचना का उपयोग करते हैं (मूल स्रोत में - स्ट्रिप्ड विभाजन [1])। विभाजन की औपचारिक परिभाषा इस प्रकार है:

परिभाषा 6. मान लीजिए कि X ⊆ R संबंध r के लिए विशेषताओं का एक समूह है। क्लस्टर r में टुपल्स के सूचकांकों का एक सेट है जिसका X के लिए समान मान है, अर्थात, c(t) = {i|ti[X] = t[X]}। एक विभाजन इकाई लंबाई के समूहों को छोड़कर, समूहों का एक सेट है:

सरल शब्दों में, किसी विशेषता के लिए एक विभाजन X सूचियों का एक समूह है, जहाँ प्रत्येक सूची में समान मानों वाली पंक्ति संख्याएँ होती हैं X. आधुनिक साहित्य में, विभाजन का प्रतिनिधित्व करने वाली संरचना को स्थिति सूची सूचकांक (पीएलआई) कहा जाता है। यूनिट-लंबाई क्लस्टर को पीएलआई संपीड़न उद्देश्यों के लिए बाहर रखा गया है क्योंकि वे ऐसे क्लस्टर हैं जिनमें एक अद्वितीय मान के साथ केवल एक रिकॉर्ड संख्या होती है जिसे पहचानना हमेशा आसान होगा।

आइए एक उदाहरण देखें. आइए मरीजों के साथ उसी टेबल पर लौटें और कॉलम के लिए विभाजन बनाएं रोगी и लिंग (बाईं ओर एक नया कॉलम दिखाई दिया है, जिसमें तालिका पंक्ति संख्याएँ अंकित हैं):

इसके अलावा, परिभाषा के अनुसार, कॉलम के लिए विभाजन रोगी वास्तव में खाली होगा, क्योंकि एकल समूहों को विभाजन से बाहर रखा गया है।

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

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

आइए एक उदाहरण देखें:

पहले मामले में, हमें एक खाली विभाजन प्राप्त हुआ। यदि आप तालिका को ध्यान से देखें, तो वास्तव में, दोनों विशेषताओं के लिए कोई समान मान नहीं हैं। यदि हम तालिका (दाईं ओर का मामला) को थोड़ा संशोधित करते हैं, तो हमें पहले से ही एक गैर-रिक्त चौराहा मिलेगा। इसके अलावा, पंक्ति 1 और 2 में वास्तव में विशेषताओं के लिए समान मान हैं लिंग и चिकित्सक.

इसके बाद, हमें विभाजन आकार जैसी अवधारणा की आवश्यकता होगी। औपचारिक रूप से:

सीधे शब्दों में कहें तो, विभाजन का आकार विभाजन में शामिल समूहों की संख्या है (याद रखें कि विभाजन में एकल क्लस्टर शामिल नहीं हैं!):

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

लेम्मा 1. निर्भरता A, B → C यदि और केवल यदि रखती है

लेम्मा के अनुसार, यह निर्धारित करने के लिए कि कोई निर्भरता कायम है या नहीं, चार चरणों का पालन किया जाना चाहिए:

1. निर्भरता के बाईं ओर के विभाजन की गणना करें
2. निर्भरता के दाएँ पक्ष के लिए विभाजन की गणना करें
3. पहले और दूसरे चरण के उत्पाद की गणना करें
4. पहले और तीसरे चरण में प्राप्त विभाजनों के आकार की तुलना करें

नीचे यह जांचने का एक उदाहरण दिया गया है कि निर्भरता इस लेम्मा के अनुसार है या नहीं:

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

सन्दर्भ:

1. हुहताला वाई. एट अल. TANE: कार्यात्मक और अनुमानित निर्भरता की खोज के लिए एक कुशल एल्गोरिदम // कंप्यूटर जर्नल। - 1999. - टी. 42. - नहीं. 2. - पृ. 100-111.
2. क्रूस एस., नौमान एफ. अनुमानित निर्भरता की कुशल खोज // वीएलडीबी बंदोबस्ती की कार्यवाही। – 2018. – टी. 11. – नहीं. 7. - पृ. 759-772.
3. पैपेनब्रॉक टी., नौमन एफ. कार्यात्मक निर्भरता खोज के लिए एक संकर दृष्टिकोण // डेटा प्रबंधन पर 2016 अंतर्राष्ट्रीय सम्मेलन की कार्यवाही। - एसीएम, 2016। - पीपी. 821-833।
4. पैपेनब्रॉक टी. एट अल. कार्यात्मक निर्भरता खोज: सात एल्गोरिदम का एक प्रयोगात्मक मूल्यांकन // वीएलडीबी बंदोबस्ती की कार्यवाही। – 2015. – टी. 8. – नहीं. 10. - पृ. 1082-1093.
5. कुमार ए एट अल. शामिल हों या न हों?: फीचर चयन से पहले जॉइन के बारे में दो बार सोचें //डेटा प्रबंधन पर 2016 अंतर्राष्ट्रीय सम्मेलन की कार्यवाही। - एसीएम, 2016. - पीपी. 19-34.
6. अबो खामिस एम. एट अल. विरल टेंसरों के साथ इन-डेटाबेस सीखना //डेटाबेस सिस्टम के सिद्धांतों पर 37वें ACM SIGMOD-SIGACT-SIGAI संगोष्ठी की कार्यवाही। - एसीएम, 2018. - पीपी. 325-340।
7. हेलरस्टीन जेएम एट अल। MADlib एनालिटिक्स लाइब्रेरी: या MAD कौशल, SQL // VLDB बंदोबस्ती की कार्यवाही। – 2012. – टी. 5. – नहीं. 12. - पृ. 1700-1711.
8. किन सी., रुसु एफ. टेरास्केल वितरित ग्रेडिएंट डीसेंट ऑप्टिमाइज़ेशन के लिए सट्टा अनुमान // क्लाउड में डेटा एनालिटिक्स पर चौथी कार्यशाला की कार्यवाही। - एसीएम, 2015. - पी. 1.
9. मेंग एक्स एट अल. एमएललिब: अपाचे स्पार्क में मशीन लर्निंग // द जर्नल ऑफ मशीन लर्निंग रिसर्च। – 2016. – टी. 17. – नहीं. 1. - पृ. 1235-1241.

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

स्रोत: www.habr.com