Transaction

Question

Find the number of concurrent schedule that are conflict serializable

Comments

almost duplicate to https://gateoverflow.in/118640/gate2017-2-44

in your question, you have to find T2 -> T1 also

---

But Bro this question is having  2 common data item so please solve it and then post it please

---

Answer added, you can check it

Answer 1

Conflict serializable schedules may be T1 → T2 or T2  → T1

Basic points:-

1) In a transaction, all operations should be sequential i.e., W1(A) should be Before R1(B)

2) between R1(A) and W1(A) there should be no chance for R2(A) why because if you place it between them it should form loop.

 

i) T1 → T2 , For occurring T1 firstly, you have to use R1(A) as 1

	T1	T2
1	R1(A)
2	W1(A)
3
4
5	R1(B)
6
7
8	W2(B)
9
10
11		R2(B)
12		W2(B)

Now Fix R₂(A) at 3 ====> There are 3 places for W₂(A) which are {4,6,10} note that placing it at 6 or 7 leads to same schedule, so i didn't count it.

Now Fix R₂(A) at 6 ====> There are 2 places for W₂(A) which are {6,10}

Now Fix R₂(A) at 9 ====> There are 1 place for W₂(A) which is {10}

In all these schedules ,  T1 → T2 , is conflict serializable. ===> total schedules which are T1 → T2 , conflict serializable. = 3+2+1 = 6

 

ii) T2 → T1 , For occurring T2 firstly, you have to use R2(A) as 1

These is quite similar to previous one ====> do it your self

total schedules which are T2 → T1 , conflict serializable. = 3+2+1 = 6

∴ total schedules which are conflict serializable. = 6+6 = 12