GATE CS 2022 Q.39: Transactions, Serializability and Concurrency Control

Let $R_i(z)$ and $W_i(z)$ denote read and write operations on a data element $z$ by a transaction $T_i$ , respectively. Consider the schedule $S$ with four transactions.

S: R_4(x) R_2(x) R_3(x) R_1(y) W_1(y) W_2(x) W_3(y) R_4(y)

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

$T_1 \to T_3 \to T_4 \to T_2$

$T_1 \to T_4 \to T_3 \to T_2$

$T_4 \to T_1 \to T_3 \to T_2$

$T_3 \to T_1 \to T_4 \to T_2$

Official answer and solution

Official answer: A
From: Official GATE 2022 answer key

Solution

Construct the conflict serializability precedence graph from conflicting read and write operations.

Given schedule $S: R_4(x) R_2(x) R_3(x) R_1(y) W_1(y) W_2(x) W_3(y) R_4(y)$ .

We identify conflicting operations (operations by different transactions on the same data item where at least one is a write) in order of appearance:

Conflicts on $x$ $x$ :
- $R_4(x)$ occurs before $W_2(x) \implies T_4 \to T_2$
- $R_3(x)$ occurs before $W_2(x) \implies T_3 \to T_2$
Conflicts on $y$ $y$ :
- $R_1(y)$ occurs before $W_3(y) \implies T_1 \to T_3$
- $W_1(y)$ occurs before $W_3(y) \implies T_1 \to T_3$
- $W_1(y)$ occurs before $R_4(y) \implies T_1 \to T_4$
- $W_3(y)$ occurs before $R_4(y) \implies T_3 \to T_4$

Summarizing the precedence edges:

$T_1 \to T_3$
$T_3 \to T_4$
$T_4 \to T_2$

This directed acyclic graph has a unique topological sort:

T_1 \to T_3 \to T_4 \to T_2

This matches Option (A).

Final answer

Option (A)

Common trap

Missing the conflict between $W_3(y)$ and $R_4(y)$ which enforces $T_3 \to T_4$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 39 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source