Decomposition: lossless joins, preservation और 4NF
लक्ष्य और मान्यताएँ
Relation को ऐसे हिस्सों में बाँटना सीखें कि projections का natural join नई, गलत सूचना न बनाए। इसे dependencies को स्थानीय रूप से जाँच सकने से अलग रखें। BCNF decomposition और 3NF synthesis के guarantees समझें। यहाँ NULL-विहीन set relations तथा functional dependencies (FD) हैं, जब तक multivalued dependency (MVD) अलग न बताई जाए। सभी component schemas का union मूल schema होना चाहिए। Projection duplicate tuples हटाता है।
1. Design के दो अलग प्रश्न
R का R1,...,Rn में decomposition, F के सापेक्ष lossless तब है जब F मानने वाली हर legal instance r, अपनी component projections के natural join के बराबर हो। Original tuples join में हमेशा मिलते हैं; समस्या extra या spurious tuples की है। एक sample का ठीक जुड़ जाना सभी legal instances के लिए guarantee नहीं है।
Dependency preservation पूछता है कि original constraints को components में अलग-अलग जाँचकर enforce कर सकते हैं या join करना पड़ेगा। Fi, F का Ri पर projection है: F+ की वे सभी dependencies जिनके attributes Ri में हैं। केवल लिखी हुई FDs जो component में फिट होती हैं, लेना पर्याप्त नहीं। Preservation के लिए सभी Fi का union, F की हर FD imply करे। उल्टी implication स्वतः है क्योंकि Fi, F+ से निकला है। Losslessness reconstruction की property है; preservation constraint checking की। एक से दूसरा निष्कर्ष न निकालें।
2. Binary lossless-join test
जब R1∪R2=R हो, FD-based binary decomposition lossless ठीक तब है जब F+ में (R1∩R2)→R1 या (R1∩R2)→R2 हो। Common attributes का closure F के तहत निकालें और देखें कि वह किसी एक पूरे component को cover करता है या नहीं। Intersection का पूरे original schema को determine करना आवश्यक नहीं।
उदाहरण: R(A,B,C), F={A→B} को AB तथा AC में बाँटें। Intersection A है; A+={A,B}। यह AB cover करता है, इसलिए decomposition lossless है, भले A से C न मिले। A→B को AB में जाँच सकते हैं, इसलिए dependency preservation भी है।
विपरीत उदाहरण: उसी R को AB तथा BC में बाँटें। Common B का closure {B} है; वह किसी component को पूरा determine नहीं करता। Legal original relation {(a1,b,c1),(a2,b,c2)} लें; A→B सत्य है। AB projection {(a1,b),(a2,b)} और BC projection {(b,c1),(b,c2)} है। Join चार tuples देता है; (a1,b,c2) तथा (a2,b,c1) अतिरिक्त हैं। यहाँ A→B locally preserved है, फिर भी decomposition lossy है। अलग A values का एक ही B होना allowed है।
Arbitrary multiway decomposition के हर pair पर यह binary test लगाकर पूरे decomposition को lossless घोषित न करें। General case में chase/tableau test या valid binary lossless splits की पूरी sequence दें। हर split उस relation को दोबारा reconstruct करता है जिसे उसने replace किया, इसलिए lossless splits की sequence पर्याप्त है।
3. BCNF violation से decomposition
Schema S में nontrivial X→Y, BCNF violate करे। Z=Y−X लें। S1=X∪Z और S2=S−Z बनाएँ। Intersection X है और X से S1 मिलता है, इसलिए यह split lossless है। नए components की projected dependencies निकालकर प्रक्रिया दोहराएँ, जब तक हर component BCNF न हो। इससे lossless result मिलता है, लेकिन dependency preservation का guarantee नहीं। अलग violation चुनने से अलग decomposition मिल सकता है।
Trade-off का उदाहरण: R(A,B,C), F={AB→C,C→B}। Candidate keys AB तथा AC हैं। C→B, BCNF violate करता है क्योंकि C से A नहीं मिलता। CB तथा AC में split करें। Common C से CB मिलता है, इसलिए split lossless है। CB में C key है; AC में कोई nontrivial projected FD नहीं। दोनों BCNF हैं। लेकिन AB→C preserved नहीं: local nontrivial dependencies के union में सिर्फ C→B है, जिसके तहत AB का closure C नहीं जोड़ सकता।
स्थानीय जाँच पर्याप्त क्यों नहीं, इसे tuples से देखें: CB={(c1,b),(c2,b)}, AC={(a,c1),(a,c2)}। CB में C→B मान्य है और AC में कोई nontrivial FD restriction नहीं। Join में (a,b,c1),(a,b,c2) मिलते हैं, जो AB→C तोड़ते हैं। Losslessness केवल legal original relation के projections का सही reconstruction कहता है; arbitrary locally valid components सभी original dependencies मानेंगे, ऐसा नहीं कहता।
4. Dependency-preserving 3NF synthesis
Singleton right sides वाला minimal cover G बनाएँ। हर determinant X के लिए X तथा G में उसकी सभी right-side attributes वाला schema बनाएँ। किसी अन्य schema के भीतर contained schema हटाएँ। यदि कोई resulting schema original R की candidate key contain नहीं करता, तो किसी candidate key के attributes वाला schema जोड़ें। सामान्य FD model में यह synthesis dependency-preserving, lossless और 3NF decomposition देता है। Key-containing schema lossless guarantee के लिए महत्वपूर्ण है; preservation अकेले यह guarantee नहीं देता।
उदाहरण: R(A,B,C,D), F={A→B,B→C}। यह पहले से minimal cover है। AB और BC बनाएँ। A तथा D किसी right side में नहीं आते, इसलिए key में दोनों जरूरी हैं। AD का closure पूरा R है: A से B,C आते हैं और D स्वयं मौजूद है। A या D अकेला पूरा R नहीं देता, इसलिए AD candidate key है। AB या BC में AD नहीं आता, अतः AD schema जोड़ें। {AB,BC,AD} dependencies को locally preserve करता है और lossless है। केवल AB,BC पर रुकना तो schema coverage भी तोड़ता, क्योंकि D गायब होता।
Projection में implied dependency महत्वपूर्ण हो सकती है। F={A→B,B→C} का AC पर projection, A→C include करता है, भले इसे मूल सूची में नहीं लिखा था। केवल syntactically retained FDs से preservation test करना गलत उत्तर दे सकता है। प्रत्येक original X→Y के लिए सही projected dependencies के union के तहत X का closure, Y contain करे।
5. सहायक विस्तार: independent multivalued facts और 4NF
MVD X↠Y कहता है कि fixed X के लिए Y के संभव values, बाकी attributes Z=R−(X∪Y) के values से independent हैं। यदि दो tuples X पर समान हों, तो पहले का Y और दूसरे का Z मिलाने वाला tuple तथा दूसरे का Y और पहले का Z मिलाने वाला tuple भी होना चाहिए। Y⊆X या X∪Y=R होने पर MVD trivial है। हर FD X→Y से MVD X↠Y मिलता है, लेकिन MVD से सामान्यतः FD नहीं मिलता।
PersonSkillLanguage(P,S,L) में व्यक्ति की independent skills और languages रखें। किसी व्यक्ति की skills s1,s2 और languages l1,l2 हों तो सभी चार combinations चाहिए। P↠S सत्य है, लेकिन P→S नहीं। कोई nontrivial FD न मानें तो relation BCNF में है; फिर भी independent facts दोहरते हैं। 4NF में हर nontrivial MVD का determinant superkey होना चाहिए। P superkey नहीं, इसलिए 4NF fail। PS तथा PL में split करें। P↠S के तहत उनकी projections का join lossless है। यदि कोई skill केवल किसी particular language से जुड़ी है, तो independence और यह MVD मत मानें। यह semantic assumption है, केवल दो lists देखकर सिद्ध बात नहीं।
परीक्षा की सावधानियाँ
- पहले schema coverage, फिर losslessness और preservation अलग-अलग जाँचें।
- Binary condition में OR है: intersection किसी एक side को determine करे; दोनों जरूरी नहीं।
- BCNF split preservation खो सकता है; 3NF synthesis इसे बनाए रखता है।
- एक sample में spurious tuples न मिलना universal proof नहीं।
- Projected FDs दोबारा निकालें; implied dependencies component में local बन सकती हैं।
- 4NF यहाँ normal forms की सहायक depth है, अलग official syllabus heading होने का दावा नहीं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. R(A,B,C), F={A→B}। {AB,AC} lossless है?
A. हाँ, A से AB मिलता है B. नहीं, A से C नहीं मिलता C. केवल B→A भी हो तो D. केवल one-tuple relations में
उत्तर: A
A: Common A एक पूरा component determine करता है।
B: दूसरा component determine करना जरूरी नहीं।
C: Reverse FD की जरूरत नहीं।
D: FD test हर legal instance पर लागू है।
P02. F={A→B} के तहत ABC का {AB,BC} decomposition कैसा है?
A. Lossless तथा preserving B. Lossy लेकिन preserving C. Lossless लेकिन not preserving D. न preserving, न schema-covering
उत्तर: B
A: B किसी side को determine नहीं करता, इसलिए lossless नहीं।
B: A→B local है, लेकिन common B losslessness के लिए पर्याप्त नहीं।
C: यह lossy है और A→B local है।
D: Schema coverage तथा preservation दोनों हैं।
P03. Binary FD-based losslessness में intersection क्या determine करे?
A. दोनों components अनिवार्यतः B. कम-से-कम एक component C. केवल स्वयं को D. हर case में हर candidate key
उत्तर: B
A: Test में OR है, AND नहीं।
B: किसी एक पूरे component को determine करना necessary तथा sufficient है।
C: केवल trivial self-determination पर्याप्त नहीं।
D: Original key determine करना जरूरत से मजबूत condition है।
P04. F={AB→C,C→B} में ABC को CB तथा AC में split किया। कौन-सी original FD locally preserved नहीं?
A. C→B B. AB→C C. C→C D. AB→A
उत्तर: B
A: C→B को CB में enforce करते हैं।
B: Local nontrivial FD C→B से AB closure में C नहीं जुड़ता।
C: Reflexivity हमेशा सत्य है।
D: यह trivial और हमेशा सत्य है।
P05. 3NF synthesis के बाद कोई component original candidate key contain नहीं करता। Standard अगला कदम?
A. सभी FDs हटाएँ B. Candidate key वाला schema जोड़ें C. Automatic BCNF घोषित करें D. सभी components को permanently join करें
उत्तर: B
A: Constraints हटाना problem बदलता है।
B: इससे standard lossless-synthesis safeguard मिलता है।
C: 3NF synthesis से automatic BCNF guarantee नहीं।
D: Permanent join intended decomposition को वापस कर देता है।
P06. P,S,L में व्यक्ति की 3 independent skills और 2 independent languages हैं। Cross-product MVD model में उसके कितने tuples चाहिए?
A. 2 B. 3 C. 5 D. 6
उत्तर: D
A: हर language तीनों skills से pair होती है।
B: हर skill दोनों languages से pair होती है।
C: Independent combinations में गुणा करते हैं, जोड़ नहीं।
D: 3×2 अलग skill-language pairs हैं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Databases syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन