Hệ quản trị cơ sở dữ liệu - Chương 4: Giao dịch

 là khả tuần tự. Để làm điều đó, trước tiên ta phải biết làm thế nào để xác định, với 
một lịch trình cụ thể đã cho, có là khả tuần tự hay không. 
KIỂM THỬ TÍNH KHẢ TUẦN TỰ XUNG ĐỘT 
Giả sử S là một lịch trình. Ta xây dựng một đồ thị định hướng, được gọi là đồ thị trình 
tự (precedence graph), từ S. Đồ thị gồm một cặp (V, E) trong đó V là tập các đỉnh và E là tập các 
cung. Tập các đỉnh bao gồm tất cả các giao dịch tham gia vào lịch trình. Tập các cung bao gồm tất 
cả các cung dạng Ti → Tj sao cho một trong các điều kiện sau được thoả mãn: 
1. Ti thực hiện Write(Q) trước Tj thực hiện Read(Q). 
2. Ti thực hiện Read(Q) trước khi Tj thực hiện Write(Q). 
3. Ti thực hiện Write(Q) trước khi Tj thực hiện Write(Q). 
Nếu một cung Ti → Tj tồn tại trong đồ thị trình tự, thì trong bất kỳ lịch trình tuần tự S’ nào 
tương đương với S, Ti phải xuất hiện trước Tj . 
Đồ thị trình tự đối với schedule-1 là: T1 T2 vì tất cả các chỉ thị của 
T1 được thực hiện trước chỉ thị đầu tiên của T2
Đồ thị trình tự đối với schedule-2 là: T2 T1 vì tất cả các chỉ thị của 
T2 được thực hiện trước chỉ thị đầu tiên của T1 
Đồ thị trình tự đối với schedule-4 chứa các cung T1 → T2 vì T1 thực hiện Read(A) trước 
T2 thực hiện Write(A). Nó cũng chứa cung T2 → T1 vì T2 thực hiện Read(B) trước khi T1 thực 
hiện Write(B): 
 T1 T2 
CHƯƠNG IV GIAO DỊCH Trang 88
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
Nếu đồ thị trình tự đối với S có chu trình, khi đó lịch trình S không là khả tuần tự xung 
đột. Nếu đồ thị không chứa chu trình, khi đó lịch trình S là khả tuần tự xung đột. Thứ tự khả tuần 
tự có thể nhận được thông qua sắp xếp topo (topological sorting), nó xác định một thứ tự tuyến 
tính nhất quán với thứ tự bộ phận của đồ thị trình tự. Nói chung, có một vài thứ tự tuyến tính có 
thể nhận được qua sắp xếp topo. Ví dụ, đồ thị sau: 
 Ti 
 Tj Tk 
 Tm 
Có hai thứ tự tuyến tính chấp nhận được là: 
 Ti Ti 
 Tj Tk 
 Tk Tj 
 Tm Tm 
figure IV- 18 
Như vậy, để kiểm thử tính khả tuần tự xung đột, ta cần xây dựng đồ thị trình tự và gọi 
thuật toán phát hiện chu trình. Ta nhận được một sơ đồ thực nghiệm để xác định tính khả tuần tự 
xung đột. Như ví dụ, schedule-1 và schedule-2, đồ thị trình tự của chúng không có chu trình, do 
vậy chúng là các chu trình khả tuần tự xung đột, trong khi đồ thị trình tự của schedule-4 chứa 
chu trình do vậy nó không là khả tuần tự xung đột. 
KIỂM THỬ TÍNH KHẢ TUẦN TỰ VIEW 
Ta có thể sửa đổi phép kiểm thử đồ thị trình tự đối với tính khả tuần tự xung đột dể kiểm 
thử tính khả tuần tự view. Tuy nhiên, phép kiểm thử này phải trả giá cao về thời gian chạy. 
Xét lịch trình schedule-9, nếu ta tuân theo quy tắc trong phép kiểm thử tính khả tuần tự 
xung đột để tạo đồ thị trình tự, ta nhận được đồ thị sau: 
 T3 T4 
 T6 
figure IV- 19 
Đồ thị này có chu trình, do vậy schedule-9 không là khả tuần tự xung đột. Tuy nhiên, đã 
đã thấy nó là khả tuần tự view (do nó tương đương với lịch trình tuần tự ). 
CHƯƠNG IV GIAO DỊCH Trang 89
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
Cung T3 →T4 không được xen vào đồ thị vì các giá trị của hạng mục Q được sản sinh bởi T3 và T4 
không được dùng bởi bất kỳ giao dịch nào khác và T6 sản sinh ra giá trị cuối mới của Q. Các chỉ 
thị Write(Q) của T3 và T4 được gọi là các Write vô dụng (Useless Write). Điều trên chỉ ra rằng 
không thể sử dụng đơn thuần sơ đồ đồ thị trình tự dể kiểm thử tính khả tuần tự view. Cần thiết 
phát triển một sơ đồ cho việc quyết định cung nào là cần phải xen vào đồ thị trình tự. 
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 
a. Nếu Ti = Tb và Tj ≠ Tf, khi đó xen cung Tj →0 Tk vào đồ thị trình tự gán 
nhãn 
b. Nếu Ti ≠ Tb và Tj = Tf khi đó xen cung Tk →0 Ti vào đồ thị trình tự gán 
nhãn 
c. 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à: 
 T3 
 0 0 
 Tb Tf 
 T4 
CHƯƠNG IV GIAO DỊCH Trang 90
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
Đồ 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) : 
 T3 
 0 0 
 Tb 0 0 Tf 
 T4 
Đồ thị trình tự gán nhãn của schedule-9 là: 
 T3 
 0 0 
 0 
 Tb T4 Tf 
 0 0 
 T6 
figure IV- 20 
Cuối cùng, ta xét lịch trình schedule-10: 
 T3 T3 T7 
 Read(Q) 
 Write(Q) 
 Read(Q) 
 Write(Q) 
 Write(Q) 
Đồ thị trình tự gán nhãn của schedule-10 là: 
 T3 
 0 0 
CHƯƠNG IV GIAO DỊCH Trang 91
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
 0 1 1 
 Tb T4 Tf 
 0 0 
 T7 
figure IV- 21 
Đồ 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à: 
 T3 
 0 0 
 0 1 
 Tb T4 Tf 
 0 0 
 T7 
 T3 
 0 0 
 0 1 
 Tb T4 Tf 
 0 0 
 T7 
figure IV- 22 
Đồ thị thứ nhất không chứa chu trình, do vậy lịch trình là khả tuần tự view. 
CHƯƠNG IV GIAO DỊCH Trang 92
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
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.2 Trong 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.4 Xé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 
a. 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. 
b. 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. 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.5 Do 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? 
CHƯƠNG IV GIAO DỊCH Trang 93
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
IV.6 Xét đồ thị trình tự sau: 
 T1 T2 
 T4 T3 
 T5 
 Lịch trình tương ứng là khả tuần tự xung đột không? Giải thích 
IV.7 Xét đồ thị trình tự gán nhãn sau: 
 0 
 Tb 0 T1 0 T2 
 0 1 1
 0 
 T3 0 T4 0 
 0 
 Tf 
 Lịch trình tương ứng là khả tuần tự view không? Giải thích. 
IV.8 Lị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.9 Lịch trình cascadeless là gì? Tại sao cần thiết tính cascadeless của lịch trình? 
CHƯƠNG IV GIAO DỊCH Trang 94
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
CHƯƠNG IV GIAO DỊCH Trang 95