Serializability

If a schedule of concurrent transactions can be converted into an equivalent serial schedule, then we say that the schedule is serializable schedule. And this property is called serializability.
Different forms of schedule equivalence give rise to the notions of:

  1. Conflict serializability
    • Conflict:Instructions Ii and Ij conflict when they perform some operation on a data item and at least one of these operations is a write operation.
      • Let X is the shared data item, I1 is instruction for T1 and I2 is instruction for T2.
      • I1=read(X), I2=read(X). I1 and I2 doesn’t conflict.
      • I1=read(X), I2=write(X). They conflict.
      • I1=write(X), I2=read(X). They conflict.
      • I1=write(X), I2=write(X). They conflict.
    • Conflict Equivalent: If a schedule S1 can be transformed into a schedule S2 by a series of swaps of non-conflicting instructions, we say that S1 and S2 are conflict equivalent.
    • Conflict Serializable: A schedule S1 is said to be conflict serializable if it is conflict equivalent to a serial schedule.
    • Example: Consider the following conflict serializable schedule and its equivalent serial schedule(T2 follows T1):
  2. View serializability:
    • View Equivalence:- Two schedules S1 and S2 of a transaction is  view equivalence if following conditions are met:
      1. First read should be performed by same transaction i.e. For each data item X, if T1 first reads an initial value X in S1 then T1 must read initial value of X in S2 also.
      2. Last write should be performed by same transaction i.e. For each data item X, if T1 last write an initial value X in S1 then T1 must write last value of X in S2 also.
      3. Producer Consumer should be maintained: If Ti executes Read(X) in S1 where X is produced by Tj then Ti must in S2 also, reads the value of X which was produced by Tj.
    • View Serializable:- A schedule is view serializable if it is view equivalence to a serial schedule.
      • Example
      • In both schedules S1 and S2; first read operation for A and B i.e. R(A) and R(B) performed by T1.
      • In both schedules S1 and S2; final write operation for A and B i.e. W(A) and W(B) performed by T2.
      • In both S1 and S2; T2 executes R(A) which is written by T1. Also T2 executes R(B) which is written by T1.
    • Every conflict serializable schedule is also view serializable but not vice versa.
    • Every view serializable schedule that is not conflict serializable has blind writes.
    • Blind Writes: If there is no read prior to the first write then it is said to be a blind write. Example
    • W3(X) is a blind write, as there is no read before write [R3(X) before W3(X)]
    • W2(X) is not a blind write, as a read happens before write [R2(X) before W2(X)]

Leave a Reply

avatar
  Subscribe  
Notify of