GATE CSE 2017 Set 2 | Question: 44

Question

Two transactions $T_1$ and $T_2$ are given as

$T_1:r_1(X)w_1(X)r_1(Y)w_1(Y)$

$T_2:r_2(Y)w_2(Y)r_2(Z)w_2(Z)$

where $r_i(V)$ denotes a $\textit{read}$ operation by transaction $T_i$ on a variable $V$ and $w_i(V)$ denotes a $\textit{write}$ operation by transaction $T_i$ on a variable $V$. The total number of conflict serializable schedules that can be formed by $T_1$ and $T_2$ is ______

Comments

Great man :) Keep it up 👍🏻.

---

@Supriya Priyadarshan best ever explanation

---

@Anmol_Binani GOD level🙏🏻

Answer 1

Is ans 8?

Comments

Its given 7

---

To make this conflict serialisable we just have to maintain sequence of R1(B), W1(B) and R2(B) , W2(B)

Any interleaving of this sequence can make non conflict serialisatble. because that will make  cycle! and hence for remaining elements and by considering for above mentioned case using permutation I got 8. Check using this logic. i will again check my solution and will post it if got correct answer.

---

Hi @Ashwin, I think the below link has the same problem and there they are getting answer as 54.

http://www.geeksforgeeks.org/gate-gate-cs-2017-set-2-question-64/

Answer 2

If the Precedence graph of a schedule is not $acyclic$ then, that schedule is not conflict serializable schedule and it is not conflict equal to any of the serial schedule:

There are only possible two serial schedules $T1 -> T2$ and $T2 -> T1$ so a conflict serializable schedule should equal to either of the serial schedule:

Answer 3

You can check this link to better understand.

 

https://gateoverflow.in/?qa=blob&qa_blobid=15880044459337072929

Answer 4

 

for T2 --> T1

1-  First of all execute R(Y)W(Y) of second transaction. Find total transactions possible for remaining operations. (15)

2.  Execute R(Y)W(Y) of first transaction at the last and find total transaction for remaining operations. (15)

3. Now couple first two operations of both transaction and find total no. of possible transaction.(6) Do same for

    last two operations. Multiply both(36 total). Now remove the transaction which are repeated or already occurred

     in 1 and 2. (1+6+6)

    total = 15+15+36-6-6-1 = 53

for T1 --> T2

 only 1 possible.

total = 53+1 = 54 ans.