Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ LOAN TỐI ƯU HOÁ TRUY VẤN
TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN LUẬN VĂN THẠC SĨ
KHOA H ỌC M ÁY T ÍNH
LUẬN VĂN THẠC SĨ
KHOA HỌC M ÁY T ÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS ĐOÀN VĂN BAN
Thái nguyên, 2011
Thái nguyên, 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CAM ĐOAN

Tôi xin cam đoan, kết quả của luận văn hoàn toàn là kết quả
của tự bản thân tôi tìm hiểu, nghiên cứu. Các tài liệu tham khảo

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CẢM ƠN

Lời đầu tiên tôi xin gửi lời cảm ơn chân thành nhất đến thầy
PGS.TS Đoàn Văn Ban đã định hƣớng và nhiệt tình hƣớng dẫn,
giúp đỡ tôi rất nhiều về mặt chuyên môn trong quá trình làm luận
văn.
Tôi xin gửi lời biết ơn sâu sắc đến các thầy, các cô đã dạy dỗ
và truyền đạt những kinh nghiệm quý báu cho chúng tôi trong suốt
hai năm cao học ở trƣờng Đại học Công nghệ thông tin và truyền
thông.
Cuối cùng tôi xin dành tình cảm thân thiết nhất cho bạn bè,
đồng nghiệp, cha mẹ và gia đình, những ngƣời luôn gần gũi để
động viên, chia sẻ cùng tôi trong suốt thời gian qua.

Thái Nguyên, tháng 9 năm 2011
Nguyễn Thị Loan
1.1. Khái niệm về hệ cơ sở dữ liệu phân tán…………………………… 3
1.1.1. Khái niệm……………………………………………………… 3
1.1.2. Các đặc điểm chính của cơ sở dữ liệu phân tán…………………4
1.1.3. Mục đích của việc sử dụng cơ sở dữ liệu phân tán…………… 8
1.2. Các đặc trƣng trong suốt của cơ sở dữ liệu phân tán……………… 9
1.2.1.Trong suốt phân tán………………………………………………9
1.2.2. Trong suốt giao dịch…………………………………………….10
1.2.3.Trong suốt các sự cố…………………………………………… 10
1.2.4. Trong suốt thao tác…………………………………………… 10
1.2.5.Trong suốt về tính không thuần nhất…………………………… 10
1.3.Kiến trúc cơ bản của cơ sở dữ liệu phân tán…………………………10
1.3.1.Sơ đồ tổng thể……………………………………………………11
1.3.2. Sơ đồ phân đoạn……………………………………………… 11
1.3.3. Sơ đồ định vị…………………………………………………….12
1.3.4. Sơ đồ ánh xạ địa phương……………………………………….12

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1.3.5. Chia sẻ tài nguyên……………………………………………… 14
1.4. Các kỹ thuật xây dựng cơ sở dữ liệu phân tán…………………… 14
1.4.1.Phân tán……………………………………………………………14
1.4.1.1. Phân đoạn ngang………………………………………… …14
1.4.1.2. Phân đoạn ngang dẫn tiếp……………………………… 15
1.4.1.3. Phân đoạn dọc……………………………………………….16
1.4.1.4. Phân đoạn hỗn hợp………………………………………… 17
1.4.2.Nhân bản dữ liệu……………………………………………… 18
1.4.3. Định vị dữ liệu………………………………………………….19
1.4.4. Hệ quản trị CSDL phân tán…………………………………….19.
1.5. Kết luận……………………………………………………………….20

2.7. Khái quát về xử lý câu truy vấn………………………………… 55
2.7.1. Vấn đề xử lý truy vấn………………………………………….56
2.7.2. Các mục tiêu của xử lý câu truy vấn………………………… 56
2.7.3. Các giai đoạn xử lý câu truy vấn………………………………57
2.7.4. Tối ưu hóa các truy vấn phân tán…………………………… 57
2.7.4.1. Đầu vào bộ tối ưu hóa câu truy vấn………………………58
2.7.4.2. Thứ tự kết nối trên các câu truy vấn đoạn……………… 63
2.7.4.3.Thứ tự kết nối…………………………………………… 63
2.7.4.4. Các thuật toán dựa trên phép nửa kết nối……………… 65
2.8. Các thuật toán tối ƣu hóa truy vấn phân tán……………………….69
2.8.1. Thuật toán INGRES phân tán…………………………………70
2.8.2. Thuật toán R
*
………………………………………………….72
2.8.3. Thuật toán SDD -1…………………………………………….76
2.8.4. Các thuật toán AHY ( Apers – Hevner – Yao)…………………80
2.9. Kết luận…………………………………………………………….86
Chƣơng 3. CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN…………………89
3.1. Xác định thuật toán……………………………………………… 89
3.2. Cài đặt thử nghiệm thuật toán…………………………………… 89
3.2.1. Cấu trúc cơ sở dữ liệu………………………………………….89
3.2.2. Xây dựng ứng dụng……………………………………………90
3.2.3. Thử nghiệm 1………………………………………………….92
3.2.4. Thử nghiệm 2………………………………………………….94
3.3. Kết luận. ………………………………………………………… 95

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI……………………96
Hình 2.18. Rút gọn phân đoạn hỗn hợp………………………………… 55
Hình 2.19. Sơ đồ phân lớp cho việc xử lý truy vấn phân tán…………… 57
Hình 2.20. Truyền các toán hạng trong phép toán hai ngôi……………….64
Hình 2.21. Đồ thị kết nối của câu truy vấn phân tán…………………… 64
Hình 2.22. Biến đổi của câu truy vấn chu trình………………………… 68
Hình 2.23. Câu truy vấn ví dụ và các thống kê………………………… 79
Hình 2.24. Ví dụ một câu truy vấn đơn và các thống kê………………….82
Hình 2.25. Schedule tối ƣu……………………………………………… 83
Hình 2.26. Các giai đoạn của việc đánh giá một câu truy vấn phân tán….87

-1-
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

PHẦN MỞ ĐẦU
1. Đặt vấn đề.
Ngày nay lĩnh vực thương mại ngày càng mở rộng và phát triển . Để kinh

phân tán.
4. Phƣơng pháp nghiên cứu.
- Nghiên cứu lý thuyết: Tìm hi ểu nghiên cứu các tài liệu liên quan trong sách,
tạp chí, các bài báo trên mạng Internet… Tổng hợp, so sánh các kết quả viết lại
thành luận văn.
- Nghiên cứu thực nghiệm: Cài đặt thử nghiệm.
5. Ý nghĩa khoa học của đề tài.
- Giảm thiểu thời gian xử lý
- Giảm vùng nhớ trung gian
- Giảm chi phí truyền thông giữa các trạm.
6. Các kết quả dự kiến đạt đƣợc
- Giới thiệu tổng quan về CSDL phân tán.
- Trình bày các phương pháp, thuật toán tối ưu hóa truy vấn phân tán.
- Cài đặt thử nghiệm một thuật toán tối ưu truy vấn phân tán.
-3-
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Chƣơng 1. CƠ SỞ DỮ LIỆU PHÂN TÁN
1.1. Khái niệm về hệ cơ sở dữ liệu phân tán
1.1.1. Khái niệm
Cơ sở dữ liệu phân tán [3] là một tập hợp các dữ liệu phụ thuộc lôgic lẫn
nhau của cùng một hệ thống và được lưu trữ trên các trạm của một mạng máy tính.
Cơ sở dữ liệu phân tán làm tăng khả năng truy nhập tới cơ sở dữ liệu lớn trên mạng.
Trong hệ thống đó mỗi máy tính quản lý một cơ sở dữ liệu thành phần được gọi là 1
node hoặc site.
Hệ quản trị cơ sở dữ liệu phân tán (DBMS) là phần mềm quản trị cơ sở dữ
liệu, đảm bảo trong suốt đối với người sử dụng và cho phép tính tự trị nghĩa là mỗi
cơ sở dữ liệu thành phần vẫn được quản trị độc lập và riêng biệt.
Một CSDL phân tán là một tập hợp nhiều CSDL có liên đới logic và được
phân bố trên một mạng máy tính

Tính mở của hệ thống phân tán là tính dễ dàng mở rộng phần cứng của nó.
Một hệ thống được gọi là có tính mở thì phải có các điều kiện sau:
- Hệ thống có thể tạo nên bởi nhiều loại phần cứng và phần mềm của nhiều
nhà cung cấp khác nhau.
- Có thể bổ sung vào các dịch vụ dùng chung tài nguyên mà không phá hỏng
hay nhân đôi các dịch vụ đang tồn tại.
- Tính mở được hoàn thiện bằng cách xác định hay phân định rõ các giao
diện chính của một hệ và làm cho nó tương thích với các nhà phát triển phần mềm.
- Tính mở của hệ phân tán dựa trên việc cung cấp cơ chế truyền thông giữa
các tiến trình và công khai các giao diện dùng để truy nhập các tài nguyên chung.
3. Khả năng song song
Hệ phân tán hoạt động trên một mạng truyền thông có nhiều máy tính, mỗi
máy có thể có một hay nhiều CPU.
Có thể thực hiện nhiều tiến trình trong cùng một thời điểm. Việc thực hiện
tiến trình theo cơ chế phân chia thời gian (một CPU) hay (nhiều CPU).
Khả năng làm việc song song trong hệ phân tán được thể hiện qua hai tình
huống sau:
- Nhiều người sử dụng đồng thời đưa ra các lệnh hay các tương tác với các
chương trình ứng dụng.
- Nhiều tiến trình Server chạy đồng thời, mỗi tiến trình phải đáp ứng yêu cầu
từ các Clients.

-5-
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

4. Khả năng mở rộng
Hệ phân tán có khả năng hoạt động tốt và hiệu quả ở nhiều mức khác nhau.
Một hệ phân tán nhỏ nhất có thể hoạt động chỉ cần hai trạm làm việc và một File
Server. Các hệ lớn hơn tới hàng nghìn máy tính.
Khả năng mở rộng của một hệ phân tán được đặc trưng bởi tính không thay

thấy tính trong suốt này được thể hiện như sau:
Khi muốn tìm một người có Id=”Id1“ thì chỉ cần tìm trên quan hệ tổng
thể NCC mà không cần biết quan hệ NCC có phân tán hay không.
SELECT *
FROM NCC
WHERE Id=”Id1” Tính trong suốt về vị trí (location transparency):
- Người sử dụng không cần biết về vị trí vật lý của dữ liệu mà có quyền truy
cập đến cơ sở dữ liệu tại bất cứ vị trí nào.
- Các thao tác để lấy hoặc cập nhật một dữ liệu từ xa được tự động thực hiện
bởi hệ thống tại điểm đưa ra yêu cầu.
- Tính trong suốt về vị trí rất hữu ích, nó cho phép người sử dụng bỏ qua các
bản sao dữ liệu đã tồn tại ở mỗi vị trí. Do đó có thể di chuyển một bản sao dữ liệu từ
một vị trí này đến một vị trí khác và cho phép tạo các bản sao mới mà không ảnh
hưởng đến các ứng dụng.
Hình 1.1:Trong suốt phân đoạn
DDBMS
NCC
1

trả về biến điều khiển #FOUND thì một câu lệnh truy vấn tương tự được
thực hiện trên phân đoạn NCC2 ,
• Ở đây quan hệ NCC2 được sao làm hai bản trên hai vị trí 2 và vị trí 3, ta chỉ
cần tìm thông tin trên quan hệ NCC2 mà không cần quan tâm nó ở vị trí nào.
Trong suốt ánh xạ cục bộ (local mapping transparency):
- Là một đặc tính quan trọng trong một hệ thống DBMS không đồng nhất
-Ứng dụng tham chiếu đến các đối tượng có các tên độc lập từ các hệ thống
cục bộ.
DBMS
NCC
1

NCC
2

NCC
2

Vị trí
3


Xuất phát từ yêu cầu thực tế về tổ chức và kinh tế: Trong thực tế nhiều tổ
chức là không tập trung, dữ liệu ngày càng lớn và phục vụ cho đa người dùng nằm
phân tán, vì vậy cơ sở dữ liệu phân tán là con đường thích hợp với cấu trúc tự nhiên
của các tổ chức đó. Đây là một trong những yếu tố quan trọng thức đẩy việc phát
triển cơ sở dữ liệu phân tán.
Sự liên kết các cơ sở dữ liệu địa phương đang tồn tại: cơ sở dữ liệu phân tán
là giải pháp tự nhiên khi có các cơ sở dữ liệu đ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 cơ sở dữ liệu phân tán được tạo từ
dưới lên dựa trên nền tảng cơ sở dữ liệu đang tồn tại. Tiến trình này đòi hỏi cấu trúc
lại các cơ sở dữ liệu cục bộ ở một mức nhất định. Dù sao, những sửa đổi này vẫn là
nhỏ hơn rất nhiều so với việc tạo lập một cở sở dữ liệu tập trung hoàn toàn mới.
Vị trí
2

Vị trí
1

DBMS
NCC
1

NCC
2

Hình 1.3:Sự trong suốt ánh xạ cục bộ
-9-
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Làm giảm tổng chi phí tìm kiếm: Việc phân tán dữ liệu cho phép các nhóm
làm việc cục bộ có thể kiểm soát được toàn bộ dữ liệu của họ. Tuy vậy, tại cùng

-10-
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

giảm truyền tải trên mạng lớn. Hệ thống cho phép tiếp tục thực hiện nếu như các
trạm từ xa có sự cố. Trong suốt bản sao đảm bảo user không biết đó là các bản sao
vì dữ liệu luôn được cập nhật và đồng bộ với dữ liệu gốc.
+ Trong suốt phân đoạn: Một quan hệ trong cơ sở dữ liệu phân tán có thể
phân đoạn ngang hoặc phân đoạn dọc nghĩa là được tách thành các bộ dữ liệu hoặc
các quan hệ con và lưu trữ trên nhiều trạm khác nhau. Trong suốt phân đoạn cho
phép người sử dụng không cần biết có sự phân đoạn, các truy vấn dữ liệu vẫn được
viết như cơ sở dữ liệu tập trung.
1.2.2 Trong suốt giao dịch
Cơ sở dữ liệu phân tán cho phép một giao dịch có thể cập nhật, sửa đổi dữ
liệu trên các trạm khác nhau. Để đảm bảo dữ liệu nhất quán trên toàn hệ thống, các
trạm trong giao dịch chỉ ủy thác khi tất cả các trạm đã ủy thác thành công hoặc roll
back khi một trạm bị thất bại.
1.2.3 Trong suốt các sự cố
Đảm bảo tại một trạm của hệ thống bị hỏng thì hệ thống vẫn làm việc bình
thường (do cơ chế tạo bản sao hoặc làm việc trên các trạm không bị sự cố). Nếu
mạng hoặc hệ thống có sự cố trong khi ủy thác của giao dịch cơ sở dữ liệu phân tán
thì giao dịch đó được giải quyết tự động và trong suốt theo nghĩa khi mạng hoặc hệ
thống khôi phục thì tất các các trạm này hoặc là ủy thác hoặc là roll back lại giao
tác đó.
1.2.4 Trong suốt thao tác
Cho phép các câu lệnh thao các dữ liệu đơn giản để truy nhập được các cơ sở
dữ liệu tại trạm cục bộ hoặc trạm từ xa. Các thao tác xử lý dữ liệu từ xa không phức
tạp và vẫn đảm bảo vẫn giống như khi thao tác dữ liệu trên hệ cơ sở dữ liệu không
phân tán.
1.2.5 Trong suốt về tính không thuần nhất
Cho phép hỗn hợp nhiều hệ quản trị cơ sở dữ liệu khác nhau với các khả

(DBMS 1)
HÖ qu¶n trÞ CSDL t¹i vÞ trÝ n
(DBMS n)
Sơ ®å ¸nh x¹ ®Þa ph-¬ng 1
(Local mapping Schema 1)
Sơ ®å ¸nh x¹ ®Þa ph-¬ng n
(Local mapping Schema n)
Sơ ®å ®Þnh vÞ
(Allocation Schema)
Sơ ®å ph©n m¶nh
(Fragmentation Schema)
Sơ ®å tổng thể
(Global Schema)
Các
sơ
đồ
độc
lập
vị
trí
Hình 1.4. Kiến trúc CSDL phân tán
-12-
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

định nghĩa trong sơ đồ phân đoạn (fragmentation Schema),
- Các đoạn được mô tả bằng tên của quan hệ tổng thể cùng với chỉ mục đoạn.
Chẳng hạn, Ri được hiểu là đoạn thứ i của quan hệ R.
1.3.3. Sơ đồ định vị (allocation schema):
- Các đoạn là các phần logic của một quan hệ tổng thể được định vị vật lý trên
một hay nhiều trạm. R
1

R
2

R
3

R
4

R
1
2R
2
2

R
2
3R
2
1

Hình 1.5: Các đoạn và hình ảnh vật lý của một quan hệ tổng thể

-13-
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Ba yếu tố được suy ra từ kiểu kiến trúc này là:
- Tách rời khái niệm phân đoạn dữ liệu với khái niệm định vị dữ liệu.
- Biết được dữ liệu dư thừa
- Độc lập với các DBMS địa phương
Ba yếu tố này tương ứng với ba mức trong suốt tương ứng
a. Tách rời khái niệm phân đoạn dữ liệu với khái niệm định vị dữ liệu.
• Phân đoạn dữ liệu, bao gồm những công việc mà người lập trình ứng dụng
làm việc với quan hệ tổng thể, phân chia quan hệ tổng thể thành các đoạn.
• Thông qua tính trong suốt phân đoạn (fragmentation transparency) người
lập trình sẽ nhìn thấy được những đoạn dữ liệu bị phân chia như thế nào.
• Định vị dữ liệu lại liên quan đến các công việc của người sử dụng và người
lập trình ứng dụng tại trên các đoạn dữ liệu được định vị tại các trạm.
• Thông qua tính trong suốt vị trí (location transparency) người lập trình sẽ
biết được vị trí của các đoạn dữ liệu trên các trạm.
b. Biết được dữ liệu dư thừa:
• Người lập trình ứng dụng có thể biết được dư thừa dữ liệu ở các trạm.
• Trên hình vẽ trên, chúng ta thấy rằng hai ảnh vật lý R2 và R3 có trùng lặp
dữ liệu. Do đó các đoạn dữ liệu trùng nhau có thể tránh được khi xây dựng
các khối ảnh vật lý.

Một sự phân đoạn là đúng đắn nếu thoả mãn ba điều kiện sau:
- Điều kiện không mất thông tin: Tất cả dữ liệu của quan hệ tổng thể phải
đựơc ánh xạ tới các đoạn, có nghĩa mỗi phần tử dữ liệu thuộc quan hệ tổng thể
phải thuộc một hay nhiều đoạn của nó.
- Điều kiện xây dựng lại: Luôn có thể xây dựng lại được quan hệ tổng thể từ
các đoạn đã có.
- Điều kiện rời nhau (chỉ áp dụng cho phân đoạn ngang): Để tối thiểu hoá sự
lặp lại của dữ liệu.
1.4.1.1 Phân đoạn ngang
Phân đoạn ngang là sự phân chia một quan hệ thành các tập con các bộ, mỗi
tập con được xác định bởi phép chọn với tân từ p trên quan hệ tổng thể R:
R
i
=p
i
, với p
i
là tân từ của R
i
. Để có thể khôi phục được R ta dùng phép hợp các
-15-
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

quan hệ R = R
1
 R
2
  R
n
.

 NCC
2
= 

Tổng quát:
- Điều kiện không mất thông tin nếu tập các tân từ của tất cả các đoạn phải
đầy đủ.
- Điều kiện xây dựng lại luôn luôn thoả mãn với phép hợp.
- Điều kiện rời nhau đòi hỏi các tân từ phải loại trừ nhau.
1.4.1.2 Phân đoạn ngang dẫn tiếp
Phân đoạn ngang dẫn tiếp là sự phân chia một quan hệ ban đầu thành các
quan hệ thứ hai khác mà các quan hệ đó liên hệ với quan hệ ban đầu bằng một khoá
ngoài. Điều này như là liên hệ dữ liệu giữa quan hệ ban đầu và quan hệ thứ hai
được phân đoạn trong cùng một cách.
Ví dụ 1.6: Xét quan hệ tổng thể
CUNGCAP(SHNCC, SHSP, SHPHONG, SOLUONG)
Trong đó có các thuộc tính:
SHNCC: Số hiệu nhà cung cấp
SHSP: Số hiệu sản phẩm
-16-
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

SHPHONG: Số hiệu phòng
SOLUONG: Số lượng
Phân đoạn ngang dẫn tiếp của quan hệ CUNGCAP được thực hiện như sau:
CUNGCAP
1
= CUNGCAP ⋉SHNCC=SHNCCNCC
1
CUNGCAP

1
hoặc
p.SHNCC  NCC
2
qua ⋉ => s CUNGCAP
2
=> Thoả mãn điều kiện không mất thông tin
- Điều kiện xây dựng lại: CUNGCAP = CUNGCAP
1
 CUNGCAP
2
- Điều kiện rời nhau: Ta chứng minh: CUNGCAP
1
 CUNGCAP
2
= 
Giả sử: p  CUNGCAP
1
& CUNGCAP
2
=> p
1
 NCC
1
p.SHNCC=p
1
.SHNCC
=> p
2
 NCC