GATE CSE 2024 | Set 1 | Question: 36

Question

​​​​Consider the following read-write schedule $\text{S}$ over three transactions $T_{1}, T_{2}$, and $T_{3}$, where the subscripts in the schedule indicate transaction IDs:

$S: r_{1}(z) ; w_{1}(z) ; r_{2}(x) ; r_{3}(y) ; w_{3}(y) ; r_{2}(y) ; w_{2}(x) ; w_{2}(y) ;$

Which of the following transaction schedules is/are conflict equivalent to $\text{S}$?

• A. $T_{1} T_{2} T_{3}$
• B. $T_{1} T_{3} T_{2}$
• C. $T_{3} T_{2} T_{1}$
• D. $T_{3} T_{1} T_{2}$

Comments

When you draw a timeline table for this you will observe that transaction T1 doesn't matter where you put only there will be dependency between T2 and T3 and then play according to it.

---

option B,C,D are correct

---

This will help !! 

---

$\text{Number of Conflict-Equivalent Serial Schedules} = \text{Total Topological Sorts of } G(S)$

Answer 1

$\begin{array}{c|c|c} \hline 
\bf{T_1} & \bf{T_2}& \bf{T_3} \\ \hline
r_1(z)\\
w_1(z) \\
&r_2(x) \\
&&r_3(y) \\
&&w_3(y) \\
&r_2(y)\\ &w_2(x)\\ &w_2(y)\\ \hline
\end{array}$

 

 

The corresponding polygraph for the given transaction. it has three conflict pairs as $T_3\rightarrow T_2$ as $r_3(y)\rightarrow w_2(y),w_3(y)\rightarrow r_2(y),w_3(y)\rightarrow w_2(y)$.
Because the graph is acyclic it is conflict serializable schedule and its corresponding conflict equal schedule is based on the topological order of the given graph.

Therefore, the following are possible serial schedules:

1. $T_1,T_3,T_2$
2. $T_3,T_1,T_2$
3. $T_3,T_2,T_1$

Option $(B, C, D)$ are correct.

Comments

The graph is correct but the sequences should be like _T3_T2_.in one of the underscore places we can have T1 and leave the others.
So, the correct options are B, C, and D.

Please correct me if I'm wrong.

---

Yes, you are correct. I updated it.

---

There are 3 simple rules . If a pair of operation follows that 3 rules then they are conflicting :

1) both operation should not belongs to same transaction.

2)both operation must be on same data

3)atleast one of the operation is write.

Answer 2

Here for this question, first we need to understand the conflict pairs which may occur. They are R(x)-W(x), R(y)-W(y), R(z)-W(z), W(x)-W(x), W(y)-W(y), W(z)-W(z), W(x)-R(x), W(y)-R(y), W(z)-R(z).

Now we need to create a precedence graph for the given schedule. Upon creating the graph we see that there is only one conflict pair present i.e. between T2 and T3 and there is no cycle or loop in the graph. This means the schedule is conflict serializable.

Since only T2 and T3 are involved in the conflict so the transaction schedule will be independent of T1's position.

It needs to be understood, that for choosing the transaction from the graph we have to consider the indegree of each transaction(node). We will have to start with the node having least indegree and then choose accordingly. This is why T2 cannot happen before T3 because indegree of T3 is 0 while that of T2 is 1.

So the possible transaction schedules are: B. T1-T3-T2

                                                                     C. T3-T2-T1

                                                                     D. T3-T1-T2

 

Note: Indegree is the number of incoming arrows in that node.

Answer 3

just use topological sort for getting the answer