Conflict serializability

Question

Comments

Answer given is 56

---

Number instruction as 1-7.

In same transaction order of instruction cannot be changed.

1 -> 3

1 -> 5

2 -> 4

2 -> 6

4 -> 6

1 and 2 cannot be moved up.

3 => can take position of W1(B) and be at 3.

4 => cannot move. Why? It cannot move above 3rd one. (R2(A) ) , Also it cannot go above W1(B). Draw the schedule you will know.

5 => 4 place it can take. Remember it isn't conflicting with 3 ( R2(A) ).

It can be at position 2-5. (4 ways)

6 => Cannot move. Similar reason as 3.

7 => Can take any of the 7 positions, as its non conflicting with any of the instructions.

So total = Number of ways we can interchange instruction each instruction => $2 *  4* 7 = 56$

Answer 1

Structuring the schedule like this :
 

T1	T2	T3	T4
$\color{Red}{W(A)}$
$\color{Blue}{W(B)}$
	$\color{Magenta}{R(A)}$
	$\color{Blue}{W(B)}$
		$\color{Magenta}{R(A)}$
		$\color{Blue}{W(B)}$
			W(C)

• The Write of $T_1$ on $A$ is conflicting with Read of $T_2$ and $T_3$
• The Write of on $B$ of $T_1$ $T_2$ $T_3 $is conflicting with each other.
• Write of $T_3$ is free.

---

 Whenever there is a conflict operation , the order of original schedule should be maintained.

 W(C) can be perform any time and R(A) of both transaction can be performed anytime after Write of T1.

$\therefore \ 2 $ positions for $R_2(A)$ $2$ for $R_3(A)$ and order can be changed so $2!$ for order change.

Total  $2 \times 2 \times 2=8$

For these $8$ schedules W(C) can be done at any time because its not a conflicting operation .

Total places in schedule which is feasible for $T_4(C)=7$

So total schedules = $8 \times 7=\color{Red}{56}$

Comments

Still not getting. Can u represent in any other way.

Answer 2

R4(c) can be placed to any seven position as it is independent

Remaining 3 transition can be placed in 8 way (2*2*2)

So total no of conflict is 8*7=56

Comments

A pictorial representation would be good

Answer 3

Looking at the precedence Graph, we get

                                   

So from here, we can see that any transaction of T1 should happen before T2 & T3 and any transaction of T2 should happen after T1 and before T3 and any transaction of T3 should happen after T1 & T2.

Let us ignore W₄(C) for now since that can occur anywhere among 7 possible places.

So for | W₁(A),W₁(B)  |  R₂(A),W₂(B)  |  R₃(A),W₃(B) | none of the separated Read/Write can occur in/before/after the next/previous separated section since that will violate our above condition.

So possible permutations are limited only among the Reads/Writes of One single Underlined section.

So Possible number of permutations are 2*2*2=8

Consider W₄(C) and its 7 possible places, we get 7*8=56 possible permutations.

Comments

Can u please elaborate 3rd statement more.

So for | W₁(A),W₁(B)  |  R₂(A),W₂(B)  |  R₃(A),W₃(B) | none of the separated Read/Write can occur in/before/after the next/previous separated section since that will violate our above condition.

---

W1,W2 cannot occur after r2,w2,r3,w3 (according to precedence graph) so they can occupy only the first two places in 2 ways -w1,w2 or w2,w1.

similarly r2,w2 cannot occur after r3,w3. so they can occupy only the middle two places. so no of possible combinations- r2,w2 or w2,r2. again 2 ways.

same for r3,w3.(2 ways.

so total ways=2*2*2

Answer 4

​​​​​​following is the pictorial explanation... here at the time of finding position for r2(a) and r3(a) keep in mind that conflict precedence should not alter..