Transactions, ACID और schedule serializability
लक्ष्य और notation
Transaction guarantees समझें, interleaving में हर transaction का program order बनाए रखें और conflict serializability जाँचें। Conflict equivalence, view equivalence और केवल एक final value का समान होना अलग बातें हैं। r_i(X), w_i(X), c_i, a_i क्रमशः Ti का X पढ़ना, लिखना, commit और abort हैं। अलग निर्देश न हो तो read को उसी item की सबसे हाल की preceding write या initial value मिलती है। Serializability अभ्यासों में committed transactions के single-version schedules हैं।
1. ACID के चार अलग guarantees
Atomicity का अर्थ transaction के effects एक unit की तरह होना है: failure के बाद केवल कुछ effects committed जैसे नहीं बचने चाहिए। Consistency का अर्थ correct transaction द्वारा valid state से शुरू करके declared constraints और application invariants बनाए रखना है। DBMS सारे business rules स्वयं नहीं जान सकता। Isolation बताता है concurrent execution कैसे दिखाई देगा। Durability का अर्थ reported commit का system के covered failures के बाद भी सुरक्षित रहना है।
उदाहरण: A से B में 40 units transfer करें। शुरुआती balances 100 और 50 हैं। Correct serial transfer के बाद 60 तथा 90 होंगे, कुल 150 बना रहेगा। A=60 store करने के बाद और B बदलने से पहले crash हो तो recovery design के अनुसार rollback या completion चाहिए। 60 और 50 छोड़ना invariant तोड़ता है। बीच में दूसरा transaction पढ़े तो isolation protection के बिना partial transfer देख सकता है। Recoverable durable information सुनिश्चित किए बिना commit बताना durability को खतरे में डालता है।
Lifecycle: operations चलने पर active; आखिरी statement के बाद लेकिन commitment guarantee से पहले partially committed; successful commit के बाद committed; आगे न चल पाने पर failed; rollback के बाद aborted। Restart नया execution attempt है। आखिरी SQL statement समाप्त होने का अर्थ durable commit नहीं।
2. Serial schedules तथा interleavings
Serial schedule में हर transaction की operations contiguous चलती हैं, interleaving नहीं होती। Serializable schedule interleave कर सकता है, लेकिन किसी निर्दिष्ट equivalence के तहत एक serial ordering के बराबर होता है। हर transaction का अपना program order बदलना मना है। T1 में m और T2 में n अलग operations हों, और कोई अतिरिक्त restriction न हो, तो order-preserving interleavings की संख्या binomial(m+n,m) है। सभी interleavings serializable हों, ऐसा नहीं।
Lost update: X=10 हो। T1 का लक्ष्य X←X+5 और T2 का X←2X है। Schedule r1(X=10),r2(X=10),w1(X=15),w2(X=20) का final X=20 है। Serial T1 फिर T2 से 30 और T2 फिर T1 से 25 मिलता। Concurrent answer दोनों से अलग है। यह numeric anomaly दिखाता है; general serializability proof के लिए chosen initial value की जगह dependencies देखें।
3. Conflicts और precedence graph
दो operations conflict करती हैं यदि वे अलग transactions की हों, एक ही item access करें और कम-से-कम एक write हो। इसलिए read–write, write–read तथा write–write conflict हैं; read–read नहीं। इस abstract model में अलग items की operations conflict नहीं करतीं। Same transaction का order program तय करता है; उसे अलग graph vertices के बीच edge नहीं बनाते।
हर transaction का एक vertex बनाएँ। Conflicting pair में Ti की operation पहले और Tj की बाद में हो तो Ti→Tj edge डालें। Schedule conflict serializable ठीक तब है जब graph acyclic हो। कोई भी topological order conflict-equivalent serial order देता है। कई topological orders संभव हैं। एक edge के कई कारण हों तो भी edge एक ही है। Directed cycle, जिसमें two-way pair भी शामिल है, conflict serializability रोकता है।
Acyclic उदाहरण: r1(A),w1(A),r2(A),w2(B),r3(B),w3(C)। A पर T1→T2 और B पर T2→T3 मिलता है; C पर intertransaction conflict नहीं। Chain का अकेला topological order T1,T2,T3 है। T1 तथा T3 में direct conflict न होने पर भी transitive order constraint है।
Cycle उदाहरण: r1(A),r2(B),w1(B),w2(A)। A पर पहली read और अंतिम write से T1→T2। B पर T2 की read और T1 की write से T2→T1। Cycle के कारण कोई conflict-equivalent serial order नहीं, भले हर transaction में सिर्फ दो operations हैं।
4. Conflict equivalence तथा safe swaps
दो schedules conflict equivalent हैं यदि उन्हीं transactions की वही operations हों और हर conflicting pair का order समान हो। अलग transactions की adjacent nonconflicting operations swap कर सकते हैं। ऐसे repeated safe swaps conflict-serializable schedule को serial रूप में बदल सकते हैं। अलग items पर reads swap करना यहाँ सुरक्षित है; एक item पर write और दूसरे transaction की read swap करना सुरक्षित नहीं।
एक initial state के लिए समान final state कमजोर condition है। X=0 पर arithmetic संयोग से बराबर answer दे सकती है, जबकि graph में cycle हो। Reads क्या देखती हैं, वह भी महत्वपूर्ण है। Conflict serializability schedule की structural property है।
5. View equivalence और blind writes
View equivalent schedules में initial-value read वैसी ही रहे; हर noninitial read को उसी specific transaction की write से value मिले; और हर item का final writer वही हो। ये read-from relations और final writer की conditions हैं, केवल numeric values के बराबर होने की नहीं। किसी serial schedule से view equivalent schedule, view serializable है।
हर conflict-serializable schedule view serializable है, लेकिन converse नहीं। बिना reads का उदाहरण w1(X),w2(X),w1(X) लें। Graph में T1→T2 और T2→T1 दोनों हैं, इसलिए conflict serializable नहीं। लेकिन serial T2 फिर T1 से view equivalent है: reads नहीं हैं और दोनों में final writer T1 है। T1 की writes blind हैं, क्योंकि T1 ने पहले X read नहीं किया। Conflict-serializable class के बाहर view-serializable schedules में blind writes जरूरी हैं; केवल blind write मौजूद होने से view serializability guarantee नहीं। General view-serializability test, conflict graph के polynomial test से कठिन है।
सावधानियाँ और अगला कदम
Serializability concurrent execution की equivalence है; recoverability commit/abort dependencies की सुरक्षा है। एक से दूसरा automatically नहीं मिलता। ACID isolation का अर्थ सभी real DBMS के default isolation levels serializable होना नहीं। Item-level assumptions स्पष्ट रखें; predicates और phantom rows को graph से छोड़कर उनके बारे में निष्कर्ष न दें। अगले पाठ में commit/abort events जोड़कर recoverability और recovery देखेंगे।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Item-level schedule में कौन-सा pair conflict है?
A. r1(X), r2(X) B. r1(X), w2(Y), X≠Y C. w1(X), r2(X) D. r1(X), w1(X)
उत्तर: C
A: Read–read में write नहीं।
B: यहाँ अलग items conflict नहीं।
C: अलग transactions, same item और write तीनों conditions हैं।
D: ये एक transaction की operations हैं।
P02. Precedence graph acyclic है। क्या निष्कर्ष है?
A. Schedule conflict serializable है B. Schedule अनिवार्यतः serial है C. Schedule अनिवार्यतः strict है D. ठीक एक serial order है
उत्तर: A
A: Topological order conflict-equivalent serial schedule देता है।
B: Interleaving allowed है।
C: Strictness uncommitted accesses की अलग property है।
D: DAG के कई topological orders हो सकते हैं।
P03. r1(A),r2(B),w1(B),w2(A) के graph में क्या है?
A. केवल T1→T2 B. केवल T2→T1 C. दोनों directions D. कोई edge नहीं
उत्तर: C
A: B से reverse edge भी है।
B: A से reverse edge भी है।
C: A से T1→T2; B से T2→T1।
D: दोनों items पर read–write conflicts हैं।
P04. बिना reads के w1(X),w2(X),w1(X) कैसा है?
A. केवल conflict serializable B. View serializable लेकिन conflict serializable नहीं C. दोनों नहीं D. केवल T1 फिर T2 से view equivalent
उत्तर: B
A: Graph में cycle है।
B: Final writer T1, serial T2 फिर T1 से मिलता है; reads नहीं।
C: View-equivalent serial order है।
D: T1 फिर T2 में final writer T2 होगा।
P05. कौन-सा guarantee failed transfer का केवल debit permanently बचने से रोकता है?
A. Atomicity B. कोई विशेष index type C. Read–read conflicts D. Unique topological order
उत्तर: A
A: Atomicity transfer effects को unit मानती है।
B: Index choice all-or-nothing behavior नहीं देती।
C: केवल reads यहाँ conflict नहीं।
D: Unique graph order rollback नहीं देता।
P06. Graph में केवल T1→T3 और T2→T3 हैं। कितने serial orders consistent हैं?
A. 1 B. 2 C. 3 D. 6
उत्तर: B
A: T1 तथा T2 का order बदल सकता है।
B: T1,T2,T3 तथा T2,T1,T3 दो orders हैं।
C: T3 दोनों के बाद जरूरी है।
D: सभी छह permutations में T3 last नहीं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Databases syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन