BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƢỜNG ĐẠI HỌC KHOA HỌC TRẦN LÊ NGỌC TÌM HIỂU MỘT SỐ THUẬT TOÁN ĐIỀU KHIỂN
TƢƠNG TRANH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC
CÔNG NGHỆ THÔNG TIN

Tôi xin gửi lời cảm ơn chân thành đến TS. Nguyễn Mậu Hân, Thầy đã tận tình
hướng dẫn em trong suốt thời gian học tập cũng như thời gian thực hiện luận văn.
Vì thời gian và trình độ còn nhiều hạn chế cũng như số lượng lớn các thuật
ngữ, khái niệm cần trình bày, chắc chắn luận văn còn có chỗ sai sót. Rất mong
nhận được ý kiến góp ý và động viên của các Thầy/Cô cũng như tất cả các Anh/Chị
và các bạn để luận văn được hoàn thiện hơn nữa.
Xin chân thành cảm ơn!
Người thực hiện luận văn Trần Lê Ngọc

MỤC LỤC
Trang phụ bìa
Lời cam đoan
Mục lục
Danh mục các ký hiệu, các chữ viết tắt
Danh mục các bảng
Danh mục các hình vẽ, đồ thị
MỞ ĐẦU 1
1. Lý do chọn đề tài 1
2. Mục đích nghiên cứu 1
3. Đối tƣợng và phạm vi nghiên cứu 1
4. Phƣơng pháp nghiên cứu. 1
5. Ý nghĩa khoa học và thực tiễn 2
6. Cấu trúc luận văn 2
CHƢƠNG 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN 3

2.4.2. Tiến trình không tuần tự 25
2.4.3. Hai thao tác xung đột 25
2.4.4. Tiến trình tƣơng đƣơng 26
2.4.5. Tiến trình khả tuần tự 26
2.4.6. Tính khả tuần tự trong cơ sở dữ liệu phân tán 27
CHƢƠNG 3. ĐIỀU KHIỂN TƢƠNG TRANH TRONG CƠ SỞ DỮ LIỆU
PHÂN TÁN 28
3.1. Cơ sở của điều khiển tƣơng tranh phân tán 28
3.1.1. Các khái niệm 30
32
3.2. Các kỹ thuật điều khiển tƣơng tranh 34
3.2.1. Các kỹ thuật đồng bộ hóa dựa trên khóa hai pha 34
3.2.1.1. Quá trình thực hiện 2PL cơ bản 35
3.2.1.2. Kỹ thuật 2PL sao chép chính 39
3.2.1.3. Kỹ thuật 2PL biểu quyết 40
3.2.1.4. Kỹ thuật 2PL tập trung 40
3.2.1.4. Kỹ thuật 2PL phân tán 41
3.2.2. Phát hiện và ngăn chặn tắc nghẽn 42
3.2.2.1. Ngăn chặn tắc nghẽn 44
3.2.2.2. Phát hiện tắc nghẽn 46
47
3.2.3.1. Thuật toán TO cơ bản 49
3.2.3.2. Thuật toán TO bảo thủ 50
3.2.3.3. Thuật toán TO đa bản 52
3.2.3.4. Duy trì TO: 53
3.2.3.5. Quản lý nhãn thời gian: 53
1.3.Mô phỏng nhiều giao dịch đồng thời trên hệ thống ATM đa ngân hàng. 55

LC
Lock controller
PC
Primary copy
ROWA
Read one Write all
TM
Transaction Management
TO
Timestamp ordering
TS
Timestamp

DANH MỤC CÁC BẢNG

Số hiệu bảng
Tên bảng
Trang
1.1
Cơ sở dữ liệu của một công ty máy tính
7
1.2
Phân mảnh ngang Cơ sở dữ liệu
7
1.3
Phân mảnh dọc Cơ sở dữ liệu
7

Trang
2.1
Quá trình xử lý truy vấn trong hệ thống phân tán
12
2.2
dữ liệu phân tán
13
2.3
Biểu đồ trạng thái của giao dịch
19
2.4
Lịch biểu tuần tự
23
2.5
Lịch biểu bất tuần tự
23
2.6
Lịch biểu khả tuần tự
24
3.1
Hiện tƣợng khóa chết (Deadlock)
31
3.2

33
3.3
t
34
3.4
Biểu đồ khóa 2 pha

61
3.15
Giao diện Bảng điều khiển máy ATM
62
3.16
Hiển thị quá trình xử lý
62
3.17
Log và lƣu file Log
62 1
MỞ ĐẦU

1. Lý do chọn đề tài
Trong thực tiễn hiện nay, nhu cầu dùng chung một hệ cơ sở dữ liệu là rất lớn.
Vấn đề đặt ra là làm thế nào để có thể quản lý tốt các luồng dữ liệu và việc sử dụng
chung dữ liệu, chƣơng trình ứng dụng. Đặc biệt là làm thế nào để đáp ứng nhu cầu
ngƣời dùng một cách tốt nhất, chính xác nhất.
Lý thuyết điều khiển tƣơng tranh (hay đồng thời) đƣợc đƣa ra trong việc
quản lý các giao dịch trên cơ sở dữ liệu phân tán nhằm giải quyết các tính chất biệt
lập và nhất quán [5] trên một hệ cơ sở dữ liệu phân tán.
Từ những lý do cơ bản trên, đƣợc sự hƣớng dẫn và gợi ý của TS. Nguyễn
Mậu Hân, tôi đã chọn đề tài nghiên cứu của luận văn tốt nghiệp cao học là “Tìm
hiểu một số thuật toán điều khiển tương tranh trong cơ sở dữ liệu phân tán”.
2. Mục đích nghiên cứu

Nội dung luận văn gồm 3 chƣơng, cụ thể nhƣ sau:
Chương 1: Tổng quan về cơ sở dữ liệu phân tán
Giới thiệu tổng quan về cơ sở dữ liệu phân tán, các nguyên tắc phân mảnh dữ
liệu, các chiến lƣợc phân tán dữ liệu và việc cấp phát tài nguyên trong hệ cơ sở dữ
liệu phân tán.
Chương 2: Quản trị cơ sở dữ liệu phân tán
Tập trung nghiên cứu về xử lý truy vấn phân tán, quản lý các giao dịch phân
tán, lịch biểu và tính khả tuần tự trong thực thi các giao dịch phân tán.
Chương 3: Mô hình tương tranh trong cơ sở dữ liệu phân tán
Nghiên cứu về điều khiển tƣơng tranh trong cơ sở dữ liệu phân tán, các kỹ
thuật, thuật toán điều khiển tƣơng tranh.
Xây dựng chƣơng trình mô phỏng thuật toán điều khiển tƣơng tranh trên hệ
thống giao dịch vụ đa ngân hàng.
3
CHƢƠNG 1
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN

Cơ sở dữ liệu phân tán là tập hợp các cơ sở dữ liệu (CSDL) đƣợc liên kết
logic và làm việc một cách trong suốt với ngƣời sử dụng. Trong suốt với ngƣời sử
dụng hàm nghĩa ngƣời sử dụng có thể truy cập tất cả cơ sở dữ liệu nhƣ chúng thuộc
về một cơ sở dữ liệu duy nhất. Có sự độc lập ví trí, ngƣời sử dụng không biết nơi
lƣu trữ dữ liệu, có thể di chuyển dữ liệu dữ liệu từ vị trí vật lý này đến vị trí khác
mà không ảnh hƣởng đến ngƣời dùng khác.
Lý do phát triển cơ sở dữ liệu phân tán là:
• Các tổ chức thƣờng có nhiều chi nhánh ở nhiều nơi khác nhau.
• Cho phép mỗi vị trí lƣu giữ cơ sở dữ liệu 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.

liệu là thích hợp nhất.
Thứ hai, nếu các ứng dụng có các khung nhìn đƣợc định nghĩa trên một quan
hệ cho trƣớc nằm tại những vị trí khác nhau thì có hai cách lựa chọn làm cơ sở để
phân tán: hoặc là toàn bộ quan hệ hoặc quan hệ không được nhân bản mà được lưu
ở một vị trí có chạy ứng dụng. Lựa chọn thứ nhất gây ra một số lƣợng lớn các truy
xuất không cần thiết đến dữ liệu ở xa. Ngƣợc lại, lựa chọn sau thực hiện nhân bản
không cần thiết, gây ra nhiều vấn đề khi cập nhật và có thể gây lãng phí không gian
lƣu trữ.
Thứ ba, việc phân rã một quan hệ thành nhiều mảnh, mỗi mảnh đƣợc xử lý
nhƣ một đơn vị, sẽ cho phép nhiều giao dịch thực hiện đồng thời. Ngoài ra việc
phân mảnh các quan hệ sẽ cho phép thực hiện song song một câu vấn tin bằng cách
chia nó ra thành một tập các câu vấn tin con hoạt tác trên các mảnh. Vì thế việc
phân mảnh sẽ làm tăng mức độ hoạt động đồng thời (song hành) và nhƣ vậy sẽ làm
tăng lƣu lƣợng hoạt động của hệ thống. Kiểu hoạt động đồng thời này mà chúng ta
gọi là đồng thời nội truy vấn (interquery concurrency).
Bên cạnh đó việc phân mảnh cũng tồn tại một số khiếm khuyết. Nếu ứng
dụng có những yêu cầu ngăn cản việc phân rã thành các mảnh để đƣợc sử dụng độc
quyền, thì những ứng dụng có các khung nhìn đƣợc định nghĩa trên nhiều mảnh sẽ
bị giảm hiệu suất hoạt động. Chẳng hạn nó có thể cần phải truy xuất dữ liệu từ hai
5
mảnh rồi nối hoặc hợp chúng lại với chi phí rất cao. Tránh đƣợc điều này là một vấn
đề cơ bản của kỹ thuật phân mảnh.
Vấn đề liên quan đến việc kiểm soát dữ liệu ngữ nghĩa (semantic data control),
đặc biệt là vấn đề kiểm tra tính toàn vẹn. Do kết quả của phân mảnh, các thuộc tính
tham gia vào một phụ thuộc có thể bị phân rã vào các mảnh khác nhau và đƣợc cấp
phát cho những vị trí khác nhau [1]. Trong trƣờng hợp này, một nhiệm vụ đơn giản nhƣ
kiểm tra các phụ thuộc cũng phải thực hiện truy tìm dữ liệu ở nhiều vị trí.

Tính tách biệt (disjointness): Nếu một quan hệ R đƣợc phân mảnh ngang
thành các quan hệ R
1
, R
2
, , R
k
và mục dữ liệu t
i
nằm trong mảnh R
i
thì nó
sẽ không nằm trong một mảnh R
k
, k i. Tiêu chuẩn này bảo đảm các mảnh
ngang phải đƣợc tách rời nhau. Nếu quan hệ đƣợc phân mảnh dọc thì các
thuộc tính chung phải đƣợc lặp lại trong mỗi mảnh. Do đó, trong trƣờng hợp
phân mảnh dọc tính tách biệt chỉ đƣợc định nghĩa trên các trƣờng không phải
là thuộc tính chung của quan hệ.
Ví dụ: Xét cơ sở dữ liệu của một công ty phần mềm đƣợc tổ chức nhƣ sau:
6
CANBO (MACB, TENCB, CHUCVU): là quan hệ chứa dữ liệu về cán bộ
của công ty. Bao gồm, tên cán bộ (TENCB), mã số của cán bộ (MACB), chức vụ
của cán bộ trong công ty (CHUCVU) và ngày sinh của cán bộ (NGAYSINH).
TIENLUONG (CHUCVU, MUCLUONG): là quan hệ chứa dữ liệu quản lý
các mức lƣơng của cán bộ trong công ty. Gồm hai trƣờng CHUCVU và
MUCLUONG (mức lƣơng tƣơng ứng với chức vụ).

Hùng
Dũng
Sinh
Phân tích HT
Lập trình viên
Phân tích HT
Phân tích HT
Lập trình viên
Kỹ sƣ điện tử
Phân tích HT
Thiết kế DL

C1
C2
C2
C3
C3
C4
C5
C6
C7
C8
P1
P1
P2
P3
P4
P2
P2
P4

PHANMEM TIENLUONG

Ví dụ về phân mảnh ngang:
Xét các phép toán đại số quan hệ sau:
PHANMEM 1 =
KINHPHI 20000
(PHANMEM)
PHANMEM 2 =
KINHPHI > 20000
(PHANMEM)
Bảng 1.2: Phân mảnh ngang Cơ sở dữ liệu
PHANMEM 1 PHANMEM 2

Dễ thấy, các mảnh thỏa mãn tính tái thiết được và tính đầy đủ
PHANMEM 1 PHANMEM ; PHANMEM 2 PHANMEM;
PHANMEM = PHANMEM 1 PHANMEM 2
Ví dụ về phân mảnh dọc:
Xét các phép toán đại số quan hệ sau:
PHANMEM 3 =
$1,$3
PHANMEM ; PHANMEM 4 =
$1,$4
PHANMEM
Bảng 1.3: Phân mảnh dọc Cơ sở dữ liệu
PHANMEM 3 PHANMEM 4
MAPM
TENPM
KINHPHI

CHUCVU

12000
MAPM
TENPM
KINHPHI
P3
P4
BẢO TRÌ
PHÁT TRIỂN
28000
25000
MAPM
KINHPHI

MAPM
TENPM
P1
P2
P3
P4
20000
12000
28000
25000

P1
P2
P3
P4
CSDL
CÀI ĐẶT

Việc định vị và phân tán dữ liệu ở các nút trong một mạng máy tính sẽ quyết
định tính hiệu quả và đúng đắn của hệ thống phân tán. Hiện nay ngƣời ta sử dụng 4
chiến lƣợc phân tán dữ liệu cơ bản là:
1.2.1. Tập trung dữ liệu
Tất cả các dữ liệu đƣợc tập trung tại một chổ. Cách này đơn giản nhƣng nó
tồn tại 3 nhƣợc điểm sau:
Dữ liệu không sẵn sàng cho ngƣời sử dụng khi truy nhập từ xa
Chi phí cho truyền thông lớn
Hệ thống ngừng hoạt động khi cơ sở dữ liệu bị sự cố
1.2.2. Chia nhỏ dữ liệu
Cơ sở dữ liệu đƣợc chia thành các phần nhỏ liên kết nhau (không trùng lặp).
Mỗi phần dữ liệu đƣợc đƣa đến các vị trí một cách thích hợp để sử dụng.
1.2.3. Sao lặp dữ liệu
Cơ sở dữ liệu đƣợc nhân thành nhiều bản từng phần hoặc đầy đủ và đƣợc đặt
ở nhiều vị trí trên mạng. Nếu bản sao của CSDL đƣợc lƣu giữ tại mọi vị trí của hệ
thống ta có trƣờng hợp sao lặp đầy đủ. Cách này thƣờng làm cực đại việc truy nhập
TENPM
KINHPHI
CSDL
CÀI ĐẶT
20000
12000
TENPM
KINHPHI
CSDL
CÀI ĐẶT
28000
25000
, , S
m
} trên đó có một tập các ứng dụng Q={Q
1
, Q
2
, ,
Q
q
} đang thực thi. Bài toán cấp phát (allocation problem) là tìm một phân phối tối
ƣu các mảnh F cho các vị trí S. Một phân phối đƣợc gọi là tối ƣu nếu nó thỏa mãn
hai yếu tố sau:
Chi phí nhỏ nhất: hàm chi phí bao gồm chi phí lƣu mỗi mảnh dữ liệu F
i
tại vị
trí S
j,
chi phí vấn tin F
i
tại vị trí S
j
, chi phí cập nhật F
i
tại tất cả các vị trí có
chứa nó, và chi phí truyền dữ liệu. Vì thế bài toán cấp phát sẽ tìm một lƣợc
đồ cấp phát với hàm chi phí là cực tiểu.
Hiệu quả: chiến lƣợc cấp phát đƣợc thiết kế nhằm cực tiểu hóa thời gian thực
hiện và tăng tối đa lƣu lƣợng hệ thống tại mỗi vị trí.
Ngƣời ta chứng minh đƣợc rằng bài toán cấp phát tổng quát, ký hiệu DAP
(database allocation problem) là một bài toán NP-đầy đủ. Vì thế hầu hết các nghiên

2.1.2. Chức năng của xử lý truy vấn
Biến đổi một truy vấn phức tạp thành một truy vấn tƣơng đƣơng đơn giản
hơn.
Phép biến đổi này phải đạt đƣợc cả về tính đúng đắn và hiệu quả.
Mỗi cách biến đổi dẫn đến việc sử dụng tài nguyên máy tính khác nhau,
nên vấn đề đặt ra là lựa chọn phƣơng án nào dùng tài nguyên ít nhất.
2.1.3. Các phương pháp xử lý truy vấn cơ bản
Phƣơng pháp biến đổi đại số:
Đơn giản hóa câu truy vấn nhờ các phép biến đổi đại số tƣơng đƣơng
nhằm giảm thiểu thời gian thực hiện các phép toán. Phƣơng pháp này
không quan tâm đến kích thƣớc và cấu trúc dữ liệu.
Phƣơng pháp ƣớc lƣợng chi phí:
Xác định kích thƣớc dữ liệu, thời gian thực hiện mỗi phép toán trong câu
truy vấn. Phƣơng pháp này quan tâm đến kích thƣớc dữ liệu và phải tính
toán chi phí thời gian thực hiện mỗi phép toán.
12
2.1.4. So sánh xử lý truy vấn tập trung và phân tán
* Tập trung:
 Chọn một truy vấn đại số quan hệ tốt nhất trong số tất cả các truy vấn
đại số tƣơng đƣơng.
 Các chiến lƣợc xử lý truy vấn có thể biểu diễn trong sự mở rộng của
đại số quan hệ.
* Phân tán:
Kế thừa chiến lƣợc xử lý truy vấn nhƣ môi trƣờng tập trung. Ngoài ra
phải quan tâm thêm:
 Các phép toán truyền dữ liệu giữa các trạm
 Chọn các trạm tốt nhất để xử lý dữ liệu


14
2.2.1.2. Giao dịch (Transaction):
Giao dịch là một đơn vị tính toán nhất quán và tin cậy trong các hệ cơ sở dữ
liệu phân tán, nó hàm chứa một số các đặt tính cơ bản nhƣ tính nguyên tố và tính
bền vững, nhằm chỉ ra sự khác biệt giữa một giao dịch và một câu truy vấn.
Về mặt trực quan, giao dịch nhận một cơ sở dữ liệu và thực hiện trên nó một
hành động làm thay đổi trạng thái, tạo ra một cơ sở dữ liệu mới. Nếu cơ sở dữ liệu
nhất quán trƣớc khi thực thi giao dịch, có thể đảm bảo rằng cơ sở dữ liệu cũng sẽ
nhất quán vào lúc kết thúc thực thi giao dịch dù cho thực thi đồng thời nhiều giao
dịch cùng một lúc hay là xảy ra sự cố trong quá trình thực thi.
Một giao dịch là một đơn vị thực hiện chƣơng trình truy xuất và có thể cập
nhật nhiều mục dữ liệu. Một giao dịch thƣờng là kết quả của sự thực hiện một
chƣơng trình ngƣời dùng và đƣợc phân cách bởi các câu lệnh (hoặc các lời gọi hàm)
có dạng Begin transaction và End transaction. Nó bao gồm tất cả các hoạt động thực
hiện giữa Begin transaction và End transaction.
Các lệnh của giao dịch 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 dịch:
- Start(): Bắt đầu thực hiện một giao dịch.
- Commit(): Kết thúc thành công một giao dịch.
- Abort(): Hủy bỏ một giao dịch.
2.2.2. Tính chất của giao dịch
a) Tính nguyên tố (Atomicity)
Một giao dịch khi thực hiện thành công với sự phản ánh đúng trong cơ
sở dữ liệu hoặc bị hủy bỏ và không có thay đổi gì trong cơ sở dữ liệu.
Một giao dịch kết thúc thành công (gọi lệnh Commit) sau khi hoàn tất

rằng kết quả giao dịch 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 dịch.
16
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 dịch.
Trƣờng hợp đĩa bị lỗi, dữ liệu đƣợc phục hồi từ dữ liệu sao lƣu dự
phòng, đĩa mirror,
e) Ví dụ
Giả sử rằng có một CSDL về thông tin ngân hàng.
Accounts : chứa thông tin về tài khoản và số dƣ của khách hàng.
Công việc cần thực hiện là chuyển tiền từ tài khoản của một ngân hàng
sang một tài khoản của một ngân hàng khác.
Ví dụ 1
- Thủ tục sau đây mô phỏng giao dịch chuyển tiền:
Procedure Transfer
Begin
Start;
input(fromaccount, toaccount, amount);
/‟ This procedure transfers “amount” from “fromaccount” into
“toaccount.‟ ”
temp : = Read(Accounts[fromaccount]);
if temp < amount then
begin
output(“insufficient funds”);
Abort;
end