PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Serializability: Conflict Serializability and Precedence Graph (कॉनफ्लिक्ट सीरियलाइजेबिलिटी और प्रेसीडेंस ग्राफ (साइकिल डिटेक्शन)) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Conflict Serializability guarantees that a non-serial schedule can be transformed into an equivalent serial schedule purely by swapping adjacent non-conflicting operations. Using a directed Precedence Graph (Serialization Graph) built from R-W, W-R, and W-W conflicts on identical data items, a schedule is Conflict Serializable if and only if the graph contains NO cycles (is a DAG), testable in polynomial time.
अध्याय सार: कॉनफ्लिक्ट सीरियलाइजेबिलिटी (Conflict Serializability) यह बताती है कि क्या किसी नॉन-सीरियल शेड्यूल के बिना-टकराव वाले (Non-conflicting) आसन्न ऑपरेशन्स को आपस में बदलकर उसे किसी सीरियल शेड्यूल में बदला जा सकता है। समान डेटा आइटम पर R-W, W-R और W-W कन्फ्लिक्ट्स से बने प्रेसीडेंस ग्राफ (Precedence Graph) में यदि कोई चक्र (Cycle) न हो, तभी शेड्यूल कॉनफ्लिक्ट सीरियलाइजेबल होता है।
Serializability: Conflict Serializability and Precedence Graph: Detailed Notes & Architecture (कॉनफ्लिक्ट सीरियलाइजेबिलिटी और प्रेसीडेंस ग्राफ (साइकिल डिटेक्शन))
1. Definition of Conflicting Operations (3 Mandatory Conditions) (कॉनफ्लिक्टिंग ऑपरेशन्स की तीन अनिवार्य शर्तें)
[EN] Two operations Oi (from Ti) and Oj (from Tj) in a schedule are said to CONFLICT if and only if ALL THREE conditions hold simultaneously: (1) they belong to DIFFERENT transactions (i != j), (2) they operate on the EXACT SAME data item X, and (3) AT LEAST ONE of them is a WRITE operation. Therefore, only R-W, W-R, and W-W pairs on the same item X conflict; Read-Read (R-R) on the same item or any operations on distinct items (X vs Y) NEVER conflict and can always swap safely.
[HI] किसी शेड्यूल के दो ऑपरेशन्स Oi और Oj तभी आपस में टकराते (Conflict) हैं जब तीनों शर्तें पूरी हों: (1) वे अलग-अलग ट्रांजैक्शन्स (Ti और Tj) के हों, (2) वे एक ही डेटा आइटम X पर काम करें, और (3) उनमें से कम से कम एक WRITE ऑपरेशन हो। अर्थात समान आइटम पर केवल R-W, W-R व W-W कन्फ्लिक्ट होते हैं; R-R या अलग-अलग आइटम्स (X व Y) पर कोई कन्फ्लिक्ट नहीं होता।
2. Conflict Equivalence & Conflict Serializability (कॉनफ्लिक्ट इक्विवेलेंस और कॉनफ्लिक्ट सीरियलाइजेबिलिटी)
[EN] Two schedules S and S' over the same transactions are Conflict Equivalent if every pair of conflicting operations appears in the same relative order in both S and S' (equivalently, S' can be derived from S via valid swaps of adjacent non-conflicting operations). A schedule S is Conflict Serializable if it is conflict equivalent to at least one serial schedule—guaranteeing identical final database state and identical read return values.
[HI] दो शेड्यूल S और S' तब Conflict Equivalent कहलाते हैं जब उनके सभी कॉनफ्लिक्टिंग ऑपरेशन्स के जोड़ों का आपसी क्रम दोनों में समान हो (यानी गैर-टकराव वाले पड़ोसी ऑपरेशन्स को अदला-बदली करके एक से दूसरा बन सके)। यदि कोई नॉन-सीरियल शेड्यूल कम से कम एक सीरियल शेड्यूल के कॉनफ्लिक्ट-समतुल्य हो, तो उसे Conflict Serializable कहते हैं।
3. Precedence Graph (Serialization Graph) Construction & Cycle Test (प्रेसीडेंस ग्राफ निर्माण और साइकिल डिटेक्शन परीक्षण)
[EN] To test Conflict Serializability algorithmically, construct a directed Precedence Graph G = (V, E): create one vertex Ti in V for each transaction. For every conflicting pair on any item X where Ti's operation precedes Tj's operation—(1) Ri(X) before Wj(X), (2) Wi(X) before Rj(X), or (3) Wi(X) before Wj(X)—add a directed edge Ti -> Tj. Theorem: Schedule S is Conflict Serializable IF AND ONLY IF its Precedence Graph G has NO directed cycles (i.e., G is a Directed Acyclic Graph / DAG)!
[HI] प्रेसीडेंस ग्राफ G = (V, E) में प्रत्येक ट्रांजैक्शन एक नोड (Vertex) होता है। जब भी एक ही आइटम X पर Ti का ऑपरेशन Tj के ऑपरेशन से पहले आकर कन्फ्लिक्ट करे (Ri->Wj, Wi->Rj या Wi->Wj), तब Ti से Tj की ओर एक दिष्ट तीर (Edge Ti -> Tj) खींचा जाता है। नियम: शेड्यूल तभी Conflict Serializable होगा जब ग्राफ में कोई भी चक्र (Cycle) न हो!
4. Topological Ordering & Polynomial Complexity Advantage (टोपोलॉजिकल सॉर्ट से सीरियल क्रम और पॉलीनोमियल समय जटिलता)
[EN] When the Precedence Graph is acyclic, finding the equivalent serial schedule(s) simply computes any Topological Sort of the DAG (vertices with zero in-degree come first; multiple topological orders can exist). Crucially, cycle detection in a Precedence Graph takes polynomial time—O(n + e) via DFS once the O(m^2) or O(m) conflict scan builds the edges—making Conflict Serializability practical to enforce via Strict 2PL in real-world RDBMS engines.
[HI] यदि ग्राफ में कोई साइकिल नहीं है, तो ग्राफ का Topological Sort निकालकर तुरंत समतुल्य सीरियल क्रम (एक या अधिक) प्राप्त किया जा सकता है। प्रेसीडेंस ग्राफ में साइकिल की जांच पॉलीनोमियल समय में तेज़ी से हो जाती है, जबकि व्यू सीरियलाइजेबिलिटी NP-Complete है—यही कारण है कि वास्तविक DBMS Strict 2PL के माध्यम से कॉनफ्लिक्ट सीरियलाइजेबिलिटी लागू करते हैं।
Syntax, Formula & Technical Example (Serializability: Conflict Serializability and Precedence Graph)
-- Testing Schedule S: R1(A), W1(A), R2(A), W2(A), R2(B), W2(B), R1(B), W1(B)
-- Vertices: {T1, T2}
-- Conflicts on A: W1(A) -> R2(A), R1(A) -> W2(A), W1(A) -> W2(A) ==> Edge: T1 -> T2
-- Conflicts on B: W2(B) -> R1(B), R2(B) -> W1(B), W2(B) -> W1(B) ==> Edge: T2 -> T1
-- Precedence Graph has cycle: T1 -> T2 -> T1!
-- Verdict: NOT Conflict Serializable (Topological sort impossible)
Serializability: Conflict Serializability and Precedence Graph Quick Reference & Comparison Table
| Graph / Conflict Element | Rule / Meaning in Schedule | Exam Significance |
|---|---|---|
| Conflicting Pair | Different transactions, same item X, at least one WRITE | Includes R-W, W-R, and W-W; excludes R-R |
| Directed Edge Ti -> Tj | Conflict operation in Ti executes before Tj on same X | Forces Ti before Tj in any equivalent serial order |
| Cycle in Graph | Path Ti -> ... -> Ti exists (e.g., T1 -> T2 -> T1) | Proves schedule is NOT Conflict Serializable |
| Topological Sort | Linear ordering of DAG nodes honoring every edge | Produces exact equivalent serial schedule(s) |
Serializability: Conflict Serializability and Precedence Graph Top 20 Bilingual MCQs with Answers
Q1. Which three conditions must ALL hold for two operations Oi (of Ti) and Oj (of Tj) to be conflicting operations?
(दो ऑपरेशन्स Oi व Oj के आपस में कन्फ्लिक्टिंग (Conflicting) होने के लिए कौन सी तीन शर्तें एक साथ पूरी होनी चाहिए?)
(A) Different transactions, different items, both WRITEs
(B) Different transactions (i != j), same data item X, and at least one operation is a WRITE
(C) Different transactions, same item, both READs
(D) Same transaction, same item, both READs
Correct Answer: (B)
[EN] Two reads (R-R) never conflict, operations on separate items (X vs Y) never conflict, and intra-transaction steps keep fixed order.
[HI] अलग ट्रांजैक्शन (i ≠ j), एक ही डेटा आइटम X, और कम से कम एक WRITE ऑपरेशन होने पर ही कन्फ्लिक्ट बनता है।
Q2. Which operation pair on the SAME data item X NEVER conflicts?
(एक ही डेटा आइटम X पर कौन सा ऑपरेशन युग्म कभी कन्फ्लिक्ट नहीं करता?)
(A) W1(X) and W2(X) (Write-Write)
(B) W1(X) and R2(X) (Write-Read)
(C) R1(X) and W2(X) (Read-Write)
(D) R1(X) and R2(X) (Read-Read)
Correct Answer: (D)
[EN] Reading data does not alter X, so swapping adjacent R1(X) and R2(X) always preserves identical values.
[HI] पढ़ने से डेटा में कोई बदलाव नहीं होता, इसलिए समान आइटम पर R1(X) और R2(X) कभी कन्फ्लिक्ट नहीं करते।
Q3. A non-serial schedule S is Conflict Serializable IF AND ONLY IF its Precedence Graph:
(कोई नॉन-सीरियल शेड्यूल S तभी Conflict Serializable होता है जब उसका प्रेसीडेंस ग्राफ:)
(A) Contains NO directed cycles (is a Directed Acyclic Graph / DAG)
(B) Contains at least one self-loop on every vertex
(C) Has zero vertices
(D) Is a complete undirected bipartite graph
Correct Answer: (A)
[EN] Acyclicity in the Precedence Graph is both necessary and sufficient for Conflict Serializability.
[HI] प्रेसीडेंस ग्राफ का चक्र-रहित (Acyclic / DAG) होना Conflict Serializability की आवश्यक व पर्याप्त शर्त है।
Q4. In schedule S: R1(X), W2(X), R2(Y), W1(Y), what edges appear in the Precedence Graph and is S Conflict Serializable?
(शेड्यूल S: R1(X), W2(X), R2(Y), W1(Y) के प्रेसीडेंस ग्राफ में कौन से एज (Edges) बनेंगे और क्या यह Conflict Serializable है?)
(A) No edges at all; Conflict Serializable
(B) Only T2 -> T1; Conflict Serializable
(C) Edges T1 -> T2 (on X) and T2 -> T1 (on Y); Cycle exists -> NOT Conflict Serializable
(D) Only T1 -> T2; Conflict Serializable
Correct Answer: (C)
[EN] R1(X) precedes W2(X) creating T1 -> T2, while R2(Y) precedes W1(Y) creating T2 -> T1; the 2-cycle forbids conflict serializability.
[HI] X पर R1->W2 से T1->T2 और Y पर R2->W1 से T2->T1 एज बनने के कारण चक्र (Cycle) बन जाता है—अतः यह Conflict Serializable नहीं है।
Q5. In schedule S: R1(A), R2(A), W1(B), W2(B), what edges exist in the Precedence Graph?
(शेड्यूल S: R1(A), R2(A), W1(B), W2(B) के प्रेसीडेंस ग्राफ में कौन से दिष्ट एज बनते हैं?)
(A) No edges at all
(B) Both T1 -> T2 and T2 -> T1
(C) Only T2 -> T1
(D) Only T1 -> T2 (from W1(B) before W2(B)); S is Conflict Serializable as T1 -> T2
Correct Answer: (D)
[EN] R1(A) and R2(A) do NOT conflict (both reads); W1(B) precedes W2(B) giving the single edge T1 -> T2 (acyclic!).
[HI] R1(A) और R2(A) में कोई कन्फ्लिक्ट नहीं है; केवल B पर W1(B)->W2(B) से T1 -> T2 एज बनता है—चक्र न होने से यह Conflict Serializable है।
Q6. How is an equivalent Serial Schedule derived once a Precedence Graph is proven acyclic?
(प्रेसीडेंस ग्राफ को चक्र-रहित (Acyclic) सिद्ध करने के बाद समतुल्य सीरियल शेड्यूल किस एल्गोरिद्म से निकाला जाता है?)
(A) Breadth-First Spanning Tree from highest vertex ID
(B) Topological Sort of the Precedence Graph
(C) Dijkstra's Algorithm with negative weights
(D) Prim's Minimum Spanning Tree
Correct Answer: (B)
[EN] Topological sorting places every vertex Ti before Tj whenever an edge Ti -> Tj exists, yielding all valid conflict-equivalent serial orders.
[HI] चक्र-रहित प्रेसीडेंस ग्राफ का Topological Sort निकालने से वे सभी वैध सीरियल क्रम मिल जाते हैं जो शेड्यूल के समतुल्य हैं।
Q7. In Precedence Graph for S: R1(X), R2(Y), W1(X), W2(X), W2(Y), R3(X), W3(Y), determine the valid equivalent serial order.
(शेड्यूल S: R1(X), R2(Y), W1(X), W2(X), W2(Y), R3(X), W3(Y) के प्रेसीडेंस ग्राफ से सही समतुल्य सीरियल क्रम पहचानिए।)
(A) T3 -> T2 -> T1
(B) Not Conflict Serializable (Cycle exists)
(C) T2 -> T1 -> T3
(D) T1 -> T2 -> T3
Correct Answer: (D)
[EN] Conflicts on X yield T1 -> T2, T1 -> T3, and T2 -> T3; conflicts on Y yield T2 -> T3. The acyclic DAG uniquely forces the serial order T1 -> T2 -> T3.
[HI] X पर कन्फ्लिक्ट्स से T1 -> T2, T1 -> T3 व T2 -> T3 तथा Y पर T2 -> T3 एज बनते हैं। ग्राफ चक्र-रहित है और अद्वितीय सीरियल क्रम T1 -> T2 -> T3 देता है।
Q8. Consider schedule S: R1(X), W1(X), R2(Y), W2(Y), R3(X), W3(Y). Check edges in its Precedence Graph.
(शेड्यूल S: R1(X), W1(X), R2(Y), W2(Y), R3(X), W3(Y) के प्रेसीडेंस ग्राफ में कौन से एज बनेंगे?)
(A) T3 -> T1 and T3 -> T2
(B) T1 -> T3 (on X) and T2 -> T3 (on Y); Acyclic -> valid serial orders are T1->T2->T3 AND T2->T1->T3
(C) Cycle T1 -> T2 -> T3 -> T1
(D) Only T1 -> T2
Correct Answer: (B)
[EN] On X: R1/W1 precede R3 giving T1 -> T3. On Y: R2/W2 precede W3 giving T2 -> T3. Both T1 and T2 have in-degree 0, giving 2 serial orders!
[HI] X पर T1->T3 और Y पर T2->T3 एज बनते हैं; कोई साइकिल नहीं है, अतः T1->T2->T3 और T2->T1->T3 दोनों मान्य सीरियल क्रम हैं।
Q9. What is the time complexity class of testing Conflict Serializability using a Precedence Graph?
(प्रेसीडेंस ग्राफ द्वारा Conflict Serializability की जांच करने की समय जटिलता (Time Complexity) किस वर्ग की है?)
(A) Constant O(1) regardless of operations
(B) Polynomial Time (e.g., O(V + E) for cycle check after building conflict edges in O(m^2))
(C) NP-Complete (Exponential)
(D) Undecidable
Correct Answer: (B)
[EN] Unlike View Serializability (NP-complete), Precedence Graph construction and DFS cycle checking run strictly in polynomial time.
[HI] व्यू सीरियलाइजेबिलिटी (NP-Complete) के विपरीत कॉनफ्लिक्ट सीरियलाइजेबिलिटी पॉलीनोमियल समय में आसानी से जांची जा सकती है।
Q10. Which pair of adjacent operations in S = R1(A), W2(B), R2(A), W1(C) can be swapped WITHOUT changing conflict equivalence?
(S = R1(A), W2(B), R2(A), W1(C) में किन पड़ोसी ऑपरेशन्स को बिना परिणाम बदले आपस में बदला (Swap) जा सकता है?)
(A) Swapping always creates a Dirty Read
(B) ALL adjacent cross-transaction pairs here (A, B, C are different items, and R1(A) with R2(A) are both reads!)
(C) None can swap because i != j
(D) Only W2(B) and W1(C)
Correct Answer: (B)
[EN] Notice A, B, C are disjoint and R1(A), R2(A) are both reads—so ZERO conflicts exist across T1 and T2!
[HI] यहाँ A, B, C अलग आइटम्स हैं और A पर केवल रीड-रीड हो रहे हैं; कोई कन्फ्लिक्ट न होने से T1 व T2 के सभी पड़ोसी स्टेप्स आपस में बदल सकते हैं।
Q11. Which concurrency control protocol automatically guarantees that EVERY permitted schedule is Conflict Serializable?
(निम्नलिखित में से कौन सा कॉनकरेंसी कंट्रोल प्रोटोकॉल हमेशा यह सुनिश्चित करता है कि हर अनुमत शेड्यूल Conflict Serializable हो?)
(A) READ UNCOMMITTED with zero locks
(B) Timestamp-free random interleaving
(C) Plain Snapshot Isolation (without SSI)
(D) Two-Phase Locking (2PL / Strict 2PL)
Correct Answer: (D)
[EN] All 2PL schedules have Precedence Graph edges matching lock-point order, guaranteeing acyclicity (Conflict Serializability).
[HI] Two-Phase Locking (2PL / Strict 2PL) में लॉक-पॉइंट क्रम के कारण प्रेसीडेंस ग्राफ में कभी चक्र नहीं बनता और शेड्यूल हमेशा Conflict Serializable होता है।
Q12. In schedule S: R1(A), R2(A), W1(A), W2(A), why can you NOT swap R2(A) and W1(A) directly, and what does the Precedence Graph show?
(S: R1(A), R2(A), W1(A), W2(A) में R2(A) और W1(A) को क्यों नहीं बदल सकते, और प्रेसीडेंस ग्राफ क्या दिखाता है?)
(A) R2(A) and W1(A) are both reads
(B) Only T1 -> T2 exists so S is Conflict Serializable
(C) R2(A)->W1(A) creates T2 -> T1 while W1(A)->W2(A) creates T1 -> T2, forming a cycle (NOT Conflict Serializable)
(D) S is a Serial schedule
Correct Answer: (C)
[EN] Because R2(A) precedes W1(A) (T2->T1) and W1(A) precedes W2(A) (T1->T2), there is a cycle between T1 and T2.
[HI] यहाँ R2(A)->W1(A) से T2->T1 और W1(A)->W2(A) से T1->T2 एज बनकर चक्र बन जाता है—अतः यह Conflict Serializable नहीं है।
Q13. What does a Precedence Graph check if two transactions access only disjoint items, except T1 aborts mid-way—which transactions belong in the Conflict Graph?
(मानक थ्योरी में कन्फ्लिक्ट सीरियलाइजेबिलिटी के प्रेसीडेंस ग्राफ में किस श्रेणी के ट्रांजैक्शन्स के बीच एज बनाए जाते हैं?)
(A) Committed transactions (in a Complete Schedule / Committed Projection C(S)); aborted transactions' effects are rolled back
(B) Only read-only transactions with zero edges
(C) Only aborted transactions
(D) Only system backup jobs
Correct Answer: (A)
[EN] Serializability theory evaluates the Committed Projection C(S) of complete schedules because aborted transactions leave no permanent effects.
[HI] सीरियलाइजेबिलिटी सिद्धांत में कमिटेड प्रोजेक्शन C(S) के कमिटेड ट्रांजैक्शन्स के बीच ही प्रेसीडेंस ग्राफ देखा जाता है।
Q14. If a Precedence Graph over {T1, T2, T3} has edges T1 -> T2 and T2 -> T3 ONLY (no other edges), how many valid topological serial orders exist?
(यदि {T1, T2, T3} के प्रेसीडेंस ग्राफ में केवल T1 -> T2 और T2 -> T3 एज हों, तो कितने समतुल्य सीरियल क्रम संभव हैं?)
(A) Exactly 1 unique serial order: T1 -> T2 -> T3
(B) 6 serial orders
(C) 3 serial orders
(D) 2 serial orders
Correct Answer: (A)
[EN] Because the DAG forms a single linear chain T1 -> T2 -> T3, only one topological ordering exists.
[HI] यह एक रैखिक श्रृंखला है, इसलिए केवल 1 ही अद्वितीय सीरियल क्रम (T1 -> T2 -> T3) संभव है।
Q15. Which statement is FALSE (NOT true) regarding Conflict Serializability and Precedence Graphs?
(कॉनफ्लिक्ट सीरियलाइजेबिलिटी और प्रेसीडेंस ग्राफ के बारे में निम्नलिखित में से कौन सा कथन असत्य (FALSE) है?)
(A) Every Conflict Serializable schedule is also View Serializable
(B) A schedule is Conflict Serializable iff its Precedence Graph has no cycles
(C) Every schedule that is NOT Conflict Serializable is automatically inconsistent and NOT View Serializable either
(D) Read-Read operations on the same data item never create a Precedence Graph edge
Correct Answer: (C)
[EN] Some non-conflict-serializable schedules containing blind writes ARE still View Serializable and consistent!
[HI] कुछ ब्लाइंड राइट्स वाले शेड्यूल Conflict Serializable न होने पर भी View Serializable व सही हो सकते हैं—अतः पहला कथन असत्य है।
Q16. Analyze schedule S: R1(X), W2(X), W1(X), W3(X) in a Precedence Graph. What does the edge structure on X show?
(शेड्यूल S: R1(X), W2(X), W1(X), W3(X) के प्रेसीडेंस ग्राफ के बारे में क्या सही है?)
(A) Edges T1 -> T2, T2 -> T1, T1 -> T3, and T2 -> T3 appear -> Cycle T1 <-> T2 makes S NOT Conflict Serializable
(B) No cycle exists; serial order is T1 -> T2 -> T3
(C) All operations are non-conflicting
(D) Only T3 -> T1 exists
Correct Answer: (A)
[EN] Notice R1(X)->W2(X) creates T1->T2 and W2(X)->W1(X) creates T2->T1 (a cycle!), even though S happens to be View Serializable via blind writes.
[HI] X पर R1->W2 से T1->T2 और W2->W1 से T2->T1 चक्र बन जाता है—अतः यह Conflict Serializable नहीं है (यद्यपि ब्लाइंड राइट से View Serializable है)।
Q17. Within Serializability: Conflict Serializability and Precedence Graph, which graph / conflict element directly maps to: "Different transactions, same item X, at least one WRITE"?
(Serializability: Conflict Serializability and Precedence Graph में कौन सा Graph / Conflict Element सीधे "Different transactions, same item X, at least one WRITE" से संबंधित है?)
(A) Conflicting Pair
(B) Directed Edge Ti -> Tj
(C) Topological Sort
(D) Cycle in Graph
Correct Answer: (A)
[EN] In Serializability: Conflict Serializability and Precedence Graph, 'Conflicting Pair' handles 'Different transactions, same item X, at least one WRITE' (Includes R-W, W-R, and W-W; excludes R-R).
[HI] Serializability: Conflict Serializability and Precedence Graph में 'Conflicting Pair' का कार्य/विवरण 'Different transactions, same item X, at least one WRITE' (Includes R-W, W-R, and W-W; excludes R-R) है।
Q18. Which option accurately describes 'Directed Edge Ti -> Tj' in Serializability: Conflict Serializability and Precedence Graph?
(Serializability: Conflict Serializability and Precedence Graph के संदर्भ में 'Directed Edge Ti -> Tj' की सही विशेषता कौन सी है?)
(A) Conflict operation in Ti executes before Tj on same X
(B) Linear ordering of DAG nodes honoring every edge
(C) Path Ti -> ... -> Ti exists (e.g., T1 -> T2 -> T1)
(D) Different transactions, same item X, at least one WRITE
Correct Answer: (A)
[EN] 'Directed Edge Ti -> Tj' provides 'Conflict operation in Ti executes before Tj on same X' — key point: Forces Ti before Tj in any equivalent serial order.
[HI] 'Directed Edge Ti -> Tj' का मुख्य विवरण 'Conflict operation in Ti executes before Tj on same X' है (Forces Ti before Tj in any equivalent serial order)।
Q19. In Serializability: Conflict Serializability and Precedence Graph, identify the correct parameter for the specification: "Path Ti -> ... -> Ti exists (e.g., T1 -> T2 -> T1)".
(Serializability: Conflict Serializability and Precedence Graph में "Path Ti -> ... -> Ti exists (e.g., T1 -> T2 -> T1)" विवरण किस विकल्प के लिए सही है?)
(A) Cycle in Graph
(B) Conflicting Pair
(C) Directed Edge Ti -> Tj
(D) Topological Sort
Correct Answer: (A)
[EN] 'Cycle in Graph' corresponds to 'Path Ti -> ... -> Ti exists (e.g., T1 -> T2 -> T1)' (Proves schedule is NOT Conflict Serializable).
[HI] 'Cycle in Graph' का संबंध 'Path Ti -> ... -> Ti exists (e.g., T1 -> T2 -> T1)' (Proves schedule is NOT Conflict Serializable) से है।
Q20. Considering Serializability: Conflict Serializability and Precedence Graph, what key behavior defines 'Topological Sort'?
(Serializability: Conflict Serializability and Precedence Graph में 'Topological Sort' की मुख्य भूमिका या मान क्या है?)
(A) Different transactions, same item X, at least one WRITE
(B) Conflict operation in Ti executes before Tj on same X
(C) Linear ordering of DAG nodes honoring every edge
(D) Path Ti -> ... -> Ti exists (e.g., T1 -> T2 -> T1)
Correct Answer: (C)
[EN] 'Topological Sort' represents 'Linear ordering of DAG nodes honoring every edge' (Produces exact equivalent serial schedule(s)).
[HI] 'Topological Sort' का अर्थ/मान 'Linear ordering of DAG nodes honoring every edge' है (Produces exact equivalent serial schedule(s))।
Serializability: Conflict Serializability and Precedence Graph — Exam FAQs
Q1: Do Read-Read (R-R) operations on the same variable create an edge in a Precedence Graph?
क्या एक ही आइटम पर होने वाले दो Read ऑपरेशन्स (R1(X) व R2(X)) प्रेसीडेंस ग्राफ में कोई एज बनाते हैं?
[EN] No. Two reads never conflict because neither changes the value of X, so swapping them leaves all results identical and produces zero graph edges.
[HI] नहीं। दो रीड ऑपरेशन्स डेटा में कोई बदलाव नहीं करते, इसलिए वे कभी कन्फ्लिक्ट नहीं होते और ग्राफ में कोई तीर (Edge) नहीं बनाते।
Q2: If a schedule has a cycle in its Precedence Graph, is it guaranteed to corrupt the database?
यदि किसी शेड्यूल के प्रेसीडेंस ग्राफ में साइकिल हो, तो क्या वह डेटाबेस को हमेशा खराब ही करेगा?
[EN] Not necessarily always—it only proves the schedule is NOT Conflict Serializable. It might still be View Serializable (if blind writes exist) or accidentally yield consistent values for specific inputs.
[HI] हमेशा नहीं—साइकिल केवल यह सिद्ध करती है कि वह Conflict Serializable नहीं है; ब्लाइंड राइट्स होने पर वह तब भी View Serializable हो सकता है।
Q3: Can one Precedence Graph produce more than one valid serial schedule?
क्या एक ही प्रेसीडेंस ग्राफ से एक से अधिक समतुल्य सीरियल शेड्यूल निकल सकते हैं?
[EN] Yes! Any DAG that is not a total linear chain permits multiple valid topological sorts—for instance, two edges T1 -> T3 and T2 -> T3 allow both T1->T2->T3 and T2->T1->T3.
[HI] हाँ! जब भी ग्राफ में दो स्वतंत्र नोड्स हों (जैसे T1->T3 व T2->T3), तो एक से अधिक टोपोलॉजिकल क्रम (T1->T2->T3 व T2->T1->T3) संभव होते हैं।
Post a Comment
Post a Comment