Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1…

2009

Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below: 

T1 = R1[X] W1[X] W1[Y]
T2 = R2[X] R2[Y] W2[Y]
S1 = R1[X] R2[X] R2[Y] W1[X] W1[Y] W2[Y]
S2 = R1[X] R2[X] R2[Y] W1[X] W2[Y] W1[Y]
S3 = R1[X] W1[X] R2[X] W1[Y] R2[Y] W2[Y]
S4 = R2[X] R2[Y] R1[X] W1[X] W1[Y] W2[Y]

Which of the above schedules are conflict-serializable?

  1. A.

    S1 and S2

  2. B.

    S2 and S3

  3. C.

    S3 only

  4. D.

    S4 only

Attempted by 25 students.

Show answer & explanation

Correct answer: B

Key idea: Build the precedence (conflict) graph with nodes for T1 and T2. Add an edge Ti -> Tj when an action of Ti on a data item precedes a conflicting action of Tj on the same item. If the graph is acyclic the schedule is conflict-serializable.

  • S1 = R1[X] R2[X] R2[Y] W1[X] W1[Y] W2[Y] -> Conflicts: R2[X] before W1[X] and R2[Y] before W1[Y] give edges T2 -> T1; W1[Y] before W2[Y] gives edge T1 -> T2. Both edges exist, creating a cycle, so S1 is not conflict-serializable.

  • S2 = R1[X] R2[X] R2[Y] W1[X] W2[Y] W1[Y] -> Conflicts: R2[X] before W1[X] gives T2 -> T1; W2[Y] before W1[Y] gives T2 -> T1 as well. All conflict edges point T2 -> T1, no edge T1 -> T2, so the graph is acyclic. S2 is conflict-serializable and is equivalent to the serial order T2 before T1.

  • S3 = R1[X] W1[X] R2[X] W1[Y] R2[Y] W2[Y] -> Conflicts: W1[X] before R2[X] and W1[Y] before R2[Y] (and W1[Y] before W2[Y]) give edges T1 -> T2. All conflict edges point T1 -> T2, so the graph is acyclic. S3 is conflict-serializable and is equivalent to the serial order T1 before T2.

  • S4 = R2[X] R2[Y] R1[X] W1[X] W1[Y] W2[Y] -> Conflicts: R2[X] before W1[X] and R2[Y] before W1[Y] give T2 -> T1; W1[Y] before W2[Y] gives T1 -> T2. Both edges exist, creating a cycle, so S4 is not conflict-serializable.

Conclusion: S2 and S3 are conflict-serializable (S2 equivalent to serial order T2 then T1; S3 equivalent to serial order T1 then T2). S1 and S4 are not conflict-serializable because their precedence graphs contain cycles.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir