3.3.1. Các khái niệm cơ bản về giao dịch
Giao dịch là một lần thực hiện chương trình. Đôi khi để biểu thị một giao dịch T ta viết T: begin…end. Giữa begin và end là nh ững bước cơ bản của giao dịch. Chương trình này có thể là một câu vấn tin hoặc một chương trình ngôn ngữ chủ với các lời gọi được gắn vào một câu vấn tin. Có nhiều thực hiện độc lập của cùng m ột chương trình T được tiến hành đồng thời ở nhiều vị trí khác nhau trên m ạng; mỗi thực hiện này là m ột giao dịch khác nhau.
Một giao dịch sẽ đọc dữ liệu và ghi dữ liệu vào CSDL, qua một vùng làm vi ệc riêng (private) – gọi là vùng b ộ nhớ tính toán tạm thời. Cụ thể là các tính toán do giao dịch thực hiện sẽ không có tác dụng trên CSDL cho đến khi các giá trị mới được ghi vào CSDL.
Ví dụ chúng ta có giao dịch T:
Begin
Read A
A=A+100
Read A
A=A+2
Write A
End
Khi đó trong CSDL giá trị của A chỉ được tăng lên 2, vì phép toán A = A + 100 ch ỉ làm việc trong vùng b ộ nhớ tính toán tạm thời.
3.3.1.1. Tính nguyên tử
Trên quan điểm về quản lý được, quản lý giao dịch là một có gắp nhằm làm cho các thao tác phức tạp xuất hiện dưới dạng các nguyên tử. Nghĩa là thao tác x ảy ra trọn vẹn hoặc không xảy ra. Nếu xảy ra, không có biến cố hay giao dịch nào cùng x ảy ra trong suốt thời gian tồn tại của nó. Mỗi nguyên tử về sau ta sẽ gọi là một bước cơ bản hoặc một thao tác cơ bản. Cách thông dụng nhằm đảm bảo được tính nguyên tử của các giao dịch là phương pháp tuần tự hóa. Phương pháp này làm cho các giao dịch được thực hiện một cách tuần tự. Một giao dịch không có tính nguyên tử nếu:
1, Trong hệ thống phân chia thời gian, thời gian cho giao dịch T có thê kết thúc trong khi T đang tính toán và các hoạt động của một giao dịch khác sẽ được thực hiện trước khi T hoàn tất.
2, Một giao dịch có thể không hoàn tất được, chẳng hạn có khi nó phải chấm dứt giữa chứng, có thể vì nó thực hiện một phép tính không hợp lệ (ví dụ phép chia cho 0), hoặc có thể do nó đ òi h ỏi những dữ liệu không được quyền truy xuất. Bản thân hệ thống CSDL có thể buộc giao dịch này ngừng lại vì nhiều lý do. Chẳng hạn giao dịch đó có thể bị kẹt trong một khóa “cứng” (deadlock)
Trong trường hợp (1), nhiệm vụ của hệ thống CSDL là phải bảo đảm rằng cho dù b ất kỳ điều gì xảy ra ngay giữa một giao dịch, tác dụng của giao dịch trên CSDL không b ị ảnh hưởng của những biến cố bất ngờ này. Trong trường hợp (2), hệ thống phải bảo đảm rằng giao dịch bị hủy bỏ không ảnh hường gì trên CSDL hoặc các giao dịch khác
Trong thực tế, mỗi giao dịch đều có m ột chuỗi các bước cơ bản như: đọc hay ghi một mục dữ liệu vào CSDL hoặc thực hiện các phép toán số học đơn giản trong vùng làm vi ệc riêng, hoặc những bước sơ đẳng khác như các bước khóa, mở khóa, ủy thác hoàn tất giao dịch… Chúng ta luôn giả sử rằng những bước sở đằng này là nguyên t ử. Thậm chí thao tác tính toán kết thúc sau khi thời gian dành cho nó đã hết cũng có thể xem là nguyên t ử, bởi vì các phép tính toán xảy ra khi đang làm việc trong vùng d ữ liệu cục bộ và không th ể ảnh hưởng đến vùng làm vi ệc đó cho đến khi giao dịch đang thực hiện dở phép tính số học được tái hoạt động trở lại.
3.3.1.2. Mục dữ liệu
Để quản lý các hoạt động đồng thời, CSDL phải được phân nhỏ thành các m ục dữ liệu, đó là những đơn vị dữ liệu cần được truy xuất có điều khiển. Bản chất và kích thước các mục dữ liệu do nhà thiết kế hệ thống chọn lựa. Chẳng hạn trong mô hình dữ liệu quan hệ, chúng ta có thể chọn các mục lớn như các quan hệ, hoặc các mục nhỏ như các bộ hay thành phần của các bộ. Chúng ta cũng có th ể chọn lựa các mục có kích thước trung gian, như một khối của quan hệ. Kích thước của các mục dữ liệu được hệ thống sử dụng gọi là độ mịn của hệ thống. Một hệ thống được gọi là hạt mịn, nếu nó sử dụng các mục dữ liệu nhỏ và hệ thống là hạt thô nếu nó sử dụng các mục dữ liệu lớn.
Phương pháp thông dụng nhất để điều khiển việc truy xuất các mục là sử dụng khóa. Bộ quản lý khóa là thành ph ần của hệ quản trị chịu trách nhiệm theo dõi xem m ột mục I hiện có giao dịch nào đang đọc ghi vào các ph ần của I hay không. Nếu có thì bộ quản lý khóa s ẽ ngăn cản không cho các giao dịch khác truy xuất I trong trường hợp truy xuất đó có thể gây ra xung đột.
Chọn chế độ hạt thô sẽ làm giảm đi tổng chi phí cần để duy trì các khóa, bởi vì chúng ta cần ít chỗ để lưu các khóa, và chúng ta tiết kiệm được thời gian bởi vì hệ thống chỉ phải thực hiện rất ít hành động đóng mở khóa. Tuy nhiện độ hạt mịn cho phép nhiều giao dịch hoạt động song song, bởi vì xác xuất các giao dịch yêu cầu khóa trên cùng m ột mục sẽ thấp.
3.3.1.3. Khóa
Như chúng ta đã khẳng định, khóa là m ột đặc quyền truy xuất trên một mục dữ liệu mà bộ quản lý khóa có th ể trao cho một giao dịch hay thu hồi lại. Có thể có nhiều kiểu khóa, ví dụ như khóa đọc, khóa ghi… Thông thường tại mỗi thời điểm, chỉ có một tập con các mục bị khóa, vì vậy bộ quản lý khóa có thể lưu các khóa hiện hành trong một bảng khóa vơi các mẫu tin: (I, L, T) – giao dịch T có một khóa kiểu L trên mục I.
3.3.1.4. Kiểm soát hoạt động đồng thời bằng khóa
Để thấy được nhu cầu phải sử dụng khóa chúng ta xem xét ví dụ sau đây:
Xét hai giao dịch T1 và T2. Mỗi giao dịch truy xuất một mục dữ liệu A được giả sử là mang giá trị nguyên, rồi cộng thêm 1 vào A. hai giao d ịch này thực hiện chương trình P.
P: Begin Read A
A=A+1
Write A
End
Chúng ta thực hiện hai giao dịch T1 và T2 như sau:
Giá trị của A tồn tại trong CSDL, với mỗi giao dịch P đọc A vào vùng làm việc, cộng 1 vào giá trị này rồi ghi kết quả vào trong CSDL. Chúng ta nh ận thấy rằng, mặc dù hai giao d ịch đều đã cộng thêm 1 vào A, giá tr ị của A trong CSDL chỉ tăng 1.
Giải pháp thông dụng nhất cho vấn đề được trình bày trong ví dụ trên là cung c ấp một khóa trên A. Trước khi đọc A, một giao dịch T phải khóa A lại, ngăn cản không cho giao dịch khác truy xuất A cho đến khi T hoàn tất xong thao tác trên A. Hơn nữa T khóa được mục A chỉ khi trước đó A không bị khóa bởi một giao dịch khác. Nếu A đã bị khóa, T phải đợi đến khi giao dịch mở khóa cho A.
Vậy để ngăn cản những trường hợp đáng tiếc xẩy ra ta phải dùng khóa. Như vậy trong những chương trình giao dịch phải có khóa và mở khóa. Ta giả sử rằng một khóa phải được đặt trên một mục trước khi đọc hay ghi nó, và thao tác khóa hành động như một hàm đồng bộ hóa. Nghĩa là nếu một giao dịch khóa một mục đã được khóa, nó không thể tiến hành cho đến khi khóa này được giải phóng b ằng một lệnh mở khóa được thực hiện bởi giao dịch đang giữ khóa. Ta cũng giả sử rằng mỗi giao dịch đều có thể mở được mọi khóa do chính nó khóa. Một lịch biểu chứa cá thao tác cơ bản của nhiều giao dịch tuân theo các quy tắc của khóa được gọi là hợp lệ.
Ví dụ:
Chương trình P của ví dụ trên được viết lại với các khóa như sau:
P: begin Lock A Read A A=A+1
Write A
Unlock A
End
Giả sử T1 và T2 là hai giao d ịch thực hiện P. Nếu T1 bắt đầu trước, nó yêu cầu khóa trên A. Giả sử rằng không có giao dịch nào đang khóa, bộ quản lý khóa sẽ cho nó khóa mục A. Bây giờ chỉ có T1 mới có thể truy xuất A, nếu T2 bắt đầu trước khi T1 chấm dứt thì khi T2 thực hiện lệnh khóa A, hệ thống buộc T2 phải đợi. Chi khi T1 thực hiện lệnh Unlock A, hệ thống mới cho phép T2 tiến hành. Kết quả là điều bất thường không xảy ra; T1 hoặc T2 sẽ hoàn tất trước khi giao dịch kia bắt đầu, và kết quả chung của chúng là cộng 2 vào A.
3.3.1.5. Khóa sống (livelock)
Hệ thống quản lý khóa trao và buộc khóa các mục dữ liệu không thể hoạt động một cách tùy tiện. Giả sử trong ví dụ trên, khi T1 giải phóng khóa trên A, trong khi T2 đang đợi nhận khóa, một giao dịch T3 khác cùng xin m ột khóa trên A, và T3 được trao khóa này trước T2. Tương tự sau khi T3 mở khóa cho A thì lại có giao dịch T4 xin khóa A… Và rất có thể T2 phải đợi rất lâu hoặc không bao gi ờ nhận được khóa trên A.
Tình huống này gọi là khóa s ống. Vậy khóa sống trên mục A của giao dịch T là T không khóa được A vì A luôn bị khóa bởi một giao dịch khác. Rất nhiều giải pháp đã được các nhà thiết kế hệ điều hành đề xuất để giải quyết vấn đề khóa sống, ví dụ như các giao dịch khi khóa m ột mục phải đăng ký thứ tự, và bộ quản lý khóa sẽ lần lượt trao quyền khóa mục A khi mục này không b ị khóa theo thứ tự đã xác định trước.
3.3.1.6. Khóa “cứng” (deadlock)
Một vấn đề khác có thể xẩy ra trong điều khiển các hoạt động đồng thời, đó là vấn đề khóa “cứng” (deadlock). Đó là các giao d ịch khóa chéo lẫn nhau các mục cần để hoàn thiện giao dịch.
Ví dụ:
Giả sử chúng ta có hai giao dịch đồng thời T1 và T2 như sau:
Giả sử T1 và T2 được thực hiện cùng lúc. T1 yêu c ầu khóa A và được trao quyền khóa trên A, còn T2 yêu c ầu và được trao quyền khóa trên B. Do đó khi T1 yêu cầu khóa trên B thì nó phải đợi vị T2 đã khóa B. T ương tự khi T2 yêu cầu khó trên A, nó c ũng buộc phải đợi vì T1 đã khóa A. K ết quả là không m ột giao dịch nào tiếp tục hoạt động được, mỗi giao dịch đều phải đợi cho giao dịch kia mở khóa, và chúng đều phải đợi nhưng chẳng bao giờ nhận được khó như yêu cầu.
Như vậy khóa “cứng” là một tình huống mà trong đó mỗi thành viên T i của một tập giao dịch T
= {T1, T2,…, TN} đang đợi nhận khóa của một mục hiện đang bị khóa bởi một giao dịch khác trong tập T. Bởi vì mỗi giao dịch trong tập T đều đang đợi, nói không thể mở khóa cho mục mà một giao dịch khác đang cần, vì vậy tất cả vẫn tiếp tục đợi mãi mãi.
Một số giải pháp cho vấn đề khóa “cứng”:
1. Yêu cầu các giao dịch phải đưa tất cả mọi yêu cầu khóa cùng m ột lúc, và bộ quản lý khóa trao tất cả các khóa cho chúng nếu được, hoặc không trao và cho giao dịch này đợi nếu một hay nhiều khóa đang được giữ bởi một giao dịch khác.
2. Gán một thứ tự tuyến tính cho các mục, buộc tất cả các giao dịch phải xin khóa theo thứ tự
này.
Một cách khác nhằm xử lý các khóa “cứng” là không ngăn cản chúng. Và cứ sau mỗi khoảng thời gian nhất định ,hệ thống sẽ kiểm tra yêu cầu khóa và tìm xem có xảy ra khóa “cứng” hay không. N ếu chúng ta sử dụng đồ thị chờ đợi, với các nút là cá giao d ịch và các cung T1 ® T2 biểu thị cho T2 đang đợi nhận khóa trên một mục đang được T1 giữ. Thế thì mỗi chu trình trong đồ thị chờ sẽ biểu thị cho một khóa “cứng”, và nếu không có chu trình thì kết luật là không có khóa “cứng”. Nếu một khóa “cứng” được phát hiện, thì hệ thống phải khởi động lại và các tác d ụng trên CSĐL của giao dịch khóa “cứng” đó phải bỏ đi. Quá trình hủy bỏ và tái kh ởi động có thể gặp rắc rối nếu chúng ta không biết được cách thức các giao dịch ghi vào CSDL trước khi chúng hoàn
thành.
3.3.1.7. Tính khả tuần tự của lịch biểu.
Giả sử chúng ta có một tập các giao dịch T = {T1, T2,…, TN}. Chúng ta th ấy ngay rằng nếu các giao dịch thực hiện tuần tự theo một thứ tự nào đó, giao dịch nọ nối tiếp giao dịch kia thì các sự cố tranh chấp chắc chắn không xẩy ra và trong CSDL chúng ta có m ột kết quả nào đó.
Giả sử chúng ta có tập giao dịch T = {T1, T2,…, TN}, tương ứng với T ta có N! các lịch biểu tuần tự khác nhau. Bởi vậy chúng ta giả sử rằng hoạt động của các giao dịch đồng thời là đúng đắn nếu và chỉ nếu tác dụng cảu nó giống như tác dụng có được của một lịch biểu tuần tự.
Chúng ta định nghĩa một lịch biểu S cho một tập cá giao dịch T là thứ tự (có thể xen kẽ) các bước cơ bản của các giao dịch (khóa, đọc, ghi, …) được thực hiện.
Các bước của một giao dịch đã cho phải xuất hiện trong lịch biểu theo đúng thứ tự xảy ra trong giao dịch đó.
Vậy một lịch biểu S của tập giao dịch T được gọi là hợp lệ và đúng đắn nếu các bước cơ bản
của một giao dịch Ti đã cho phải xuất hiện trong lịch biểu S theo đúng thứ tự xảy ra trong giao dịch
Ti và các bước cơ bản của các giao dịch tuân theo các quy tắc của khóa.
Một lịch biểu S của các giao dịch trong T là một hoán vị của các bước cơ bản của Ti Î T. Giả sử trong T có k bước cơ bản nên chúng ta có k! hoán v ị khác nhau của các bước cơ bản. Vậy với tập giao dịch T ta có k! lịch biểu S khác nhau. Tuy nhiên trong số đó có nhiều lịch biểu vô nghĩa và không đúng đắn hoặc không hợp lệ.
Việc quản lý các giao dịch là quản lý các lịch biểu đúng đắn và hợp lệ tương đơn với một lịch biểu tuần tự nào đó. Lịch biểu được gọi là khả tuần tự nếu tác dụng của nó giống với tác dụng của một lịch biểu tuần tự ngược lại gọi là bất khả tuần tự.
Hai lịch biểu được gọi là tương đương nếu chúng cho kết quả giống nhau.
3.3.1.8. Bộ xếp lịch
Chúng ta nh ận thấy rằng khi thực hiện hoạt động đồng thời các giao dịch có thể gây ra t ình trạng khóa sống, khóa “cứng” và vấn đề bất khả tuần tự. Để loại bỏ những vấn đền này, chúng ta s ẽ dùng b ộ xép lịch và các nghi th ức.
Bộ xếp lịch là thành ph ần của hệ thống CSDL, có vai trò làm tr ọng tài phân x ử các yêu cầu đang có xung đột. Chẳng hạn chúng ta đã biết cách loại bỏ khác sống của một bộ xép lịch “đến trước phục vụ trước”. Một bộ xếp lịch cũng có thể xử lý các khóa “cứng” và tính bất khả tuần tự bằng cách”
1. Buộc một giao dịch phải đợi, chẳng hạn cho đến khi khóa đang được yêu cầu phải giải phóng.
2. Buộc một giao dịch ngừng lại và tái kh ởi động.
3.3.1.9. Nghi thức
Chúng ta c ũng có thể sử dụng một công cụ khác để xử lý khóa gài và tính bất khả tuần tự. Công cụ đó là các nghi th ức mà tất cả các giao dịch phải tuân theo.
Một nghi thức, theo nghĩa tổng quát nhất, chỉ là một hạn chế trên chuỗi các bước cơ bản mà một giao dịch có thể thực hiện.
3.3.2. Mô hình giao dịch đơn giản
3.3.2.1. Ý nghĩa của giao dịch – hàm đặc trưng
Về nguyên tắc, ý nghĩa của giao dịch Ti chính là tác dụng của chương trình P tương ứng trên CSDL. Về hình thức, chúng ta gán một hàm f đặc trưng cho mỗi cặp Lock A và Unlock A.
Hàm f nhận đối là các giá tr ị của tất cả các mục bị khóa bởi giao dịch T trước khi mở khóa cho A, và giá tr ị của f là giá tr ị mới của A sau khi mở khóa A. Chú ý rằng một giao dịch có thể có nhiều hàm như thế đối với một mục A, bởi vì chúng ta có th ể khóa và mở khóa một mục A nhiều lần.
Vậy gọi A0 là giá tr ị ban đầu của A trước khi các giao dịch bắt đầu thực hiện, như vậy giá trị của hàm f(A0,….) sau khi Unlock A là giá trị mới của A. Một cách tổng quát gọi A là giá tr ị của mục A
trước khi lock A thì giá trị mới của A sau khi Unlock A là f(A,…) ta ký hiệu: lock A….unlock A
f(A,…).
Các giá tr ị mà A có th ể nhận trong khi thực hiện giao dịch là những công thức được xây dựng bằng cách áp dụng những hàm này cho các giá tr ị ban đầu của các mục.
Hai công thức khác nhau được coi là những giá trị khác nhau. Hai lịch biểu là tương đương nếu các công thức cho giá trị cuối cùng của mỗi mục giống nhau trong cả hai lịch biểu.
Ta xét ví dụ sau:
Chúng ta có ba giao dịch và những hàm đặc trưng có liên quan với mỗi cặp Lock – Unlock; là những hàm xuất hiện trên cùng m ột dòng v ới Unlock. Chẳng hạn f1, nhận A và B làm đối số, bởi vậy là những mục trong Lock A – Unlock A của T1. Hàm f3 chỉ nhận B và C làm đối số bởi vì T2 mở khóa B, và trong Lock B – Unlock B có B và C.
Hình sau trình bày một lịch biểu của những giao dịch này và tác d ụng của chúng trên các m ục A, B, và C.
Ký hiệu:
(i) = f4(f1(A0,f3(B0,C0)),B0,C0)
(ii) = f5(f1(A0,f3(B0,C0)),B0,C0)
(iii) = f6((ii), (i))
(iv) = f7((ii),(i))
Chúng ta có th ể nhận xét rằng lịch biểu này là không có đặc tính khả tuần tự. Thật vậy, giả sử rằng nó khả tuần tự. Thế thì nếu T1 thực hiện trước T2 trong lịch biểu tuần tự, giá trị cuối cùng c ủa B sẽ là: f3(f2(A0,B0),C0) chứ không phải f2(A0, f3(B0,C0)).
Chúng ta th ấy rằng giả thiết các công thức của hàm f sinh ra một giá trị duy nhất là mấu chốt lập luận, thật vậy điều gì sẽ xẩy ra chẳng hạn nếu tồn tại:
f3(f2(A0,B0),C0) = f3(A0,f3(B0,C0))
Trong trường hợp này chúng ta k hông thể kết luận lịch biểu bất khả tuần tự được.
Cần lưu ý rằng phép kiểm tra tính khả tuần tự bằng hàm đặc trưng là một phương pháp phức tạp với những tập nhiều giao dịch và nhiều thao tác. hơn nữa phép kiểm tra này là một phương pháp
yếu vì hai công thức của các hàm đặc trưng có thể khác nhau nhưng giá trị của chúng có thể giống nhau.
3.3.2.2. Kiểm tra tính khả tuần tự bằng đồ thị có hướng.
Để xác định rằng một bộ xếp lịch nào đó là đúng, chúng ta phải chứng minh rằng mỗi lịch biểu S được nó cho phép đều có đặc tính khả tuần tự. Vì vậy chúng ta cần có một phép kiểm tra đơn giản về tính khả tuần tự của một lịch biểu.
Thuật toán 3.3. Kiểm tra tính khả tuần tự một lịch biểu S Vào: Một lịch biểu S của một tập các giao dịch T1, T2,…, Tk
Ra: Khẳng định S có khả tuần tự hay không. Nếu có thì đưa ra một lịch biểu tuần tự tương đương với S.
Phương pháp:
Xây dựng một đồ thị có hướng G (được gọi là đồ thị tuần tự hóa) có các nút là các giao d ịch Ti. Để xác định các cung của đồ thị G, gọi (a1, a2,…, aN) là tập các bước cơ bản trong S. Trong đó mỗi ai là một thao tác có dạng
Tj: Lock A hoặc Tj: Unlock A
Nếu aj là thao tác ki ểu Unlock A thì tìm thao tác ap kế tiếp sau aj có d ạng Ts: Lock A. Nếu có một cặp thao tác như thế và s ¹ j, chúng ta v ẽ một cung từ Tj đến Ts (Tj ® Ts). Cung này có ý ngh ĩa là trong một lịch biểu tuần tự tương đương với S, Tj phải thực hiện trước trước Ts.
Nếu G có một chu trình thì S là bất khả tuần tự, ngược lại nếu G không có chu trình thì S là khả tuần tự và chúng ta tìm một thứ tự tuyến tính cho các giao dịch cho Ti bằng một quá trình gọi là sắp xếp topo của đồ thị G như sau:
Sắp xếp Topo đồ thị có hướng G không có chu trình
Ta biết rằng trong G phải có một nút Tj nào đó không có cung đến, nếu không G có một chu trình. Liệt kê Tj rồi loại Tj ra khỏi G. Sau đó lặp lại quá trình này trên đồ thị còn l ại cho đến khi không còn nút nào n ữa. Thứ tự các nút được liệt kê trong danh sách là m ột thứ tự tuần tự của các giao dịch. Thứ tự đó tạo nên lịch biểu tuần tự tương dương với S.
3.3.3. Nghi thức khóa 2 pha
Chúng ta c ần phải hiểu rõ nh ững điều kiện để một lịch biểu là khả tuần tự nhằm tìm được một bộ xếp lịch và một nghi thức, đảm bảo rằng mọi lịch biểu mà chúng ta cho phép đều khả tuần tự.
Nghi thức được gọi là nghi thức hai phai, nếu mọi giao dịch thực hiện tất cả các thao tác khóa trước tất cả các thao tác mở khóa. Các giao dịch tuân thủ theo nghi thức này được gọi là các giao dịch hai pha: pha đầu là khóa và pha th ứ hai là pha mở khóa.
Nghi thức hai pha có đặc điểm là mọi tập giao dịch tuân theo nghi thức này đều có các lịch biểu khả tuần tự. Trước tiên chúng ta s ẽ chứng minh rằng nghi thức hai pha bảo đảm được tính khả tuần tự.
Định lý 3.1. Nếu S là một lịch biểu của các giao dịch hai pha thì S là khả tuần tự.
Chứng minh:
Giả sử khẳng định trên không đúng. Vậy đồ thị G của lịch biểu S sẽ có một chu trình
Ti1 ® Ti2 ®…. ® Tin ® Ti1
Do đó có một thao tác khóa do Ti2 sẽ đi sau một thao tác mở khóa do Ti1, một thao tác kho do
Ti3 sẽ đi sau một thao tác mở khóa Ti2… Cuối cùng m ột thao tác khóa Ti1 sẽ đi sau một thao tác mở
khóa T i1. Điều này mâu thu ẫn với giả thiết Ti1 là giao dịch hai pha.
Vậy khẳng định trên là đúng.
3.3.4. Mô hình khóa đọc và khóa ghi
Nếu chúng ta phân biệt một truy xuất chỉ đọc và một truy xuất đọc – ghi, chúng ta có th ể phát triển một mô hình chi tiết hơn cho các giao dịch loại đọc ghi này. Trong một số trường hợp mô hình này cho phép s ử dụng một số hoạt động đồng thời bị cấm ví dụ như nhiều giao dịch có thể cùng gi ữ khóa đọc một mục A.
Chúng ta phân bi ệt hai loại khóa.
1. Khóa đọc Rlock. Một giao dịch T chỉ đọc một mục A sẽ thực hiện lệnh Rlock A, ngăn không cho bất kỳ giao dịch khác ghi giá trị mới lên A, tuy nhiên các giao d ịch khác vẫn có thể giữ một khóa đọc trên A cùng lúc v ới T.
2.Khóa ghi Wlock. Khi m ột giao dịch muốn thay đổi giá trị của mục A đầu tiên sẽ lấy khóa ghi bằng cách thực hiện lệnh Wlock A, khi một giao dịch đang giữ khóa ghi trên một mục, những giao dịch khác không thể lấy được khóa đọc hoặc khóa ghi trên mục đó.
Như vậy khóa đọc mục A chỉ cám các giao dịch khác ghi dữ liệu vào a, còn khóa ghi trên m ục cấm các giao dịch khác cả ghi hoặc đọc mục A.
3.3.4.1. Ý ngh ĩa của giao dịch với khóa đọc và khóa ghi
Chúng ta gi ả sử mỗi lần áp dụng khóa ghi cho một mục A sẽ có một hàm duy nhất đi kèm với khóa đó và nó tạo ra một giá trị mới cho A; hàm đó phụ thuộc vào tất cả các mục bị khóa trước khi mở khóa A. Tuy nhiên chúng ta gi ả sử rằng một khóa đọc trên A không làm thay đổi A.
Giả sử rằng mục A có một giá trị ban đầu A0 và tác d ụng của một lịch biểu trên CSDL có th ể được diễn tả bằng những công thức của các hàm đặc tưng f, là những giá trị của mỗi mục được ghi ít nhất là một lần bởi các giao dịch. Tuy nhiên vì có thể có một giao địch đọc các mục nhưng không ghi gì hoặc đọc một số mục chỉ sau khi ghi vào lần cuối cùng, vì thế những giá trị mà mỗi mục đang có khi m ột giao dịch chỉ đọc nó cũng được xử lý như giá trị cũ. Vì vậy chúng ta có thể nói hai lịch biểu là tương đương nếu:
1. Chúng sinh ra cùng giá tr ị cho mỗi mục.
2. Mỗi khóa đọc được áp dụng bởi mỗi giao dịch trong cả hai lịch biểu vào những lúc mục bị khóa có cùng giá tr ị.
3.3.4.2. Đồ thị tuần tự hóa trong các giao dịch Rlock và Wlock
Chúng ta xét nh ững điều kiện mà trong đó, từ ý nghĩa của các giao dịch và các l ịch biểu, ta có thể suy ra được khi nào một giao dịch phải đi trước một giao dịch khác trong một lịch biểu tuần tự tương đương. Giả sử rằng có một lịch biểu S trong đó một khóa ghi mục A bởi giao dịch T1, và gọi f là hàm đi kèm với khóa ghi đó. Sau khi T1 mở khóa A, gọi T2 là một trong những giao dịch kế tiếp nhận khóa đọc A trước khi một giao dịch khác nhân khóa ghi A. Chắc chắn rằng T1 phải thực hiện trước T2 trong một lịch biểu tuần tự tương đương với S. Nếu không thì T2 đọc một tía trì của A không ch ứa hàm f. Tương tự, nếu T3 là giao dịch kế tiếp sau T1 nhận khóa ghi A thì T1 phải thực hiện trước T3.
Bây giờ ta giả sử rằng T4 là một giao dịch nhận khóa đọc A trước khi T1 khóa ghi A. N ếu T1 xuất hiện trước T4 trong lịch biểu tuần tự thì T4 đọc một giá trị của A có chứa hàm f, còn trong l ịch biểu S, giá trị được đọc bởi T4 không ch ứa f. Vì vậy, T4 phải thực hiện trước T1 trong một lịch biểu tuần tự tương đương với S. Suy luận duy nhất không thê thực hiện được là nếu trong S hai giao dịch cùng nh ần khóa đọc một mục A theo một thứ tự nào đó thì những giao dịch này phải xuất hiện theo thứ tự đó trong một lịch biểu tuần tự. Đúng ra thứ tự tương đối này là c ủa các khóa đọc không tạo ra sẹ khác biệt nào trên các giá tr ị được tạo ra bởi các giao dịch thực hiện đồng thời.
Thuật toán 3.4. Kiểm tra tính khả tuần tự của các lịch biểu với các khóa đọc/ghi.
Vào: Một lịch biểu S cho một tập các giao dịch T1, T2,…, TN
Ra: Khẳng định S có khả tuần tự hay không, nếu được sẽ đưa ra một lịch biểu tuần tự tương ứng.
Phương pháp:
Chúng ta xây d ựng một đồ thị G như sau. Các nút tương ứng là các giao dịch. Các cung được xác định bằng quy tắc sau:
1. Giả sử trong S, giao dịch Ti nhận khóa đọc hoặc khóa A. Tj là giao dịch kế tiếp khóa ghi A, và i ¹ j. Khi đó chúng ta đặt một cung từ Ti đến Tj.
2. Giả sử trong S, giao dịch Ti khóa ghi A. G ọi Tm với m ¹ i là một giao dịch khác khóa đọc A sau khi Ti mở khóa A những trước các giao dịch khác khóa ghi A. Chúng ta vẽ mộ cung từ Ti đến
Tm.
Nếu G có chu trình thi S là bất khả tuần tự, ngược lại thì một sắp xếp topo của G là thứ tự tuần tự cho các giao dịch này.
Được cập nhật: hôm kia lúc 16:15:51 | Lượt xem: 1825
