edited by
18,445 views
42 votes
42 votes

Consider the following three schedules of transactions T1, T2 and T3. [Notation: In the following NYO represents the action Y (R for read, W for write) performed by transaction N on object O.]$$\begin{array}{llll}\hline (S1) & 2RA & 2WA & 3RC & 2WB & 3WA & 3WC & 1RA & 1RB & 1WA & 1WB  \\\hline (S2) & 3RC & 2RA & 2WA & 2WB & 3WA & 1RA & 1RB & 1WA & 1WB & 3WC  \\\hline (S3) & 2RA & 3RC & 3WA & 2WA & 2WB & 3WC & 1RA & 1RB & 1WA & 1WB  \\\hline \end{array}$$Which of the following statements is TRUE?

  1. S1, S2 and S3 are all conflict equivalent to each other
  2. No two of S1, S2 and S3 are conflict equivalent to each other
  3. S2 is conflict equivalent to S3, but not to S1
  4. S1 is conflict equivalent to S2, but not to S3
edited by

8 Answers

Best answer
24 votes
24 votes

Two schedules are conflict equivalent if we can derive one schedule by swapping the non-conflicting operations of the other schedule.

S1$$\begin{array}{|l|l|l|}\hline T1 & T2 & T3 \\\hline & R(A) &  \\\hline  & W(A) &  \\\hline   &  &  {\color{Blue} {R(C)}} \\\hline & {\color{Blue} {W(B)}} & \\\hline  &  & W(A)  \\\hline &  & W(C) \\\hline R(A) & & \\\hline R(B) & &  \\\hline W(A) & & \\\hline W(B)  \\\hline \end{array}$$Here, we can swap R(C) and W(B) since they are non-conflicting pair (since they are operating on different data items) 

After swapping the schedule will become $T2 \rightarrow T3 \rightarrow  T1$ $$\begin{array}{|l|l|l|}\hline T1 & T2 & T3 \\\hline & R(A) &  \\\hline  & W(A) &  \\\hline  & W(B) & \\\hline &  & R(C) \\\hline  &  & W(A)  \\\hline &  & W(C) \\\hline R(A) & & \\\hline R(B) & &  \\\hline W(A) & & \\\hline W(B)  \\\hline \end{array}$$


 S2$$\begin{array}{|l|l|l|}\hline T1 & T2 & T3 \\\hline   & & {\color{Blue} {R(C)}}  \\\hline  & R(A) &  \\\hline  & W(A) &  \\\hline  & W(B) &  \\\hline & & W(A)  \\\hline R(A) & &  \\\hline R(B) & & \\\hline W(A) & &  \\\hline  W(B) & &   \\\hline & & {\color{Blue} {W(C)}}  \\\hline \end{array}$$ Here, we can swap and write R(C) after performing T2 operations:-  R(A), W(A) and W(B) since each of them form non-conflicting pair with R(C)  (since they are operating on different data items)

Also, we can swap W(C) and can execute it before all the T1 operations as each of the t1 operations are forming non-conflicting pair with W(C) (since they are operating on different data items)

After swapping the schedule will become $T2 \rightarrow T3 \rightarrow  T1$ $$\begin{array}{|l|l|l|}\hline T1 & T2 & T3 \\\hline & R(A) &  \\\hline  & W(A) &  \\\hline  & W(B) & \\\hline &  & R(C) \\\hline  &  & W(A)  \\\hline &  & W(C) \\\hline R(A) & & \\\hline R(B) & &  \\\hline W(A) & & \\\hline W(B)  \\\hline \end{array}$$


S3$$\begin{array}{|l|l|l|}\hline T1 & T2 & T3 \\\hline   & R(A) &  \\\hline  &  &R(C)  \\\hline   & & {\color{Blue} {W(A)}}  \\\hline  & {\color{Blue} {W(A)}} &  \\\hline & W(B) &  \\\hline  & &W(C)  \\\hline R(A) & & \\\hline R(B) & &  \\\hline  W(A) & &   \\\hline W(B) & &  \\\hline \end{array}$$Here, we can't swap the operations and make it as $T2 \rightarrow T3 \rightarrow  T1$ because of the conflicting pairs W(A)and W(A)

$\therefore$ Option $D.$ S1 is conflict equivalent to S2, but not to S3 is the correct answer.

selected by
25 votes
25 votes

Answer: D

Two schedules are conflict equivalent when the precedence graphs are isomorphic.

For S1, edges in precedence graph are: 2->3, 3->1, 2->1.

For S2, edges in precedence graph are: 2->1, 3->1, 2->3.

For S3, edges in precedence graph are: 3->1, 3->2, 2->1.

Hence, S1 is conflict equivalent to S2, but not to S3.

8 votes
8 votes

According to Wiki...Conflict equivalence

The schedules S1 and S2 are said to be conflict-equivalent if the following two conditions are satisfied:

  1. Both schedules S1 and S2 involve the same set of transactions (including ordering of actions within each transaction). //Holds for S1,S2 in our case but not for S3 due to 2RZ operation.
  2. Both schedules have same set of conflicting operations.//Holds for S1 and S2 in our case
In our case Set of Conflicting operation for S1 = S2 = {2RA ->1RA, 2RA-> 3WA, 2WA->1RA, 2WA->3WA , 2WB->1RB, 3WA->1RA}

Both S1 and S2 satisfies above two conditions so S1 is conflict equivalent to S2. (and S3 eliminated earlier) .Hence Option D is Ans.

//Comment plz if I am missing something

Answer:

Related questions

47 votes
47 votes
5 answers
1
52 votes
52 votes
5 answers
2
Ishrat Jahan asked Oct 29, 2014
18,072 views
Consider the following relational schema:$\text{Student} (\underline{\text{school-id}, \text{sch-roll-no}}, \text{sname}, \text{saddress})$$\text{School} (\underline{\tex...