Consider the following read-write schedule over three transactions , , and , where the subscripts in the schedule indicate transaction IDs:
Which of the following transaction schedules is/are conflict equivalent to ?
- (A)
- (B)
- (C)
- (D)
Consider the following read-write schedule over three transactions , , and , where the subscripts in the schedule indicate transaction IDs:
Which of the following transaction schedules is/are conflict equivalent to ?
ANSWER
Options B, C and D are conflict equivalent to . They are , and .
Official answer: B, C, DSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)
Two operations conflict if they belong to different transactions, access the same item, and at least one is a write. A serial schedule is conflict equivalent to if it orders every conflicting pair the same way as .
Item : only touches it (, ), so there is no conflict.
Item : only touches it (, ), so there is no conflict.
Item : the operations in are , in that order. The conflicting pairs from different transactions are before , before and before . Every one of them puts before .
Precedence graph: the only edge is . is isolated, so it can go anywhere in the order.
Serial orders with before : , , . These are options B, D and C.
Option A, , puts before , which reverses the conflicts, so it is not conflict equivalent to .
KEY IDEA
Draw the precedence graph. Only item has conflicts between different transactions, and they give the single edge . Every serial order that respects that edge is conflict equivalent to , and can sit anywhere.
WATCH OUT FOR
Seeing appear first in and assuming it must come first in the serial order. only touches , so it conflicts with nobody and can go anywhere. The other slip is missing that before is also a conflict.
From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 9 Transactions questions, with notes