Serializability
Conflict Serializability MCWs for Gate Exam
Q1
Schedule: r1(A) r2(B) r1(B) w2(B) w1(A) c1 c2
Is this schedule conflict-serializable?
A. Yes; equivalent serial order T1 → T2
B. Yes; equivalent serial order T2 → T1
C. No; not conflict-serializable
D. Insufficient information (need timestamps)
✅ Answer: A
💡 Solution: Conflicts: r1(B) before w2(B) ⇒ edge T1 → T2? Actually r1(B) (T1) precedes w2(B) (T2) is a read–write conflict causing edge T1 → T2. w1(A) after r1(A) is same txn. No edge T2→T1. Graph has only T1→T2; acyclic → serial T1 then T2.
Q2
Schedule: r1(X) w2(X) r1(X) c1 c2
Conflict-serializable?
A. Yes; T2 → T1
B. Yes; T1 → T2
C. No
D. Equivalent to parallel execution
✅ Answer: A
💡 Solution: w2(X) after r1(X) is read–write conflict T1 → T2? Wait: r1(X) then w2(X) gives edge T1 → T2 (because T1 reads before T2 writes). But r1(X) after w2(X)? Here r1 then w2 then r1 — the second r1 occurs after w2 (same T1). There is also w2 before r1 (the second r1) causing T2 → T1. So both edges exist → cycle → C would be correct if we had both. But careful: both r1 are by T1; sequence: r1(X) [T1], w2(X) [T2], r1(X) [T1]. Conflicts: r1 (first) — w2 is R-W: edge T1→T2. w2 — r1 (second) is W-R: edge T2→T1. Cycle ⇒ C.
Correction: option C.
✅ Final Answer: C
Q3
Schedule: w1(A) r2(A) w2(A) c1 c2
Conflict-serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No
D. Equivalent to T2 only
✅ Answer: A
💡 Solution: w1(A) then r2(A) gives edge T1 → T2 (W-R). w2(A) after r2(A) is same T2 (R then W) internal. No edge T2→T1. Graph acyclic → serial T1 then T2.
Q4
Schedule: r1(A) r2(A) w1(A) w2(A) c1 c2
Serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No (cycle)
D. Yes; equivalent serial both ways
✅ Answer: C
💡 Solution: Conflicts: r1(A) before w2(A) gives T1→T2. r2(A) before w1(A) gives T2→T1. Both edges → cycle → not conflict-serializable.
Q5
Schedule: r1(X) w1(Y) r2(Y) w2(X) c1 c2
Which serial order (if any)?
A. T1 → T2
B. T2 → T1
C. Not conflict-serializable
D. Equivalent to both orders
✅ Answer: C
💡 Solution: Conflicts: w1(Y) before r2(Y) ⇒ T1→T2. w2(X) after r1(X) ⇒ r1(X) then w2(X) gives T1→T2 also. But check w2(X) (T2) may cause w2(X) after w1(Y) — no cross back edge. Wait need examine: r1(X) then w2(X) gives T1→T2 (R-W). r2(Y) after w1(Y) gives T1→T2. No T2→T1 edge; graph has single T1→T2 edge → acyclic → A.
Correction: Answer A.
✅ Final Answer: A
Q6
Schedule: w1(A) w2(B) r3(A) r3(B) c1 c2 c3
Is schedule conflict-serializable?
A. Yes; T1 → T3 → T2
B. Yes; T2 → T1 → T3
C. Yes; T1, T2 independent, T3 last (T1 → T3 and T2 → T3)
D. No
✅ Answer: C
💡 Solution: w1(A) then r3(A) ⇒ T1→T3. w2(B) then r3(B) ⇒ T2→T3. No conflicts between T1 and T2. Graph acyclic: T1 and T2 before T3; serial orders where T3 last and T1,T2 order interchangeable.
Q7
Schedule: r1(A) w2(A) w1(B) r2(B) c1 c2
Conflict-serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No
D. Equivalent to both orders
✅ Answer: C
💡 Solution: r1(A) before w2(A) ⇒ T1→T2. w1(B) before r2(B) ⇒ T1→T2 as well (both same direction). Wait both edges same T1→T2, so acyclic; schedule serializable T1→T2. But check w2(A) may conflict w1(B)? They are on different items A and B. So graph is T1→T2 only. So answer A.
Correction: Answer A.
✅ Final Answer: A
Q8
Schedule: w1(A) w2(A) c1 c2
Conflict-serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No (write-write conflict causes cycle)
D. Yes; both orders equivalent
✅ Answer: A
💡 Solution: w1 then w2 yields W-W conflict: edge T1→T2. No reverse edge. Acyclic → serial T1 then T2.
Q9
Schedule: r1(A) w2(A) r3(A) w1(A) c1 c2 c3
Conflict-serializable?
A. Yes; T2 → T1 → T3
B. Yes; T1 → T2 → T3
C. No
D. Yes; T1 and T3 independent then T2
✅ Answer: C
💡 Solution: r1(A) before w2(A) ⇒ T1→T2. w2(A) before r3(A) ⇒ T2→T3. w1(A) after w2(A)? w1(A) after w2(A) is W-W: w2→w1 gives T2→T1. So edges T1→T2, T2→T3, T2→T1 → cycle T1→T2→T1 → not serializable.
Q10
Schedule: r1(X) r2(X) w1(X) w2(Y) c1 c2
Conflict-serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No
D. Equivalent to T1 and T2 independent
✅ Answer: A
💡 Solution: r1(X) before w1(X) same txn. r2(X) before w1(X) yields T2→T1? Wait order: r1(X), r2(X), w1(X), w2(Y). Conflicts: r2(X) then w1(X) is R-W => T2→T1. r1(X) then w1(X) is same T1. w2(Y) unrelated. So T2→T1 only ⇒ serial T2 then T1. So answer B.
Correction: Answer B.
✅ Final Answer: B
Q11
Schedule: r1(A) w2(A) w2(B) r1(B) c1 c2
Conflict-serializable?
A. Yes; T2 → T1
B. Yes; T1 → T2
C. No
D. Both orders possible
✅ Answer: C
💡 Solution: r1(A) before w2(A) ⇒ T1→T2. w2(B) before r1(B) ⇒ T2→T1. Both edges ⇒ cycle → not conflict-serializable.
Q12
Schedule: w1(A) r2(A) w3(A) c1 c2 c3
Which ordering possible?
A. T1 → T2 → T3
B. T2 → T1 → T3
C. T1 → T3 → T2
D. Not conflict-serializable
✅ Answer: A
💡 Solution: w1 then r2 gives T1→T2. r2 before w3 gives T2→T3. Also w1 before w3 gives T1→T3. Graph edges T1→T2→T3 (and T1→T3) acyclic → serial T1,T2,T3.
Q13
Schedule: r1(A) r2(A) r3(A) c1 c2 c3
Conflict-serializable?
A. Yes; any serial order (no conflicts)
B. No
C. Only T1→T2→T3
D. Only T3→T2→T1
✅ Answer: A
💡 Solution: Only reads — no conflicts → all serial orders equivalent.
Q14
Schedule: w1(A) w2(B) w1(B) w2(A) c1 c2
Conflict-serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No (cycle)
D. Yes; T1 and T2 independent
✅ Answer: C
💡 Solution: w1(A) before w2(A)? Sequence: w1(A), w2(B), w1(B), w2(A). Conflicts: w1(A) before w2(A) ⇒ T1→T2. w2(B) before w1(B) ⇒ T2→T1. Cycle → not serializable.
Q15
Schedule: r1(X) w2(Y) r3(Z) c1 c2 c3
Conflict-serializable?
A. Yes; no conflicts (reads/writes on different items)
B. No
C. Yes; T1→T2→T3
D. Only T3→T2→T1
✅ Answer: A
💡 Solution: Operations access disjoint items X,Y,Z so no conflicts; any serial order valid.
Q16
Schedule: w1(A) r2(A) w2(B) r1(B) c1 c2
Conflict-serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No
D. Equivalent to T1 and T2 independent
✅ Answer: C
💡 Solution: w1(A) then r2(A) ⇒ T1→T2. w2(B) then r1(B) ⇒ T2→T1. Cycle exists → not serializable.
Q17
Schedule: r1(A) w1(A) r2(A) w2(A) c1 c2
Conflict-serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No
D. Both orders possible
✅ Answer: C
💡 Solution: r1 then w1 internal. w1 before r2 yields T1→T2. r2 before w2 is T2 internal. w2 after w1 yields T2→? Actually w1 then w2 gives T1→T2 only. But is there any reverse edge? r2 occurs after w1 only, so T1→T2. No T2→T1; graph acyclic → serial T1→T2. Wait check: r1(A), w1(A), r2(A), w2(A). r2 reads after w1 (W-R) ⇒ edge T1→T2? W-R is T1→T2. w2 (T2) after w1 (T1) is W-W T1→T2 still. No reverse edge. So serializable. So answer A.
Correction: Answer A.
✅ Final Answer: A
Q18
Schedule: w1(A) r2(A) r3(A) w2(B) w3(B) c1 c2 c3
Possible serial order?
A. T1 → T2 → T3
B. T1 → T3 → T2
C. Not serializable
D. Any order ok
✅ Answer: B
💡 Solution: w1(A) then r2(A), r3(A) ⇒ T1→T2 and T1→T3. w2(B) before w3(B) ⇒ T2→T3. So edges T1→T2→T3 gives T1→T2→T3. Wait we had w2 before w3 making T2→T3; so serial T1,T2,T3 (A). But check r3(A) occurs before w3(B) etc — no back edges. So A is correct.
Correction: Answer A.
✅ Final Answer: A
Q19
Schedule: r1(A) w2(A) w3(A) r1(A) c1 c2 c3
Serializable?
A. Yes; cycle-free (T1→T2→T3→T1?)
B. No
C. Yes; T2 → T3 → T1
D. Yes; T1 → T3 → T2
✅ Answer: B
💡 Solution: r1 then w2 gives T1→T2; w2 then w3 gives T2→T3; w3 then r1 (second r1) gives T3→T1. Cycle T1→T2→T3→T1 ⇒ not serializable.
Q20
Schedule: r1(A) r2(A) w2(A) w1(B) r3(B) c1 c2 c3
Conflict-serializable?
A. Yes; T1 → T2 → T3
B. Yes; T2 → T1 → T3
C. No
D. Yes; T1 and T3 before T2
✅ Answer: B
💡 Solution: r1(A) before w2(A) ⇒ T1→T2. r2(A) before w2(A) same T2 internal. w1(B) before r3(B) ⇒ T1→T3. Wait edges T1→T2 and T1→T3 -> implies T1 before both. But r2(A) and w1(B) are independent. Which order? There is no edge T2→T1. So T1 must be before T2 and T3. But w2(A) (T2) after r2 gives T2 after T1 only. Final graph edges: T1→T2 and T1→T3. Acyclic → possible serial T1 then T2 and T3 in any order. Option A lists T1→T2→T3 which is valid. Option B lists T2→T1->T3 invalid. So answer A.
Correction: Answer A.
✅ Final Answer: A
Q21
Schedule: w1(A) r2(A) w2(B) r3(B) w3(A) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. Yes; T2 → T3 → T1
C. No
D. Yes; T1 → T3 → T2
✅ Answer: C
💡 Solution: w1→r2 gives T1→T2. w2→r3 gives T2→T3. w3(A) after w1(A) gives w1 before w3 ⇒ T1→T3. Also w3(A) (T3) after r2(A) ??? r2 earlier; r2 then w3 gives T2→T3 as well. So graph edges T1→T2→T3 and T1→T3, acyclic actually => serial T1,T2,T3. Wait check conflict w3(A) after w1(A) gives T1→T3. No reverse edges. So schedule serializable T1→T2→T3 (A).
Correction: Answer A.
✅ Final Answer: A
Q22
Schedule: r1(A) w2(A) r3(A) w3(B) w2(B) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. Yes; T2 → T3 → T1
C. No
D. Yes; T3 → T2 → T1
✅ Answer: C
💡 Solution: r1 then w2 ⇒ T1→T2. w2(B) after w3(B) yields w3 before w2 gives T3→T2. Also w3(B) after r3(A) unrelated. r3(A) after w2? sequence r1, w2, r3: w2 before r3 gives T2→T3. So edges: T1→T2, T2→T3, T3→T2? Wait T3→T2 from w3 before w2 (w3 then w2) actually w3(B) occurs before w2(B)? But schedule shows w3(B) then w2(B) — so w3 before w2 ⇒ T3→T2. That plus T2→T3 (from w2 before r3 then r3 prior? Let’s recalc: order: r1(A), w2(A), r3(A), w3(B), w2(B). Conflicts: r1(A) -> w2(A) T1→T2. w2(A) -> r3(A) is W-R giving T2→T3. w3(B) before w2(B) gives T3→T2. So T2→T3 and T3→T2 form cycle → not serializable. So C.
Q23
Schedule: w1(A) r2(A) w2(B) r1(B) w3(C) c1 c2 c3
Conflict-serializable?
A. Yes; T1 → T2 → T3
B. Yes; T2 → T1 → T3
C. No
D. Yes; T1 and T2 before T3, order between T1/T2 determined by conflicts
✅ Answer: A
💡 Solution: w1→r2 => T1→T2. w2(B) before r1(B) => T2→T1 creating cycle? Sequence w2(B) then r1(B) gives T2→T1. Combined with T1→T2 ⇒ cycle → not serializable. Wait check order: w1(A), r2(A), w2(B), r1(B). So w1 before r2 gives T1→T2. w2 before r1 gives T2→T1. That is cycle => not serializable. So answer C.
Correction: Answer C.
✅ Final Answer: C
Q24
Schedule: r1(A) r2(B) w1(B) w2(A) c1 c2
Serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No
D. Both orders possible
✅ Answer: C
💡 Solution: r1(A) then w2(A) ⇒ T1→T2. r2(B) then w1(B) ⇒ T2→T1. Cycle -> not serializable.
Q25
Schedule: w1(A) w2(B) w3(A) w2(A) c1 c2 c3
Conflict-serializable?
A. Yes; T1 → T3 → T2
B. No (cycle involving T2 and T3)
C. Yes; T2 → T1 → T3
D. Yes; T3 → T1 → T2
✅ Answer: B
💡 Solution: Conflicts: w1(A) before w3(A) ⇒ T1→T3. w3(A) before w2(A) ⇒ T3→T2. w2(B) doesn’t affect A. But also w2(A) after w1? w1(A) before w2(A) yields T1→T2. Edges T1→T3→T2 and T1→T2 produce no cycle by themselves (T1→T3, T3→T2, T1→T2). This is acyclic: T1 then T3 then T2. Wait check w2(A) is from T2; sequence w2(B) earlier then w3(A) then w2(A). Need to carefully parse original schedule: w1(A), w2(B), w3(A), w2(A). Edges: w1(A) before w3(A): T1→T3. w3(A) before w2(A): T3→T2. w1(A) before w2(A): T1→T2. Graph T1→T3→T2 and T1→T2, no cycles. So serializable T1→T3→T2. So answer A.
Correction: Answer A.
✅ Final Answer: A
Precedence Graph & Advanced Conflict Analysis — Q26–Q45)
Q26
Schedule: r1(A) w2(A) r3(A) w2(B) w3(B) c1 c2 c3
Is this schedule conflict-serializable?
A. Yes; serial order T1 → T2 → T3
B. Yes; serial order T1 → T3 → T2
C. No (cycle)
D. Yes; T2 before T1 and T3
✅ Answer: B
💡 Solution: Conflicts: r1(A) before w2(A) ⇒ T1→T2. w2(A) before r3(A) ⇒ T2→T3. w3(B) after w2(B)? w2(B) before w3(B) gives T2→T3. So edges: T1→T2→T3. That implies serial T1,T2,T3 (option A). But note r3(A) occurs before w3(B) — no reverse edges. Final acyclic chain T1→T2→T3 → A.
(Final) ✅ Answer: A
Q27
Schedule: w1(X) r2(X) w3(X) r1(X) c1 c2 c3
Conflict-serializable?
A. Yes; T1 → T2 → T3
B. Yes; T3 → T2 → T1
C. No
D. Yes; T2 → T1 → T3
✅ Answer: C
💡 Solution: w1→r2 gives T1→T2. r2 before w3 gives T2→T3. w3 before r1 (second r1) gives T3→T1. Cycle T1→T2→T3→T1 ⇒ not serializable.
Q28
Schedule: r1(A) r2(A) w2(A) r3(B) w1(B) c1 c2 c3
Is it conflict-serializable?
A. Yes; T1 → T2 → T3
B. Yes; T3 → T1 → T2
C. No
D. Yes; T1 and T3 before T2
✅ Answer: D
💡 Solution: r1(A) before w2(A) ⇒ T1→T2. r3(B) before w1(B) ⇒ T3→T1. So edges T3→T1→T2; acyclic ⇒ serial T3,T1,T2 (so T1 and T3 are before T2 with T3 before T1). Option D says T1 and T3 before T2 (not specific order) — acceptable; safest is serial T3→T1→T2.
Q29
Schedule: w1(A) w2(A) r3(A) c1 c2 c3
Conflict-serializable?
A. Yes; T1 → T2 → T3
B. Yes; T2 → T1 → T3
C. Yes; T1 → T3 → T2
D. No
✅ Answer: A
💡 Solution: w1 then w2 gives T1→T2. w2 then r3 gives T2→T3. Combined chain T1→T2→T3, acyclic.
Q30
Schedule: r1(X) w2(Y) w3(X) r2(X) c1 c2 c3
Conflict-serializable?
A. Yes; T1 → T3 → T2
B. Yes; T3 → T1 → T2
C. No
D. Yes; T1 and T3 independent of T2
✅ Answer: C
💡 Solution: r1(X) before w3(X) gives T1→T3. w3(X) before r2(X) gives T3→T2. r1(X) and r2(X) have no direct conflict before w3? Also w2(Y) not relevant. But is there T2→T1? r2(X) after w3(X) doesn’t produce T2→T1. No cycle — graph T1→T3→T2 is acyclic — serial T1,T3,T2. So correct answer A.
(Final) ✅ Answer: A
Q31
Schedule: r1(A) w2(A) w1(B) r2(B) w3(C) c1 c2 c3
Conflict-serializable?
A. Yes; T1 → T2 → T3
B. No
C. Yes; T2 → T1 → T3
D. Yes; T1 and T2 independent, T3 last
✅ Answer: C
💡 Solution: r1(A) before w2(A) ⇒ T1→T2. w1(B) before r2(B) ⇒ T1→T2 as well — same direction. w3(C) independent. So T1→T2 and T3 independent → serial T1 then T2 then T3 (A). But we must check: w1(B) by T1 before r2(B) by T2 gives T1→T2; no edge T2→T1. So answer A (T1→T2→T3).
(Final) ✅ Answer: A
Q32
Schedule: w1(A) r2(A) w2(A) r3(A) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. No
C. Yes; T3 → T2 → T1
D. Yes; T1 and T3 before T2
✅ Answer: B
💡 Solution: w1→r2 gives T1→T2. w2 (T2) before r3 gives T2→T3. w2 after w1 also gives T1→T2. Additionally, r3 after w2 could cause T3→? No reverse edge, but check r3(A) after w1(A) initial? Sequence w1,r2,w2,r3 — edges T1→T2 and T2→T3: acyclic ⇒ serial T1,T2,T3. So actually schedule is serializable: A.
(Final) ✅ Answer: A
Q33
Schedule: r1(A) w2(B) r3(B) w1(B) w3(A) c1 c2 c3
Conflict-serializable?
A. Yes; T2 → T1 → T3
B. Yes; T1 → T3 → T2
C. No (cycle)
D. Yes; T3 → T1 → T2
✅ Answer: C
💡 Solution: r3(B) before w1(B) gives T3→T1. w2(B) before r3(B) gives T2→T3. r1(A) before w3(A) gives T1→T3. Edges: T2→T3→T1→T3 produces cycle T3→T1→T3? Also T1→T3 and T3→T1? If both present, cycle. Conclude not serializable.
Q34
Schedule: w1(A) w2(B) r3(B) r3(A) c1 c2 c3
Conflict-serializable?
A. Yes; T1 → T2 → T3
B. Yes; T2 → T1 → T3
C. No
D. Yes; T1 and T2 before T3 (order between T1/T2 free)
✅ Answer: D
💡 Solution: w1(A) and w2(B) both before r3’s reads produce T1→T3 and T2→T3. No conflicts between T1 and T2 → both before T3; order between them free.
Q35
Schedule: r1(A) w2(A) w3(A) w2(B) w3(B) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. No
C. Yes; T1 → T3 → T2
D. Yes; T2 → T3 → T1
✅ Answer: B
💡 Solution: r1→w2 gives T1→T2. w2 before w3 on A gives T2→T3. w3 before w2 on B? w2(B) before w3(B) gives T2→T3 again. No reverse edge T3→T2. Edges produce T1→T2→T3 acyclic => serializable. So A.
(Final) ✅ Answer: A
Q36
Schedule: r1(X) r2(Y) r3(Z) c1 c2 c3
Serializable?
A. Yes; any order (no conflicts)
B. No
C. Only T1→T2→T3
D. Only T3→T2→T1
✅ Answer: A
💡 Solution: All operations are reads on distinct items — no conflicts.
Q37
Schedule: w1(A) r2(A) w3(A) w2(B) r1(B) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. No (cycle)
C. Yes; T2 → T1 → T3
D. Yes; T1 → T3 → T2
✅ Answer: B
💡 Solution: w1→r2 ⇒ T1→T2. r1(B) after w2(B) gives T2→T1. So T1→T2 and T2→T1 ⇒ cycle (regardless of T3) → not serializable.
Q38
Schedule: w1(A) w2(A) w3(B) r1(B) r2(B) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. Yes; T3 → T1 → T2
C. No
D. Yes; T1 and T2 before T3
✅ Answer: D
💡 Solution: w3(B) before r1(B)/r2(B) gives T3→T1 and T3→T2 (because w3 then reads by T1/T2). w1 and w2 conflict (W-W) giving T1→T2 (w1 before w2). Combining: edges: T1→T2 and T3→T1,T3→T2 => T3 must be before T1 and T2, and T1 before T2 → serial T3,T1,T2. So D.
Q39
Schedule: r1(A) w2(B) r3(B) w1(B) w2(A) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. No
C. Yes; T2 → T3 → T1
D. Yes; T3 → T2 → T1
✅ Answer: B
💡 Solution: r3(B) before w1(B) gives T3→T1. w2(B) before r3(B) gives T2→T3. w2(A) after r1(A) gives T1→T2. So edges T1→T2→T3→T1 cycle → not serializable.
Q40
Schedule: w1(A) w2(B) r3(A) r3(B) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. Yes; T2 → T1 → T3
C. No
D. Yes; T1 and T2 before T3 (either order)
✅ Answer: D
💡 Solution: w1 before r3(A) ⇒ T1→T3. w2 before r3(B) ⇒ T2→T3. No conflicts between T1 and T2 → both must precede T3; order between them free.
Q41
Schedule: r1(A) w2(A) w3(A) w1(A) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. No
C. Yes; T2 → T3 → T1
D. Yes; T3 → T2 → T1
✅ Answer: B
💡 Solution: r1→w2 gives T1→T2. w2→w3 gives T2→T3. w3→w1 (w1 after w3) gives T3→T1. Cycle T1→T2→T3→T1 → not serializable.
Q42
Schedule: r1(X) w2(X) r1(Y) w2(Y) c1 c2
Is it conflict-serializable?
A. Yes; T1 → T2
B. Yes; T2 → T1
C. No
D. Equivalent to concurrent execution with no serial order
✅ Answer: A
💡 Solution: r1(X) before w2(X) gives T1→T2. r1(Y) before w2(Y) gives T1→T2 again. No reverse edge. Acyclic.
Q43
Schedule: w1(A) r2(B) w2(A) r1(B) c1 c2
Serializable?
A. Yes; T1 → T2
B. No (cycle)
C. Yes; T2 → T1
D. Yes; both orders possible
✅ Answer: B
💡 Solution: w1(A) before w2(A) gives T1→T2. r2(B) before r1(B) and w2? r2(B) before r1(B) is R-R (no conflict). r1(B) after r2(B) no write—But w2(A) before r1(B) doesn’t create cross-edge. However w2(A) (T2) before r1(B) (T1) does not conflict on B. Re-evaluate: operations on A: w1 then w2 => T1→T2. On B: r2(B) then r1(B) are reads — no conflict. So graph is T1→T2 only → serial T1,T2 ⇒ answer A.
(Final) ✅ Answer: A
Q44
Schedule: r1(A) r2(A) w2(A) w3(A) r1(A) c1 c2 c3
Serializable?
A. Yes; T1 → T2 → T3
B. No
C. Yes; T2 → T3 → T1
D. Yes;T1 and T2 before T3
✅ Answer: B
💡 Solution: r1 first then w2 gives T1→T2. w2 before w3 gives T2→T3. w3 before r1 (second r1) gives T3→T1. Cycle → not serializable.
Q45
Schedule: w1(A) r2(A) w3(A) r4(A) w2(B) r1(B) c1 c2 c3 c4
Is it conflict-serializable?
A. Yes; T1 → T2 → T3 → T4
B. No (cycle exists)
C. Yes; T3 → T4 → T1 → T2
D. Yes; T1 and T3 before T2 and T4
✅ Answer: B
💡 Solution: w1→r2 ⇒ T1→T2. r2 before w3 ⇒ T2→T3. w3 before r1 (if r1 after) yields T3→T1. Thus cycle T1→T2→T3→T1 → not serializable.
Part 3 — View Serializability, Recoverability, Cascading Aborts, Timestamps (Q51–Q75)
Q51
Schedule: w1(A,5) w2(A,5) r3(A) c1 c2 c3 (values shown for clarity).
Is this schedule view-serializable?
A. Yes, equivalent to T1→T2→T3
B. Yes, equivalent to T2→T1→T3
C. No (not view-serializable)
D. Cannot determine
✅ Answer: A
💡 Solution: Final write on A is from T2 (value 5) — both w1 and w2 wrote same value but last writer is T2; read by T3 reads value 5; order T1 then T2 then T3 preserves same read-from and final-writes → view-serializable.
Q52
Schedule: r1(A) w2(A,10) r3(A) w1(B,7) c1 c2 c3.
Is it view-serializable?
A. Yes
B. No
C. Only conflict-serializable
D. Only recoverable
✅ Answer: A
💡 Solution: T1 read A (initial), T2 writes A=10, T3 reads A (could read initial or 10 depending), but you can find equivalent serial order T1→T2→T3 preserving reads/writes → view-serializable.
Q53
Consider schedule where a transaction reads a value written by an uncommitted transaction that later aborts. This schedule is:
A. Cascadeless
B. Non-recoverable
C. Cascading-abort prone (not cascadeless)
D. Always strict
✅ Answer: C
💡 Solution: Reading from uncommitted data causes cascading aborts if the writer aborts; schedule is not cascadeless.
Q54
If every transaction reads only committed values and writes are deferred until commit, the schedule class is:
A. Strict
B. Recoverable but not strict
C. Cascadeless
D. Non-recoverable
✅ Answer: C
💡 Solution: Deferring writes until commit prevents reading uncommitted data ⇒ cascadeless (and also usually recoverable).
Q55
Schedule: w1(A) r2(A) abort1 r2(A) c2 (T1 aborts after T2 already read). Is schedule recoverable?
A. Yes
B. No (non-recoverable)
C. Cascadeless
D. View-serializable only
✅ Answer: B
💡 Solution: T2 read uncommitted value from T1; T1 aborts but T2 commits later ⇒ T2 depends on aborted data → non-recoverable.
Q56
Which property requires that if Tj reads a value written by Ti, then Ti must commit before Tj commits?
A. Recoverability
B. Strictness
C. Conflict-serializability
D. View-serializability
✅ Answer: A
💡 Solution: Recoverability enforces commit order matching read-from dependencies to avoid committing on aborted data.
Q57
Schedule: w1(A) c1 w2(A) c2 — is this strict?
A. Yes
B. No
C. Depends on other items
D. Only cascadeless
✅ Answer: A
💡 Solution: Strictness requires that a transaction cannot read or write an item modified by an uncommitted transaction; here writes happen and are committed before next writes — no read of uncommitted data, so it can be strict (also recoverable).
Q58
Timestamp-ordering: Ti has TS=5, Tj has TS=10. If Tj wants to write item X whose last-read-timestamp = 12 (from a later transaction), then strict timestamp protocol: the write should be:
A. Allowed and proceed
B. Rejected and Tj aborts (write-too-old)
C. Delayed until commit
D. Converted to read-only
✅ Answer: B
💡 Solution: If write’s TS < last-read-timestamp, it violates timestamp ordering (write-too-old) → abort to preserve timestamp order.
Q59
Which schedule property ensures no cascading aborts even if transactions abort?
A. Cascadeless schedules
B. Non-recoverable schedules
C. View-serializable only
D. Conflict-serializable only
✅ Answer: A
💡 Solution: Cascadeless ensures transactions read only committed values, so abort of one transaction cannot force others to abort.
Q60
If a schedule is strict, which of the following is true?
A. It is cascadeless and recoverable
B. It may be non-recoverable
C. It is always non-serializable
D. It allows reading uncommitted data
✅ Answer: A
💡 Solution: Strictness implies writes lock items until commit, preventing reads of uncommitted data → cascadeless and recoverable.
Q61
Schedule: r1(A) w2(A) c2 c1 — T1 read A then T2 wrote and committed, and T1 later commits. Is the schedule recoverable?
A. Yes
B. No (non-recoverable)
C. Cascadeless
D. View-serializable only
✅ Answer: A
💡 Solution: T1 read before T2’s write — no read-from uncommitted relation; commit order not violating dependencies ⇒ recoverable.
Q62
A transaction T reads values only after the writer committed; but its write is visible to others before T commits. This schedule is:
A. Cascadeless but not strict
B. Strict
C. Non-recoverable
D. View-serializable only
✅ Answer: A
💡 Solution: Reading only committed values ensures cascadeless; but making writes visible before commit breaks strictness.
Q63
Which of the following is a necessary condition for view-serializability but not sufficient for conflict-serializability?
A. Same final-write results and same read-from relations
B. No conflicting operations at all
C. All reads from initial DB state
D. No cycles in precedence graph
✅ Answer: A
💡 Solution: View-serializability requires preserving final-writes and read-from relations; conflict-serializability is stricter (based on pairwise conflicts).
Q64
Schedule is view-equivalent to some serial schedule but not conflict-equivalent. Which is true?
A. It is view-serializable but not conflict-serializable
B. It is conflict-serializable but not view-serializable
C. Neither serializable
D. Both serializable always
✅ Answer: A
💡 Solution: View-serializability is more general — some schedules are view-serializable yet fail conflict-serializability.
Q65
Given timestamps: TS(T1)=20, TS(T2)=30. Strict timestamp-ordering allows which sequence?
A. T1’s operations may be delayed or aborted if they conflict with later timestamps
B. T1 can override writes of T2 with higher TS
C. T2 must abort if T1 later writes older value
D. None
✅ Answer: A
💡 Solution: Lower-timestamp transactions cannot perform operations that violate timestamp rules; operations may be aborted or delayed to preserve order.
Q66
Schedule: r1(A) w2(A) c2 r1(B) c1 — T1 read A, T2 wrote and committed, then T1 read B and committed. Is schedule recoverable?
A. No (T1 read uncommitted earlier)
B. Yes (no T1 committed after reading uncommitted)
C. Non-recoverable because T1 committed before T2
D. Depends on B’s state
✅ Answer: B
💡 Solution: T1 read A before T2 wrote it — T1 did not read uncommitted data from T2; commit order fine → recoverable.
Q67
Which is true about cascading aborts?
A. They occur when transactions read uncommitted data and a writer aborts.
B. They happen only under strict schedules.
C. They are prevented by non-recoverable schedules.
D. They are unrelated to read-from relationships.
✅ Answer: A
💡 Solution: Reading uncommitted data ties transactions to writer’s fate, causing potential cascading aborts.
Q68
In strict 2PL (two-phase locking) policy, when are locks released?
A. Only at transaction commit or abort
B. Immediately after each operation
C. After a fixed timeout
D. When requested by client
✅ Answer: A
💡 Solution: Strict 2PL holds exclusive locks until commit/abort → enforces strictness and prevents dirty reads.
Q69
Schedule: w1(A) r2(A) c1 abort2 (T2 aborts). Is T1 affected?
A. No — T1 committed before T2 aborted, so T1 safe
B. Yes — T1 must abort too (cascading)
C. Depends on read-from relations
D. T1 becomes non-recoverable
✅ Answer: A
💡 Solution: T1 committed before T2 aborted — T2 reading T1’s committed data is fine; abort of reader does not force writer to abort.
Q70
Which schedule property is violated if some transaction commits after reading an uncommitted value written by an aborting transaction?
A. Recoverability
B. Strictness remains satisfied
C. Cascadelessness holds
D. View-serializability violated
✅ Answer: A
💡 Solution: Reading from uncommitted values and then committing while writer aborts breaks recoverability.
Q71
Under Thomas’ write rule (timestamp protocol), a late write with smaller timestamp than the last write is:
A. Ignored (discarded) without abort
B. Causes writing transaction to abort always
C. Converted to read-only
D. Applied after committing writer
✅ Answer: A
💡 Solution: Thomas’ rule allows safely ignoring obsolete writes (write-too-old) instead of aborting.
Q72
If schedule S is conflict-serializable, then:
A. S is also view-serializable
B. S may not be view-serializable
C. S must be non-recoverable
D. S cannot be strict
✅ Answer: A
💡 Solution: Conflict-serializable ⇒ view-serializable (conflict-serializability is stronger).
Q73
Transaction T2 reads A written by T1 (T1 uncommitted), and T1 later commits. This scenario is:
A. Recoverable if T2 commits after T1
B. Non-recoverable regardless
C. Cascadeless always
D. Strictness violated
✅ Answer: A
💡 Solution: If T1 commits before T2 commits, the read-from dependency is safe and schedule is recoverable.
Q74
In timestamp ordering, if a transaction Ti’s read request on item X has TS(Ti) < lastWriteTS(X), then:
A. Ti must be aborted (read-too-old)
B. Read is allowed and value returned
C. Ti’s timestamp increased automatically
D. LastWriteTS is lowered
✅ Answer: A
💡 Solution: Reading older than last write violates timestamp order → transaction aborts (read-too-old).
Q75
Which property guarantees that transactions see only committed values and therefore avoids cascading aborts and dirty reads?
A. Strict schedules (or strict 2PL)
B. Only timestamp ordering
C. Conflict-serializability alone
D. View-serializability alone
✅ Answer: A
💡 Solution: Strict scheduling (holding writes until commit) prevents uncommitted data exposure, avoiding cascading aborts and dirty reads.
Excellent ✅
Here’s Part 4 (Q76 – Q100) — 25 fully original, plagiarism-free Serializability MCQs for the GATE Database Systems syllabus, focused on advanced timestamp ordering, hybrid locking/timestamp cases, recoverability, and tricky view-serializability analysis.
Solutions are brief (2–3 lines) but complete enough for quick GATE revision.
🔹 Part 4 — Advanced Serializability (Q76 – Q100)
Q76
Schedule: w1(A) w3(B) r2(A) r2(B) c1 c2 c3.
Is this conflict-serializable?
A. Yes, equivalent to T1→T3→T2
B. Yes, equivalent to T3→T1→T2
C. No
D. Cannot determine
✅ Answer: A
💡 Solution: T2 reads both A,B after writes of T1,T3; precedence T1,T3 → T2 gives acyclic graph ⇒ conflict-serializable.
Q77
Schedule: r1(X) w2(X) r3(X) w1(Y) c2 c3 c1.
Is it view-serializable?
A. Yes
B. No
C. Only conflict-serializable
D. Non-recoverable
✅ Answer: A
💡 Solution: Equivalent serial order T1→T2→T3 preserves read-from and final-write on Y ⇒ view-serializable.
Q78
Which statement is false for a strict schedule?
A. It is always recoverable
B. It avoids cascading aborts
C. Uncommitted writes may be read
D. Locks are held till commit
✅ Answer: C
💡 Solution: Strict schedules never allow reading uncommitted writes.
Q79
In a recoverable schedule, which can still occur?
A. Dirty read
B. Cascading abort
C. Non-recoverable commit
D. Strict violation
✅ Answer: B
💡 Solution: Recoverable allows cascading aborts (still possible) though avoids non-recoverable commits.
Q80
Timestamp protocol: TS(T1)=40, TS(T2)=60. T2 wants to read X whose lastWriteTS=50.
A. Allowed
B. Rejected (read-too-new)
C. Aborted immediately
D. Delayed until T1 commits
✅ Answer: A
💡 Solution: Read’s TS > lastWriteTS ⇒ consistent with order; allowed.
Q81
Under Thomas’ Write Rule, obsolete write detection avoids:
A. Unnecessary aborts
B. Conflict serializability
C. Recoverability
D. Cascading aborts
✅ Answer: A
💡 Solution: Thomas’ rule skips obsolete writes instead of aborting ⇒ reduces aborts.
Q82
Schedule: r1(A) r2(A) w2(A) c1 c2. Is this recoverable?
A. Yes
B. No
C. Strict only
D. Cascadeless
✅ Answer: A
💡 Solution: T1 commits before reading uncommitted data ⇒ recoverable.
Q83
Which schedule property ensures both recoverability and no cascading aborts?
A. Strictness
B. View-serializability
C. Non-recoverability
D. None
✅ Answer: A
💡 Solution: Strict schedules guarantee both recoverable and cascadeless behavior.
Q84
If every transaction in schedule S reads only initial database values, S is:
A. Conflict-serializable
B. View-serializable
C. Both A and B
D. Non-serializable
✅ Answer: C
💡 Solution: No inter-transaction dependency ⇒ trivially serializable under both definitions.
Q85
For two transactions, absence of RW or WR conflicts implies schedule is:
A. Conflict-serializable
B. Non-serializable
C. Cascadeless
D. Strict
✅ Answer: A
💡 Solution: No conflicting pairs ⇒ precedence graph acyclic ⇒ conflict-serializable.
Q86
Schedule: r1(A) w2(A) w1(A) c2 c1.
Is it conflict-serializable?
A. Yes
B. No
C. View-serializable only
D. Cascadeless
✅ Answer: B
💡 Solution: Graph edges T1→T2 (r-w) and T2→T1 (w-w) form cycle ⇒ not conflict-serializable.
Q87
Under timestamp ordering, if Ti wants to write X with TS(Ti)=45 and lastReadTS(X)=50:
A. Ti aborted (write-too-old)
B. Allowed
C. Ignored safely
D. Postponed
✅ Answer: A
💡 Solution: Write timestamp < last read ⇒ violates order → abort.
Q88
If schedule is strict ⇒ recoverable ⇒ ?
A. Cascadeless
B. View-serializable
C. Conflict-serializable
D. Non-recoverable
✅ Answer: A
💡 Solution: Strict ⟹ cascadeless ⟹ recoverable hierarchy holds.
Q89
A view-serializable schedule may not be:
A. Conflict-serializable
B. Recoverable
C. Strict
D. View-equivalent
✅ Answer: A
💡 Solution: View-serializability ⊃ Conflict-serializability set.
Q90
Schedule: w1(A) r2(A) w2(A) c1 c2. Is it recoverable?
A. Yes
B. No
C. Cascadeless
D. Strict
✅ Answer: A
💡 Solution: T2 reads after T1 wrote; T1 commits before T2 ⇒ recoverable.
Q91
Which one is not necessary for recoverability?
A. Reader commits after writer commits
B. Writer commits before reader commits
C. All writers must commit before any readers commit
D. Reader must abort if writer aborts
✅ Answer: C
💡 Solution: Only relevant writers must commit before dependent readers; not all.
Q92
Schedule: r1(X) w1(X) r2(X) abort1 c2. This schedule is:
A. Non-recoverable
B. Cascadeless
C. Strict
D. View-serializable
✅ Answer: A
💡 Solution: T2 reads uncommitted X from T1 which aborts ⇒ non-recoverable.
Q93
Which is true about two-phase locking (2PL) and serializability?
A. Every 2PL schedule is conflict-serializable
B. Every serializable schedule follows 2PL
C. 2PL allows non-serializable schedules
D. 2PL never guarantees recoverability
✅ Answer: A
💡 Solution: 2PL ensures conflict-serializability by construction.
Q94
In timestamp ordering, if a transaction Ti is aborted due to a read-too-old conflict, what happens?
A. Ti restarted with new timestamp
B. Schedule rolled back fully
C. Item locked permanently
D. Writer aborted too
✅ Answer: A
💡 Solution: Aborted transaction restarts with new TS to maintain order.
Q95
Schedule: r1(A) r2(A) w2(A) w1(A) c2 c1. Conflict-serializable?
A. Yes
B. No
C. View-serializable only
D. Cascadeless
✅ Answer: B
💡 Solution: Edges T1→T2 (r-w) and T2→T1 (w-w) → cycle ⇒ not conflict-serializable.
Q96
Which is always true about strict 2PL?
A. Avoids deadlocks
B. Avoids cascading aborts
C. Allows non-recoverable schedules
D. Non-serializable
✅ Answer: B
💡 Solution: Strict 2PL holds locks till commit ⇒ avoids dirty reads/aborts cascade.
Q97
Schedule: r1(A) w2(A) r3(A) c2 c3 c1. Is it view-serializable?
A. Yes
B. No
C. Only conflict-serializable
D. Strict only
✅ Answer: A
💡 Solution: Equivalent to T1→T2→T3 order; dependencies preserved ⇒ view-serializable.
Q98
If precedence graph has a cycle, schedule is:
A. Not conflict-serializable
B. View-serializable
C. Strict
D. Cascadeless
✅ Answer: A
💡 Solution: Cycle implies conflicting dependency loop ⇒ not conflict-serializable.
Q99
Recoverable schedule guarantees:
A. No dirty reads
B. No transaction commits before the one whose data it read commits
C. Serial equivalence
D. Absence of deadlocks
✅ Answer: B
💡 Solution: Commit ordering preserves read-from dependencies ⇒ recoverable.
Q100
If schedule is conflict-serializable but not strict, which can still happen?
A. Cascading aborts
B. Dirty writes
C. Non-recoverable commits
D. View-inconsistency
✅ Answer: A
💡 Solution: Conflict-serializable ensures serial order but doesn’t forbid reading uncommitted data ⇒ cascading aborts possible.
About the Author
