Serializability Concept

Serializability

A schedule S is serial if, for every transaction T participating in the schedule, all the operations of T is executed consecutively on the schedule. Interleaving does not occur in the serial schedule. A schedule S of n transactions is serializable if it is equivalent to some of the serial schedule of the same n transactions.

Two schedules are called result equivalent if they produce the same final state of the database. A schedule is serializable if it is equivalent to a serial schedule. Given below are different forms of schedule equivalence that give rise to the notions of:

• Conflict Serializability
• View Serializability

Conflict Serializability:

Two actions A_i and A_j executed on the same data object by T_i and T_j conflicts if either one of them is a write operation. Let A_i and A_j be consecutive non-conflicting actions that belong to different transactions. We can swap A_i and A_j without changing the result. Two schedules are conflict equivalent if they can be turned into one another by a sequence of non-conflicting swaps of adjacent actions. If a schedule S can be transformed into a schedule S’ by a series of swaps of non-conflicting instructions we can say that S and S’ are conflict equivalent. A schedule S is said to be conflict serializable if it is conflict equivalent to a serial schedule. Actions I_i and I_j of transactions T_i and T_j respectively conflict if and only if there exists some item Q accessed by I_i as well as I_j and at least one of these instructions wrote Q.

• I_i = read (Q), I_j = read (Q). I_i and I_j don’t conflict.
• I_i = read (Q), I_j = write (Q). They conflict.
• I_i = write (Q), I_j = read (Q). They conflict.
• I_i = write (Q), I_j = write (Q). They conflict.

Intuitively, a conflict between I_i and I_j forces a logical or temporal order between them. That is, replacing their order will change the result. If I_i and I_j are consecutive on a schedule and they do not conflict their results would still be the same even if they have been interchanged in the schedule. For example Schedule 3 can be transformed into Schedule 4, a serial schedule where T₂ follows by T₁, by series of swaps of non-conflicting instructions. Therefore Schedule 3 is conflict serializable.

An example of a Schedule that does not conflict serializable. We are unable to swap instructions in the schedule given above to obtain either the serial schedule < T₃, T₄ > or the serial schedule <T₄,T₃>.

Test for Conflict Serializability of a Schedule

• For each transaction, T_i participating in schedule S create a node labeled T_i in the precedence graph.
• For each case in S where Tj executes a read_item(X) after T_i executes a write_item(X), create an edge (T_i→ T_j)
• For each case in S where Tj executes a write_item(X) after T_i executes a read_item(X), create an edge (T_i→ T_j)
• For each case in S where Tj executes a write_item(X) after T_i executes a write_item(X), create an edge (T_i→ T_j)
• The schedule S is serializable if and only if the precedence graph has no cycles.

Example

Assume we have these three transactions:

T1: r₁(x); w₁ (x);r₁(y); w₁(y)

T2: r₂(z); r₂(y); w₂(y); r₂(x); w₂(x)

T3: r₃ (y); r₃ (z); w₃ (y);w₃(z)

Assume we have these schedules:

S1:r₂(z); r₂(y); w₂(y); r₃ (y); r₃ (z); r₁(x); w₁ (x); w₃ (y); w₃(z); r₂(x); r₁(y); w₁(y); w₂(x)

No equivalent serial schedule

(Cycle x (T₁→ T₂), y (T₂→T₁))

(Cycle x (T₁→ T₂), yz (T₂→T₃), y(T₃→ T₁))

Assume we have another schedule for the same transactions:

S2:r₃ (y); r₃ (z); r₁(x); w₁ (x); w₃ (y); w₃(z); r₂(z); r₁(y); w₁(y); r₂(y); w₂(y); r₂(x); w₂(x)

Equivalent serial schedule

T₃→ T₁→ T₂

View Serializability

A schedule S is said to be view serializable if it is view equivalent to a serial schedule. Every conflict serializable schedule is also viewed serializable. Schedules S1 and S2 are view equivalent if:

• If T_i reads initial value of A in S1 then T_i also reads initial value of A in S2.
• If T_i reads a value of A written by T_j in S1 then T_i also reads the value of A written by T_j in S2.
• If T_iwrites final value of A in S1, then T_i also writes the final value of A in S2.

Example:

• Consider the following schedule of three transactions
  T1: r1 (X), w1(X); T2: w2(X); and T3: w3(X);
  Schedule S: r1 (X); w2(X); w1(X); w3(X); c1; c2; c3;
• In S, the operations w2(X) and w3(X) are blind writes, since T1 and T3 do not read the value of X.
• S is view serializable since it is view equivalent to the serial schedule T1, T2, T3.
• However, S is not conflicted serializable since it does not conflict equivalent to any serial serializable.

References:

1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
2. A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
3. F.Korth, Henry. Database System Concepts. 6th edition.