QUESTION:
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. Calculate The total number of conflict serializable schedules that can be formed by T1 and T2
ANSWER:
In both transaction T₁ and T₂, common data item is Y. There can be conflict between T₁ and T₂ on data item Y.
FIRST SEQUENCE OF EXECUTION:
T₁ executes first and then T2. There is conflict between r₁(Y) and w₂(Y). SO, either both the read and write of T₁ on Y should be performed before read write pair of T₂ or after read write pair of T2. Because in all other cases, it causes violation.
According to the, one serial arrangement is r₁ (X)w₁ (X)r₁ (Y)W₁ (Y), 2 (Y)W2 (Y)r2 (Z)w₂ (Z)
As, there are total 8 operations, so total sequence possible = 8!/4! * 4! = 70
Now find the schedules which have a cycle in the precedence graph or which violate the conflict serializability.
These operations are: r₁(Y) w₁(Y), r2(Y) W2(Y).
Sequences of operation possible from this are:
r₁(Y) W₁(Y), 1₂(Y) W₂(Y).

Possible

r₁(Y) r₂(Y), W₁ (Y) W₂(Y).

No

r₁(Y) r₂(Y), W₂(Y) W₁ (Y).

No

r₂(Y) W₂(Y), r₁(Y) w₁(Y).

Yes

r₂(Y) r₁(Y), W₂(Y) W₁(Y).

No

r₂(Y) r₁(Y), w₁(Y) W₂(Y).

No

Consider the possible sequences as core sequence and then find the other sequences.
Out of the total, 16 schedules are not possible in this way.
Total conflict serializable schedule that are possible = 70  16 = 54
Share with your friends: 