The GATE Grind

GATE 2014 CS (CS1) – Question 39

Databases · Transactions and Concurrency Control · 2 marks · Multiple choice

Three transactions read and write item x using rᵢ and wᵢ. Which schedule is conflict serializable?

  1. r₁(x); r₂(x); w₁(x); r₃(x); w₂(x)
  2. r₂(x); r₁(x); w₂(x); r₃(x); w₁(x)
  3. r₃(x); r₂(x); r₁(x); w₂(x); w₁(x)
  4. r₂(x); w₂(x); r₃(x); r₁(x); w₁(x)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) r₂(x); w₂(x); r₃(x); r₁(x); w₁(x)

Explanation

For D, T₂ reads and writes before the other transactions, and T₃ reads before T₁ writes. The precedence edges are T₂→T₃,T₂→T₁,T₃→T₁, forming an acyclic graph with order T₂,T₃,T₁. Hence **D** is conflict serializable. The other schedules generate opposing edges and cycles.