- những hoạt động nào của các giao dịch tác động lẫn nhau. - Vì lý do này, ta sẽ không giải thích kiểu hoạt động mà một giao dịch có thể thực hiện trên một mục dữ liệu. - Ta cũng giả thiết rằng giữa một chỉ thị Read(Q) và một chỉ thị Write(Q) trên một mục dữ liệu Q, một giao dịch có thể thực hiện một dãy tuỳ ý các hoạt động trên bản sao của Q được lưu trú trong buffer cục bộ của giao dịch. - Vì vậy ta sẽ chỉ nêu các chỉ thị Read và Write trong thời lịch, nếu biểu diễn với quy ước như vậy của thời lịch 3 sẽ là:. - Xét thời lịch S trong đó có hai chỉ thị liên tiếp I i và I j của các giao dịch T i , T j tương ứng (i ≠ j). - Nếu I i và I j tham khảo đến các mục dữ liệu khác nhau, ta có thể đổi chỗ I i và I j mà không làm ảnh hưởng đến kết quả của bất kỳ chỉ thị nào trong thời lịch. - I j = 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 T. - Ta nói I i và I j 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 mục dữ liệu và có ít nhất một hoạt động là Write.. - Ví dụ, trong thời lịch schedule - 3: Chỉ thị Write(A) trong T 1 xung đột với Read(A) trong T 2 . - I i và I j là hai chỉ thị liên tiếp trong thời lịch S. - Nếu I i và I j 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 thời lịch mới S’ tương đương với S. - Chẳng hạn, do chỉ thị Write(A) của T 2 không xung đột với chỉ thị Read(B) của T 1 , ta có thể đổi chỗ các chỉ thị này để được một thời lịch tương đương – thời lịch 5 dưới đây. - Thời lịch 5 Ta tiếp tục đổi chỗ các chỉ thị không xung đột như sau:. - Kết quả cuối cùng của các bước đổi chỗ này là một thời lịch mới (thời lịch 6 –thời lịch tuần tự) tương đương với thời lịch ban đầu (thời lịch 3):. - Thời lịch 6. - Sự tương đương này cho ta thấy: bất chấp trạng thái hệ thống ban đầu, thời lịch-3 sẽ sinh ra cùng trạng thái cuối như một thời lịch tuần tự nào đó.. - Tương đương xung đột (conflict equivalent):Nếu một thời lịch S có thể biến đổi thành một thời lịch S’ bởi một dãy các thao tác đổi chỗ các chỉ thị không xung đột, ta nói S và S’ là tương đương xung đột.. - Ví dụ, trong các thời lịch đã được nêu ở trên, ta thấy thời lịch-1 tương đương xung đột với thời lịch-3.. - Khả tuần tự xung đột (conflict serializable): Một thời lịch S là khả tuần tự xung đột (conflict serializable) nếu nó tương đương xung đột với một thời lịch tuần tự.. - Ví dụ, thời lịch 3 là khả tuần tự xung đột còn thời lịch 7 dưới đây không tương đương xung đột với một thời lịch tuần tự nào do vậy nó không là khả tuần tự xung đột:. - Thời lịch 7. - Có thể có hai thời lịch sinh ra cùng kết quả, nhưng không tương đương xung đột. - Ví dụ, giao dịch T 5 chuyển 10$ từ tài khoản B sang tài khoản A. - Ta xét thời lịch 8 như dưới đây, thời lịch này không tương đương xung đột với thời lịch tuần tự <. - do trong thời lịch 8 chỉ thị Write(B) của T 5 xung đột với chỉ thị Read(B) của T 1 như vậy ta không thể di chuyển tất cả các chỉ thị của T 1 về trước các chỉ thị của T 5 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 thời lịch 8 hoặc sau khi thực hiện thời lịch tuần tự <T 1 , T 5 >. - 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. - Xét hai thời lịch S và S’, trong đó cùng một tập hợp các giao dịch tham gia vào cả hai thời lịch. - Các thời lịch S và S’ được gọi là tương đương view nếu ba điều kiện sau được thỏa mãn:. - Đối với mỗi mục dữ liệu Q, nếu giao dịch T i đọc giá trị khởi đầu của Q trong thời lịch S, thì giao dịch T i phải cũng đọc giá trị khởi đầu của Q trong thời lịch S’.. - Đối với mỗi mục dữ liệu Q, nếu giao dịch T i thực hiện Read(Q) trong thời lịch S và giá trị đó được sản sinh ra bởi giao dịch T j thì T i cũng phải đọc giá trị của Q được sinh ra bởi giao dịch T j trong S’.. - Đối với mỗi mục dữ liệu Q, giao dịch thực hiện hoạt động Write(Q) sau cùng trong thời lịch S, phải thực hiện hoạt động Write(Q) sau cùng trong thời lịch 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 thời lịch 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 thời lịch 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, thời lịch-1 là không tương đương view với thời lịch 2 do trong thời lịch-1, giá trị. - của tài khoản A được đọc bởi giao dịch T 2 được sinh ra bởi T 1 , trong khi điều này không xảy ra trong thời lịch-2. - Thời lịch-1 tương đương view với thời lịch-3 vì các giá trị của các tài khoản A và B được đọc bởi T 2 được sinh ra bởi T 1 trong cả hai thời lịch.. - Ta nói thời lịch S là khả tuần tự view (view serializable) nếu nó tương đương view với một thời lịch tuần tự.. - Ta xét thời lịch sau:. - Thời lịch 9. - Nó tương đương view với thời lịch tuần tự <. - do chỉ thị Read(Q) đọc giá trị khởi đầu của Q trong cả hai thời lịch và T 6 thực hiện Write sau cùng trong cả hai thời lịch như vậy thời lịch 9 khả tuần tự view.. - Mỗi thời lịch khả tuần tự xung đột là khả tuần tự view, nhưng có những thời lịch khả tuần tự view không khả tuần tự xung đột (ví dụ thời lịch 9).. - Trong thời lịch 9 các giao dịch T 4 và T 6 thực hiện các hoạt động Write(Q) mà không thực hiện hoạt động Read(Q), Các Write dạng này được gọi là các Write mờ (blind write). - Các Write mờ xuất hiện trong bất kỳ thời lịch khả tuần tự view không khả tuần tự xung đột.. - Ta đã nghiên cứu các thời lịch có thể chấp nhận dưới quan điểm sự nhất quán của CSDL với giả thiết không có giao dịch nào thất bại. - Ta sẽ xét hiệu quả của thất bại giao dịch trong thực hiện tương tranh.. - Để thực hiện sự chắc chắn này, ta cần bố trí các hạn chế trên kiểu thời lịch được phép trong hệ thống.. - Thời lịch khả phục hồi (Recoverable Schedule). - Xét thời lịch 10 trong đó T 9 là một giao dịch chỉ thực hiện một chỉ thị Read(A). - Thời lịch 10. - Thời lịch 10 là một ví dụ về thời lịch không phục hồi được và không được phép. - Hầu hết các hệ CSDL đòi hỏi tất cả các thời lịch phải phục hồi được.. - Một thời lịch khả phục hồi là thời lịch trong đó, đối với mỗi cặp giao dịch T i , T j , nếu T j đọc mục dữ liệu được viết bởi T i thì hoạt động bàn giao của T j phải xảy ra sau hoạt động bàn giao của T i. - Thời lịch cascadeless (Cascadeless Schedule). - Ngay cả khi thời lịch là khả phục hồi, để phục hồi đúng sau thất bại của một giao dịch T i ta phải cuộn lại một vài giao dịch. - Tình huống như thế xảy ra khi các giao dịch đọc dữ liệu được viết bởi T i . - Ta xét thời lịch 11 sau. - Read (A) Thời lịch 11. - Giao dịch T 10 viết một giá trị được đọc bởi T 11 . - Giao dịch T 12 đọc một giá trị được viết bởi T 11 . - Phải hạn chế các thời lịch để việc cuộn lại hàng loạt không thể xảy ra. - Các thời lịch như vậy được gọi là các thời lịch cascadeless.. - Một thời lịch cascadeless là một thời lịch trong đó mỗi cặp giao dịch T i , T j nếu T j đọc một mục dữ liệu được viết trước đó bởi T i , hoạt động bàn giao của T i phải xuất hiện trước hoạt động đọc của T j . - Một thời lịch cascadeless là khả phục hồi.. - Có nhiều sơ đồ điều khiển tương tranh có thể được sử dụng để đảm bảo các tính chất một thời lịch phải có (nhằm giữ CSDL ở trạng thái nhất quán, cho phép quản lý các giao dịch. - ngay cả khi nhiều giao dịch thực hiện tương tranh, chỉ các thời lịch có thể chấp nhận được sinh ra, bất kể hệ điều hành chia sẻ thời gian tài nguyên như thế nào giữa các giao dịch.. - Trong cơ chế khóa, chỉ một giao dịch được thực hiện tại một thời điểm và như vậy chỉ thời lịch tuần tự được sinh ra. - Mục đích của các sơ đồ điều khiển tương tranh là cung cấp một bậc cạnh tranh cao trong khi vẫn đảm bảo các thời lịch được sinh ra là khả tuần tự xung đột hoặc khả tuần tự view và cascadeless.. - Cho S là một thời lịch. - Tập các đỉnh V bao gồm tất cả các giao dịch tham gia vào thời lịch.. - Nếu một cung T i → T j tồn tại trong đồ thị trình tự, thì trong bất kỳ thời lịch tuần tự S’ nào tương đương với S, T i phải xuất hiện trước T j. - Thời lịch 1 được biểu diễn bằng đồ thị. - Thời lịch 2 được biểu diễn bằng đồ thị. - Thời lịch 4 được biểu diễn bằng đồ thị chứa các cung T 1 → T 2 vì T 1 thực hiện Read(A) trước T 2 thực hiện Write(A). - Nếu đồ thị trình tự đối với S có chu trình, khi đó thời lịch S không là khả tuần tự xung đột. - Như vậy bài toán kiểm tra tính khả tuần tự xung đột của thời lịch S đưa về bài toán kiểm tra chu trình trên đồ thị trình tự biểu diễn của S.. - Không có thuật toán nào hiệu quả để kiểm tra tính khả tuần tự view của một thời lịch.. - Giả sử S là thời lịch gồm các giao dịch {T 1 , T 2. - T b và T f là hai giao dịch giả sao cho: T b bắt nguồn lệnh Write(Q) đối với mỗi mục dữ liệu Q được truy xuất trong S, T f bắt nguồn lệnh Read(Q) đối với mỗi mục dữ liệu Q được truy xuất trong S. - Ta xây dựng thời lịch mới S’ từ S bằng cách xen T b ở bắt đầu của S và T f ở cuối của S. - Xóa tất cả các cung liên quan tới các giao dịch không dùng. - Một giao dịch T i được gọi. - Ví dụ: xét thời lịch 9. - Nếu đồ thị trình tự gán nhãn không chứa chu trình, thời lịch tương ứng là khả tuần tự view, như vậy thời lịch 9 là khả tuần tự view. - Tuy nhiên, nếu đồ thị S’ chứa chu trình, điều kiện này không kéo theo thời lịch tương ứng không là khả tuần tự view. - Nếu một đồ thị nào đó trong các đồ thị này là phi chu trình, khi đó thời lịch tương ứng là khả tuần tự view. - có nghĩa là trong khi một giao dịch đang truy xuất một mục dữ liệu, không một giao dịch nào khác có thể sửa đổi mục dữ liệu này.. - Shared: Nếu một giao dịch T i nhận được một khóa ở phương thức shared (ký hiệu là S) trên mục Q, khi đó T i có thể đọc, nhưng không được viết Q.. - Nếu một giao dịch T i nhận được một khóa ở phương thức Exclusive (ký hiệu là X), khi đó T i có thể cả đọc lẫn viết Q.. - Mỗi giao dịch đòi hỏi một khóa ở một phương thức thích hợp trên mục dữ liệu Q, phụ thuộc vào kiểu hoạt động mà nó sẽ thực hiện trên Q. - Để truy xuất một mục dữ liệu, giao dịch T i đầu tiên phải khóa mục này. - Như vậy T i phải chờ đến tận khi tất cả các khóa không tương thích bị giữ bởi các giao dịch khác được giải phóng.. - Giao dịch T i có thể tháo khóa một mục dữ liệu mà nó đã khóa trước đây. - Một giao dịch cần thiết phải giữ một khóa trên một mục dữ liệu chừng nào mà nó còn truy xuất mục này. - Hơn nữa, đối với một giao dịch việc tháo khóa ngay sau truy xuất cuối cùng đến mục dữ liệu không luôn luôn là điều mong muốn vì như vậy tính khả tuần tự có thể không được đảm bảo. - Để minh hoạ cho tình huống này, ta xét ví dụ sau: A và B là hai tài khoản có thể được truy xuất bởi các giao dịch T 1 và T 2 . - Giao dịch T 1 chuyển 50$ từ tài khoản B sang tài khoản A và được xác định như sau:. - Tuy nhiên nếu các giao dịch này thực hiện tương tranh, giả sử theo thời lịch schedule-1, trong trường hợp như vậy giao dịch T 2 sẽ hiển thị giá trị 250$, một kết quả không đúng vì giao dịch T 1 đã tháo khóa mục B quá sớm và T 2 đã tham khảo một trạng thái không nhất quán.. - Thời lịch 12 cho thấy các hoạt động được thực hiện bởi các giao dịch cũng như các thời điểm khi các khóa được cấp bởi bộ quản trị điều khiển tương tranh
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt