Project ForgeConsider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?
- Ar₁(x); r₂(x); w₁(x); r₃(x); w₂(x)
- Br₂(x); r₁(x); w₂(x); r₃(x); w₁(x)
- Cr₃(x); r₂(x); r₁(x); w₂(x); w₁(x)
- r₂(x); w₂(x); r₃(x); r₁(x); w₁(x)
Explanation
For schedule D (r₂(x); w₂(x); r₃(x); r₁(x); w₁(x)), build the precedence graph from conflicting operation pairs in execution order: w₂ before r₃ (write-read conflict) gives T2→T3; w₂ before r₁ and before w₁ gives T2→T1; r₃ before w₁ (read-write conflict) gives T3→T1. The resulting graph (T2→T3, T2→T1, T3→T1) is acyclic, so schedule D is conflict serializable (equivalent to the serial order T2, T3, T1). Working through A, B, and C similarly each produces a cycle in their precedence graphs, so none of them is conflict serializable.
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.