in Databases edited by
1,639 views
1 vote
1 vote

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}?$

  1. $T_{1} \rightarrow T_{3} \rightarrow T_{4} \rightarrow T_{2}$
  2. $T_{1} \rightarrow T_{4} \rightarrow T_{3} \rightarrow T_{2}$
  3. $T_{4} \rightarrow T_{1} \rightarrow T_{3} \rightarrow T_{2}$
  4. $T_{3} \rightarrow T_{1} \rightarrow T_{4} \rightarrow T_{2}$
in Databases edited by
by
1.6k views

1 comment

Following the simple steps is also helpful in solving this question:

a.) Make Precedence Graph.

b.) Do topological Sorting to find the serial schedule.

a.) Making Precedence is like Every transaction is a vertex and inserts/creates a directed edge between transaction Ti and Tj, If there is a conflicting pair then Ti proceeds Tj. 

If there is a cycle in the precedence graph then it’s not CSS else CSS.

b.) Now find the topological sort. You will get the serial schedule.

 

0
0

2 Answers

5 votes
5 votes
Best answer

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.

selected by

2 Comments

reshown by

Your point #4 is incorrect as, Line 4 and Line 8 are Non conflicting operations as both are Read operation only. But Line 5 and Line 8 are Conflicting operations as it is Read Write Conflict

 

1
1
edited by
corrected 👍

it was a typo.
1
1
4 votes
4 votes

Precedence graph from the schedule :

4 Comments

T1,T3,T2,T4 is also possible
0
0

@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.

0
0

@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$. 

0
0
Answer:

Related questions