GATE CSE 2015 Set 3 | Question: 29

Question

Consider the partial Schedule $S$ involving two transactions $T1$ and $T2$. Only the $\textit{read}$ and the $\textit{write}$ operations have been shown. The $\textit{read}$ operation on data item $P$ is denoted by $\textit{read(P)}$ and $\textit{write}$ operation on data item $P$ is denoted by $\textit{write(P)}$.
$$\overset{\large{\text{Schedule S}}}{\begin{array}{c|ll}
\textbf{Time Instance}&    \rlap{\text{Transaction ID}}\\&\textbf{T1}&  \textbf{T2} \\\hline
1&     \text{read(A)}  \\ 
2&     \text{write(A)}\\   
3&     & \text{read(C)}     \\
4&     & \text{write(C)}     \\
5&     & \text{read(B)}  \\
6&     & \text{write(B)}     \\  
7&     & \text{read(A)}     \\
8&     & \text{commit}       \\
9&     \text{read(B)} \\
\end{array}}$$

Suppose that the transaction $T1$ fails immediately after time instance 9. Which of the following statements is correct?

• A. $T2$ must be aborted and then both $T1$ and $T2$ must be re-started to ensure transaction atomicity
• B. Schedule $S$ is non-recoverable and cannot ensure transaction atomicity
• C. Only $T2$ must be aborted and then re-started to ensure transaction atomicity
• D. Schedule $S$ is recoverable and can ensure transaction atomicity and nothing else needs to be done

Comments

$T_2$ Read the data $A$ from an uncommitted transaction ( Dirty Reading) $T_1$ and then committed.

Now the commit is causing the problem here if the user in future prints value of $A$ then $T_2$ will see the value written by $T_1$, which violates consistency and atomicity coz $T_1$ was rolled back and shouldn't have had any effect on other transaction ( violation of atomicity) and since value of $A$ is different for $T_2$ so DB might not remain consistent anymore.

---

ATOMICITY definition: either execute all the operations of all the transactions or execute none of any transaction if failure occurs.

But here as T2 is committed its changes are made in Database and as it’s doing dirty read from T1, T1 is failing nd rolling back its all operations but T2 has already made the changes so atomicity violated so B is True.

---

in option B how this is not follow Atomicity  here transaction T2 all opearation performed and T1all operation not performed ?

according to definition of Atomicity is either performed all operation or none operation of the transaction T1 and T2

@viral8702

Answer 1

The correct option is B.

Why A is not correct because it says abort transaction T2 and then redo all the operations .

But is there a guarantee that it will succeed this time ??(no maybe again T1 will fail).

Now as to why b is correct because as the other answer points out it is by definition an irrecoverable schedule now even if we start to undo the actions on by one(after t1 fails) in order to ensure transaction atomicity. Still we cannot undo a committed transaction. Hence, this schedule is unrecoverable by definition and also not atomic since it leaves the data base in an inconsistent state.

Comments

Yes , if T2 reads something which is written by  T1 then T2 should commit after T1.i.e. there should not be dirty read for a schedule for it to be recoverable.

"If transaction fails before first commit everything is recoverable, problem is after first commit."

This is also correct because we will undo all the operations in log file and will start doing everything from scratch if crash happens before first commit.$\implies$ recoverable schedule.

---

Without any recovery mechanism, how can a schedule ensure atomicity? So I think, restarting transactions won’t help in ensuring atomicity. Also, committed read cannot be recovered.

---

Sharing my thoughts on the answer to this question. Hope it helps somebody (and do point out the fallacies in my arguments if they seem wrong):-

1. A transaction can either be committed or aborted. Aborting a committed transaction violates the durability requirement of transactions, and committing an aborted transaction (may) violate the consistency requirement of transactions. This observation naturally rejects options \((A)\) and \((C)\).
2. Transaction \(T_2\) is reading \(A\) after an uncommitted \(write(A)\) produced by transaction \(T_1\). Also, \(T_2\) is the only transaction among the two who commits. So naturally, the schedule \(S\) is irrecoverable. This observation naturally rejects option \((D)\).
3. This leaves us option \((B)\) as the only surviving option (and a potential answer), but I am unsure about its second part, i.e., “cannot ensure transaction atomicity”. Recoverability can potentially violate the consistency requirement of transactions, but I’m clueless as to how it relates to the atomicity requirement of transactions. Nevertheless, this option is better then the rest (which are clearly wrong), and so we choose option \((B)\) as the correct option.

Answer 2

if transaction fails, atomicity requires effect of transaction to be undone. Durability states that once transaction commits, its change cannot be undone (without running another, compensating, transaction). 
Recoverable schedule: A schedules exactly where, for every set of transaction Ti and Tj. If Tj reads a data items previously written by Ti, then the commit operation of Ti precedes the commit operation of Tj. 
Aborting involves undoing the operations and redoing them since by the time stamp it is aborted.

Option (A): T2 must be aborted and then both T1 and T2 must be re-started to ensure transaction atomicity. It is incorrect because it says abort transaction T2 and then redo all the operations. But there is no gaurantee that it will succeed this time as again T1 may be fail.

Option(B): Schedule S is non-recoverable and cannot ensure transaction atomicity. Correct, it is by definition an irrecoverable schedule so now even if we start to undo the actions one by one(after t1 fails) in order to ensure transaction atomicity. Still we cannot undo a commited transaction. hence this schedule is irrecoverable by definition and also not atomic since it leaves the database in an inconsistent state. Simply dirty read so nonrecoverable.

Option (C): Only T2 must be aborted and then re-started to ensure transaction atomicity. It is incorrect because it says abort only transaction T2 and then redo all the T2 operations. But this is dirty read problem as it is reading the data item A which is written by T1 and T1 is not committed. Again it will be the dirty read problem. So incorrect.

Option (D): Schedule S is recoverable and can ensure transaction atomicity and nothing else needs to be done. Incorrect, it is clearly saying that schedule s is recoverable but it is irrecoverable because T2 read the data item A which is written by T1 and T1 failed and rollback, at the rollback T1 start undo all operations and modified the value of A with previous value but T2 is already committed so T2 can’t change the read value of A which was earlier taken from T1.

Answer 3

A. T2 must be aborted and then both T1 and T2 must be re-started to ensure transaction atomicity

     because according to atomicity "execute all the operations of the transaction  or none of them"

  B.Schedule S is non-recoverable and cannot ensure transaction atomicity because t1 is writing data item A which is read by t2 and t2 is committed before t1.... but here t1 fails and rollbacking of comitted transaction is not possible so its irrecoverable schedule
so option A&B is true

Comments

In transaction T2,  after reading A  no write action is performed.

Hence we are sure that incorrect A value is read but not used anywhere (and it does not effect B and C's value).

Therefore rolling back of T2 may not be required.

But i agree that spurious read has occured in T2.

Please explain how option D is eliminated

---

option D is eliminated because its clearly saying schedule s is recoverable which is irrecoverable because t2 read the data item which is written by t1 and t1 failed and rollback, at the  rollback t1 start undo all operations and modified the value of A with previous value but t2 committed t2 cant change that read value of A which taken from t1.

---

what exactly is the answer to this question then ?? A or B. since both cannot be correct ??

and also does aborting involve undoing the operations and redoing them since by the time stamp 9 the transaction T2 has already commited .

---

In option A...When to abort T2?

In option B...How to define atomicity??

please explain.!!

Answer 4

As per Korth

A recoverable schedule is one where, for each pair of transactions $T_i$ and $T_j$ such that $T_j$ reads a data item previously written by $T_i$, the commit operation of $T_i$ appears before the commit operation of $T_j$.

 

A cascadeless schedule is one where, for each pair of transactions $T_i$ and $T_j$ such that $T_j$ reads a data item previously written by $T_i$, the commit operation of $T_i$ appears before the read operation of $T_j$.
It is easy to verify that every cascadeless schedule is also recoverable.

 

We can simplify the definitions as:

A schedule is said to be recoverable if for every dirty read, the transaction who's object has been read "dirtily" commits before the transaction that performs the dirty read.

A schedule is said to be cascadeless if there's no dirty read.

 

Clearly, the schedule in the question is non-recoverable. Hence, Option B

Comments

You cannot choose the option based on first part of the option B