GATE IT 2008 | Question: 63

Question

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?

• A. S1, S2 and S3 are all conflict equivalent to each other
• B. No two of S1, S2 and S3 are conflict equivalent to each other
• C. S2 is conflict equivalent to S3, but not to S1
• D. S1 is conflict equivalent to S2, but not to S3

Comments

Is there a typo error in this question or not ?? If yes please correct it or it create unnecessary confusion!!

---

Similar question:

https://gateoverflow.in/333194/gate-2020-cse-question-37

---

Its not Wrong- Two Schedules are conflict equivalent when there (i)Precedence graphs are isomorphic AND (ii) Graph should be Acyclic.

Answer 1

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.

Answer 2

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.

Comments

Ooh i think you r talking about sachin mittal's comment.

Then u r right.

---

@Sachin Mittal 1 

sir, Are no of Conflicting pairs in Conflict Equivalent Schedules are SAME always? OR both schedule have same set of confliting operations.

OR conflict operations are in same order?

pls explain

---

What if we label the edges also? For @Sachin Mittal 1's schedules, I have added precedence graphs. Without labels, the graphs are isomorphic. But with labels, we can account for the ordering of instructions in the transactions.

Labeling scheme: R -> W (A) means Read before Write on item A. So if the edge goes from 2 to 1, it means 2 reads item A before 1 writes item A.

For the 3 schedules in the question, precedence graphs + my labeling scheme show that S1 and S2 are conflict equivalent (the graphs are completely the same even with edge labeling applied) (I have not taken a photo of that).

 

Answer 3

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

Comments

2RA ->1RA

it is not a conflict operation bcz two transaction operation are conflict if:

a) both access same data item

b) atleast one of them is write operation

---

There is some mistake @Rajesh Pradhan beacause how two read operations could be conflicting. Edit Your answer.

---

Schedules should have same set of conflicting operations means conflicting operations in both the schedules are executed in same order.

Answer 4

• Schedules should involve the same set of transactions (including ordering of actions within each transaction)

• Schedules should have same set of conflicting operations.

So Answer is (D)

For Conflict and view equivalence of two transaction refer https://en.wikipedia.org/wiki/Schedule_(computer_science)#Conflict_equivalence