0.3 Giao dịch  (Page 12/12)

Xét một lịch trình S. Giả sử giao dịch Tj đọc hạng mục dữ liệu Q được viết bởi Ti . Rõ ràng là nếu S là khả tuần tự view, khi đó, trong bất kỳ lịch trình tuần tự S’ tương đương với S, Ti phải đi trước Tj . Bây giờ giả sử rằng, trong lịch trình S, giao dịch Tk thực hiện một Write(Q), khi đó, trong lịch trình S’, Tk phải hoặc đi trước Ti hoặc đi sau Tj . Nó không thể xuất hiện giữa Ti và Tj vì như vậy Tj­ không đọc giá trị của Q được viết bởi Ti và như vậy S không tương đương view với S’. Các ràng buộc này không thể biểu diễn được trong thuật ngữ của mô hình đồ thị trình tự đơn giản được nêu lên trước đây. Như trong ví dụ trước, khó khăn nảy sinh ở chỗ ta biết một trong hai cung Tk  Ti và Tj  Tk phải được xen vào đồ thị nhưng ta chưa tạo được quy tắc để xác định sự lựa chọn thích hợp. Để tạo ra quy tắc này, ta cần mở rộng đồ thị định hướng để bao hàm các cung gán nhãn, ta gọi đồ thị như vậy là đồ thị trình tự gán nhãn (Label precedence graph). Cũng như trước đây, các nút của đồ thị là tất cả các giao dịch tham gia vào lịch trình. Các quy tắc xen cung gán nhãn được diễn giải như sau:

Giả sử S là lịch trình gồm các giao dịch { T1 , T2 , ... , Tn }. Tb và Tf là hai giao dịch giả: Tb phát ra Write(Q) đối với mỗi Q được truy xuất trong S, Tf phát ra Read(Q) đối với mỗi Q được truy xuất trong S. Ta xây dựng lich trình mới S’ từ S bằng cách xen Tb ở bắt đầu của S và Tf ở cuối của S. Đồ thị trình tự gán nhãn đố với S’ được xây dung dựa trên các quy tắc:

1. Thêm cung Ti 0 Tj , nếu Tj đọc giá trị của hạng mục dữ liệu Q được viết bởi Ti
2. Xoá tất cả các cung liên quan tới các giao dịch vô dụng. Một giao dịch Ti được gọi là vô dụng nếu không có con đường nào trong đồ thị trình tự dẫn từ Ti đến Tf .
3. Đối với mỗi hạng mục dữ liệu Q sao cho Tj đọc giá trị của Q được viết bởi Ti và Tk thực hiện Write(Q), Tk  Tb tiến hành các bước sau
   • Nếu Ti = Tb và Tj  Tf, khi đó xen cung Tj 0 Tk vào đồ thị trình tự gán nhãn
   • Nếu Ti  Tb và Tj = Tf khi đó xen cung Tk 0 Ti vào đồ thị trình tự gán nhãn
   • Nếu Ti  Tb và Tj  Tf khi đó xen cả hai cung Tk p Ti và Tj p Tk vào đồ thị trình tự gán nhãn, trong đó p là một số nguyên duy nhất lớn hơn 0 mà chưa được sử dụng trước đó để gán nhãn cung.

Quy tắc 3c phản ánh rằng nếu Ti viết hạng mục dữ liệu được đọc bởi Tj thì một giao dịch Tk viết cùng hạng mục dữ liệu này phải hoặc đi trước Ti hoặc đi sau Tj . Quy tắc 3a và 3b là trường hợp đặc biệt là kết quả của sự kiện Tb và Tf cần thiết là các giao dịch đầu tiên và cuối cùng tương ứng. Như một ví dụ, ta xét schedule-7. Đồ thị trình tự gán nhãn của nó được xây dựng qua các bước 1 và 2 là:

Đồ thị sau cùng của nó là (cung T3  T4 là kết quả của 3a, cung T4  T3 là kết quả của 3b) :

Đồ thị trình tự gán nhãn của schedule-9 là:

figure IV-

Cuối cùng, ta xét lịch trình schedule-10:

Đồ thị trình tự gán nhãn của schedule-10 là:

figure IV-

Đồ thị trình tự gán nhãn của schedule-7 chứa chu trình tối tiểu : T3  T4  T3

Đồ thị trình tự gán nhãn của schedule-10 chứa chu trình tối tiểu: T3  T1  T3

Đồ thị trình tự gán nhãn của schedule-9 không chứa chứa chu trình nào.

Nếu đồ thị trình tự gán nhãn không chứa chu trình, lịch trình tương ứng là khả tuàn tự view, như vậy schedule-9 là khả tuần tự view. Tuy nhiên, nếu đồ thị chứa chu trình, điều kiện này không kéo theo lịch trình tương ứng không là khả tuần tự view. Đồ thị trình tự gán nhãn của schedule-7 chứa chu trình và lịch trình này không là khả tuần tự view. Bên cạnh đó, lịch trình schedule-10 là khả tuần tự view, nhưng đồ thị trình tự gán nhãn của nó có chứa chu trình. Bây giờ ta giả sử rằng có n cặp cung tách biệt, đó là do ta đã áp dụng n lần quy tắc 3c trong sự xây dựng đồ thị trình tự. Khi đó có 2n đồ thị khác nhau, mỗi một chứa đúng một cung trong mỗi cặp. Nếu một đồ thị nào đó trong các đồ thị này là phi chu trình, khi đó lịch trình tương ứng là khả tuần tự view. Thuật toán này đòi hỏi một phép kiểm thử vét cạn các đồ thị riêng biệt, và như vậy thuộc về lớp vấn đề NP-complet !!!

Ta xét đồ thị schedule-10. nó có đúng một cặp tách biệt. Hai đồ thị triên biệt là:

figure IV-

Đồ thị thứ nhất không chứa chu trình, do vậy lịch trình là khả tuần tự view.

BÀI TẬP CHƯƠNG IV

IV.1 Liệt kê các tính chất ACID. Giải thích sự hữu ích của mỗi một trong chúng.

IV.2Trong khi thực hiện, một giao dịch trải qua một vài trạng thái đến tận khi nó bàn giao hoặc bỏ dở. Liệt kê tất cả các dãy trạng thái có thể giao dịch có thể trải qua. Giải thích tại sao mỗi bắc cầu trạng thái có thể xảy ra.

IV.3 Giải thích sự khác biệt giữa lịch trình tuần tự (Serial schedule) và lịch trình khả tuần tự (Serializable schedule).

IV.4Xét hai giao dịch sau:

T1 : Read(A);

Read(B);

If A=0 then B:=B+1;

Write(B).

T2 :Read(B);

Read(A);

If B=0 then A:=A+1;

Write(A).

Giả thiết yêu cầu nhất quán là A=0 V B=0 với A=B=0 là các giá trị khởi đầu

• Chứng tỏ rằng mỗi sự thự hiện tuần tự bao gồm hai giao dịch này bảo tồn tính nhất quán của CSDL.
• Nêu một sự thực hiện cạnh tranh của T1 và T2 sinh ra một lịch trình không khả tuần tự.
• Có một sự thực hiện cạnh tranh của T1 và T2 sinh ra một lịch trình khả tuần tự không ?

Iv.5do một lịch trình khả tuần tự xung đột là một lịch trình khả tuần tự view. tại sao ta lại nhấn mạnh tính khả tuần tự xung đột hơn tính khả tuần tự view?

IV.6Xét đồ thị trình tự sau:

Lịch trình tương ứng là khả tuần tự xung đột không? Giải thích

IV.7Xét đồ thị trình tự gán nhãn sau:

Lịch trình tương ứng là khả tuần tự view không? Giải thích.

IV.8Lịch trình khả phục hồi là gì? Tại sao cần thiết tính khả phục hổi của một lịch trình?

IV.9Lịch trình cascadeless là gì? Tại sao cần thiết tính cascadeless của lịch trình?