Functional dependencies: closures, keys और covers
लक्ष्य और assumptions
Functional dependencies (FDs) के consequences निकालें, attribute closure तथा candidate keys खोजें और equivalent dependency set को छोटा करें। Classical finite relations, no NULL और set semantics लें। X→Y का अर्थ: X के हर attribute पर agree करने वाले कोई भी दो tuples, Y के हर attribute पर भी agree करेंगे। इससे reverse direction या पूरे row की key होने का दावा नहीं होता।
1. FD का pairwise अर्थ
Student(sid,dept,building) में sid→dept कहता है कि हर legal instance में student का एक department value है। dept→building से हर department का एक building value है। दोनों से sid→building निकलता है। एक department में कई students तथा एक building में अलग departments allowed हैं। Y⊆X हो तो FD trivial है; AB→A हमेशा सही है। Right side में X से बाहर कोई attribute हो तो nontrivial है।
Instance FD को violate कर सकता है: (1,x),(1,y), x≠y, A→B को गलत बताते हैं। सभी A values अलग दिखने से A→B universal schema rule सिद्ध नहीं होता। FD किसी determinant value का मौजूद होना अनिवार्य नहीं करता।
2. Armstrong rules
Reflexivity: Y⊆X हो तो X→Y। Augmentation: X→Y से XZ→YZ। Transitivity: X→Y तथा Y→Z से X→Z। ये rules FD implication के लिए sound और complete हैं। Union में X→Y तथा X→Z से X→YZ; decomposition में X→YZ से X→Y तथा X→Z। Pseudotransitivity में X→Y और WY→Z से WX→Z। X→Y और Z→Y से X→Z नहीं निकलता: समान output एक-दूसरे को determine नहीं करता।
3. Closure algorithm
F के अंतर्गत X+ निकालने के लिए X से शुरू करें। जिस FD की पूरी left side set में आ गई हो, उसकी right side जोड़ें। बदलाव रुकने तक दोहराएँ। X→Y तभी implied है जब Y⊆X+। X+ में R के सभी attributes हों तो X superkey है।
उदाहरण: R(A,B,C,D,E), F={A→BC,C→D,BD→E}। A+={A} से शुरू करें। A→BC से {A,B,C}; C→D से {A,B,C,D}; BD→E से सभी पाँच। इसलिए A superkey है। Empty set से कोई FD लागू नहीं, इसलिए सभी attributes नहीं मिलते; अतः {A} minimal और candidate key है। B+={B}; BD+={B,D,E}, जिसमें A तथा C नहीं हैं।
4. Candidate key में coverage और minimality दोनों
Nontrivial FDs की किसी right side पर न आने वाला attribute अन्य attributes से generate नहीं होगा और हर key में चाहिए, बशर्ते F के implications के अलावा कोई FD न मानें। ऐसे mandatory attributes से शुरू करें, candidates जोड़ें, closure निकालें और known keys के supersets छोड़ें। Minimality के लिए एक-एक attribute हटाएँ। कोई single removal superkey न रहे तो छोटा subset भी superkey नहीं हो सकता, क्योंकि closure monotonic है।
उदाहरण: R(A,B,C,D), F={A→B,B→A,C→D}। C किसी right side पर नहीं है, इसलिए mandatory है। C+={C,D}, अकेला C fail। A जोड़ें: AC+ में चारों; B जोड़ें: BC+ में चारों। AC या BC का कोई member हटाने पर fail। ठीक AC और BC candidate keys हैं: हर key में C और A/B में कम-से-कम एक चाहिए; D जोड़ने से A या B नहीं मिलता। केवल schema का attribute होने से D mandatory नहीं।
Candidate keys के sizes अलग हो सकते हैं। R(A,B,C), F={A→BC,BC→A} में A और BC दोनों candidate keys हैं। BC minimal है क्योंकि B और C अकेले fail हैं, भले A में कम attributes हों।
5. Minimal cover
Minimal cover में singleton right sides, left side पर कोई extraneous attribute नहीं, और कोई redundant FD नहीं होती। Equivalent covers अलग दिख सकते हैं; unique होना जरूरी नहीं। पहले right sides split करें। X→a में b को left side से हटाने की जाँच के लिए current set में (X−{b})+ निकालकर a देखें। पूरी FD X→a redundant है या नहीं, इसके लिए उस FD को अस्थायी हटाएँ और बाकी set से X द्वारा a derive होने को जाँचें। पूरी FD की जाँच में उसे न हटाने से हर FD गलत तरह redundant लगेगी।
उदाहरण: F={A→BC,B→C,A→B,AB→C}। Split तथा duplicate A→B हटाने पर {A→B,A→C,B→C,AB→C} है। B→C से AB→C implied है, इसलिए redundant। A→B और B→C से A→C implied है, इसलिए redundant। Minimal cover {A→B,B→C} है। बची कोई FD अकेली दूसरी से नहीं निकलती। हर deletion के बाद current set पर recompute करें; stale simultaneous tests से कई FDs एक साथ न हटाएँ।
सावधानियाँ
- Determinant पूरे row की key होना जरूरी नहीं।
- Closure fixed point तक निकालें; एक scan पर्याप्त नहीं हो सकता।
- Keys minimal होनी चाहिए, superkeys नहीं।
- Minimal का मतलब globally smallest size या unique cover नहीं।
- Attribute names या accidental sample से FD न मानें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. A→B और B→C से कौन-सी FD जरूरी है?
A. C→A B. A→C C. B→A D. C→B
उत्तर: B
A: Reverse chain implied नहीं।
B: Transitivity से A→C।
C: A→B का reverse implied नहीं।
D: B→C का reverse implied नहीं।
P02. R(A,B,C,D), F={A→B,B→C} में A+?
A. {A} B. {A,B} C. {A,B,C} D. {A,B,C,D}
उत्तर: C
A: A→B लागू है।
B: B→C से C आता है।
C: A से B फिर C; D जोड़ने वाली FD नहीं।
D: इन FDs से D नहीं मिलता।
P03. R(A,B,C,D), F={A→B,B→A,C→D} की candidate keys?
A. A और B B. AC और BC C. केवल C D. ACD और BCD
उत्तर: B
A: A या B से C नहीं आता।
B: C mandatory है; A या B बाकी pair देता है।
C: C से D आता है, A/B नहीं।
D: ये AC तथा BC के nonminimal supersets हैं।
P04. कौन-सी FD trivial है?
A. A→B for distinct A,B B. AB→A C. A→BC for distinct A,B,C D. B→A for distinct A,B
उत्तर: B
A: B, A का subset नहीं।
B: Right side A, AB में शामिल है।
C: Right side में A के बाहर attributes हैं।
D: A, B का subset नहीं।
P05. X→a पूरी FD redundant है या नहीं जाँचने के लिए X+ किससे निकालें?
A. केवल X→a B. F से X→a हटाकर C. हमेशा बिना dependencies D. F में a→X जोड़कर
उत्तर: B
A: यह FD को उसी से सिद्ध करता है।
B: बाकी dependencies से निकलना redundancy की शर्त है।
C: अन्य dependencies इसे imply कर सकती हैं।
D: नई reverse FD जोड़ना problem बदलता है।
P06. R(A,B,C), F={A→BC,BC→A} में क्या सही है?
A. छोटा होने से केवल A key है B. A और BC दोनों candidate keys C. B अकेला candidate key D. ABC candidate key
उत्तर: B
A: Minimality subset से है, global smallest size से नहीं।
B: दोनों सभी attributes देते हैं और उनका proper subset नहीं देता।
C: C बिना B अकेला BC→A नहीं लगा सकता।
D: A पर्याप्त है, इसलिए ABC minimal नहीं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Databases syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन