Answer is 29. We can use the Complementary method i.e.
Number of Recoverable Schedules = All Schedules - Number of Irrecoverable Schedules
All Schedules : $\binom{7}{4}$ = $35$
Irrecoverable Schedules :
A Recoverable schedule is one where, for each pair of Transaction Ti and Tj such that Tj reads data item previously written by Ti the commit operation of Ti appears before the commit operation Tj . Otherwise, Schedule is Irrecoverable.
Here, To make the Schedule Irrecoverable, We just have to to do Two Things :
1. $R_2(B) \,\,after\,\,W_1(B)$ But $W_2(B)$ Not in Between them.
2. $C_1$ at the end
Let's do these things and get the answer.
| T1 |
T2 |
| |
|
| $W_1(A)$ |
|
| |
|
| $W_1(B)$ |
|
| |
|
| |
$R_2(B)$ |
| |
|
| |
$C_2$ |
| $C_1$ |
|
In the Above table, The Order will not change if we want to make Irrecoverable Schedule.(In Between things may come but the Order of the items shown in the table will be same as in the Table)
Now, We can have Different Cases :
Case (1) : When $W_2(B)$ is at the Top i.e. At first. Then $R_1(C)$ has $3$ places to be. So, $3$ Irrecoverable Schedule
Case(2) : When $W_2(B)$ is After $W_1(A)$ then Again, $R_1(C)$ has $3$ places to be. So, $3$ Irrecoverable Schedule.
So, We have $6$ Possible Irrecoverable Schedules.
Hence, Recoverable Schedules = 35 - 6 = $29$
The definition of recoverable schedule is as follows: A schedule $S$ is recoverable if no transaction $T$ in $S$ commits until all transactions $T'$ that have written some item $X$ that $T$ reads have committed.
When Do we say that Trans $T$ reads from $T' :$
A transaction $T$ reads from transaction $T'$ in a schedule $S$ if some item $X$ is first written by $T'$ and later read by $T$. In addition, $T'$ should not have been aborted before $T$ reads item $X$, and there should be no transactions that write $X$ after $T'$ writes it and before $T$ reads it (unless those transactions, if any, have aborted before $T$ reads $X$).
In Simple Words, $T$ reads from $T2$ if the schedule contains a subsequence $w2(x)...r(x),$ where $w2$ is the first write on $x$ going backwards from $r(x).$
Credit : @PrateekRaghuvanshi
