Consider the following read-write schedule π over three transactions π1,β¦
2024
Consider the following read-write schedule π over three transactions π1, π2, and π3, where the subscripts in the schedule indicate transaction IDs:
Β Β Β Β π: π1(π§); π€1(π§); π2(π₯); π3(π¦); π€3(π¦); π2(π¦); π€2(π₯); π€2(π¦);
Which of the following transaction schedules is/are conflict equivalent to π ?
- A.
\(T_1 T_2 T_3\) - B.
\(T_1 T_3 T_2\) - C.
\(T_3 T_2 T_1\) - D.
\(T_3 T_1 T_2\)
Attempted by 193 students.
Show answer & explanation
Correct answer: B, C, D
Key insight: build the precedence graph from conflicting operations and read off allowed serial orders.
Step 1: Find conflicts in the schedule.
All conflicts occur on item y: the third transaction writes y before the second transaction later reads and writes y. This creates a precedence edge from the third transaction to the second transaction.
The first transaction only accesses z, which no other transaction touches, so it has no conflicts with the others and is independent.
Step 2: Read off conflict-equivalent serial orders.
The only required ordering from conflicts is: the transaction that writes y must appear before the transaction that later reads/writes y.
Because the transaction that accesses z is independent, it can be placed anywhere.
Therefore the serial schedules that are conflict-equivalent to the given schedule are: T1, T3, T2 ; T3, T1, T2 ; and T3, T2, T1.
A video solution is available for this question β log in and enroll to watch it.