GATE CSE 2022 | Question: 29

Question

Let $\textit{R}_{i}(z)$ and $\textit{W}_{i}(z)$ denote read and write operations on a data element $z$ by a transaction $\textit{T}_{i},$ respectively. Consider the schedule $\textit{S}$ with four transactions.

$S: \; R_{4}(x) R_{2}(x) R_{3}(x)R_{1}(y) W_{1}(y) W_{2}(x) W_{3}(y) R_{4}(y)$

Which one of the following serial schedules is conflict equivalent to $\textit{S}?$

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

Comments

option A is correct

---

follow this simple step !!  

and find topological order of graph

---

Note : 

A schedule $S$ is conflict serializable if and only if its precedence graph $G(S)$ contains no directed cycles.Every valid Topological Sort of the Precedence Graph $G(S)$ corresponds to a unique conflict-equivalent serial schedule.

• Any transaction $T_k$ with an in-degree of 0 can be chosen as the first transaction in the serial execution order.

• Recursive formula : $\text{TopologicalSorts}(G) =\sum_{v \in V \text{ where } \text{in-degree}(v) = 0} \text{TopologicalSorts}(G \setminus \{v\})$ , Base Case: $\text{TopologicalSorts}(\emptyset) = 1$.

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

For Finding Topological Sort use Kahn's  Algorithms 

1. Maintain an indegree array for all vertices.

2. Find all vertices with indegree == 0.

3. Pick one such vertex, add it to the path, decrement the indegree of its outgoing neighbors, and recurse.

4. Backtrack by restoring the indegree state.

Answer 1

Answer : Option A

---

Conflict operations:

1. Transaction $T_i$ reading data item K, after that Transaction $T_j$ writing data item K
2. Transaction $T_i$ writing data item K, after that Transaction $T_j$ reading data item K
3. Transaction $T_i$ writing data item K, after that Transaction $T_j$ writing data item K.

Note that, Transaction $T_i$ writing data item ‘K’, after that Transaction $T_j$ writing data item ‘P’ are not conflict operations due to those are different data items.

Tabular representation of given schedule is :

If you observe,

1. Line 1 and Line 6 are conflict operations. So in Serial schedule Transaction $T_4$ must be before  $T_2$
2. Line 3 and Line 6 are conflict operations. So in Serial schedule Transaction $T_3$ must be before  $T_2$
3. Line 4 and Line 7 are conflict operations. So in Serial schedule Transaction $T_1$ must be before  $T_3$
4. Line 5 and Line 8 are conflict operations. So in Serial schedule Transaction $T_1$ must be before  $T_4$
5. Line 7 and Line 8 are conflict operations. So in Serial schedule Transaction $T_3$ must be before  $T_4$

Accumulating all these points and running Topological sort, $T_1$ should be first followed by $T_3,T_4$ and $T_2$ in order.

Comments

doubt clrs

 

---

I didn't get why T1 , T4, T3, T2 is not possible can anyone please tell me like how can we conclude that T3 will come before T4 by line 7 and 8 their is no direct connection.

---

In line 7, T3 writing Y and in line 8, T4 reading that value.

If T4 comes prior to T3, that will not read the Y value wrote by T3 anymore.

Answer 2

Precedence graph from the schedule :

Comments

T1,T3,T2,T4 is also possible

---

@Shashwat Pandey T1, T3, T2, T4 topological order not possible because in finding for topological order from precedence graph, when T3 deleted after T1, in-order of T4 is 0 but T2 in-order is non-zero, so T4 will be deleted first then T2.

---

@Shashwat Pandey No. T2 is depending upon T4. Hence T4 must be completed before T2.

Correct ordering is only Option A $T1->T3->T4->T2$. 

Answer 3

Option A T1−>T3−>T4−>T2