0.3 Giao dịch  (Page 7/12)

Schedule-3 ( viết dưới dạng thoả thuận)

figure IV-

Tuần tự xung đột (conflict serializability)

Xét lịch trình S trong đó có hai chỉ thị liên tiếp Ii và Ij của các giao dịch Ti , Tj tương ứng (i  j). Nếu Ii và Ij tham khảo đến các hạng mục dữ liệu khác nhau, ta có thể đổi chỗ Ii và Ij mà không làm ảnh hưởng đến kết quả của bất kỳ chỉ thị nào trong lịch trình. Tuy nhiên, nếu Ii và Ij tham khảo cùng một hạng mục dữ liệu Q, khi đó thứ tự của hai bước này có thể rất quan trọng. Do ta đang thực hiện chỉ các chỉ thị Read và Write, nên ta có bốn trường hợp cần phải xét sau:

1. Ii = Read(Q); Ij = Read(Q): Thứ tự của Ii và Ij không gây ra vấn đề nào, do Ti và Tj đọc cùng một giá trị Q bất kể đến thứ tự giữa Ii và Ij.
2. Ii = Read(Q); Ij = Write(Q): Nếu Ii thực hiện trước Ij, Khi đó Ti không đọc giá trị được viết bởi Tj bởi chỉ thị Ij . Nếu Ij thực hiện trước Ii , Ti sẽ đọc giá trị của Q được viết bởi Ij , như vậy thứ tự của Ii và Ij là quan trọng.
3. Ii = Write(Q); Ij = Read(Q): Thứ tự của Ii và Ij là quan trọng do cùng lý do trong trường hợp trước.
4. Ii = Write(Q); Ij = Write(Q): Cả hai chỉ thị là hoạt động Write, thứ tự của hai chỉ thị này không ảnh hưởng đến cả hai giao dịch Ti và Tj . Tuy nhiên, giá trị nhận được bởi chỉ thị Read kế trong S sẽ bị ảnh hưởng do kết quả phụ thuộc vào chỉ thị Write được thực hiện sau cùng trong hai chỉ thị Write này. Nếu không còn chỉ thị Write nào sau Ii và Ij trong S, thứ tự của Ii vf Ij sẽ ảnh hưởng trực tiếp đến giá trị cuối của Q trong trạng thái CSDL kết quả (của lịch trình S).

Như vậy chỉ trong trường hợp cả Ii và Ij là các chỉ thị Read, thứ tự thực hiện của hai chỉ thị này (trong S) là không gây ra vấn đề.

Ta nói Ii và Ij xung đột nếu các hoạt động này nằm trong các giao dịch khác nhau, tiến hành trên cùng một hạng mục dữ liệu và có ít nhất một hoạt động là Write. Ta xét lịch trình schedule-3 như ví dụ minh hoạ cho các chỉ thị xung đột.

figure IV-

Chỉ thị Write(A) trong T1 xung đột với Read(A) trong T2. Tuy nhiên, chỉ thị Write(A) trong T2 không xung đột với chỉ thị Read(B) trong T1 do các chỉ thị này truy xuất các hạng mục dữ liệu khác nhau.

Ii và Ij là hai chỉ thị liên tiếp trong lịch trình S. Nếu Ii và Ij là các chỉ thị của các giao dịch khác nhau và không xung đột, khi đó ta có thể đổi thứ tự của chúng mà không làm ảnh hưởng gì đến kết quả xử lý và như vậy ta nhận được một lịch trình mới S’ tương đương với S. Do chỉ thị Write(A) của T2 không xung đột với chỉ thị Read(B) của T1, ta có thể đổi chỗ các chỉ thị này để được một lịch trình tương đương – schedule-5 dưới đây

figure IV-

Ta tiếp tục đổi chỗ các chỉ thị không xung đột như sau:

• Đổi chỗ chỉ thị Read(B) của T1 với chỉ thị Read(A) của T2
• Đổi chỗ chỉ thị Write(B) của T1 với chỉ thị Write(A) của T2
• Đổi chỗ chỉ thị Write(B) của T1 với chỉ thị Read(A) của T2

Kết quả cuối cùng của các bước đổi chỗ này là một lịch trình mới (schedule-6 –lịch trình tuần tự) tương đương với lịch trình ban đầu (schedule-3):

Schedule-6

figure IV-

Sự tương đương này cho ta thấy: bất chấp trạng thái hệ thống ban đầu, schedule-3 sẽ sinh ra cùng trạng thái cuối như một lịch trình tuần tự nào đó.