HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
khởi động sau sự cố. Sau hhi các thông tin sau cùng này được viết lên đĩa, giao dịch chuyển sang
trạng thái committed.
Biểu đồ trạng thái tương ứng với một giao dịch như sau:
Partially Committed
Committed
Active
Failed Aborted
figure IV- 2
Với giả thiết sự cố hệ thống không gây ra sự mất dữ liệu trên đĩa, Một giao dịch đi vào
trạng thái Failed sau khi hệ thống xác định rằng giao dịch không thể tiến triển bình thường được
nữa (do lỗi phần cứng hoặc phần mềm). Như vậy, giao dịch phải được cuộn lại rồi chuyển sang
trạng thái bỏ dở. Tại điểm này, hệ thống có hai lựa chọn:
• Khởi động lại giao dịch, nhưng chỉ nếu giao dịch bị bở dở là do lỗi phần cứng hoặc
phần mềm nào đó không liên quan đến logic bên trong của giao dịch. Giao dịch được
khởi động lại được xem là một giao dịch mới.
• Giết giao dịch thường được tiến hành hoặc do lỗi logic bên trong giao dịch, lỗi này cần
được chỉnh sửa bởi viết lại chương trình ứng dụng hoặc do đầu vào xấu hoặc do dữ liệu
mong muốn không tìm thấy trong CSDL.
Ta phải thận trọng khi thực hiện viết ngoài khả quan sát (observable external Write - như
viết ra terminal hay máy in). Mỗi khi một viết như vậy xẩy ra, nó không thể bị xoá do nó có thể
phải giao tiếp với bên ngoài hệ CSDL. Hầu hết các hệ thống cho phép các viết như thế xẩy ra chỉ
khi giao dịch đã di vào trạng thái committed. Một cách để thực thi một sơ đồ như vậy là cho hệ
CSDL lưu trữ tạm thời bất kỳ giá trị nào kết hợp với các viết ngoài như vậy trong lưu trữ không
hay thay đổi và thực hiện các viết hiện tại chỉ sau khi giao dịch đã đi vào trạng thái committed.
Nếu hệ thống thất bại sau khi giao dịch đi vào trạng thái committed nhưng trước khi hoàn tất các
viết ngoài, hệ CSDL sẽ làm các viết ngoài này (sử dụng dữ liệu trong lưu trữ không hay thay đổi)
khi hệ thống khởi động lại.
Trong một số ứng dụng, có thể muốn cho phép giao dịch hoạt động trình bày dữ liệu cho
người sử dụng, đặc biệt là các giao dịch kéo dài trong vài phút hay vài giờ. Ta không thể cho phép
xuất ra dữ liệu khả quan sát như vậy trừ phi ta buộc phải làm tổn hại tính nguyên tử giao dịch.
Hầu hết các hệ thống giao dịch hiện hành đảm bảo tính nguyên tử và do vậy cấm dạng trao đổi
với người dùng này.
THỰC THI TÍNH NGUYÊN TỬ VÀ TÍNH BỀN VỮNG
Thành phần quản trị phục hồi của một hệ CSDL hỗ trợ tính nguyên tử và tính bền vững.
Trước tiên ta xét một sơ đồ đơn giản (song cực kỳ thiếu hiệu quả). Sơ đồ này giả thiết rằng chỉ
một giao dịch là hoạt động tại một thời điểm và được dựa trên tạo bản sao của CSDL được gọi là
CHƯƠNG IV GIAO DỊCH
Trang
76
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
các bản sao bóng (shadow copies). Sơ đồ giả thiết rằng CSDL chỉ là một file trên đĩa. Một con trỏ
được gọi là db_pointer được duy trì trên đĩa; nó trỏ tới bản sao hiện hành của CSDL.
Trong sơ đồ CSDL bóng (shadow-database), một giao dịch muốn cập nhật CSDL, đầu tiên
tạo ra một bản sao đầy đủ của CSDL. Tất cả các cập nhật được làm trên bản sao này, không đụng
chạm tới bản gốc (bản sao bóng). Nếu tại một thời điểm bất kỳ giao dịch bị bỏ dở, bản sao mới
bị xoá. Bản sao cũ của CSDL không bị ảnh hưởng. Nếu giao dịch hoàn tất, nó được được bàn giao
(committed) như sau. Đầu tiên, Hỏi hệ điều hành để đảm bảo rằng tất cả các trang của bản sao
mới đã được viết lên đĩa (flush). Sau khi flush con trỏ db_pointer được cập nhật để trỏ đến bản
sao mới; bản sao mới trở thành bản sao hiện hành của CSDL. Bản sao cũ bị xoá đi. Giao dịch
được gọi là đã được được bàn giao (committed) tại thời điểm sự cập nhật con trỏ db_pointer được
ghi lên đĩa. Ta xét kỹ thuật này quản lý sự cố giao dịch và sự cố hệ thống ra sao? Trước tiên, ta
xét sự cố giao dịch. Nếu giao dịch thất bại tại thời điểm bất kỳ trước khi con trỏ db_pointer được
cập nhật, nội dung cũ của CSDL không bị ảnh hưởng. Ta có thể bỏ dở giao dịch bởi xoá bản sao
mới. Mỗi khi giao dịch được được bàn giao (committed), tất cả các cập nhật mà nó đã thực hiện là
ở trong CSDL được trỏ bởi db_pointer. Như vậy, hoặc tất cả các cập nhật của giao dịch đã được
phản ánh hoặc không hiệu quả nào được phản ánh, bất chấp tới sự cố giao dịch. Bây giờ ta xét sự
cố hệ thống. Giả sử sự cố hệ thống xảy ra tại thời điểm bất kỳ trước khi db_pointer đã được cập
nhật được viết lên đĩa. Khi đó, khi hệ thống khởi động lại, nó sẽ đọc db_pointer và như vậy sẽ
thấy nội dung gốc của CSDL – không hiệu quả nào của giao dịch được nhìn thấy trên CSDL. Bây
giờ lại giả sử rằng sự cố hệ thống xảy ra sau khi db_pointer đã được cập nhật lên đĩa. Trước khi
con trỏ được cập nhật, tất cả các trang được cập nhật của bản sao mới đã được viết lên đĩa. Từ giả
thiết file trên đĩa không bị hư hại do sự cố hệ thống. Do vậy, khi hệ thống khởi động lại, nó sẽ đọc
db_pointer và sẽ thấy nội dung của CSDL sau tất cả các cập nhật đã thực hiện bởi giao dịch. Sự
thực thi này phụ thuộc vào việc viết lên db_pointer, việc viết này phải là nguyên tử, có nghĩa là
hoặc tất cả các byte của nó được viết hoặc không byte nào được viết. Nếu chỉ một số byte của con
trỏ được cập nhật bởi việc viết nhưng các byte khác thì không thì con trỏ trở thành vô nghĩa và cả
bản cũ lẫn bản mới của CSDL có thể tìm thấy khi hệ thống khởi động lại. May mắn thay, hệ thống
đĩa cung cấp các cập nhật nguyên tử toàn bộ khối đĩa hoặc ít nhất là một sector đĩa. Như vậy hệ
thống đĩa đảm bảo việc cập nhật con trỏ db_pointer là nguyên tử. Tính nguyên tử và tính bền
vững của giao dịch được đảm bảo bởi việc thực thi bản sao bóng của thành phần quản trị phục
hồi. Sự thực thi này cực kỳ thiếu hiệu quả trong ngữ cảnh CSDL lớn, do sự thực hiện một giao
dịch đòi hỏi phải sao toàn bộ CSDL. Hơn nữa sự thực thi này không cho phép các giao dịch thực
hiện đồng thời với các giao dịch khác. Phương pháp thực thi tính nguyên tử và tính lâu bền mạnh
hơn và đỡ tốn kém hơn được trình bày trong chương hệ thống phục hồi.
CÁC THỰC HIỆN CẠNH TRANH
Hệ thống xử lý giao dịch thường cho phép nhiều giao dịch thực hiện đồng thời. Việc cho
phép nhiều giao dịch cập nhật dữ liệu đồng thời gây ra những khó khăn trong việc bảo đảm sự
nhất quán dữ liệu. Bảo đảm sự nhất quán dữ liệu mà không đếm xỉa tới sự thực hiện cạnh tranh
các giao dịch sẽ cần thêm các công việc phụ. Một phương pháp dễ tiến hành là cho các giao dịch
thực hiện tuần tự: đảm bảo rằng một giao dịch khởi động chỉ sau khi giao dịch trước đã hoàn tất.
Tuy nhiên có hai lý do hợp lý để thực hiện cạnh tranh là:
• Một giao dịch gồm nhiều bước. Một vài bước liên quan tới hoạt động I/O; các bước
khác liên quan đến hoạt động CPU. CPU và các đĩa trong một hệ thống có thể hoạt động
song song. Do vậy hoạt động I/O có thể được tiến hành song song với xử lý tại CPU. Sự
song song của hệ thống CPU và I/O có thể được khai thác để chạy nhiều giao dịch song
song. Trong khi một giao dịch tiến hành một hoạt động đọc/viết trên một đĩa, một giao
dịch khác có thể đang chạy trong CPU, một giao dịch thứ ba có thể thực hiện đọc/viết
CHƯƠNG IV GIAO DỊCH
Trang
77
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
trên một đĩa khác như vậy sẽ tăng lượng đầu vào hệ thống có nghĩa là tăng số lượng
giao dịch có thể được thực hiện trong một lượng thời gian đã cho, cũng có nghĩa là hiệu
suất sử dụng bộ xử lý và đĩa tăng lên.
• Có thể có sự trộn lẫn các giao dịch đang chạy trong hệ thống, cái thì dài cái thì ngắn.
Nếu thực hiện tuần tự, một quá trình ngắn có thể phải chờ một quá trình dài đến trước
hoàn tất, mà điều đó dẫn đến một sự trì hoãn không lường trước được trong việc chạy
một giao dịch. Nếu các giao dịch đang hoạt động trên các phần khác nhau của CSDL, sẽ
tốt hơn nếu ta cho chúng chạy đồng thời, chia sẻ các chu kỳ CPU và truy xuất đĩa giữa
chúng. Thực hiện cạnh tranh làm giảm sự trì hoãn không lường trước trong việc chạy các
giao dịch, đồng thời làm giảm thời gian đáp ứng trung bình: Thời gian để một giao dịch
được hoàn tất sau khi đã được đệ trình.
Động cơ để sử dụng thực hiện cạnh tranh trong CSDL cũng giống như động cơ để thực
hiện đa chương trong hệ điều hành. Khi một vài giao dịch chạy đồng thời, tính nhất quán CSDL
có thể bị phá huỷ cho dù mỗi giao dịch là đúng. Một giải pháp để giải quyết vấn đề này là sử dụng
định thời. Hệ CSDL phải điều khiển sự trao đổi giữa các giao dịch cạnh tranh để ngăn ngừa chúng
phá huỷ sự nhất quán của CSDL. Các cơ chế cho điều đó được gọi là sơ đồ điều khiển cạnh
tranh (concurrency-control scheme).
Xét hệ thống nhà băng đơn giản, nó có một số tài khoản và có một tập hợp các giao dịch,
chúng truy xuất, cập nhật các tài khoản này. Giả sử T
1
và T
2
là hai giao dịch chuyển khoản từ một
tài khoản sang một tài khoản khác. Giao dịch T
1
chuyển 50$ từ tài khoản A sang tài khoản B và
được xác định như sau:
T
1
: Read(A);
A:=A-50;
Write(A);
Read(B);
B:=B+50;
Write(B);
figure IV- 3
Giao dịch T
2
chuyển 10% số dư từ tài khoản A sang tài khoản B, và được xác định như
sau:
T
2
: Read(A);
Temp:=A*0.1;
A:=A-temp;
Write(A);
Read(B);
B:=B+temp;
Write(B);
figure IV- 4
Giả sử giá trị hiện tại của A và B tương ứng là 1000$ và 2000$. Giả sử rằng hai giao dịch
này được thực hiện mỗi một tại một thời điểm theo thứ tự T
1
rồi tới T
2
. Như vậy, dãy thực hiện
này là như hình bên dưới, trong đó dãy các bước chỉ thị ở trong thứ tự thời gian từ đỉnh xuống
đáy, các chỉ thị của T
1
nằm ở cột trái còn các chỉ thị của T
2
nằm ở cột phải:
CHƯƠNG IV GIAO DỊCH
Trang
78
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
T
1
T
2
Read(A);
A:=A-50;
Write(A);
Read(B);
B:=B+50;
Write(B);
Read(A);
Temp:=A*0.1;
A:=A-temp;
Write(A);
Read(B);
B:=B+temp;
Write(B);
Schedule-1
figure IV- 5
Giá trị sau cùng của các tài khoản A và B, sau khi thực hiện dãy các chỉ thị theo trình tự
này là 855$ và 2145$ tương ứng. Như vậy, tổng giá trị của hai tài khoản này (A + B) được bảo
tồn sau khi thực hiện cả hai giao dịch.
Tương tự, nếu hai giao dịch được thực hiện mỗi một tại một thời điểm song theo trình tự
T
2
rồi đến T
1
, khi đó
dãy thực hiện sẽ là:
T
1
T
2
Read(A);
Temp:=A*0.1;
A:=A-temp;
Write(A);
Read(B);
B:=B+temp;
Write(B);
Read(A);
A:=A-50;
Write(A);
Read(B);
B:=B+50;
Write(B);
CHƯƠNG IV GIAO DỊCH
Trang
79
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
Schedule-2
figure IV- 6
Và kết quả là các giá trị cuối cùng của tài khoản A và B tương ứng sẽ là 850$ và 2150$.
Các dãy thực hiện vừa được mô tả trên được gọi là các lịch trình (schedules). Chúng biểu
diễn trình tự thời gian các chỉ thị được thực hiện trong hệ thống. Một lịch trình đối với một tập
các giao dịch phải bao gồm tất cả các chỉ thị của các giao dich này và phải bảo tồn thứ tự các chỉ
thị xuất hiện trong mỗi một giao dịch. Ví dụ, đối với giao dịch T
1
, chỉ thị Write(A) phải xuất
hiện trước chỉ thị Read(B), trong bất kỳ lịch trình hợp lệ nào. Các lịch trình schedule-1 và
schedule-2 là tuần tự. Mỗi lịch trình tuần tự gồm một dãy các chỉ thị từ các giao dịch, trong đó các
chỉ thị thuộc về một giao dịch xuất hiện cùng nhau trong lịch trình. Như vậy, đối với một tập n
giao dịch, có n! lịch trình tuần tự hợp lệ khác nhau. Khi một số giao dịch được thực hiện đồng
thời, lịc trình tương ứng không nhất thiết là tuần tự. Nếu hai giao dịch đang chạy đồng thời, hệ
điều hành có thể thực hiện một giao dịch trong một khoảng ngắn thời gian, sau đó chuyển đổi ngữ
cảnh, thực hiện giao dịch thứ hai một khoảng thời gian sau đó lại chuyển sang thực hiện giao dịch
thứ nhất một khoảng và cứ như vậy (hệ thống chia sẻ thời gian).
Có thể có một vài dãy thực hiện, vì nhiều chỉ thị của các giao dịch có thể đan xen nhau.
Nói chung, không thể dự đoán chính xác những chỉ thị nào của một giao dịch sẽ được thực hiện
trước khi CPU chuyển cho giao dịch khác. Do vậy, số các lịch trình có thể đối với một tập n giao
dịch lớn hơn n! nhiều.
T
1
T
2
Read(A);
A:=A-50;
Write(A);
Read(A);
Temp:=A*0.1;
A:=A-temp;
Write(A);
Read(B);
B:=B+50;
Write(B);
Read(B);
B:=B+temp;
Write(B);
Schedule-3 một lịch trình cạnh tranh tương đương schedule-1
figure IV- 7
Không phải tất cả các thực hiện cạnh tranh cho ra một trạng thái đúng. Ví dụ schedule-4
sau cho ta một minh hoạ về nhận định này:
Sau khi thực hiện giao dịch này, ta đạt tới trạng thái trong đó giá trị cuối của A và B tương
ứng là 950$ và 2100$. Trạng thái này là một trạng thái không nhất quán (A+B trước khi thực hiện
giao dịch là 3000$ nhưng sau khi giao dịch là 3050$). Như vậy, nếu giao phó việc điều khiển thực
hiện cạnh tranh cho hệ điều hành, sẽ có thể dẫn tới các trạng thái không nhất quán. Nhiệm vụ của
CHƯƠNG IV GIAO DỊCH
Trang
80
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
hệ CSDL là đảm bảo rằng một lịch trình được phép thực hiện sẽ đưa CSDL sang một trạng thái
nhất quán. Thành phần của hệ CSDL thực hiện nhiệm vụ này được gọi là thành phần điều khiển
cạnh tranh (concurrency-control component). Ta có thể đảm bảo sự nhất quán của CSDL với thực
hiện cạnh tranh bằng cách nắm chắc rằng một lịch trình được thực hiện có cùng hiệu quả như một
lịch trình tuần tự.
T
1
T
2
Read(A);
A:=A-50;
Read(A);
Temp:=A*0.1;
A:=A-temp;
Write(A);
Read(B);
Write(A);
Read(B);
B:=B+50;
Write(B);
B:=B+temp;
Write(B);
Schedule-4 một lịch trình cạnh tranh
figure IV- 8
TÍNH KHẢ TUẦN TỰ (Serializability)
Hệ CSDL phải điều khiển sự thực hiện cạnh tranh các giao dịch để đảm bảo rằng trạng
thái CSDL giữ nguyên ở trạng thái nhất quán. Trước khi ta kiểm tra hệ CSDL có thể thực hiện
nhiệm vụ này như thế nào, đầu tiên ta phải hiểu các lịch trình nào sẽ đảm bảo tính nhất quán và
các lịch trình nào không. Vì các giao dịch là các chương trình, nên thật khó xác định các hoạt
động chính xác được thực hiện bởi một giao dịch là hoạt động gì và 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 hạng mục dữ liệu. Thay vào đó, ta chỉ xét hai hoạt động: Read và
Write. 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 hạng
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 lịch trình, như trong biểu diễn với quy ước như vậy của schedule-3 dưới đây:
T
1
T
2
Read(A);
Write(A);
Read(A);
Write(A);
Read(B);
Write(B);
Read(B);
CHƯƠNG IV GIAO DỊCH
Trang
81
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
Write(B);
Schedule-3 ( viết dưới dạng thoả thuận)
figure IV- 9
TUẦN TỰ XUNG ĐỘT (Conflict Serializability)
Xét lịch trình 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 hạng 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 lịch trình. Tuy nhiên, nếu I
i
và
I
j
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. I
i
= Read(Q); I
j
= Read(Q): Thứ tự của I
i
và I
j
không gây ra vấn đề nào, do T
i
và T
j
đọc cùng một giá trị Q bất kể đến thứ tự giữa I
i
và I
j
.
2. I
i
= Read(Q); I
j
= Write(Q): Nếu I
i
thực hiện trước I
j
, Khi đó T
i
không đọc giá trị được
viết bởi T
j
bởi chỉ thị I
j
. Nếu I
j
thực hiện trước I
i
, T
i
sẽ đọc giá trị của Q được viết
bởi I
j
, như vậy thứ tự của I
i
và I
j
là quan trọng.
3. I
i
= Write(Q); I
j
= Read(Q): Thứ tự của I
i
và I
j
là quan trọng do cùng lý do trong
trường hợp trước.
4. I
i
= Write(Q); 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
i
và T
j
. 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 I
i
và I
j
trong S, thứ tự của I
i
vf I
j
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ả I
i
và I
j
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 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 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.
T
1
T
2
Read(A);
Write(A);
Read(A);
Write(A);
Read(B);
Write(B);
Read(B);
Write(B);
figure IV- 10
Chỉ thị Write(A) trong T
1
xung đột với Read(A) trong T
2
. Tuy nhiên, chỉ thị Write(A)
trong T
2
không xung đột với chỉ thị Read(B) trong T
1
do các chỉ thị này truy xuất các hạng mục
dữ liệu khác nhau.
CHƯƠNG IV GIAO DỊCH
Trang
82
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
I
i
và I
j
là hai chỉ thị liên tiếp trong lịch trình 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 lịch trình mới S’ tương đương với S. 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 lịch trình tương đương – schedule-5 dưới đây
T
1
T
2
Read(A);
Write(A);
Read(A);
Read(B);
Write(A);
Write(B);
Read(B);
Write(B);
figure IV- 11
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 T
1
với chỉ thị Read(A) của T
2
○ Đổi chỗ chỉ thị Write(B) của T
1
với chỉ thị Write(A) của T
2
○ Đổi chỗ chỉ thị Write(B) của T
1
với chỉ thị Read(A) của T
2
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):
T
1
T
2
Read(A);
Write(A);
Read(B);
Write(B);
Read(A);
Write(A);
Read(B);
Write(B);
Schedule-6
figure IV- 12
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 đó.
Nếu một lịch trình S có thể biến đổi thành một lịch trình S’ bởi một dãy các đổi chỗ các
chỉ thị không xung đột, ta nói S và S’ là tương đương xung đột (conflict equivalent). Trong các
schedule đã được nêu ở trên, ta thấy schedule-1 tương đương xung đột với schedule-3.
CHƯƠNG IV GIAO DỊCH
Trang
83
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
Khái niệm tương đương xung đột dẫn đến khái niệm tuần tự xung đột. Ta nói một lịch
trình S là khả tuần tự xung đột (conflict serializable) nếu nó tương đương xung đột với một lịch
trình tuần tự. Như vậy, schedule-3 là khả tuần tự xung đột. Như một ví dụ, lịch trình schedule-7
dưới đây không tương đương xung đột với một lịch trình tuần tự nào do vậy nó không là khả tuần
tự xung đột:
T
3
T
4
Read(Q)
Write(Q)
Write(Q)
Schedule-7
figure IV- 13
Có thể có hai lịch trình 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 lịch trình schedule-8 như dưới
đây, lịch trình này không tương đương xung đột với lịch trình tuần tự < T
1
, T
5
> do trong lịch
trình schedule-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 lịch
schedule-8 hoặc sau khi thực hiện lịch trình tuần tự <T
1
, T
5
> là như nhau là 960 và 2040 tương
ứng. 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. Tuy nhiên sự phân tích như vậy sẽ nặng nề và
phải trả một giá tính toán cao hơn.
T
1
T
2
Read(A);
A:=A-50;
Write(A);
Read(B);
B:=B-10;
Write(A);
Read(B);
B:=B+50;
Write(B);
Read(A);
A:=A+50;
Write(A);
Schedule-8
figure IV- 14
CHƯƠNG IV GIAO DỊCH
Trang
84
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
TUẦN TỰ VIEW (View Serializability)
Xét hai lịch trình S và S’, trong đó cùng một tập hợp các giao dịch tham gia vào cả hai lịch
trình. Các lịch trình S và S’ được gọi là tương đương view nếu ba điều kiện sau được thoả mãn:
1. Đối với mỗi hạng mục dữ liệu Q, nếu giao dịch T
i
đọc giá trị khởi đầu của Q trong lịch
trình S, thì giao dịch T
i
phải cũng đọc giá trị khởi đầu của Q trong lịch trình S’.
2. Đối với mỗi hạng mục dữ liệu Q, nếu giao dịch T
i
thực hiện Read(Q) trong lịch trình
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’.
3. Đối với mỗi hạng mục dữ liệu Q, giao dịch thực hiện hoạt động Write(Q) sau cùng
trong lịch trình S, phải thực hiện hoạt động Write(Q) sau cùng trong lịch trình 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 lịch trình 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 lịch trình
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, schedule-1 là
không tương tương view với lịch trình 2 do, trong schedule-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 schedule-2. Schedule-
1 tương đương view với schedule-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 lịch trình.
Quan niệm tương đương view đưa đến quan niểm tuần tự view. Ta nói lịch trình S là khả
tuần tự view (view serializable) nếu nó tương dương view với một lịch trình tuần tự. Ta xét lịch
trình sau:
T
3
T
4
T
6
Read(Q)
Write(Q)
Write(Q)
Write(Q)
Schedule-9
figure IV- 15
Nó tương đương view với lịch trình tuần tự < T
3
, T
4
, T
6
> do chỉ thị Read(Q) đọc giá trị
khởi đầu của Q trong cả hai lịch trình và T
6
thực hiện Write sau cùng trong cả hai lịch trình như
vậy schedule-9 khả tuần tự view.
Mỗi lịch trình khả tuần tự xung đột là khả tuần tự view, nhưng có những lịch trình khả
tuần tự view không khả tuần tự xung đột (ví dụ schedule-9).
Trong schedule-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ỳ lịch trình khả tuần tự view không khả tuần tự xung đột.
CHƯƠNG IV GIAO DỊCH
Trang
85
Không có nhận xét nào:
Đăng nhận xét