Basic Assumption – Each transaction preserves database consistency
Thus, serial execution of set of transactions preserves database consistency.
A (possibly concurrent) schedule is serializable if it os equivalent to serial schedule (say, Transaction T1 follows Transaction T2 or T2 follows T1)
Different form of schedule equivalence gives rise to the notions of
1. Conflict serializability
2. View serializability
Conflict serializability
Instruction Ii and Ij of Transaction Ti and Tj respectively conflict if and only if there exists some item Q, accessed by both Ii and Ij and atleast one of these instructions wrote data item Q.
- if Ii = read(Q) and Ij = read(Q) then Ii and Ij don’t conflict
- if Ii = read(Q) and Ij = write(Q) then Ii and Ij conflict
- if Ii = write(Q) and Ij = read(Q) then Ii and Ij conflict
- if Ii = write(Q) and Ij = write(Q) then Ii and Ij conflict
If a schedule can be transformed into a schedule S’ by a series of swaps of non-conflicting instructions, we say that S and S’ are conflict equivalent.
We say that a schedule S is conflict serializable if it is conflict equivalent to serial schedule.
View Serializability
Let S and S’ be two schedules with the same set of transactions.
S and S’ are view equivalent if the following three conditions are met
- For each data item Q, if transaction Ti reads the initial value of Q in schedule S, then transaction Ti must in schedule S’, also read the initial value of Q
- For each data item Q if transaction Ti executes read(Q) in schedule S and that value was produced by the transition Tj (if any), then transaction Ti must in schedule S’ also read the value of Q that was produced by Transaction Tj.
- For each data item Q, the transaction (if any) that performs the final write(Q) operation in schedule S must perform the final write(Q) operation in schedule S’
A schedule S in view serializable if it is view equivalent to a serial schedule.
Every conflict serializable schedule is also view serializable but reverse is not true.
Schedule 1 is not view equivalent to schedule 2, the value of data item A read by transaction T2 was produced by T1(in schedule1) where as this case does not hold in schedule 2
schedule A is view serializable, it is view equivalent to the serial schedule <T3,T4,T6> since the one read(Q) instruction reads the initial value of Q in both schedules and T6 performs the final write of Q in both schedules.
However, schedule A is not conflict serializable, also observe that in schedule A, transaction T4 and T6 performs write(Q) operations without having performed a read(Q) operation. Writes of this sort are called blind writes.
Blind writes appear in tany view serializable schedule that is not conflict serializable.
Testing of Conflict Serializability
- We construct a directed graph, called a precedence graph of the schedule Schedule
- The set of vertices consists of all the transaction participating in schedule. The set of edges consists of all edges Ti -> Tj for which one of the following conditions holds:
a. Ti executes write(Q), before Tj executes read(Q) hence Tj is dependent on Ti
b. Ti executes read(Q), before Tj executes write(Q)
c. Ti executes write(Q) before Tj executes write(Q)
- If an edge Ti to Tj exists in the precedence graph then in any serial schedule S’ equivalent to S, Ti must appear before Tj.
- If the precedence graph for S has cycle the schedule S is not conflict serializable. If graph contains no cycle then the schedule S is conflict serializable.
For example
Precedence graph for above schedule, the graph do not contain any cycle hence the scedule is conflict serializable.
