GATE CS 2021 Set 1 Q.42 (CS Q.32): Transactions, Serializability and Concurrency Control

Let $r_i(z)$ and $w_i(z)$ denote read and write operations respectively on a data item $z$ by a transaction $T_i$ . Consider the following two schedules.

S_1: r_1(x) \; r_1(y) \; r_2(x) \; r_2(y) \; w_2(y) \; w_1(x)

S_2: r_1(x) \; r_2(x) \; r_2(y) \; w_2(y) \; r_1(y) \; w_1(x)

Which one of the following options is correct?

$S_1$ is conflict serializable, and $S_2$ is not conflict serializable.

$S_1$ is not conflict serializable, and $S_2$ is conflict serializable.

Both $S_1$ and $S_2$ are conflict serializable.

Neither $S_1$ nor $S_2$ is conflict serializable.

Official answer and solution

Official answer: B
From: Official GATE 2021 answer key

Solution

Construct the precedence (conflict) graph for each schedule and check for directed cycles.

Two operations conflict if they belong to different transactions, access the same data item, and at least one of them is a write.

Examine schedule $S_1: r_1(x) \; r_1(y) \; r_2(x) \; r_2(y) \; w_2(y) \; w_1(x)$ :

Operation $r_1(y)$ precedes $w_2(y)$ on item $y \implies T_1 \rightarrow T_2$ .
Operation $r_2(x)$ precedes $w_1(x)$ on item $x \implies T_2 \rightarrow T_1$ .
The precedence graph contains a cycle $T_1 \rightarrow T_2 \rightarrow T_1$ . Hence, $S_1$ is not conflict serializable.

Examine schedule $S_2: r_1(x) \; r_2(x) \; r_2(y) \; w_2(y) \; r_1(y) \; w_1(x)$ :

Operation $r_2(x)$ precedes $w_1(x)$ on item $x \implies T_2 \rightarrow T_1$ .
Operations $r_2(y)$ and $w_2(y)$ precede $r_1(y)$ on item $y \implies T_2 \rightarrow T_1$ .
There are no conflicts where an operation of $T_1$ precedes an operation of $T_2$ . The precedence graph contains only the edge $T_2 \rightarrow T_1$ , which is acyclic. Hence, $S_2$ is conflict serializable (equivalent to serial schedule $T_2, T_1$ ).

Thus, $S_1$ is not conflict serializable, and $S_2$ is conflict serializable (option B).

Final answer

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

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 42 of 65, printed as CS Q.32
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