Relational algebra: operators, joins और division
लक्ष्य और semantic contract
Algebra expression को operator-दर-operator evaluate करें, schemas सही रखें और existential तथा universal queries अलग पहचानें। यहाँ relations finite sets हैं, values non-null हैं और comparisons two-valued logic लेते हैं। Projection duplicates हटाता है। SQL bags तथा NULL आगे आएँगे। Algebra expression relation देता है, इसलिए उसका result अगले operator का input बन सकता है।
1. Selection, projection और rename
Selection σ_condition(R) predicate सही करने वाले tuples रखता है और schema नहीं बदलता। Projection π_attributes(R) केवल बताए attributes रखता और duplicate result tuples हटाता है। Rename ρ relation या attributes का नाम बदलता है ताकि self-join तथा set operations स्पष्ट हों।
Enrol(sid,cid)={(1,A),(1,B),(2,A),(3,C)} लें। σ_cid=A(Enrol)={(1,A),(2,A)}। इससे sid project करने पर {1,2} मिलता है। पूरी relation से sid project करने पर {1,2,3}, यानी cardinality 3 मिलती है, 4 नहीं। Selection rows नहीं बढ़ाता; set semantics में projection भी rows नहीं बढ़ाता। अगर zero-attribute projection algebra में allowed हो, तो nonempty input पर {()} और empty input पर empty result है; अभ्यास में attribute lists nonempty हैं।
2. Set operators और Cartesian product
Union, intersection, difference के schemas union-compatible होने चाहिए: समान arity और corresponding compatible domains; named-attribute notation में names align करें। R−S में वे tuples रहते हैं जो R में हैं लेकिन S में नहीं। यह commutative नहीं। R={1,2,3}, S={2,4} के लिए union {1,2,3,4}, intersection {2}, difference R−S={1,3} है।
Cartesian product हर R tuple को हर S tuple से जोड़ता है, इसलिए attributes को rename करके collisions हटाने पर cardinality |R||S| है। Empty relation से product empty है। Product पर selection theta join देता है: R ⋈_θ S = σ_θ(R×S)। Equality theta predicate का एक प्रकार है, एकमात्र नहीं।
3. Join values मिलाता है, row positions नहीं
Student(sid,name)={(1,Ana),(2,Bob),(4,Dev)} और ऊपर के Enrol में sid common है। Natural join सभी common attributes को बराबर करता है और हर common column की एक copy रखता है। (sid,name,cid) पर result {(1,Ana,A),(1,Ana,B),(2,Bob,A)} है। Student 4 का enrollment नहीं, इसलिए inner join में नहीं आता। Enrol के sid 3 का matching Student नहीं, इसलिए वह भी नहीं आता। इस teaching instance में referential-integrity constraint assume नहीं है।
Natural join हर साझा नाम उपयोग करता है। दो असंबंधित columns का नाम name हो तो rename न करने पर वे भी बराबर किए जाएँगे। कोई common attribute न हो तो natural join Cartesian product है। Rows को order में zip करना या counts बराबर मानना गलत है।
Self-join के लिए दो renamed copies चाहिए। Employee(eid,managerId) से employee और manager पाने के लिए copies E और M लें, E×M पर E.managerId=M.eid select करें, फिर E.eid और M.eid project करें। अलग names बिना roles स्पष्ट नहीं रहते।
4. Division “हर एक के लिए” बताता है
R(X,Y) और S(Y) में R÷S वे X values देता है जो π_X(R) में आती हैं और S के हर Y के साथ R में pair बनाती हैं। Candidate domain स्पष्ट रूप से π_X(R) है। Construction:
Candidates = π_X(R) Missing = (Candidates×S)−R Bad = π_X(Missing) Answer = Candidates−Bad
सभी schemas align होने चाहिए। ऊपर Enrol तथा Required(cid)={A,B} लें। Candidates={1,2,3}। 1 के पास A तथा B दोनों हैं; 2 के पास B नहीं; 3 के पास A और B दोनों नहीं। इसलिए Enrol÷Required={1}। “कम-से-कम एक required course लेता है” का existential result {1,2} होगा; वह अलग query है।
Required empty हो तो हर candidate universal condition को vacuously satisfy करता है। Division {1,2,3} देता है; sid 4 नहीं बनाता क्योंकि वह π_sid(Enrol) में नहीं। अगर सवाल सभी students के बारे में है, जिनका कोई enrollment नहीं उन्हें भी शामिल करना है, तो Student candidate domain लें: π_sid(Student)−π_sid((π_sid(Student)×Required)−Enrol)। Empty Required पर सभी Student sid मिलेंगे। “For all” लगाने से पहले candidate domain तय करें।
5. Safe rewrites और query trace
Selection predicate केवल एक input के attributes पर निर्भर हो तो उसे join से पहले उसी input पर push कर सकते हैं। Projection pushdown में final output तथा आगे के join/predicate के सभी जरूरी attributes बचने चाहिए। Student को Enrol से जोड़ने से पहले sid हटाना join तोड़ देगा।
A में enrolled students के names के लिए पहले Enrol पर cid=A filter करें, फिर sid पर Student से join करें, फिर name project करें। Filtered rows (1,A),(2,A) हैं; join में Ana तथा Bob आते हैं; final set {Ana,Bob} है। दो qualifying students का name समान हो तो set projection उसे केवल एक बार देता है। Individual identity बचानी हो तो sid तथा name दोनों project करें।
सावधानियाँ
- Selection rows चुनता है; projection attributes चुनता और duplicates हटाता है।
- Difference directional है और compatible schemas चाहिए।
- Natural join सभी common names match करता है; accidental overlaps rename करें।
- “कम-से-कम एक” existence है; “हर” के लिए missing pairs हटाएँ।
- Empty requirements पर universal condition चुने हुए candidate domain में सत्य है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. R(A,B)={(1,x),(1,y),(2,x)} में set semantics पर |π_A(R)| कितना है?
A. 1 B. 2 C. 3 D. 6
उत्तर: B
A: A=1 और A=2 दोनों मौजूद हैं।
B: Projection {1,2} देता है; repeated 1 हटता है।
C: यह duplicates रखता है, set projection के विपरीत।
D: Projection tuple count दोगुना नहीं करता।
P02. 4 tuples वाली relation का empty relation से product कितना है?
A. 0 B. 1 C. 4 D. अपरिभाषित
उत्तर: A
A: दूसरे input में tuple नहीं, इसलिए कोई pair नहीं।
B: Empty relation singleton empty tuple नहीं है।
C: हर पहले tuple को partner चाहिए।
D: Cartesian product defined है।
P03. R(A)={1,2,3}, S(A)={2,4}। R−S क्या है?
A. {2} B. {4} C. {1,3} D. {1,2,3,4}
उत्तर: C
A: यह intersection है।
B: यह S−R है।
C: केवल R की वे values रखें जो S में नहीं।
D: यह union है।
P04. बिना common attribute names वाली relations का natural join किसके बराबर है?
A. Union B. Cartesian product C. हमेशा empty D. Difference
उत्तर: B
A: Union को compatible schemas चाहिए और उसका अर्थ अलग है।
B: Shared equality conditions नहीं, इसलिए हर pair जुड़ता है।
C: Common attributes न होना pairs को रोकता नहीं।
D: Difference tuples हटाता है, join नहीं।
P05. R(s,c)={(1,A),(1,B),(2,A)}, S(c)={A,B}। R÷S क्या है?
A. {1} B. {2} C. {1,2} D. Empty
उत्तर: A
A: केवल 1 हर required c से paired है।
B: 2 के पास B नहीं।
C: यह कम-से-कम एक required c का उत्तर होगा।
D: 1 universal requirement पूरी करता है।
P06. Nonempty R(X,Y) को empty S(Y) से divide करें; candidates π_X(R) हैं। Result?
A. हमेशा empty B. π_X(R) C. सभी कल्पनीय X values D. दोनों columns के साथ R
उत्तर: B
A: Requirements empty हों तो किसी candidate का required pair missing नहीं।
B: दिए domain का हर candidate universal condition पूरी करता है।
C: Division domain के बाहर values नहीं बनाता।
D: Division X schema लौटाता है, X,Y नहीं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Databases syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन