उम्मीदवार कुंजी

From Vigyanwiki

एक उम्मीदवार कुंजी या केवल रिलेशनल डेटाबेस की कुंजी एक न्यूनतम सुपरकी है।[1] यह स्तंभों का कोई समुच्चय है जिसमें प्रत्येक पंक्ति में मानों का अनूठा संयोजन होता है (जो इसे सुपरकी बनाता है), अतिरिक्त बाधा के साथ कि किसी भी स्तंभों को हटाने से मानों के प्रतिलिपि संयोजन उत्पन्न हो सकते हैं (जो इसे न्यूनतम सुपरकी बनाता है) .

विशिष्ट उम्मीदवार कुंजियों को कभी-कभी प्राथमिक कुंजी, द्वितीयक कुंजी या वैकल्पिक कुंजी कहा जाता है।

उम्मीदवार की में स्तंभों को प्राइम एट्रिब्यूट कहा जाता है,[2] और स्तंभों जो किसी उम्मीदवार कुंजी में नहीं होता है उसे गैर-प्रमुख विशेषता कहा जाता है।

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

संबंध में सभी विशेषताओं के लिए उम्मीदवार कुंजी से कार्यात्मक निर्भरता है।

किसी संबंध की उम्मीदवार कुंजी वे सभी संभव तरीके हैं जिनसे हम पंक्ति की पहचान कर सकते हैं। जैसे, वे डेटाबेस स्कीमा के डिजाइन के लिए महत्वपूर्ण अवधारणा हैं।

उदाहरण

उम्मीदवार कुंजियों की परिभाषा को निम्नलिखित (सार) उदाहरण के साथ चित्रित किया जा सकता है। विशेषताओं (A, B, C, D) के साथ रिलेशन वेरिएबल (रिलेवर) R पर विचार करें जिसमें केवल निम्नलिखित दो नियमी मान r1 और r2 हैं:

r1
A B C D
a1 b1 c1 d1
a1 b2 c2 d1
a2 b1 c2 d1
r2
A B C D
a1 b1 c1 d1
a1 b2 c2 d1
a1 b1 c2 d2

यहाँ r2 केवल अंतिम टपल के 'A' और 'D' मानों में r1 से भिन्न है।

r1 के लिए निम्नलिखित समुच्चयों में विशिष्टता गुण है, अर्थात, समुच्चय में समान विशेषता मानों के साथ उदाहरण में दो अलग-अलग टुपल्स नहीं हैं:

{A,B}, {A,C}, {B,C}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

r2 के लिए अद्वितीयता संपत्ति निम्नलिखित समुच्चयों के लिए है;

{B,C}, {B,D}, {C,D}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

चूंकि रिल्वर की सुपरकीज़ उन विशेषताओं के समुच्चय हैं जिनके पास उस रिल्वर के सभी नियमी मानों के लिए विशिष्टता संपत्ति है और क्योंकि हम मानते हैं कि r1 और r2 सभी नियमी मान हैं जो R ले सकते हैं, हम R के सुपरकीज़ के समुच्चय को निर्धारित कर सकते हैं दो सूचियों का प्रतिच्छेदन लेना:

{B,C}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

अंत में हमें उन समुच्चयों का चयन करने की आवश्यकता है जिनके लिए सूची में कोई उपसमुच्चय या उचित उपसमुच्चय नहीं है, जो इस स्थितियों में हैं:

{B,C}, {A,B,D}, {A,C,D}

ये वास्तव में रिल्वर R की उम्मीदवार कुंजी हैं।

हमें उन सभी संबंधों पर विचार करना होगा जो यह निर्धारित करने के लिए रिलेवर को सौंपे जा सकते हैं कि क्या विशेषताओं का निश्चित समुच्चय एक उम्मीदवार कुंजी है। उदाहरण के लिए, यदि हमने केवल r1 पर विचार किया होता तो हम यह निष्कर्ष निकालते कि {A,B} उम्मीदवार कुंजी है, जो गलत है। चूंकि, हम इस तरह के संबंध से यह निष्कर्ष निकालने में सक्षम हो सकते हैं कि निश्चित समुच्चय एक उम्मीदवार कुंजी नहीं है, क्योंकि उस समुच्चय में अद्वितीयता गुण नहीं है (उदाहरण के लिए {A,D} r1 के लिए)। ध्यान दें कि समुच्चय के उचित उपसमुच्चय का अस्तित्व जिसमें अद्वितीयता संपत्ति है, को सामान्यतः सबूत के रूप में उपयोग नहीं किया जा सकता है कि सुपरसमुच्चय उम्मीदवार कुंजी नहीं है। विशेष रूप से, ध्यान दें कि खाली संबंध के स्थितियों में, शीर्षक के प्रत्येक उपसमुच्चय में खाली समुच्चय सहित अद्वितीयता गुण होता है।

उम्मीदवार कुंजियों का निर्धारण

सभी उम्मीदवार कुंजियों के समुच्चय की गणना की जा सकती है उदा. कार्यात्मक निर्भरता के समुच्चय से। इसके लिए हमें विशेषता समुच्चय के लिए विशेषता क्लोजर को परिभाषित करने की आवश्यकता है। समुच्चय में वे सभी विशेषताएँ होती हैं जो कार्यात्मक रूप से अल्फा द्वारा निहित होती हैं।

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

वास्तव में हम इस प्रक्रिया के साथ प्रत्येक उम्मीदवार कुंजी का पता लगा सकते हैं, केवल विशेषताओं को हटाने के हर संभव क्रम का प्रयास करके। सामान्यतः उपसमुच्चय () की तुलना में विशेषताओं () के कई और क्रमपरिवर्तन हैं। यही है, कई विशेषता आदेश एक ही उम्मीदवार कुंजी की ओर ले जाएंगे।

उम्मीदवार कुंजी संगणना के लिए कुशल एल्गोरिदम के लिए मूलभूत कठिनाई है: कार्यात्मक निर्भरता के कुछ समुच्चय घातीय रूप से कई उम्मीदवार कुंजियों की ओर ले जाते हैं। क्रियात्मक निर्भरता पर विचार करें जो उम्मीदवार कुंजियाँ उत्पन्न करती है: । यही है, हम सबसे अच्छी उम्मीद कर सकते हैं कि एक एल्गोरिदम है जो उम्मीदवार कुंजी की संख्या के संबंध में कुशल है।

निम्नलिखित एल्गोरिदम वास्तव में उम्मीदवार कुंजी और कार्यात्मक निर्भरताओं की संख्या में बहुपद समय में चलता है:[3]

function find_candidate_keys(A, F)
    /* A is the set of all attributes and F is the set of functional dependencies */
    K[0] := minimize(A);
    n := 1; /* Number of Keys known so far */
    i := 0; /* Currently processed key */
    while i < n do
        for each α → β ∈ F do
            /* Build a new potential key from the previous known key and the current FD */
            S := α ∪ (K[i] − β);
            /* Search whether the new potential key is part of the already known keys */ 
            found := false;
            for j := 0 to n-1 do
                if K[j] ⊆ S then found := true;
            /* If not, add if 
            if not found then
                K[n] := minimize(S);
                n := n + 1;
        i := i + 1
    return K

एल्गोरिदम के पीछे विचार यह है कि एक उम्मीदवार कुंजी दी गई है और कार्यात्मक निर्भरता , कार्यात्मक निर्भरता पैदावार का उल्टा अनुप्रयोग समुच्चय , जो कुंजी भी है। चूंकि यह अन्य पहले से ज्ञात उम्मीदवार कुंजियों द्वारा कवर किया जा सकता है।(एल्गोरिदम 'पाया' चर का उपयोग करके इस स्थितियों की जांच करता है।) यदि नहीं, तो नई कुंजी को न्यूनतम करने से नई उम्मीदवार कुंजी प्राप्त होती है। मुख्य अंतर्दृष्टि यह है कि सभी उम्मीदवार कुंजी इस तरह से बनाई जा सकती हैं।

यह भी देखें

संदर्भ

  1. Date, Christopher (2015). "Codd's First Relational Papers: A Critical Analysis" (PDF). warwick.ac.uk. Retrieved 2020-01-04. Note that the extract allows a "relation" to have any number of primary keys, and moreover that such keys are allowed to be "redundant" (better: reducible). In other words, what the paper calls a primary key is what later (and better) became known as a superkey, and what the paper calls a nonredundant (better: irreducible) primary key is what later became known as a candidate key or (better) just a key.
  2. Saiedian, H. (1996-02-01). "An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema". The Computer Journal (in English). 39 (2): 124–132. doi:10.1093/comjnl/39.2.124. ISSN 0010-4620.
  3. L. Lucchesi, Cláudio; Osborn, Sylvia L. (October 1978). "Candidate keys for relations". Journal of Computer and System Sciences. 17 (2): 270–279. doi:10.1016/0022-0000(78)90009-0.


बाहरी संबंध