Tuple relational calculus: quantifiers और safety
लक्ष्य और relations
“कुछ,” “कोई नहीं,” और “हर” को tuple predicates में लिखें और unbounded universe पर फैलने वाली queries पहचानें। Relational algebra तथा predicate logic का आधार चाहिए। यहाँ finite, non-null, set-valued Student(sid,name), Course(cid), Enrol(sid,cid) हैं। Tuple relational calculus (TRC) operator sequence के बजाय result की property बताता है।
{t | P(t)} उन result tuples t का set है जो P पूरा करते हैं। Student(s) का अर्थ s, Student का tuple है। s.sid=e.sid attributes compare करता है। ∃e किसी उपयुक्त tuple e की मौजूदगी और ∀c universe के हर tuple c के लिए शर्त बताता है। Parentheses तथा guards scope स्पष्ट रखते हैं। केवल sid output हो तो t(sid) schema लिखा गया है।
1. Free और bound variables
{t(sid) | ∃s(Student(s) ∧ t.sid=s.sid)} में s, ∃ से bound है; predicate में t free है और output तय करता है। Student(s) guard witnesses को stored students तक सीमित करता है। Bound variable का नाम हर जगह एकसमान बदलने से अर्थ नहीं बदलता। Output t को bound variable से मिलाने पर अर्थ बदल सकता है या output अस्पष्ट रह सकता है।
पूरा student tuple लौटाने के लिए {s | Student(s) ∧ condition(s)} सुविधाजनक है। केवल ids के लिए output t(sid) को matching student id से बाँधें। कई existential witnesses मिलने पर भी TRC set semantics duplicate result नहीं देता।
2. Existential queries और joins
A में enrolled students:
{s | Student(s) ∧ ∃e(Enrol(e) ∧ e.sid=s.sid ∧ e.cid=A)}।
हल किया instance: Student={(1,Ana),(2,Bob),(3,Chen),(4,Dev)}; Enrol={(1,A),(1,B),(2,A),(3,C)}। Students 1 और 2 के cid=A witnesses हैं; 3 तथा 4 के नहीं। Result full tuples (1,Ana),(2,Bob) है। अतिरिक्त witnesses student को duplicate नहीं करेंगे।
बिना enrollment वाले students:
{s | Student(s) ∧ ¬∃e(Enrol(e) ∧ e.sid=s.sid)}।
केवल (4,Dev) मिलता है। Positive Student(s) guard negation के बाहर रहता है। हम stored students में बिना match वाले खोज रहे हैं, arbitrary बाहरी tuples नहीं।
3. Universal query: कोई counterexample नहीं
Course के हर course के लिए student का matching enrollment चाहिए:
{s | Student(s) ∧ ∀c(Course(c) → ∃e(Enrol(e) ∧ e.sid=s.sid ∧ e.cid=c.cid))}।
Course(c) guard implication में है। Course के बाहर के tuples कोई requirement नहीं बनाते। Unrestricted ∀ के अंदर implication की जगह Course(c) ∧ ... करने से गलत रूप में universe के हर tuple को Course में होना पड़ेगा।
Identity ∀c(A(c)→B(c)) ≡ ¬∃c(A(c)∧¬B(c)) से query:
{s | Student(s) ∧ ¬∃c(Course(c) ∧ ¬∃e(Enrol(e) ∧ e.sid=s.sid ∧ e.cid=c.cid))}।
Course={A,B} में student 1 का कोई course missing नहीं; 2 का B missing; 3 और 4 के दोनों missing हैं। केवल 1 पास होता है। Course empty हो तो हर stored student, student 4 भी, qualify करता है क्योंकि counterexample course ही नहीं है। Requirement में “कम-से-कम एक course भी लेता हो” हो तो अलग existential enrollment condition जोड़ें।
4. Safety और domain independence
{t | ¬Student(t)} intended finite relational setting में unsafe है: stored relation के बाहर सारे possible tuples गिन सकता है। Stored data न बदले, फिर भी ambient domain बढ़ने पर result बढ़ सकता है। इसके विपरीत {s | Student(s) ∧ ¬∃e(Enrol(e) ∧ e.sid=s.sid)} finite stored Student का subset है और domain-independent query है।
व्यावहारिक तरीका: result values को stored data या explicit constants से लें, witness variables को positive relation atoms से bind करें और negation/quantifiers guard करें। यह safe query लिखने की उपयोगी discipline है, arbitrary first-order formula के लिए complete decision algorithm नहीं। Explicit constant output में आ सकता है भले stored data में न हो; safety का मतलब “constants मना” नहीं। Standard relational setting में safe/domain-independent calculus और relational algebra की expressive power समान है; unrestricted calculus intended executable query language नहीं।
5. जाँच का क्रम और गलतियाँ
- Output schema और candidate domain लिखें।
- Stored candidates को positive relation atom से guard करें।
- तय करें: एक witness, कोई witness नहीं, या कोई counterexample नहीं।
- Quantifier scopes parenthesize करें और comparisons जाँचें।
- Empty input, empty requirement relation और no-match candidate पर test करें।
“हर student कोई course लेता है” में हर student का course अलग हो सकता है: guards सहित ∀s∃c। “कोई course हर student लेता है” में ∃c∀s है और एक common course चाहिए। Quantifier order अर्थ बदलता है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. {t(sid) | ∃s(Student(s) ∧ t.sid=s.sid)} में quantifier से कौन bound है?
A. केवल t B. केवल s C. t और s दोनों D. कोई नहीं
उत्तर: B
A: Predicate में t free output variable है।
B: Existential quantifier s को bind करता है।
C: ∃s output variable को bind नहीं करता।
D: s स्पष्ट रूप से bound है।
P02. “कोई matching enrollment मौजूद नहीं” कैसे लिखेंगे?
A. Unguarded output complement B. Negated existential matching predicate C. कोई unrelated enrollment मौजूद है D. Relation names की equality
उत्तर: B
A: इसमें stored candidates के बाहर arbitrary tuples आ सकते हैं।
B: ¬∃ कहता है match का कोई witness नहीं।
C: Unrelated witness इस student की बात नहीं बताता।
D: Relation names की equality आवश्यक tuple condition नहीं।
P03. ∀x(P(x)→Q(x)) के equivalent क्या है?
A. ∃x(P(x)∧Q(x)) B. ¬∃x(P(x)∧¬Q(x)) C. ∀x(P(x)∧Q(x)) D. ¬∃x(P(x)∧Q(x))
उत्तर: B
A: एक सफल witness सभी P के लिए पर्याप्त नहीं।
B: कोई P witness Q को violate नहीं करता।
C: यह हर domain value पर P भी अनिवार्य करता है।
D: यह सफल P-and-Q witnesses को रोकता है।
P04. Candidates सभी stored students हैं। Required Course empty हो तो “हर required course में enrolled” कौन है?
A. कोई student नहीं B. केवल enrollment वाले C. हर stored student D. Universe का हर possible tuple
उत्तर: C
A: कोई counterexample course नहीं है।
B: Condition अलग से enrollment अनिवार्य नहीं करती।
C: Vacuous truth सभी stored candidates पर लागू है।
D: Student membership output को bound रखती है।
P05. Unrestricted tuple universe में {t | ¬Student(t)} unsafe क्यों है?
A. इसमें relation name है B. यह stored data के बाहर unbounded tuples दे सकता है C. हमेशा zero rows देता है D. इसमें existential quantifier है
उत्तर: B
A: Safe queries में relation membership सामान्य है।
B: Complement ambient universe पर निर्भर है।
C: Student के बाहर कई tuples हो सकते हैं।
D: Formula में existential quantifier है ही नहीं।
P06. किस requirement में हर student का एक common course चाहिए?
A. हर student कोई course लेता है B. कोई course हर student लेता है C. कोई student कोई course लेता है D. एक भी student कोई भी course नहीं लेता
उत्तर: B
A: हर student का चुना course अलग हो सकता है।
B: Existential course पहले, universal student बाद में चुना जाता है।
C: यह केवल एक enrollment witness माँगता है।
D: यह enrollments रोकता है, common course नहीं खोजता।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Databases syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन