Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 1/49

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG
KHÓA 2
oOo

BÁO CÁO THU HOẠCH MÔN HỌC
CƠ SỞ DỮ LIỆU NÂNG CAO

ĐỀ TÀI:
NGHIÊN CỨU XỬ LÝ ĐỒNG HÀNH
TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN

VÀ
ỨNG DỤNG XÂY DỰNG CHƯƠNG TRÌNH DEMO
MÁY RÚT TIỀN TỰ ĐỘNG ĐA NGÂN HÀNG.

Giảng viên phụ trách: TS Đỗ Phúc.

; Tương quan logic: dữ liệu có một số thuộc tính ràng buộc chúng với nhau, điều này
có thể giúp ta phân biệt được CSDLPT với một tập hợp các CSDL cục bộ hoặc các tập tin
CSDL lưu giữ tại các vị trí khác nhau trên một mạng máy tính.
Ngày nay, tầm quan trọng của CSDLPT là không thể phủ nhận và các lý do chính yếu
để giải thích tại sao lại cần sử dụng và phát triển CSDLPT là:
; Nguyên nhân về tổ chức và kinh tế: Các tổ chức, đặc biệt là các tổ chức kinh tế lớn
thường có khuynh hướng mở rộng địa bàn hoạt động (mở các chi nhánh mới) nhưng vẫn phải
đảm bảo tính thông suốt và nhất quán của hệ thống CSDL.
; Sự liên kết các CSDL đang tồn tại: CSDLPT là giải pháp tự nhiên khi có các CSDL
đang tồn tại và sự cần thiết xây dựng một ứng dụng toàn cục. Trong trường hợp này CSDLPT
được làm từ dưới lên (bottom-up) từ các CSDL đã tồn tại từ trước. Tiến trình này có thể đòi
hởi phải cấu trúc lại một cách cục bộ ở một mức độ nhất định. Nhưng dù sao những sửa đổi
này vẫn nhỏ hơn nhiều so với việc tạo lập một CSDL tập trung hoàn toàn mới.
; CSDLPT cho phép mỗi vị trí lưu giữ CSDL riêng nhằm hỗ trợ truy cập hiệu quả và
tức thì các dữ liệu được dùng thường xuyên. Các dữ liệu này vẫn có thể được dùng ở những
nơi khác nhưng có tần suất sử dụng ít hơn.
; Nếu có sự cố hư hỏng máy tính cục bộ hoặc đường liên lạc bị sụp đổ thì phần còn
lại của mạng vẫn tiếp tục làm việc được.
; Làm giảm tổng chi phí tìm kiếm.
; Tính tin cậy và sẵn sàng cao.
b. Thuận lợi của CSDLPT:
; Khả năng phục hồi nhanh chóng (Resilience): việc truy cập dữ liệu không phụ
thuộc vào một máy tính hay một đường kết nối trên mạng. Nếu có bất kỳ một lỗi nào xảy ra
thì sẽ có một vài CSDL được truy cập trên các nút cục bộ khác, hơn nữa, nếu có lỗi xảy ra
trên đường kết nối thì có thể đường nối dữ liệu khác được chọn thay thế.
; Giảm dòng dữ liệu trên đường truyền đồng thời tăng khả năng trả lời.
; “Trong suốt vị trí” cho phép dữ liệu vật lý di chuyển mà không cần thay đổi ứng
dụng hay thông báo cho người sử dụng.
; Cách thức mở rộng dễ dàng: dễ dàng phát triển, mở rộng và điều này là nhờ vào:
Ö Nhiều bộ xử lý có thể được thêm vào mạng;

DC = Truyền dữ liệu Communications GSC
= Global Systems Catalog
DDBMS = Hệ QTCSDLPT
DDBM
S
D
C

Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 5/49
2. Giao tác (Transaction)
a. Khái niệm giao tác
Giao tác là một chuỗi lệnh thực hiện trên các đối tượng dữ liệu (các dòng -
tuples, cột- fields) trong một hệ cơ sở dữ liệu (CSDL). Các lệnh của giao tác bao
gồm:
• Các lệnh thực hiện:
- Read(): Đọc dữ liệu từ CSDL và trả về giá trị phần tử được lưu trong CSDL.
- Write(): Lưu giá trị của phần tử vào CSDL.
• Các lệnh giao tác:
- Start(): Bắt đầu thực hiện một giao tác
- Commit(): Kết thúc thành công một giao tác.
- Abort(): Hủy bỏ một giao tác.
Hình thức hóa khái niệm giao tác như sau:
Gọi O
ij
(x) là lệnh O
j
của giao tác T
i
truy xuất trên cùng mục dữ liệu x, trong đó:

(x) và O
ik
(x)∈OS
i
thì hoặc O
ij
(x)<
i
O
ik
(x) (lệnh O
ij
(x)
thực hiện trước, lệnh O
ik
(x) thực hiện sau) hoặc O
ik
(x) <
i
O
ij
(x) (lệnh O
ik
(x)
thực hiện trước, lệnh O
ij
(x) thực hiện sau).
- Đối với các lệnh đọc R
ij
(x) và R

nhân phía người dùng hoặc hệ thống phát sinh lỗi. Lệnh này cũng
được gọi để loại trừ những kết quả chưa hoàn thiện.
- Một giao tác thường bao gồm một số lệnh được thực hiện tại những thời điểm
khác nhau.
Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 6/49
- Nếu site bị đổ (crashes), những giao tác đang còn dở dang sẽ được phục hồi lại
ban đầu.
 Nhất quán (consistency)
- Mỗi giao tác phải bảo toàn sự nhất quán dữ liệu.
- Hình thức nhất quán dữ liệu có thể được thực hiện bởi hệ thống thông qua ràng
buộc toàn vẹn.
- Ràng buộc toàn vẹn hoạt động như bộ lọc, xác định rằng một giao tác được
chấp nhận hay không.
 Cô lập (isolation)
- Khi người sử dụng gửi đi các giao tác, mỗi giao tác được thực hiện bởi chính
nó, không để lộ kết quả của nó cho những giao tác khác cùng hoạt động trước
khi nó kết thúc.
- Đảm bảo cho mọi kết quả luôn luôn đúng, thậm chí khi có nhiều giao tác được
thực hiện đồng thời trên cùng một mục dữ liệu.
- Các kết quả từ việc xử lý giao tác đồng hành cũng giống từ việc xử lý giao tác
nối tiếp.
- Tuân theo giao thức xử lý đồng hành.
 Bền vững (durability)
- Đảm bảo một giao tác khi kết thúc, kết quả của chúng được duy trì và không bị
xóa khỏi CSDL. Vì thế, DBMS đảm bảo rằng kết quả giao tác luôn tồn tại dù
xảy ra sự cố hệ thống, bằng cách:
+ Phục hồi những thay đổi trên đĩa tại thời điểm kết thúc giao tác.
+ Ghi lại những thay đổi vào một file log trên đĩa và tại thời điểm bắt đầu
lại, đọc file log này và phục hồi lại những thay đổi trước đó của giao tác.

Commit;
output( “transfer completed”);
end;
return;
End.
- Giao tác chuyển tiền được mô tả thành chuỗi lệnh:
Abort.
Start, Read(X),
Write(X-A), Read(Y), Write(Y+A), Commit.
Trong đó:
X là số dư của tải khoản người chuyển tiền, A là số tiền được chuyển.
Y là số dư của tải khoản người nhận.
(Nếu X<A)
Ví dụ 2
- Thủ tục Deposit() mô phỏng giao tác cập nhật tiền gửi của khách hàng vào tài
khoản:
Procedure Deposit
begin
Start;
input( account#, amount);
temp : = Read(Accounts[account#]);
temp : = temp + amount;
Write(Accounts[account#], temp);
Commit;
End;

- Giả sử AccountID =’00001’ có số tiền hiện tại là 1.000.000 đồng.
- Nếu đồng thời có hai khách hành muốn chuyển vào tài khoản này, khách thứ nhất
muốn chuyển vào 1.000.000 đồng và khách thứ hai là 100.000.000 đồng.
- Giả sử các giao tác thực thi của procedure Deposit như sau:

Giả sử ta có T
1
và T
2
là hai giao dịch chuyển quỹ từ một tài khoản đến một tài
khoản khác.
Giao dịch T
1
chuyển 50$ từ tài khoản A đến tài khoản B, được định nghĩa như
sau:
T
1
: Read(A);
A:= A-50;
Write(A);
Read(B);
B:= B+50;
Write(B);
Giao dịch T
2
chuyển 10% số dư từ tài khoản A đến tài khoản B và được định
nghĩa như sau:
T
2
: Read(A);
Temp:= A * 0.1;
Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 9/49
A:= A – Temp;
Write(A);

tác động tương đương với một lịch biểu thực hiện được sinh ra với các giao
dịch thực hiện tuần tự theo một thứ tự nào đó. Một hệ thống đảm bảo tính chất
này được nói là đảm bảo tính khả tuần tự. Vậy ta hãy xét đến khái niệm về lịch
biểu tuần tự, khả tuần tự và bất tuần tự.
i. Lịch biểu tuần tự:
Một lịch biểu H được gọi là tuần tự nếu mọi giao dịch T trong H đều
có tất cả các lệnh của T và được thực hiện liên tiếp nhau.
Ta nhận thấy rằng: các lệnh trong T
1
thực hiện trước, sau đó đến các
lệnh trong T
2
.

ii. Lịch biểu bất tuần tự:
Một lịch biểu H được gọi là bất tuần tự nếu với mọi giao dịch T trong
H, tất cả các lệnh của T trong H được thực hiện không liên tiếp
nhau.
Ví dụ:
Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 10/49 Ta nhận thấy rằng: các lệnh thứ 1 và 2 trong T
1
được thực hiện trước,
sau đó thực hiện tiếp 2 lệnh thứ 1 và thứ 2 trong T

R(X)
W(X)
COMMIT
W(X)
W(Y)
R(Z)
COMMIT
R(X)
R(Y)
R(Z)
COMMIT

Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 11/49
Khi đó:
• Lịch biểu sau là tuần tự:
S= {W2(X), W2(Y), R2(Z), C2, R1(X), W1( X), C1, R3(X), R3( Y),
R3( Z), C3}

• Lịch biểu sau là khả tuần tự:
S= {W2(X), R1(X), W1(X), C1, R3(X), W2( Y), R3(Y), R2(Z), C2,
R3(Z), C3}

c. Thuật toán kiểm tra lịch biểu tuần tự:
i. Định lý:
Định lý:
Nếu mọi giao tác đều tuân theo nghi thức khoá chốt hai pha
thì đồ thị xung đột sẽ không có chu trình.
Hệ quả:
Nếu T

2
OP
2
trên x với tại thời điểm t
2

t
1
< t
1

► Vì vậy: t
1
sẽ giữa khoá trên x tại t
1
, tương tự với t
2
.
Ta đã biết, hai khoá (mà có ít nhất một khoá là khoá X) không
thể đồng thời tồn tại tại cùng một thời điểm .
► Vì vậy T
2
chỉ có thể khoá x sau khi T
1
đã giải phóng khoá,
bởi vậy, với t
’
và t
’’
bất kỳ thoả t

Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 12/49
● L
1
< L
2
⇐ điều phải chứng minh!
► Giả sử có một lịch biểu tuân theo 2PL có chứa chu trình
sau:
T
1
-> T
2
, T
2
-> T
3
, T
3
->T
1
thì theo hệ quả trên:
● L
1
< L
2

● L
2
< L

chu trình;

Ví dụ:

S1:W2(x)W1(x)R3(x)R1(x)R1(x)W2(y)R3(y)R3(z)R2(x)
Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 13/49
S1 bất khả tuần tự vì đồ thị có chu trình S4: R2(z)W2(x)W2(y)W1(x)R1(x)R3(x)R3(z)R3(y)
S4 là lịch biểu khả tuần tự vì đồ thị không có chu trình

d. Khả năng tự phục hồi:
Chúng ta đã xét đến các lịch biểu có thể chấp nhận được trên quan điểm nhất
quán của cơ sở dữ liệu với ngầm định rằng không có các lỗi giao dịch xảy ra.
Bây giờ chúng ta sẽ chỉ ra tác động của các lỗi giao dịch khi thực hiện đồng
thời.
Nếu một giao dịch Ti bị lỗi vì một lý do nào đó, ta cần phải tháo bỏ tác động
của giao dịch này để đảm bảo tính nguyên tố của giao dịch. Trong một hệ
thống cho phép thực hiện đồng thời, nếu Ti bị hủy bỏ thì phải đảm bảo rằng
giao dịch Tj nào đó phụ thuộc vào Ti cũng phải được hủy bỏ. Để đạt được sự
đảm bảo này, chúng ta cần đặt ra các hạn chế trên kiểu của các lịch được cho
phép trong hệ thống này.

Các lịch có khả năng tự phục hồi:
Xét một lịch biểu sau:
T8 T9
Read(A);
Write(A);

,
chúng ta phải hủy bỏ T
9
để đảm bảo tính nguyên tố của giao dịch. Tuy nhiên
T
9
đã được chuyển giao và không thể hủy bỏ. Do vậy, chúng ta có một tình
huống ở đó lịch không thể phục hồi một các đúng đắn sau lỗi của T
8
.
Lịch biểu mà ta vừa thấy ở trên với việc chuyển giao tức thời sau lệnh
Read(A) là một ví dụ của một lịch không thể phục hồi mà sẽ không được
phép. Hầu hết các hệ cơ sở dữ liệu yêu cầu rằng tất cả các lịch phải có khả
năng phục hồi.
Một lịch có khả năng phục hồi là một lịch ở đó với mỗi cặp giao dịch Ti và
Tj, trong đó: Tj đọc một khoản mục dữ liệu được ghi trước đó bởi Ti thì
thao tác chuyển giao của Ti phải xuất hiện trước thao tác chuyển giao của
Tj.

e.
Các lịch không lan truyền:
Khi có một lịch có khả năng phục hồi, để phục hồi một cách đúng đắn từ lỗi
của một giao dịch Ti, chúng ta phải quay lui một số giao dịch. Các tình
huống như vậy xảy ra nếu các giao dịch đã đọc dữ liệu được ghi bởi Ti.
Ta hãy xét một lịch được thể hiện như sau:

T
10
T
11

10
phải quay lui. Do T
11
phụ thuộc vào
T
10
nên T
11
cũng phải quay lui. Do T
12
phụ thuộc vào T
11
nên T
12
cũng phải
quay lui. Hiện tượng này, trong đó một giao dịch bị lỗi dẫn đến một dãy các
giao dịch phải quay lui, được gọi là quay lui lan truyền.
Quay lui lan truyền là không mong muốn, do nó dẫn đến việc tháo bỏ một số
đáng kể công việc. Có thể mong muốn hạn chế các lịch mà đối với chúng các
lan truyền quan lui không thể xảy ra. Các lịch như thế được gọi là các lịch
không lan truyền.
Một lịch không lan truyền là một lịch trong đó với mỗi cặp các giao dịch Ti
và Tj – mà Tj đọc một khoản mục dữ liệu được ghi trước đó bởi Ti, thì
thao tác chuyển giao của Ti phải xuất hiện trước thao tác đọc của Tj. Từ
đây ta dễ dàng thấy rằng: một lịch không lan truyền cũng là một lịch có
khả năng phục hồi.

Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 15/49
f. Cài đặt tính độc lập:

- Khoá chốt là một cơ chế thường dùng để giải quyết những vấn đề liên quan
đến việc đồng bộ hoá dữ liệu truy cập dùng chung. Mỗi phần tử dữ liệu đều
có một khoá chốt kết hợp với chúng.
- Bộ xếp lịch đảm bảo rằng chỉ duy nhất giao tác có thể giữ khoá chốt trong
một thời điểm, và chỉ có một giao tác có thể truy xuất dữ liệu đó tại cùng một
thời điểm.
- Khoá chốt được bộ xếp lịch (schedule manager) dùng để đảm bảo tính khả
tuần tự.
- Trước khi một giao tác có thể truy cập dữ liệu dùng chung, bộ xếp lịch lịch
sẽ khảo sát trạng thái khoá chốt của những dữ liệu này.
+ Nếu không có giao tác nào khác đang giữ chúng thì bộ xếp lịch sẽ phát
lệnh thông báo khoá dữ liệu này lại và sau đó các giao tác thực hiện các
lệnh của mình trên dữ liệu đó.
+ Nếu dữ liệu đang bị khoá bởi giao tác T
2
, thì giao tác này phải chờ cho
đến khi nào T
2
giải phóng khoá đó.
Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 16/49
- Có 2 loại khoá chốt: khoá đọc (read lock, rl) và khoá ghi (write lock, wl).
+ rli(x): khoá đọc trên phần tử dữ liệu x của giao tác Ti
+ wlj(x): khoá ghi trên phần tử dữ liệu x của giao tác Tj
- Hai khoá pli(x) và qlj(y) đụng độ nếu x=y, i≠j, có nghĩa rằng chúng khoá
trên cùng một phần tử dữ liệu, chúng được phát sinh từ hai giao tác khác
nhau và một trong hai thao tác là ghi.

b. Những quy tắc quản lý và sử dùng khoá
 Qui tắc 1:

Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 17/49
Giai đoạn tăng trưởng
Giai đoạn thu hồi
Hình trên cho thấy bộ quản lý khoá giải phóng khoá ngay sau khi hoàn tất việc truy
xuất. Điều này cho phép các giao dịch đang đợi khoá tiếp tục tiến hành và nhận
khoá, do vậy, làm tăng hoạt động đồng thời.
Gọi Oper(T,x) là lệnh truy xuất mục dữ liệu x trong giao tác T.
- Dựa vào kỹ thuật khóa chốt hai giai đoạn, có thể chia giao tác thành hai
giai đoạn, dựa trên 3 nguyên tắc trên:
+ Giai đoạn tăng trưởng (growing phase), trong giai đoạn này nó
nhận các khoá và truy xuất các mục dữ liệu.
Khi bộ lập lịch nhận được lệnh Oper(T,x), nó kiểm tra lệnh này có
tranh chấp với những lệnh truy xuất trên x khác, đã được bộ lập lịch
cấp khóa.
 Nếu nó tranh chấp, lệnh Oper(T,x) bị bị trì hoãn.
 Nếu không tranh chấp, bộ lập lịch sẽ cấp 1 khóa cho x
và gửi lệnh này đến bộ quản lý dữ liệu.

- Biểu đồ khóa 2 pha chặt chẽ.

Tất cả các khóa
được giải phóng
cùng lúc

e.
Vấn đề bế tắc (deadlock)
- Vấn đề bế tắc luôn xảy ra trong các kỹ thuật dùng cơ chế khóa chốt.
- Giả sử có 2 giao tác T1 và T2 thực hiện các lệnh đọc ghi trên mục dữ liệu x và
y như sau:
T
1
: lock (x); lock(y); read (x); write (y);
T
2
: lock (y); lock(x); read (y); write (x);
T
1
chiếm giữ khóa x và cố gắng khóa y, T
2

(umax) thì chấp nhận T, ngược lại: khởi động lại T.
Như vậy: các giao dịch bị loại khỏi thao tác cập nhật các bộ cho đến khi nó có
thời nhãn trễ hơn bộ cần cập nhật. Do vậy nó không gây hại cho các giao dịch
khác.
Với mỗi giao dịch Ti trong hệ thống, chúng ta kết hợp với nó một nhãn thời
gian cố định duy nhất được ký hiệu TS(Ti). Nhãn thời gian này được gán bởi
hệ cơ sở dữ liệu trước khi giao dịch Ti được khởi động thực hiện. Nếu một
giao dịch Ti đã được gán nhãn TS(Ti), một giao dịch mới Tj đi vào hệ thống
thì TS(Ti)<TS(Tj). Có 2 phương pháp cài đặt sơ đồ này:
1. Sử dụng giá trị của đồng hồ hệ thống làm nhãn thời gian, có nghĩa là:
nhãn thời gian của mọt giao dịch là giá trị của đồng hồ khi giao dịch đi
vào hệ thống.
2. Sử dụng một bộ đến logic mà nó được tăng lên sau ki một nhãn thời
gian mới được gán, có nghĩa là: nhãn thời gian của một giao dịch là giá
trị của bộ đếm khi giao dịch đi vào hệ thống.

Các nhãn thời gian của giao dịch xác định thứ tự khả tuần tự. Do vậy, nếu
TS(Ti)<TS(Tj), thì hệ thống phải đảm bảo rằng lịch được sinh ra là tương
đương với một lịch tuần tự theo thứ tự Ti rồi đến Tj.
Các quy tắc của thuật toán này:
1. Hai thao tác O
1
và O
2
thuộc hai giao dịch T
1
và T
2
(O
1

giao dịch đã thực hiện thành công lệnh read(Q).
RTS(Q)= max{ TS(T) | T đã đọc lên Q }
Các nhãn thời gian này được cập nhật bất kể khi nào một lệnh read(Q) hay
write(Q) mới được thực hiện.

b.
Giao thức kết thúc hai giai đoạn (two phase commit protocol):
Giao thức kết thúc 2 giai đoạn (2 phase commit protocol – 2PC):
Giai đoạn 1:
Xét một giao tác T được khởi động từ một vị trí nào đó và gọi thực hiện
các giao tác ở các site khác hoặc ở chính vị trí khởi động giao tác T ( ta
gọi các giao tác này là C).
Tất cả các giao tác con Ti sẽ quyết định đồng ý hay không. Giao tác
con C gởi tín hiệu báo chuẩn bị kết thúc cho các Ti và Ti sẽ trả lời cho
C bằng tín hiệu đồng ý kết thúc hay không.
Giai đoạn 2:
Dựa trên các thông tin trả lời của giai đoạn 1, C có thể quyết định chấm
dứt T hay không. Sau đó C sẽ gởi tín hiệu đồng ý hay hủy bỏ đến các
Ti.
T sẽ không được kết thúc nếu có một Ti chưa kết thúc.
Kết thúc 2 giai đoạn (2PC) – đồng ý:

Bộ DM sẽ thực hiện từng lệnh đọc/ghi nhận được. Đối với tác vụ đọc, bộ DM
duyệt CSDL cục bộ và trả về giá trị yêu cầu. Đối với tác vụ ghi, bộ DM sửa đổi CSDL
cục bộ và và trả về một ghi nhận chấp thuận thao tác cho bộ SC. Đến lượt, bộ SC trả
về cho TM và TM trả về cho giao tác.
Kiến trúc của một bộ giám sát thực hiện các giao dịch được thể hiện như trong
hình vẽ sau:

Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 22/49 Transaction Manager
(TM)
Scheduler
(SC)
Scheduling/
Descheduling
Requests
Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 23/49
7. Các phương pháp kiểm soát đồng hành
a. Thực thi tuần tự
Một lúc chỉ cho phép thực thi một giao tác cho đến khi giao tác đó kết thúc thì giao
tác kế tiếp mới được thực hiện.
Thực thi này là phương pháp đơn giản và chính xác vì giao tác hoạt động một cách
riêng biệt trong một khoảng thời gian nhất định.
Ví dụ: cho ba giao tác cùng với tập các lệnh thực hiện như sau:

T1: Read(x) T2: Write(x) T3: Read(x)
Write(x) Write(y) Read(y)
Commit Read(z) Read(z)
Commit Commit
khi đó ta có lịch biểu:
H1={W2(x),R1(x),R3(x),W1(x),C1,W2(y),R3(y),R2(z),C2,R3(z),C3}

b. Thực thi khả tuần tự
Một thực thi được gọi là khả tuần tự nếu nó có cùng một kết xuất và tác động
lên CSDL như khi thực thi tuần tự của cùng một giao tác. Vì thực thi tuần tự là đúng
và vì thực thi mỗi thực thi khả tuần tự có cùng một tác động như thực thi tuần tự nên
các thực thi khả khả tuần tự cùng phải đúng.
Các thực thi mát mát thông tin khi cập nhật và phục hồi tranh chấp là những
điển hình của thực thi bất khả tuần tự. Ví dụ ta thực hiện hai giao dịch gửi tiền
(Deposit) tuần tự sẽ nhận được khết quả khác khi thực hiện xen kẽ, nghĩa là có sự mất
mát thông tin. Vì vậy thực thi xen kẽ là bất khả tuần tự. Tương tự như vậy, việc thực
thi xem kẽ hai giao tác Chuyển tiền (Transfer) và PrintSum sau
//Thủ tục tin tổng số dư hai tài khoản

PrintSum.
Mặc dù thứ tự thực hiện của các thao tác trong thực thi tuần tự là khác so với
thực thi xen kẽ, nhưng kết quả của mỗi thao tác lại chính xác như khi thực thi xen kẽ.
Vì thế thực thi xen kẽ như trên gọi là khả tuần tự.
Tính khả tuần tự là định nghĩa của tính chính xác cho điều khiển đồng hành
trong các DBS.
Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011
Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 25/49

8. Các thuật toán kiểm soát đồng hành
Các thuật toán kiểm soát đồng hành được chia thành 2 nhóm sau:
 Nhóm Pessimistic
Ö Dựa trên khóa 2 pha (Two Phase Locking-Based – 2PL)
♦ 2PL tập trung (Centralized 2PL hay Primary Site 2PL)
♦ 2PL bản sao chính (Primary Copy 2PL)
♦ 2PL phân tán (Distributed 2PL)
Ö Thứ tự nhãn thời gian (Timestamp Ordering – TO)
♦ TO cơ bản (Basic TO)
♦ TO đa bản (Multiversion TO)
♦ TO bảo thủ (Conservative TO)
Ö Lai (Hybrid)

 Nhóm Optimistic
Ö Dựa vào khóa (Lock based)
Ö Dựa vào thứ tự nhãn thời gian (Timestamp Ordering-based)