कार्यात्मक निर्भरता
This article needs additional citations for verification. (October 2012) (Learn how and when to remove this template message) |
संबंधपरक डेटाबेस सिद्धांत में, एक कार्यात्मक निर्भरता एक डेटाबेस से संबंध (डेटाबेस) में विशेषताओं के दो सेटों के बीच एक संबंधपरक डेटाबेस#बाधाएं है। दूसरे शब्दों में, एक संबंध में दो विशेषताओं के बीच एक कार्यात्मक निर्भरता एक बाधा है। एक संबंध 'आर' और विशेषताओं के सेट को देखते हुए , X को 'कार्यात्मक रूप से निर्धारित' Y (लिखित X → Y) कहा जाता है यदि और केवल यदि R में प्रत्येक X मान R में ठीक एक Y मान से जुड़ा हो; R को कार्यात्मक निर्भरता X → Y को संतुष्ट करने के लिए कहा जाता है। समान रूप से, प्रक्षेपण (संबंधपरक बीजगणित) एक फलन (गणित) है, अर्थात Y, X का एक फलन है।[1][2] सरल शब्दों में, यदि X विशेषताओं के मान ज्ञात हैं (कहते हैं कि वे x हैं), तो x से संबंधित Y विशेषताओं के मान उन्हें किसी भी Tuple#Relational model R of x युक्त में देखकर निर्धारित किया जा सकता है। प्रथागत रूप से X को निर्धारक समुच्चय और Y को आश्रित समुच्चय कहा जाता है। एक कार्यात्मक निर्भरता एफडी: एक्स → वाई को तुच्छ कहा जाता है यदि वाई एक्स का सबसेट है।
दूसरे शब्दों में, एक निर्भरता FD: X → Y का अर्थ है कि Y के मान X के मानों द्वारा निर्धारित किए जाते हैं। X के समान मान साझा करने वाले दो टुपल्स में अनिवार्य रूप से Y के समान मान होंगे।
कार्यात्मक निर्भरताओं का निर्धारण संबंधपरक मॉडल में डेटाबेस डिजाइन करने और डेटाबेस सामान्यीकरण और असामान्यकरण में एक महत्वपूर्ण हिस्सा है। हीथ की प्रमेय कार्यात्मक निर्भरता का एक सरल अनुप्रयोग है; यह कहता है कि एक विशेषता सेट यू पर एक संबंध आर और एक कार्यात्मक निर्भरता को संतुष्ट करना एक्स → वाई को दो संबंधों में सुरक्षित रूप से विभाजित किया जा सकता है जिसमें दोषरहित-जुड़ना अपघटन है। दोषरहित-अपघटन संपत्ति में शामिल हों, अर्थात् जहाँ Z = U - XY बाकी गुण हैं। (एट्रिब्यूट सेट के संघ स्थापित करें ों को डेटाबेस थ्योरी में केवल जक्सटैपोज़िशन द्वारा सामान्य रूप से दर्शाया जाता है।) इस संदर्भ में एक महत्वपूर्ण धारणा एक उम्मीदवार कुंजी है, जिसे विशेषताओं के न्यूनतम सेट के रूप में परिभाषित किया गया है जो एक संबंध में सभी विशेषताओं को कार्यात्मक रूप से निर्धारित करता है। विशेषता डोमेन के साथ-साथ कार्यात्मक निर्भरताओं का चयन किया जाता है ताकि ऐसी बाधा उत्पन्न की जा सके जो सिस्टम से उपयोगकर्ता डोमेन के लिए जितना संभव हो उतना डेटा अनुपयुक्त हो।
कार्यात्मक निर्भरताओं के लिए तार्किक निहितार्थ की धारणा को निम्न तरीके से परिभाषित किया गया है: कार्यात्मक निर्भरताओं का एक सेट तार्किक रूप से निर्भरताओं का एक और सेट दर्शाता है , यदि कोई संबंध आर से सभी निर्भरताओं को संतुष्ट करता है से सभी निर्भरताओं को भी संतुष्ट करता है ; यह आमतौर पर लिखा जाता है . कार्यात्मक निर्भरता के लिए तार्किक निहितार्थ की धारणा एक सुदृढ़ता और पूर्णता (तर्क) परिमित स्वयंसिद्धता को स्वीकार करती है, जिसे आर्मस्ट्रांग के स्वयंसिद्ध के रूप में जाना जाता है।
उदाहरण
कार
मान लीजिए कि कोई वाहनों और उनके इंजनों की क्षमता को ट्रैक करने के लिए एक प्रणाली डिजाइन कर रहा है। प्रत्येक वाहन में एक विशिष्ट वाहन पहचान संख्या (VIN) होती है। कोई VIN → EngineCapacity लिखेगा क्योंकि किसी वाहन के इंजन में एक से अधिक क्षमता होना अनुचित होगा। (इस मामले में, यह मानते हुए कि वाहनों में केवल एक इंजन है।) दूसरी ओर, इंजन क्षमता → VIN गलत है क्योंकि समान इंजन क्षमता वाले कई वाहन हो सकते हैं।
यह कार्यात्मक निर्भरता सुझाव दे सकती है कि विशेषता इंजन क्षमता को उम्मीदवार कुंजी VIN के संबंध में रखा जाए। हालाँकि, यह हमेशा उचित नहीं हो सकता है। उदाहरण के लिए, यदि वह कार्यात्मक निर्भरता सकर्मक संबंध कार्यात्मक निर्भरता VIN → VehicleModel और VehicleModel → EngineCapacity के परिणामस्वरूप होती है तो इसका परिणाम सामान्यीकृत संबंध नहीं होगा।
व्याख्यान
यह उदाहरण कार्यात्मक निर्भरता की अवधारणा को दर्शाता है। प्रतिरूपित स्थिति यह है कि कॉलेज के छात्र एक या एक से अधिक व्याख्यानों में जाते हैं, जिनमें से प्रत्येक में उन्हें एक शिक्षण सहायक (टीए) सौंपा जाता है। आइए आगे मान लें कि प्रत्येक छात्र किसी सेमेस्टर में है और एक अद्वितीय पूर्णांक आईडी द्वारा पहचाना जाता है।
Student ID | Semester | Lecture | TA |
---|---|---|---|
1234 | 6 | Numerical Methods | John |
1221 | 4 | Numerical Methods | Smith |
1234 | 6 | Visual Computing | Bob |
1201 | 2 | Numerical Methods | Peter |
1201 | 2 | Physics II | Simon |
हम देखते हैं कि जब भी इस तालिका में दो पंक्तियों में एक ही छात्र आईडी होती है, उनके पास आवश्यक रूप से समान सेमेस्टर मूल्य भी हैं। यह मूल तथ्य एक कार्यात्मक निर्भरता द्वारा व्यक्त किया जा सकता है:
- स्टूडेंटआईडी → सेमेस्टर।
ध्यान दें कि यदि एक पंक्ति को जोड़ा गया था जहां छात्र के सेमेस्टर का एक अलग मूल्य था, तो कार्यात्मक निर्भरता एफडी अब मौजूद नहीं होगी। इसका मतलब यह है कि एफडी डेटा द्वारा निहित है क्योंकि यह संभव है कि ऐसे मूल्य हों जो एफडी को अमान्य कर दें।
अन्य गैर-तुच्छ कार्यात्मक निर्भरताओं की पहचान की जा सकती है, उदाहरण के लिए:
- {छात्र आईडी, व्याख्यान} → टीए
- {छात्र आईडी, व्याख्यान} → {टीए, सेमेस्टर}
उत्तरार्द्ध इस तथ्य को व्यक्त करता है कि सेट {StudentID, Lecture} संबंध की एक key है।
कर्मचारी विभाग मॉडल
कार्यात्मक निर्भरता का एक उत्कृष्ट उदाहरण कर्मचारी विभाग मॉडल है।
Employee ID | Employee name | Department ID | Department name |
---|---|---|---|
0001 | John Doe | 1 | Human Resources |
0002 | Jane Doe | 2 | Marketing |
0003 | John Smith | 1 | Human Resources |
0004 | Jane Goodall | 3 | Sales |
यह मामला एक उदाहरण का प्रतिनिधित्व करता है जहां डेटा के एकल प्रतिनिधित्व में कई कार्यात्मक निर्भरताएँ सन्निहित हैं। ध्यान दें कि क्योंकि एक कर्मचारी केवल एक विभाग का सदस्य हो सकता है, उस कर्मचारी की विशिष्ट आईडी विभाग को निर्धारित करती है।
- कर्मचारी आईडी → कर्मचारी का नाम
- कर्मचारी आईडी → विभाग आईडी
इस संबंध के अतिरिक्त, तालिका में एक गैर-कुंजी विशेषता के माध्यम से कार्यात्मक निर्भरता भी होती है
- विभाग आईडी → विभाग का नाम
यह उदाहरण दर्शाता है कि भले ही एफडी कर्मचारी आईडी → विभाग आईडी मौजूद हो - कर्मचारी आईडी विभाग के नाम के निर्धारण के लिए तार्किक कुंजी नहीं होगी। डेटा के सामान्यीकरण की प्रक्रिया सभी एफडी को पहचान लेगी और डिज़ाइनर को डेटा के आधार पर अधिक तार्किक तालिकाओं और संबंधों का निर्माण करने की अनुमति देगी।
कार्यात्मक निर्भरता के गुण और स्वयंसिद्धीकरण
यह देखते हुए कि X, Y, और Z एक संबंध R में विशेषताओं के समूह हैं, कोई कार्यात्मक निर्भरता के कई गुणों को प्राप्त कर सकता है। सबसे महत्वपूर्ण निम्नलिखित हैं, जिन्हें आम तौर पर आर्मस्ट्रांग के स्वयंसिद्ध कहा जाता है:[3]
- रिफ्लेक्सिविटी: यदि Y X का उपसमुच्चय है, तो X → Y
- वृद्धि: यदि X → Y, तो XZ → YZ
- संक्रामकता: यदि X → Y और Y → Z, तो X → Z
रिफ्लेक्सिविटी को सिर्फ कमजोर किया जा सकता है , यानी यह एक वास्तविक स्वयंसिद्ध है, जहां अन्य दो उचित अनुमान नियम हैं, अधिक सटीक रूप से वाक्यात्मक परिणाम के निम्नलिखित नियमों को जन्म देते हैं:[4]
.
ये तीन नियम कार्यात्मक निर्भरताओं का एक सुदृढ़ता और पूर्णता (तर्क) स्वयंसिद्धीकरण हैं। इस स्वसिद्धीकरण को कभी-कभी परिमित के रूप में वर्णित किया जाता है क्योंकि अनुमान नियमों की संख्या परिमित होती है,[5] चेतावनी के साथ कि सिद्धांत और अनुमान के नियम सभी स्कीमा (तर्क) हैं, जिसका अर्थ है कि एक्स, वाई और जेड सभी जमीन शर्तों (विशेषता सेट) पर हैं।[4]
संवर्द्धन और ट्रांज़िटिविटी लागू करके, कोई दो अतिरिक्त नियम प्राप्त कर सकता है:
कोई भी आर्मस्ट्रांग के स्वयंसिद्ध # अतिरिक्त नियम (द्वितीयक नियम) नियम आर्मस्ट्रांग के स्वयंसिद्धों से प्राप्त कर सकता है:[3][7]
- एक्स → वाई और एक्स → जेड अगर और केवल अगर एक्स → वाईजेड
कार्यात्मक निर्भरता का समापन
क्लोजर अनिवार्य रूप से मूल्यों का पूरा सेट है जो किसी दिए गए रिश्ते के लिए ज्ञात मूल्यों के सेट से इसकी कार्यात्मक निर्भरताओं का उपयोग करके निर्धारित किया जा सकता है। एक सबूत प्रदान करने के लिए आर्मस्ट्रांग के सिद्धांतों का उपयोग करता है - यानी रिफ्लेक्सीविटी, वृद्धि, ट्रांजिटिविटी।
दिया गया और FD का एक सेट जो होल्ड करता है : का बंद होना में (निरूपित +) सभी एफडी का सेट है जो तार्किक रूप से निहित हैं .[8]
गुणों का एक सेट बंद करना
एक्स के संबंध में विशेषताओं के एक सेट को बंद करना समुच्चय X है+ सभी का विशेषताएँ जो एक्स द्वारा कार्यात्मक रूप से निर्धारित की जाती हैं +.
उदाहरण
FD की निम्नलिखित सूची की कल्पना करें। हम इस संबंध से A के समापन की गणना करने जा रहे हैं।
1. ए → बी
2. बी → सी
3. एबी → डी
समापन इस प्रकार होगा:
ए) ए → ए (आर्मस्ट्रांग की रिफ्लेक्सीविटी द्वारा)
b) A → AB (1. और (a) द्वारा)
सी) ए → एबीडी (द्वारा (बी), 3, और आर्मस्ट्रांग की पारगमनशीलता)
डी) ए → एबीसीडी (द्वारा (सी), और 2)
इसलिए समापन A → ABCD है। ए के बंद होने की गणना करके, हमने पुष्टि की है कि ए भी एक अच्छी उम्मीदवार कुंजी है क्योंकि इसका बंद होना रिश्ते में हर एक डेटा मान है।
कवर और समानता
कवर
परिभाषा: कवर अगर हर एफ.डी से अनुमान लगाया जा सकता है . कवर अगर + ⊆ +
कार्यात्मक निर्भरता के प्रत्येक सेट में एक विहित आवरण होता है।
एफडी के दो सेटों की समानता
एफडी के दो सेट और स्कीमा के ऊपर समतुल्य हैं, लिखित हैं ≡ , अगर + = +. अगर ≡ , तब के लिए एक आवरण है और इसके विपरीत। दूसरे शब्दों में, कार्यात्मक निर्भरताओं के समकक्ष सेट को एक दूसरे के कवर कहा जाता है।
गैर-निरर्थक कवर
एक सेट यदि कोई उचित उपसमुच्चय नहीं है तो एफडी की संख्या अनावश्यक है
का साथ ≡ . यदि ऐसा मौजूद, बेमानी है। के लिए एक गैर-अनावश्यक आवरण है अगर के लिए एक आवरण है और बेमानी है।
गैर-अतिरेक का एक वैकल्पिक लक्षण वर्णन है अगर कोई एफडी एक्स → वाई इन नहीं है तो गैर-अनावश्यक है ऐसा है कि -{एक्स→वाई} X → Y. FD X → Y को कॉल करें में अनावश्यक अगर -{एक्स→वाई} एक्स → वाई।
सामान्यीकरण के लिए आवेदन
हीथ की प्रमेय
कार्यात्मक निर्भरताओं की एक महत्वपूर्ण संपत्ति (तत्काल आवेदन उत्पन्न करना) यह है कि यदि आर गुणों के कुछ सेट से नामित कॉलम के साथ संबंध है और आर कुछ कार्यात्मक निर्भरता एक्स → वाई को संतुष्ट करता है तो जहां जेड = यू - एक्सवाई। सहज रूप से, यदि एक कार्यात्मक निर्भरता एक्स → वाई आर में रखती है, तो संबंध को कॉलम एक्स के साथ दो संबंधों में सुरक्षित रूप से विभाजित किया जा सकता है (जो कि एक कुंजी है ) यह सुनिश्चित करना कि जब दो भागों को वापस जोड़ा जाता है तो कोई डेटा खोया नहीं जाता है, यानी एक कार्यात्मक निर्भरता दो छोटे संबंधों में आर के दोषरहित जोड़ अपघटन के निर्माण का एक सरल तरीका प्रदान करती है। इस तथ्य को कभी-कभी हीथ्स प्रमेय कहा जाता है; यह डेटाबेस थ्योरी के शुरुआती परिणामों में से एक है।[9] हीथ की प्रमेय प्रभावी रूप से कहती है कि हम Y के मूल्यों को बड़े संबंध R से निकाल सकते हैं और उन्हें एक में संग्रहीत कर सकते हैं, , जिसमें X के लिए पंक्ति में कोई मूल्य दोहराव नहीं है और प्रभावी रूप से X द्वारा कुंजीबद्ध Y के लिए एक लुकअप तालिका है और इसके परिणामस्वरूप बड़े संबंध R के विपरीत प्रत्येक X के अनुरूप Y को अपडेट करने के लिए केवल एक स्थान है जहां प्रत्येक X की संभावित रूप से कई प्रतियां हैं , हर एक वाई की अपनी प्रति के साथ जिसे अद्यतनों पर समकालित रखने की आवश्यकता है। (ओएलटीपी संदर्भों में अतिरेक का यह उन्मूलन एक फायदा है, जहां कई बदलावों की उम्मीद है, लेकिन ओएलएपी संदर्भों में इतना अधिक नहीं है, जिसमें ज्यादातर प्रश्न शामिल हैं।) हीथ का अपघटन बड़ी तालिका के शेष भाग में केवल एक्स को विदेशी कुंजी के रूप में कार्य करने के लिए छोड़ देता है। .
हालांकि कार्यात्मक निर्भरता को समावेशन निर्भरता के साथ भ्रमित नहीं होना चाहिए, जो कि विदेशी कुंजी के लिए औपचारिकता है; भले ही उनका उपयोग सामान्यीकरण के लिए किया जाता है, कार्यात्मक निर्भरता एक संबंध (स्कीमा) पर बाधाओं को व्यक्त करती है, जबकि समावेशन निर्भरता डेटाबेस स्कीमा में संबंध स्कीमा के बीच बाधाओं को व्यक्त करती है। इसके अलावा, दो धारणाएँ निर्भरता के वर्गीकरण में भी प्रतिच्छेद नहीं करती हैं: कार्यात्मक निर्भरताएँ समानता-सृजन निर्भरता हैं | समानता-सृजन निर्भरताएँ जबकि समावेशन निर्भरताएँ टपल-सृजन निर्भरताएँ हैं। संबंध स्कीमा अपघटन (सामान्यीकरण) के बाद संदर्भित बाधाओं को लागू करने के लिए एक नई औपचारिकता की आवश्यकता होती है, अर्थात समावेशन निर्भरता। हीथ के प्रमेय से उत्पन्न अपघटन में, टपल्स के सम्मिलन को रोकने के लिए कुछ भी नहीं है X का कुछ मान इसमें नहीं मिला .
सामान्य रूप
सामान्य रूप डेटाबेस सामान्यीकरण स्तर होते हैं जो तालिका की अच्छाई निर्धारित करते हैं। आम तौर पर, तीसरे सामान्य रूप को संबंधपरक डेटाबेस के लिए एक अच्छा मानक माना जाता है।[citation needed]
सामान्यीकरण का उद्देश्य डेटाबेस को अद्यतन, सम्मिलन और विलोपन विसंगतियों से मुक्त करना है। यह यह भी सुनिश्चित करता है कि जब संबंध में एक नया मूल्य पेश किया जाता है, तो इसका डेटाबेस पर न्यूनतम प्रभाव पड़ता है, और इस प्रकार डेटाबेस का उपयोग करने वाले अनुप्रयोगों पर न्यूनतम प्रभाव पड़ता है।[citation needed]
इर्रेड्यूसिबल फ़ंक्शन सेट के आधार पर
यदि सेट में निम्नलिखित तीन गुण हैं, तो कार्यात्मक निर्भरता का एक सेट S अप्रासंगिक है:
- S की कार्यात्मक निर्भरता के प्रत्येक सही सेट में केवल एक विशेषता होती है।
- S की एक कार्यात्मक निर्भरता का प्रत्येक बायां सेट अप्रासंगिक है। इसका अर्थ है कि बाएं सेट से किसी एक विशेषता को कम करने से S की सामग्री बदल जाएगी (S कुछ जानकारी खो देगी)।
- किसी कार्यात्मक निर्भरता को कम करने से एस की सामग्री बदल जाएगी।
इन गुणों के साथ कार्यात्मक निर्भरताओं के सेट को विहित या न्यूनतम भी कहा जाता है। कार्यात्मक निर्भरताओं के ऐसे सेट एस को ढूँढना जो इनपुट के रूप में प्रदान किए गए कुछ इनपुट सेट एस 'के बराबर है, एस' का न्यूनतम कवर ढूंढना कहा जाता है: इस समस्या को बहुपद समय में हल किया जा सकता है।[10]
यह भी देखें
- चेस (एल्गोरिदम)
- समावेशन निर्भरता
- निर्भरता में शामिल हों
- बहुस्तरीय निर्भरता (एमवीडी)
- डेटाबेस सामान्यीकरण
- पहला सामान्य रूप
संदर्भ
- ↑ Terry Halpin (2008). सूचना मॉडलिंग और संबंधपरक डेटाबेस (2nd ed.). Morgan Kaufmann. p. 140. ISBN 978-0-12-373568-3.
- ↑ Chris Date (2012). Database Design and Relational Theory: Normal Forms and All That Jazz. O'Reilly Media, Inc. p. 21. ISBN 978-1-4493-2801-6.
- ↑ 3.0 3.1 3.2 Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). डाटाबेस सिस्टम अवधारणाओं (6th ed.). McGraw-Hill. p. 339. ISBN 978-0-07-352332-3.
- ↑ 4.0 4.1 M. Y. Vardi. Fundamentals of dependency theory. In E. Borger, editor, Trends in Theoretical Computer Science, pages 171–224. Computer Science Press, Rockville, MD, 1987. ISBN 0881750840
- ↑ Abiteboul, Serge; Hull, Richard B.; Vianu, Victor (1995), Foundations of Databases, Addison-Wesley, pp. 164–168, ISBN 0-201-53771-0
- ↑ S. K. Singh (2009) [2006]. Database Systems: Concepts, Design & Applications. Pearson Education India. p. 323. ISBN 978-81-7758-567-4.
- ↑ Hector Garcia-Molina; Jeffrey D. Ullman; Jennifer Widom (2009). Database systems: the complete book (2nd ed.). Pearson Prentice Hall. p. 73. ISBN 978-0-13-187325-4. This is sometimes called the splitting/combining rule.
- ↑ Saiedian, H. (1996-02-01). "एक संबंधपरक डेटाबेस स्कीमा की उम्मीदवार कुंजी की गणना करने के लिए एक कुशल एल्गोरिथम". The Computer Journal. 39 (2): 124–132. doi:10.1093/comjnl/39.2.124. ISSN 0010-4620.
- ↑ Heath, I. J. (1971). "Unacceptable file operations in a relational data base". Proceedings of the 1971 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '71. pp. 19–33. doi:10.1145/1734714.1734717. S2CID 22069259. cited in:
- Ronald Fagin and Moshe Y. Vardi (1986). "The Theory of Data Dependencies - A Survey". In Michael Anshel and William Gewirtz (ed.). Mathematics of Information Processing: [short Course Held in Louisville, Kentucky, January 23-24, 1984]. American Mathematical Soc. p. 23. ISBN 978-0-8218-0086-7.
- C. Date (2005). Database in Depth: Relational Theory for Practitioners. O'Reilly Media, Inc. p. 142. ISBN 978-0-596-10012-4.
- ↑ Meier, Daniel (1980). "रिलेशनल डेटाबेस मॉडल में न्यूनतम कवर". Journal of the ACM. 27 (4): 664–674. doi:10.1145/322217.322223. S2CID 15789293.
अग्रिम पठन
- Codd, E. F. (1972). "Further Normalization of the Data Base Relational Model" (PDF). ACM Transactions on Database Systems. San Jose, California: Association for Computing Machinery.
बाहरी संबंध
- Gary Burt (Summer 1999). "CS 461 (Database Management Systems) lecture notes". University of Maryland Baltimore County Department of Computer Science and Electrical Engineering.
- Jeffrey D. Ullman. "CS345 Lecture Notes" (PostScript). Stanford University.
- Osmar Zaiane (June 9, 1998). "Chapter 6: Integrity constraints". CMPT 354 (Database Systems I) lecture notes. Simon Fraser University Department of Computing Science.