GATE CS 2020 Q.47 (CS Q.37): Transactions, Serializability and Concurrency Control

Consider a schedule of transactions $T_1$ and $T_2$ given below.

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 & \text{RA} & & \text{RC} & & \text{WD} & & \text{WB} & \text{Commit} & & \\ \hline T_2 & & \text{RB} & \text{WB} & \text{RD} & & \text{WC} & & & \text{Commit} & \\ \hline \end{array}

Here, $\text{RX}$ stands for "Read(X)" and $\text{WX}$ stands for "Write(X)". Which one of the following schedules is conflict equivalent to the above schedule?

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 & & & & \text{RA} & \text{RC} & \text{WD} & \text{WB} & & \text{Commit} & \\ \hline T_2 & \text{RB} & \text{WB} & \text{RD} & & & & & \text{WC} & & \text{Commit} \\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 & \text{RA} & \text{RC} & \text{WD} & \text{WB} & & & & & \text{Commit} & \\ \hline T_2 & & & & & \text{RB} & \text{WB} & \text{RD} & \text{WC} & & \text{Commit} \\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 & \text{RA} & \text{RC} & & \text{WD} & \text{WB} & & & & \text{Commit} & \\ \hline T_2 & & & \text{RB} & & & \text{WB} & \text{RD} & \text{WC} & & \text{Commit} \\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 & \text{RA} & & & \text{RC} & \text{WD} & \text{WB} & & & \text{Commit} & \\ \hline T_2 & & \text{RB} & \text{WB} & & & & \text{WC} & \text{RD} & & \text{Commit} \\ \hline \end{array}

Official answer and solution

Official answer: A
From: Official GATE 2020 answer key

Solution

List all conflicting pairs of operations in the given schedule and match their order with the options.

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

In the given schedule:

Data item B: $T_2$ performs $R(B)$ then $W(B)$ . Later, $T_1$ performs $W(B)$ . Conflicting pairs: $R_2(B) \to W_1(B)$ and $W_2(B) \to W_1(B)$ (order: $T_2 \to T_1$ ).
Data item D: $T_2$ performs $R(D)$ . Later, $T_1$ performs $W(D)$ . Conflicting pair: $R_2(D) \to W_1(D)$ (order: $T_2 \to T_1$ ).
Data item C: $T_1$ performs $R(C)$ . Later, $T_2$ performs $W(C)$ . Conflicting pair: $R_1(C) \to W_2(C)$ (order: $T_1 \to T_2$ ).

Examine Option A:

$T_2$ executes $R(B), W(B), R(D)$ before $T_1$ executes $W(D), W(B)$ . Thus, $R_2(B) \to W_1(B)$ , $W_2(B) \to W_1(B)$ , and $R_2(D) \to W_1(D)$ are all preserved in the direction $T_2 \to T_1$ .
$T_1$ executes $R(C)$ before $T_2$ executes $W(C)$ . Thus, $R_1(C) \to W_2(C)$ is preserved in the direction $T_1 \to T_2$ .
Since every conflicting pair is executed in the exact same relative order, Option A is conflict equivalent to the given schedule.

Final answer

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

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 47 of 65, printed as CS Q.37
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