-
Two transactions T1 and T2 are given as
T1 : r1 (X) w1 (X)r1 (Y)w1 (Y)
T2 : r2(Y) w2 (Y)r2 (Z) w2 (Z)
where ri (V) denotes a read operation by transaction Ti on a variable V and wi (V) denotes a write operation by transaction Ti on a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is __________.
-
- 27
- 23
- 54
- 45
Correct Option: C
The given two transactions T1 and T2 are :
T1 : r1(X) w1 (X) r1(Y) w1(Y)
T2 : r2(Y) w2 (Y) r2(Z) w2(Z)
The conflict condition RW, WR, WW, because there is only 'one' way to have serializable schedule as (T1 → T2) because last operation of T1 and first operation of T2 conflicts each other. (T1 → T2 : 1)
r1 (X) w1 (X) r1 (Y) w1 (Y) r2 (Y) w2 (Y) r2 (Z) w2 (Z).
Then, we see how many schedules are conflict serializable to (T2 → T1) for this, we writing S as :
S : r2 (Y) w2 (Y) r1 (Y) w1 (Y)
r1 (X) w1 (X)
must be before r1 (Y) , so that can place, then 4C2 = 6 ways.
1. r2 (Y) w2 (Y) r1 (X) w1 (X) r1 (Y) w1 (Y) r2 (Z) w2 (Z) can place in 6C2 = 15 ways.
2. r2 (Y) r1 (X) w1 (X) w2 (Y) r1 (Y) w1 (Y) r2 (Z) w2 (Z) can place in 4C2 = 6 ways.
3. r2 (Y) r1 (X) w2 (Y) w1 (X) r1 (Y) w1 (Y) r2 (Z) w2 (Z) can place in 5C2 = 10 ways.
4. r1 (X) w1 (X) r2 (Y) w2 (Y) r1 (Y) w1 (Y) r2 (Z) w2 (Z) can place in 4C2 = 6 ways.
5. r1 (X) r2 (Y) w2 (Y) w1 (X) r1 (Y) w1 (Y) r2 (Z) w2 (Z) can place in 5C2 = (10 ways).
6. r1 (X) r2 (Y) w1 (X) w2 (Y) r1 (Y) w1 (Y) r2 (Z) w2 (Z) can place in 4C2 = (6 ways).
* Total conflict serializable of T1 and T2 = (53 + 1) = 54 ways.
Hence 54 is correct answer.
