Made easy ots dbms 2 for gate2019

Question

$T1:w(A);w(B);R(C);C;$

$T2:w(B);R(B);C$

The number schedule of $T1$ and $T2$ are recoverable ________.

Comments

No, the answer is 20.

---

Answer should be 29. Updated.

---

Yes correct answer is 29

Answer 1

Recoverable schedules = (Dirty Read Possible and Recoverable ) + ( Dirty Read Doesn't Possible )

Dirty Read Possible and recoverable are :- 7

	T1	T2
1
2	W(A)
3
4	W(B)
5
6
7		R(B)
8
9	C
10		C

If W₂(B) is at 1 ===> R₁(C) should be at 5 or 8 ====> 2 possibilities

If W₂(B) is at 3 ===> R₁(C) should be at 5 or 8 ====> 2 possibilities

If W₂(B) is at 5 ===> R₁(C) should be at 6 or 8 ====> 2 possibilities

If W₂(B) is at 6 ===> R₁(C) should be at 5  ====> 1 possibility only ( R₁(C) be at 8 is overlapped with W₂(B) is at 5 and R₁(C) be at or 8 )

Dirty Read Doesn't Possible means

(i) R₂(B) should before W₁(B)

	T1	T2
1
2
3
4	W(A)
5
6
7
8	W(B)
9
10
11
12	R(C)
13
14
15	C
16
17

If W₂(B) is at 1 and R₂(B) is at 2 ===> C should be at 3 or 5 or 9 or 13 or 16 ====> 5 possibilities

If W₂(B) is at 1 and R₂(B) is at 5 ===> C should be at 6 or 9 or 13 or 16 ====> 4 possibilities

If W₂(B) is at 5 and R₂(B) is at 6 ===> C should be at 7 or 9 or 13 or 16 ====> 4 possibilities

 ( after commenting  Deepakk Poonia (Dee) )

(ii) Even R₂(B) is coming after Commit operation of T₁ is also lead to NO DIRTY READ

Therefore R₂(B) and Commit operation of T₂ should at 16 ==> W₂(B) may come at 1 or 3 or 5 or 9 or 13

====> 5 possibilities

( after commenting   Prateek Raghuvanshi )

(iii) Even W₂(B) is coming between W₁(B) and R₂(B)  is also lead to NO DIRTY READ

therefore, if W₂(B) and R₂(B) at 9 and 10 ===> C should be at  11 or 13 or 16 ====> 3 possibilities

if W₂(B) and R₂(B) at 9 and 13 ===> C should be at  14 or 16 ====>  1 possibility (  c at 16 is overlapping )

Total possibilities of recoverable schedule = 7+18+3+1=29

Comments

See, this is written in my answer. 

Here, To make the Schedule Irrecoverable, We just have to to do Two Things :

1. R2(B) after W1(B) But W2(B) Not in Between them.

2. C1 at the end

---

at starting the line

If W₂(B) is at 5 ===> R₁(C) should be at 6 or 8 ====> 2 possibilities 

at last the line

if W₂(B) and R₂(B) at 9 and 10 ===> C should be at  11 or 13 or 16 ====> 3 possibilities

contain the overlaping case example 

W1A,W1B,W2B,R2B,R1C,C1,C2

there are some are overlapping

---

@Gurdeep Saini

i will check it brother

Answer 2

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

Comments

Tell me when you placing w2(B) on the top of w1(A),how r1(c)has 3 choice ?? U can place only w1(B) or after R2(B) only two choice,because we can't change transaction order and when you are placing w2(B) after w1(B) then no dirty read because r2(B) will read from W2(B) not from w1(B),,,we have to remember that in between w1(B) and r2(B) there should not be w2(B),correct me if i m wrong

---

U can place only w1(B) or after R2(B) only two choice,

What about After $C_2$ ?

---

When W2(B) is Just immediate After W1(B) ,

Then how can we say that there is dirty read while r2(B) reading from w2(B)?? 

---

Read the definition of Recoverable Schedule in the answer. It is from "Korth". 

A recoverable schedule is one where, for each pair of transactions Ti and Tj such that Tj reads data items previously written by Ti, the commit operation of Ti appears before the commit operation of Tj.

---

Tell me in this ,there is dirty read or not,

T1	T2
w(A)
	W(A)
	R(A)
	C2
C1

---

Thanks for mentioning this point @Prateek, I think you are right but Hold on for few time. I will get back to you on this with a concrete answer. Though I think you are right. So, The answer would be 29. It is turning out to be a very nice Question.

---

Got it. In "Navathe" the clear definition of Recoverable schedule is given(Added in my answer). I've updated my answer. Thank you for mentioning.

---

I think 29 is correct answer, and thank you so much for understanding my point

---

It always feels nice to learn and become better. Keep learning, keep getting better.

---

It's true ,thanks again

---

Hi, sorry for a naive question. Why 7C4 is the  total number of schedules, why not 7!?

---

@Prateek Raghuvanshi ... in urs table dirty read is present or not?

---

No there is no dirty read in my table

---

dirty read means reading from an uncommitted transaction.... is it correct or it should be extended? why there is no dirty read in urs table?

---

There is no dirty read because data item A is reading after writing by same transaction .dirty read means transaction $T_j$ is reading after writing by uncommitted transaction $T_i$. I hope now u understand what i mean.

---

got it....thanks @Prateek Raghuvanshi

Answer 3

T1          T2
W1(A)
W1(B)
R1(C)
C1
            W2(B)
            R2(B)
            C2;

 

Total Schedules possible=$\binom{7}{3}=35$

Since T1 does not read any value that is written by T2, the only way I can make non-recoverable schedules if by Making T1 write B, T2 read B(And T2's write of B occurs before Write(B) of T1) and T2 commits before T1.

Number of Non-Recoverable Schedule:

    W1(B)            R2(B)      C2         C1

Now We have only 1 place left for W1(A) and that is before W1(B)

W1(A)        W1(B)              R2(B)        C2     C1

Now W2(B) must appear before W1(B) -2 choices

And R1(C) must appear after W1(B) and before C1->3 choices

Total non-recoverable schedules this way=2*3=6.

Recoverable Schedules=Total Schedules-Non Recoverable=35-6=29

Similar Question : https://gateoverflow.in/31867/how-many-recoverable-schedules-are-possible-from-t1-and-t2

Comments

 Ayush Upadhyaya please explain 

Now We have only 1 place left for W1(A) and that is before W1(B)

W1(A)        W1(B)              R2(B)        C2     C1

Now W2(B) must appear before W1(B) -2 choices

And R1(C) must appear after W1(B) and before C1->3 choices

Total non-recoverable schedules this way=2*3=6.