Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 71
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. 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 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à:
T
1
T
2
Read(A);
Write(A);

Read(A);
Write(A);

Read(B);
Write(B);

Read(B);
Write(B);
Tuần tự xung đột (Conflict Serializability)
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

đọ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): thứ tự thực hiện của I
i
và I
j
là quan trọng.
3. I
i
= Write(Q); I
j
= Read(Q): thứ tự thực hiện của I
i
và I
j
là quan trọng.
4. I
i
= Write(Q); I
j
= Write(Q): Cả hai chỉ thị là hoạt động Write, thứ tự của hai chỉ

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
. 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 mục dữ liệu khác nhau.
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
T

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 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):
Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 73 T
1
T
2
Read(A);
Write(A);
Read(B);
Write(B);
Read(A);
Write(A);
Read(B);
Write(B);
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

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
> là như nhau A là
Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 74
960 và B là 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
5
Read(A);
A:=A-50;
Write(A);

Read(B);
B:=B-10;
Write(B);


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 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ị
Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 75
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.
Quan niệm tương đương view đưa đến quan niệm tuần tự view. 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:

T
3
T

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.
Tính khả phục hồi (Recoverability)
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.
Nếu giao dịch T
i
thất bại vì lý do nào đó, ta cần hủy bỏ hiệu quả của giao dịch này để
đảm bảo tính nguyên tử của giao dịch. Trong hệ thống cho phép thực hiện tương tranh,
cũng cần thiết đảm bảo rằng bất kỳ giao dịch nào phụ thuộc vào T
i
cũng phải bị bỏ. Để
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). Giả
sử hệ thống cho phép T
9
bàn giao ngay sau khi thực hiện chỉ thị Read(A). Như vậy T
9
bàn
Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 76


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
T
10
T

thất bại. T
10
phải cuộn lại, do T
11
phụ thuộc vào T
10

nên T
11
cũng phải cuộn lại và cũng như vậy với T
12
. Hiện tượng trong đó một giao dịch
thất bại kéo theo một dãy các giao dịch phải cuộn lại được gọi là sự cuộn lại hàng loạt
(cascading rollback).
Cuộn lại hàng loạt dẫn đến việc huỷ bỏ một khối lượng công việc đáng kể. 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.
Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 77
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

sau được thoả mãn:
(i). T
i
thực hiện Write(Q) trước T
j
thực hiện Read(Q).
(ii). T
i
thực hiện Read(Q) trước khi T
j
thực hiện Write(Q).
(iii). T
i
thực hiện Write(Q) trước khi T
j
thực hiện Write(Q).
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
.

Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 78
Ví dụ:
Thời lịch 1 được biểu diễn bằng đồ thị
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.
Thuật toán kiểm tra khả tuần tự view
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.
Một cách tiếp cận là cải tiến thuật toán kiểm tra xung đột tương đương để kiểm tra tính
khả tuần tự view.
Giả sử S là thời lịch gồm các giao dịch {T
1
, T
2
, , T
n
}. 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

tiến hành các bước sau :
a. Nếu T
i
= T
b
và T
j
≠ T
f
, gán nhãn 0 cho cung T
j
→T
k
trong đồ thị trình tự gán
Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 79
nhãn
b. Nếu T
i
≠ T
b
và T
j
= T
f
gán nhãn 0 cho cung T
k
→ T
i
trong đồ thị trình tự gán
nhãn

j
. Quy tắc 3a và 3b là trường
hợp đặc biệt là kết quả của sự kiện T
b
và T
f
cần thiết là các giao dịch đầu tiên và cuối
cùng tương ứng.
Ví dụ: xét thời lịch 9
T
3
T
4
T
6
Read(Q);

Write(Q);

Write(Q);

Write(Q);
Thời lịch 9

Biểu diễn đồ thị của S như sau:
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.
Hàm tương thích
Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 81
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. Giả sử một giao dịch T
i
đòi hỏi một
khóa phương thức A trên mục Q mà trên nó giao dịch T
j
(T
j
≠ T
i
) hiện đang giữ một khóa
phương thức B. Nếu giao dịch T
i
có thể được cấp một khóa trên Q ngay, bất chấp sự hiện
diện của khóa phương thức B, khi đó ta nói phương thức A tương thích với phương thức
B. Hàm tương thích giữa hai phương thức khóa được biểu diễn bởi một ma trận. Quan hệ
cho bởi ma trận comp sau:

S X
S

True

False

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:
T
1
: Lock-X(B);
Read(B);
B:=B-50;
Write(B);
Unlock(B);
Lock-X(A);
Read(A);
Bài giảng tóm tắt Hệ quản trị cơ sở dữ liệu 82
A:=A+50;
Write(A);
Unlock(A);
Giao dịch T
2
hiển thị tổng số lượng tiền trong các tài khoản A và B (A + B) và được
xác định như sau:
T
2
: Lock-S(A);
Read(A);
Unlock(A);
Lock-S(B);
Read(B);

qua cột bộ quản trị điều khiển tương tranh trong bảng.

T
1
T
2
Bộ quản trị điều khiển tương tranh

Lock-X(B)
Grant-X(B,T
1
)
Read(B)

B:=B-50

Write(B)

Unlock(B)
Lock-S(A) Grant-S(A,T
2