0.3 Giao dịch  (Page 8/12)

Nếu một lịch trình S có thể biến đổi thành một lịch trình S’ bởi một dãy các đổi chỗ các chỉ thị không xung đột, ta nói S và S’ là tương đương xung đột (conflict equivalent). Trong các schedule đã được nêu ở trên, ta thấy schedule-1 tương đương xung đột với schedule-3.

Khái niệm tương đương xung đột dẫn đến khái niệm tuần tự xung đột. Ta nói một lịch trình S là khả tuần tự xung đột (conflict serializable) nếu nó tương đương xung đột với một lịch trình tuần tự. Như vậy, schedule-3 là khả tuần tự xung đột. Như một ví dụ, lịch trình schedule-7 dưới đây không tương đương xung đột với một lịch trình tuần tự nào do vậy nó không là khả tuần tự xung đột:

Schedule-7

figure IV-

Có thể có hai lịch trình sinh ra cùng kết quả, nhưng không tương đương xung đột. Ví dụ, giao dịch T5 chuyển 10$ từ tài khoản B sang tài khoản A. Ta xét lịch trình schedule-8 như dưới đây, lịch trình này không tương đương xung đột với lịch trình tuần tự<T1, T5>do trong lịch trình schedule-8 chỉ thị Write(B) của T5 xung đột với chỉ thị Read(B) của T1 như vậy ta không thể di chuyển tất cả các chỉ thị của T1 về trước các chỉ thị của T5 bởi việc hoán đổi liên tiếp các chỉ thị không xung đột. Tuy nhiên, các giá trị sau cùng của tài khoản A và B sau khi thực hiện lịch schedule-8 hoặc sau khi thực hiện lịch trình tuần tự<T1, T5>là như nhau--- là 960 và 2040 tương ứng. Qua ví dụ này ta thấy cần thiết phải phân tích cả sự tính toán được thực hiện bởi các giao dịch mà không chỉ các hoạt động Read và Write. Tuy nhiên sự phân tích như vậy sẽ nặng nề và phải trả một giá tính toán cao hơn.

Schedule-8

figure IV-

Tuần tự view (view serializability)

Xét hai lịch trình S và S’, trong đó cùng một tập hợp các giao dịch tham gia vào cả hai lịch trình. Các lịch trình S và S’ được gọi là tương đương view nếu ba điều kiện sau được thoả mãn:

1. Đối với mỗi hạng mục dữ liệu Q, nếu giao dịch Ti đọc giá trị khởi đầu của Q trong lịch trình S, thì giao dịch Ti phải cũng đọc giá trị khởi đầu của Q trong lịch trình S’.
2. Đối với mỗi hạng mục dữ liệu Q, nếu giao dịch Ti thực hiện Read(Q) trong lịch trình S và giá trị đó được sản sinh ra bởi giao dịch Tj thì Ti cũng phải đọc giá trị của Q được sinh ra bởi giao dịch Tj trong S’.
3. Đối với mỗi hạng mục dữ liệu Q, giao dịch thực hiện hoạt động Write(Q) sau cùng trong lịch trình S, phải thực hiện hoạt động Write(Q) sau cùng trong lịch trình S’.

Điều kiện 1 và 2 đảm bảo mỗi giao dịch đọc cùng các giá trị trong cả hai lịch trình và do vậy thực hiện cùng tính toán. Điều kiện 3 đi cặp với các điều kiện 1 và 2 đảm bảo cả hai lịch trình cho ra kết quả là trạng thái cuối cùng của hệ thống như nhau. Trong các ví dụ trước, schedule-1 là không tương tương view với lịch trình 2 do, trong schedule-1, giá trị của tài khoản A được đọc bởi giao dịch T2 được sinh ra bởi T1 , trong khi điều này không xảy ra trong schedule-2. Schedule-1 tương đương view với schedule-3 vì các giá trị của các tài khoản A và B được đọc bởi T2 được sinh ra bởi T1 trong cả hai lịch trình.

Quan niệm tương đương view đưa đến quan niểm tuần tự view. Ta nói lịch trình S là khả tuần tự view (view serializable) nếu nó tương dương view với một lịch trình tuần tự. Ta xét lịch trình sau: