GATE CSE 2016 | Set 2 | Question: 51

Question

Consider the following database schedule with two transactions $T_{1}$ and $T_{2}$.

$S= r_{2}\left(X\right); r_{1}\left(X\right); r_{2} \left(Y\right); w_{1} \left(X\right); r_{1} \left(Y\right); w_{2} \left(X\right); a_{1}; a_{2}$

Where $r_{i} (Z)$ denotes a read operation by transaction $T_{i}$ on a variable $Z$, $w_{i}(Z)$ denotes a write operation by $T_{i}$ on a variable $Z$ and $a_{i}$ denotes an abort by transaction $T_{i}$.

Which one of the following statements about the above schedule is TRUE?

• A. $S$ is non-recoverable.
• B. $S$ is recoverable, but has a cascading abort.
• C. $S$ does not have a cascading abort.
• D. $S$ is strict.

Comments

Note : If there is no dirty read ,then it is always recoverable

---

Recoverable? ✅ — No dirty read exists anywhere. Both abort independently.

Cascading abort? ❌ — T2 never read T1's written X. a₁ doesn't force a₂.

Strict? ❌ — w₂(X) happens at step 6, but T1's w₁(X) is still uncommitted (aborts only at step 7). Strictness violated.

---

References : Navathe 

Given schedule is Cascadeless schedule  not cascadeless abort ..

Answer 1

Answer is C

$${\begin{array}{|c|c|}\hline
\textbf{T1}&    \textbf{T2} \\\hline  & \text{R(x)} \\
     \text{R(x)} \\   &      \text{R(y)} \\    
\text{W(x)}&     \\ \text{R(y)} \\ & \text{W(x)} \\ \text{a1} \\ &      \text{a2} \\     \hline
\end{array}}$$

(A): This is not possible, because we have no dirty read ! No dirty read $\implies$ Recoverable

(B): This is not possible, because of no Dirty read ! No dirty read $\implies$ No cascading aborts !

(D): This is not true, because we can see clearly in image that after W1(X) before T1 commit or aborts T2 does W2(x) !

C is only option remaining !

Comments

there is no dirty read i.e there is no read in T2 after the write in T1 and vice versa therefore no dirty read so recoverable now
lets say there is read in T2 after write in T1 then we its not recoverable but...if in T1 after write we commit the T1 and then there is read in T2 then its recoverable cause then its not dirty read.
DIRTY READ: when transaction reads an item written by an uncommitted transaction we call it dirty read.

so to ans your que we are not saying it is recoverable becuz it does not have commit rather becuz it does not have dirty read and if there is dirty read then it doesnt matter if commit is mentioned or not we call it not recoverable
 

---

last point you mentioned is not true it depends which transaction commits first then we decide recoverable or non recoverable

---

Remember guys: if W1(x) is not there, then this schedule become STRICT also.

Answer 2

option (c). No cascading rollback. Because no dirty read.

Comments

This is dirty read in schedule

---

Yes  cascadless schedule allows only write before commit or abort

Strict doesn't allows read or write before commit 

https://cs.stackexchange.com/questions/42924/what-is-the-difference-between-strict-schedule-and-cascadeless-schedule

---

If the order in which the dirty read is happening, and in the same order commit operation is also performed then that is also a recoverable schedule.

So you can say that dirty read always need not lead non- recoverable schedule. Order of commit operation also matters if given.

Answer 3

A) False because at a1 it aborts and a2 is still to be executed, therefore it's recoverable!  It would only be non recoverable if the abort happens after either T1 or  T2 commits. 

B) To check for cascading aborts - First check if it's Cascadeless b/c Any Schedule which is NOT cascadeless is cascading aborts.

Now, Necessary condition for Cascadeless is - Producer - Consumer  ie (W-R) conflict but there's no PC (W-R conflict) in here. Therefore it's Cascadeless and a Cascadeless schedule can never be Cascading aborts!

Note: Every cascadeless schedule is recoverable always! Foolproof option A)

C) True as reason as B) 

D) False as before T2 commits, T1 is reading as well as writing! 

Comments

I think your explanation for option A is false, you said " It would only be non recoverable if the abort happens after either T1 or  T2 commits."  
Assume even if T1 commits , T2 has read the value which has not been updated yet, so it will write its value, I think it will overwrite T1 value , if after that abort of T2 occurs ,we have to rollback and if it starts executing again it will read different value because of updated value by T1 commit.
please clarify if it is correct or not ?

 

---

 Any Schedule which is NOT cascadeless is cascading aborts.

vice versa it is true? or not 

 

 

Answer 4

BEST ANSWER

Answer 5

option c is correct the above schedule does not have cascading aborts.

Cascading aborts occurs only when there is a write by $T_i$ on data item x followed by read operation on  the same data item by $T_j$

but here $T_1$ performs $w_1$(x) which is no where followed by $r_2$(x).

See carefully  $w_1$(x) is followed by  $w_2$(x). write operation by two transactions on same data item is allowed in cascadeless schedules.

Hence the above schedule is cascadeless.

Answer 6

I think the answer is B )

because the transaction is recoverable and it's cascading oborts because if T1 transaction faliure causes T2 transaction to Roll it back

Comments

It is a GATE question...C is correct. Along with that, it has no cascading abort

---

how did you check for cascading aborts ?

---

@akshayaK by checking if there is any dirty read or not.