Database Management Systems (2130703)

Conflict serializability

• Instructions l_i and l_j of transactions T_i and T_j respectively, conflict if and only if there exists some item Q accessed by both l_i and l_j, and at least one of these instructions wrote Q.
  1. If l_i and l_j access different data item then l_i and l_j don’t conflict.
  2. l_i = read(Q), l_j = read(Q). l_i and l_j don’t conflict.
  3. l_i = read(Q), l_j = write(Q). l_i and l_j conflict.
  4. l_i = write(Q), l_j = read(Q). l_i and l_j conflict.
  5. l_i = write(Q), l_j = write(Q). l_i and l_j conflict.
• 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 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 a serial schedule.

Example

• Schedule S can be transformed into Schedule S’ by swapping of non-conflicting series of instructions. Therefore Schedule S is conflict serializable.

• Instruction Ii of transaction T1 and I_j 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 are 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 < T₃, T₄ >, or the serial schedule < T₄, T₃ >.
• So above schedule S’’ is not conflict serializable.