Recoverability in DBMS

Overview

In the Database Management Systems there are multiple transactions that are happening parallelly. Some of these transactions are dependent on each other while some are independent. If one transaction fails in the dependent transactions, can we minimize its impact on other transactions as well? Recoverability in DBMS is an area that deals with such kind of issues. In this article, we will discuss about recoverable and irrecoverable schedules, followed by cascadeless and cascade rollback recoverable schedules.

Recoverable Schedule

Suppose Aarnav has $10$ lakhs in his account and his friend Jaanvi who has $1$ lakh in her account, needs $2$ lakhs more to buy a new gaming laptop. The laptop is a limited edition, and once she places the order, she cannot cancel it. The money can be paid only within $30$ minutes of placing the order. She texted Aarnav to transfer her $2$ lakhs and placed an order for the $3$ lakh gaming laptop.

Recoverable Schedule example Fig 1

Transaction in their bank account Recoverable Schedule example Fig 2

If Aarnav doesn't transfer the money to Jaanvi, Jaanvi may get in trouble since she can't cancel the order and she does not have money. Hence, a wise decision would have been to place an order when she receives $2$ lakhs from Aarnav.

Recoverable Schedule example Fig 3

Therefore, if Jaanvi places the order once she receives the money from Aarnav can be considered a recoverable schedule since she has the option whether to place the order or not.

A schedule is a recoverable schedule if each transaction present in the schedule commits only after all the transactions from which it has read the values are executed/committed entirely. If $T_1$ and $T_2$ are two transactions and $T_2$ reads data from $T_1$ then $T_2$ should commit only after $T_1$ commits. Mathematically,

$(T_1 \rightarrow T_2\ Reads) \implies (T_1\ Commits \rightarrow T_2 \ Commits)$

Irrecoverable Schedule

A schedule is said to be irrecoverable if the transaction commits before the transaction from which it has read the data commits. Mathematically,

$(T_1 \rightarrow T_2\ Reads) \implies (T_2\ Commits \rightarrow T_1 \ Commits)$

If Jaanvi puts the order before the money arrives, then it can be considered as an irrecoverable schedule since she can't cancel the order now.

Let us see one more example for better understanding. Consider two transactions $T_1$ and $T_2$ in the schedule. $T_1$ initially reads and write the data but is not committed. $T_2$ starts, it reads the data updated by $T_1$ and commits. Now, if $T_1$ fails, both $T_1$ and $T_2$ needs to rollback and start again. This is an irrecoverable schedule since $T_1$ can rollback as it was not committed but $T_2$ can't since it is committed.

Recoverable Schedule example Fig 5

Cascade Recoverable Rollback Schedule

Let us first understand what "cascading" means by an example. Cascade generally means that successive events depend on the occurrence of previous events. For example, water falls through the $n^{th}$ stair after flowing through the $(n-1)^{th}$ stair. It is falling from the $(n-1)^{th}$ stair after traversing from the $(n-2)^{th}$ stair. Hence all the stairs form a cascade. The water would not fall through the successive cascade of stairs, if it doesn't flows through any one of the previous stair.

Cascade Recoverable Rollback Schedule

If the transactions form a cascade without any commits as shown below, then it is called a cascade recoverable schedule. In this type of schedule, if the previous transaction fails then the following transactions needs to be aborted and start again since there would be inconsistency in the data.

Recoverable Schedule example Fig 6

Cascadeless Recoverable Rollback Schedule

Abhijeet, Bhaswat, and Clara are sitting in the exam hall one behind another. Clara is cheating from Bhaswat and Bhaswat is cheating from Abhijeet. In what order should they submit the answer sheet to get equal marks ?

Abhijeet should submit the paper first, followed by Bhaswat and Clara. Otherwise, say Abhijeet found the mistake in his answer after Bhaswat and Clara submitted the answer sheet. So he can update the answer and submit. Abhijeet will now get more marks since Bhaswat and Clara can't update their solution as they have already submitted the answer sheet.

Hence, in a cascadeless recoverable schedule, a transaction should only read the data from another transaction in the schedule once the previous schedule is being committed.

Recoverable Schedule example Fig 7

The above diagram depicts a cascadeless recoverable schedule. There are $4$ transactions, $T_1,\ T_2,\ T_3$ and $T_4$ . Initially, $T_1$ reads and write the data and it commits. Then $T_2$ reds the data and commits, followed by $T_3$ and $T_4$ . If any one the transactions fails in between, they it will rollback to their initial state without affecting the other transactions.

Cascadeless schedules are more preferred than cascading schedules as the loss of CPU cycles is minimized when a rollback is required.

Conclusion

Recoverability in DBMS is like backup and restore used to satisfy the durability of transaction schedules.
If each transaction present in the schedule commits only after all the transactions from which it has read the values are committed, then the schedule is said to be recoverable schedule.
If a schedule is not recoverable then it is irrecoverable.
Cascadeless schedule is a recoverable schedule in which the following transactions can read the data of the previous transactions only when the previous transactions are committed.
If a schedule is not cascadeless, then it is a cascade rollback schedule.

Overview

Recoverable Schedule

Irrecoverable Schedule

Cascade Recoverable Rollback Schedule

Cascadeless Recoverable Rollback Schedule

Conclusion

Learn More: