- Instructions li and lj of transactions Ti and Tj respectively, conflict if and only if there exists some item Q accessed by both li and lj, and at least one of these instructions wrote Q.
- If li and lj access different data item then li and lj don’t conflict.
- li = read(Q), lj = read(Q). li and lj don’t conflict.
- Also, l i = read(Q), lj = write(Q). li and lj
- li = write(Q), lj = read(Q). li and lj
- l i = write(Q), lj = write(Q). li and lj
- Intuitively, a conflict between li and lj forces a (logical) temporal order between them.
- If a schedule S can be transformed into a schedule S by a series of swaps of nonconflicting instructions, we say that S and S´ are conflict equivalent.
- We say that a schedule S is a conflict serializable if it is Conflict Serializability equivalent to a serial schedule.
Example of Conflict Serializability
Schedule S can be transformed into Schedule S’ by swapping of non-conflicting series of instructions. Therefore Schedule S is Conflict Serializability.
- Instruction Ii of transaction T1 and Ij of transaction T2 conflict if both of these instruction access same data A and one of these two instructions performs write operation on that data (A).
- In above example the write(A) instruction of transaction T1 conflict with read(A) instruction of transaction T2 because both the instructions access same data A. But write(A) instruction of transaction T2 is not conflict with read(B) instruction of transaction T1 because both the instructions access different data. Transaction T2 performs write operation in A and transaction T1 is reading B.
- So in above example in schedule S two instructions read(A) and write(A) of transaction T2. And two instructions read(B) and write(B) of transaction T1 interchanged and we get schedule S’.
- Therefore Schedule S is conflict serializable.
- We are unable to swap instructions in the above schedule S’’ to obtain either the serial schedule <T3, T4> or the serial schedule <T4, T3>.
- So above schedule S’’ is not conflict serializable.
- Let S and S´ be two schedules with the same set of transactions. S and S´ view equivalent if the following three conditions met, for each data item Q,
- If in schedule S, transaction Ti reads the initial value of Q, then in schedule S’. And also transaction Ti must read the initial value of Q.
- If in schedule S transaction Ti executes read(Q). And that value produced by transaction Tj (if any), then in schedule S’ also transaction Ti must read the value of Q that produced by the same write(Q) operation of transaction Tj .
- The transaction Ti (if any) that performs the final write(Q) operation in schedule S. Then in schedule S’ also the final write(Q) operation must perform by Ti.
- A schedule S viewed serializable if it views equivalent to a serial schedule.
- Every conflict serializable schedule also viewed serializable but every view serializable is not conflicting serializable.
- Below is a schedule which viewed serializable but not conflicts serializable.
- Above schedule is view serializable but not conflict serializable. Because all the transactions can use same data item (Q) and all the operations conflict with each other due to one operation is write on the data item (Q). And that’s why we cannot interchange any non-conflict operation of any transaction.