Two transactions T1 and T2 are given as: T1: r1

Download 11.97 Kb.
Size11.97 Kb.


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


In both transaction T₁ and T₂, common data item is Y. There can be conflict between T₁ and T₂ on data item Y.


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).


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


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


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


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


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


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
Download 11.97 Kb.

Share with your friends:

The database is protected by copyright © 2020
send message

    Main page