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

 Date 22.11.2021 Size 11.97 Kb.

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

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