GATE CSE 2021 Set 2 | Question: 32

Question

​​​​​Let $S$ be the following schedule of operations of three transactions $T_1$, $T_2$ and $T_3$ in a relational database system:

$$R_2(Y), R_1(X), R_3(Z), R_1(Y)W_1(X), R_2(Z), W_2(Y), R_3(X), W_3(Z)$$

Consider the statements $P$ and $Q$ below:

• $P$: $S$ is conflict-serializable.
• $Q$: If $T_3$ commits before $T_1$ finishes, then $S$ is recoverable.

Which one of the following choices is correct?

• A. Both $P$ and $Q$ are true
• B. $P$ is true and $Q$ is false
• C. $P$ is false and $Q$ is true
• D. Both $P$ and $Q$ are false

Comments

@RushiK My bad. Yes, you are correct. It is not a dirty read. But there is a Lost Update Problem

---

@Abhrajyoti00 Now if T2 commits earlier than T1 then it will be recoverable right?

---

@RushiK if first T1 then T2 thenT3 commits then given shedule wlll be recoverable

 

Answer 1

$$\small \begin{array}{|c|c|c|}\hline T_{1} & T_{2} & T_{3} \\\hline  & R(Y) & \\ R(X) & &\\&& R(Z) \\ R(Y) & & \\ W(X) & & \\ & R(Z) & \\ & W(Y) & \\ & & R(X) \\ & & W(Z) \\ \hline\end{array}$$

• $T_{1} \rightarrow T_{2}$ due to $R_1(Y)$ being before $W_2(Y)$
• $T_{1} \rightarrow T_{3}$ due to $W_1(X)$ being before $R_3(X)$
• $T_{2} \rightarrow T_{3}$ due to $R_2(Z)$ is being $W_3(Z)$ in the schedule.

There are no other conflicts and the discovered conflicts are not forming the cycle.

Therefore, the given schedule is Conflict Serializable.

Statement $Q:$ If $T_{3}$ commits, before $T_{1}$ finishes, then $S$ is recoverable.

Schedule S is recoverable, if Tj creating the dirty read by reading the written data by Ti and Tj commits after Ti commits.

 By the above definition, $Q$ is wrong.

Option B is correct.

Comments

if T3 commits before T2 finishes then S will be recoverable right?

---

@Pranavpurkar

There are no dirty reads between T2 and T3. For a dirty read to happen, T2 must write a data item and T3 must read the same data item when T2 is in uncommitted state

But, there is a dirty read between T1 and T3 since T1 has written X and T2 has read the value of X that T1 wrote and T1 hasnt committed yet

If T3 commits before T1 then schedule is irrecoverable in case T1 aborts

So, in order to ensure recovery T3 must commit ONLY AFTER T1 commits

---

sk91

Thanks:)

Answer 2

B

Given Transactions written in tabular form,

$\hspace{125pt}\begin{array}{|c|c|c|}\hline T_1&T_2&T_3\\\hline &R(Y) \\R(X) \\&&R(Z) \\R(Y) \\W(X) \\&R(Z) \\&W(Y) \\&&R(X) \\&&W(Z) \\\hline \end{array}$

Precedence graph for the same,

                                                     

From the above, we can infer that the above schedule in conflict-serializable.

For commit operations, $T_1$ & $T_2$ must commit before $T_3$ which can be inferred from the above too.

Why since, if $T_3$ commits before $T_1$ and $T_1$ suddenly does an abort it would be as if $T_3$ was a successful transaction but in reality all it’s changes would be swept away by $T_1$’s rollback operations.

Comments

I think there should be an edge from T1 to T2 as well because R(y) in T1 is conflicting with W(y) in T2.

---

Yeah, I did a mistake… lol

Much obliged...