IAE Academy

GATE 2024 CS1 Q.46: solution and answer

GATE 2024 · CS1Q.46 · 2 marks · MSQ

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 ?

  1. (A)

  2. (B)

  3. (C)

  4. (D)

See the question in the paper

Answer and solution

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)

  1. 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 .

  2. Item : only touches it (, ), so there is no conflict.

  3. Item : only touches it (, ), so there is no conflict.

  4. 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 .

  5. Precedence graph: the only edge is . is isolated, so it can go anywhere in the order.

  6. Serial orders with before : , , . These are options B, D and C.

  7. 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

More Transactions questions