Conflict serializable là gì?

Một lịch biểu (schedule) được gọi là conflict serializable nếu nó có thể được chuyển đổi thành một lịch biểu nối tiếp (serial schedule) bằng cách hoán đổi các thao tác không xung đột (non-conflicting operation).

Hãy xem xét lịch biểu này:

T1         T2
-----     ------
R(A)
R(B)
          R(A)
          R(B)
          W(B)
W(A)

Để chuyển đổi lịch biểu này thành một lịch biểu nối tiếp (serial schedule), chúng ta phải hoán đổi thao tác đọc R (A) của giao dịch T2 với thao tác ghi W (A) của giao dịch T1. Tuy nhiên, chúng ta không thể hoán đổi hai thao tác này vì chúng là các thao tác xung đột (conflicting operation), do đó chúng ta có thể nói rằng lịch trình nhất định này không phải là conflict serializable.

Hãy lấy một ví dụ khác:

T1         T2
-----     ------
R(A)
          R(A)
          R(B)
          W(B)
R(B)
W(A)

Bây giờ hoán đổi các thao tác không xung đột (non-conflicting operation):

Sau khi hoán đổi R (A) của T1 và R (A) của T2, chúng ta nhận được:

T1         T2
-----     ------
          R(A)
R(A)
          R(B)
          W(B)
R(B)
W(A)

Sau khi hoán đổi R (A) của T1 và R (B) của T2, chúng ta nhận được:

T1         T2
-----     ------
          R(A)
          R(B)
R(A) 
          W(B)
R(B)
W(A)

Sau khi hoán đổi R (A) của T1 và W (B) của T2, chúng ta nhận được:

T1         T2
-----     ------
          R(A)
          R(B)
          W(B)
R(A)         
R(B)
W(A)

Cuối cùng, chúng tôi đã có một lịch biểu nối tiếp sau khi hoán đổi tất cả các thao tác không xung đột để chúng ta có thể nói rằng lịch biểu đã cho là conflict serializable.