IAE Academy

GATE 2022 CS Q.39: solution and answer

GATE 2022 · CSQ.39 · 2 marks · MCQ

Let and denote read and write operations on a data element by a transaction , respectively. Consider the schedule with four transactions.

Which one of the following serial schedules is conflict equivalent to ?

  1. (A)

  2. (B)

  3. (C)

  4. (D)

See the question in the paper

Answer and solution

ANSWER

The serial schedule conflict equivalent to is , which is option (A).

Official answer: ASource: Official answer key, GATE 2022 CS (IIT Kharagpur)

  1. Two operations conflict if they belong to different transactions, access the same data item and at least one of them is a write. For each conflicting pair, draw an edge when 's operation comes first in . A serial schedule is conflict equivalent to exactly when it is a topological order of this precedence graph.

  2. Item : the operations in order are . The only write is . The reads and come before it and belong to other transactions, so and . is 's own operation and gives no edge.

  3. Item : the operations in order are .

  4. and both come before , and against is a read-write conflict. This gives ( against is a write-write conflict and gives the same edge).

  5. comes before , so . comes before , so .

  6. The precedence graph has edges . Every edge goes from a transaction in the list to a later one, so there is no cycle and is conflict serializable.

  7. Topological order: is the only transaction with no incoming edge, so it is first. After removing it, only has no incoming edge (it still needs nothing but ), so is second. Then (its predecessors are done), and is last. The order is forced, hence unique: .

  8. Check the other options against the edges. Option B puts before , violating . Option C puts before , violating . Option D puts before , violating . Only option (A) respects every edge.

KEY IDEA

Build the precedence graph from conflicting operations (different transactions, same item, at least one write). A serial schedule is conflict equivalent to exactly when it is a topological order of that graph, and here the order is unique.

WATCH OUT FOR

Reading as creating an edge with (both are 's), or missing the edge from before . That second slip makes and look interchangeable, so options B and D look plausible. Another slip is putting first because its read is the first operation, forgetting that comes after 's and 's writes.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 9 Transactions questions, with notes

More Transactions questions