ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN


HỒ PHÚ CƯỜNG

TỐI ƯU TRUY VẤN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN

LUẬN VĂN THẠC SĨ
Ngành: Công Nghệ Thông Tin
Mã ngành: 60.48.02.01

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. NGUYỄN ĐÌNH THUÂN

TP. HỒ CHÍ MINH – 2017


LỜI CẢM ƠN
Xin chân thành cảm ơn Phòng Đào tạo Sau Đại học, Bộ môn Khoa học và Kỹ
thuật thông tin, Trường Đại học Công nghệ thông tin TPHCM đã chấp nhận và tạo
điều kiện để đề tài luận văn cao học này được thực hiện.
Đặc biệt, xin bày tỏ lòng biết ơn sâu sắc đến PGS. TS. Nguyễn Đình Thuân,
Trưởng Khoa Hệ thống thông tin, Trường Đại học Công nghệ Thông tin TP.HCM đã
tận tình hướng dẫn, chỉ bảo, giúp đỡ, định hướng cho đề tài trong suốt thời gian luận
văn được thực hiện. Đồng thời, xin chân thành cảm ơn các Quý Thầy Cô đã tận tình
giảng dạy, trang bị, bổ sung thêm nhiều kiến thức quý báu trong suốt thời gian khóa
học.
Mặc dù rất nỗ lực để hoàn thành luận văn, tuy nhiên trong quá trình thực hiện
đề tài luận văn không tránh khỏi sai sót, kinh mong nhận được sự nhận xét, góp ý từ

Quý Thầy Cô. Xin chân thành cảm ơn.

Học viên
Hồ Phú Cường
10/2017

i


LỜI CAM ĐOAN
Tôi xin cam đoan luận văn “Tối ưu truy vấn trong cơ sở dữ liệu phân tán” tuân
thủ các quy định hiện hành của pháp luật về sở hữu trí tuệ. Các số liệu sử dụng trong
luận văn là trung thực. Các kết quả nguyên cứu trong luận văn là kết quả lao động
chính của tôi, chưa được người khác công bố trong bất cứ một công trình nghiên cứu
nào.
Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách nhiệm về
nội dung luận văn của mình.
Học viên

Hồ Phú Cường

ii


DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
Ký hiệu/

Viết đầy đủ

Dịch nghĩa/ Mô tả


Chữ viết tắt
Đồ thị vô hướng mà giữa hai

Clique

điểm bất kỳ trong đồ thị đều tồn
tại một đường đi
CSDL

Cơ sở dữ liệu

DP

Dynamic Programming

Quy hoạch động

IDP

Iterative Dynamic

Quy hoạch động lặp

Programming
IDP+

Thuật toán IDP cải tiến cách tiếp
cận


Linked-Server

Các trạm liên kết trong hệ thống
CSDL phân tán của SQL Server

SDD-1

System

for

Distributed Hệ thống cho CSDL phân tán

Databases
Semi-join

Phép kết nối nửa

SQL

Trình quản trị CSDL của SQL

Management

Server

Studio
T-SQL

Ngôn ngữ lập trình CSDL hướng


Transact-SQL

thủ tục của Microsoft sử dụng
trong SQL Server.

iii


DANH MỤC CÁC BẢNG
Bảng 4.1: Mô tả các quan hệ trong CSDL thực nghiệm ...........................................53
Bảng 4.2: Mô tả phân tán quan hệ trong CSDL thực nghiệm...................................56

iv


DANH MỤC CÁC HÌNH ẢNH
Hình 1.1: Ví dụ hoạt động của semi-join ....................................................................7
Hình 2.1: Môi trường hệ thống CSDL phân tán [10] ................................................14
Hình 2.2: Mô hình kiến trúc client-server [26] .........................................................15
Hình 2.3: Quy trình tối ưu truy vấn ..........................................................................17
Hình 2.4: Cấu trúc của cây kết nối ............................................................................18
Hình 2.5: Công thức xác định tổng thời gian [27] ....................................................19
Hình 2.6: Thuật toán tối ưu quy hoạch động cổ điển [28] ........................................22
Hình 3.1: Thuật toán tối ưu IDP [8] ..........................................................................29
Hình 3.3: Biểu đồ kết của truy vấn ...........................................................................34
Hình 3.4: Các phương án có 2 quan hệ .....................................................................34
Hình 3.5: Các phương án có 3 quan hệ .....................................................................34
Hình 3.6: Phương án có 3 quan hệ được chọn ..........................................................34
Hình 3.7: Các phương án có 2 quan hệ trong lần lặp thứ hai ...................................35

Hình 3.8: Các phương án có 3 quan hệ trong lần lặp thứ hai ...................................35
Hình 3.9: Phương án có 3 quan hệ được chọn trong lần lặp thứ hai.........................35
Hình 3.10: Các phương án có 2 quan hệ trong lần lặp thứ ba...................................36
Hình 3.11: Phương án tối ưu sau cùng ......................................................................36
Hình 4.1: Các thành phần của hệ tối ưu truy vấn ......................................................40
Hình 4.2: Sơ đồ quan hệ của dữ liệu thống kê ..........................................................41
Hình 4.3: Sơ đồ quan hệ của phương án thực thi truy vấn, phép kết và quan hệ. ....43
Hình 4.4: Một phương án thực thi truy vấn được lưu trong hệ thống mô phỏng .....43
Hình 4.5: Phương án thực thi khi được biểu diễn dưới dạng cây nhị phân ..............43
Hình 4.6: Một phương án thực thi truy vấn hoàn chỉnh được lưu trong Danh mục .45
Hình 4.7: Module thực thi phương án truy vấn đặt tại các trạm ...............................45
Hình 4.8. Đoạn mã sử dụng hoạt động sao chép số lượng lớn .................................46
Hình 4.9: Giao diện Thực nghiệm 1..........................................................................47
Hình 4.10: Giao diện Thực nghiệm 2........................................................................48
Hình 4.11: Ví dụ một phương án thực thi truy vấn hoàn chỉnh được tạo ra .............49
Hình 4.12: Phương án thực thi truy vấn dưới dạng cây nhị phân .............................50
Hình 4.13 : Cấu trúc truy vấn hình chuỗi ..................................................................51
Hình 4.14 : Cấu trúc truy vấn hình sao .....................................................................51
Hình 4.15: Cấu trúc truy vấn clique ..........................................................................51
v


Hình 4.16: Cấu trúc truy vấn .....................................................................................53
Hình 4.17: Ví dụ cấu trúc truy vấn............................................................................53
Hình 4.18: Sơ đồ quan hệ của CSDL thực nghiệm ...................................................55
Hình 4.19: Sơ đồ kết nối giữa các trạm.....................................................................56
Hình 4.20: Kết quả chạy thuật toán với n=10, biểu đồ kết hình chuỗi .....................59
Hình 4.21: Kết quả chạy thuật toán với n=10, biểu đồ kết hình sao .........................59
Hình 4.22: Kết quả chạy thuật toán với n=10, biểu đồ kết hình clique ....................59
Hình 4.23: So sánh thuật toán IDP+ với thuật toán tối ưu tham lam, biểu đồ kết

hình chuỗi ..................................................................................................................60
Hình 4.24: So sánh thuật toán IDP+ với thuật toán tối ưu tham lam, biểu đồ kết
hình sao .....................................................................................................................60
Hình 4.25: So sánh thuật toán IDP+ với thuật toán tối ưu tham lam, biểu đồ kết
hình clique .................................................................................................................61
Hình 4.26: Kết quả chạy thuật toán với n=15, biểu đồ kết hình chuỗi .....................61
Hình 4.27: Kết quả chạy thuật toán với n=15, biểu đồ kết hình sao .........................62
Hình 4.28: Kết quả chạy thuật toán với n=15, biểu đồ kết hình clique ....................62
Hình 4.29: Kết quả chạy thuật toán với n=20, biểu đồ kết hình chuỗi .....................62
Hình 4.30: Kết quả chạy thuật toán với n=20, biểu đồ kết hình sao .........................63
Hình 4.31: Kết quả chạy thuật toán với n=20, biểu đồ kết hình clique ....................63
Hình 4.32: Thời gian tối ưu và thời gian thực thi phương án của IDP, IDP+ ...........65
Hình 4.33: Thời gian trả về kết quả truy vấn cho người dùng ..................................65
Hình 4.34: Thời gian tối ưu và thời gian thực thi phương án của IDP, IDP+ ...........66
Hình 4.35: Thời gian trả về kết quả truy vấn cho người dùng ..................................67
Hình 4.36: Giao diện chương trình mô phỏng thực hiện tối ưu truy vấn .................67

vi


MỤC LỤC
LỜI CẢM ƠN ............................................................................................................ i
LỜI CAM ĐOAN ..................................................................................................... ii
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ........................................... iii
DANH MỤC CÁC BẢNG ...................................................................................... iv
DANH MỤC CÁC HÌNH ẢNH ...............................................................................v
MỤC LỤC ............................................................................................................... vii
MỞ ĐẦU ....................................................................................................................1
CHƯƠNG 1. TỔNG QUAN VỀ TỐI ƯU TRUY VẤN CƠ SỞ DỮ LIỆU
PHÂN TÁN ................................................................................................................4

1.1. Giới thiệu về tối ưu truy vấn: ...........................................................................4
1.2. Các nghiên cứu về tối ưu truy vấn cơ sở dữ liệu phân tán:..............................5
CHƯƠNG 2: CÁC THÀNH PHẦN QUAN TRỌNG TRONG TỐI ƯU TRUY
VẤN CƠ SỞ DỮ LIỆU PHÂN TÁN .....................................................................13
2.1. Giới thiệu: ......................................................................................................13
2.2. Kiến trúc hệ thống cơ sở dữ liệu phân tán: ....................................................14
2.3. Xử lý truy vấn trong cơ sở dữ liệu phân tán: .................................................16
2.4. Tối ưu truy vấn cơ sở dữ liệu phân tán: .........................................................17
2.4.1. Không gian tìm kiếm:..............................................................................17
2.4.2. Mô hình chi phí: ......................................................................................19
2.4.3. Thuật toán tối ưu quy hoạch động: .........................................................21
CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN IDP VỚI SỰ CẢI TIẾN CÁCH
TIẾP CẬN ................................................................................................................26
3.1. Giới thiệu: ......................................................................................................26
3.2. Thuật toán tối ưu IDP và cách tiếp cận cải tiến: ............................................27
3.2.1. Mô tả thuật toán tối ưu IDP: ...................................................................27
3.2.2. Cách tiếp cận đề xuất cải tiến thuật toán IDP: ........................................31
3.2.3. Lưu đồ thuật toán IDP+: ..........................................................................33
3.2.4. Ví dụ minh họa hoạt động của thuật toán IDP+: .....................................33
3.2.5. Độ phức tạp thuật toán IDP+: ..................................................................36
CHƯƠNG 4: HỆ THỐNG MÔ PHỎNG ỨNG DỤNG THUẬT TOÁN IDP+
TỐI ƯU TRUY VẤN CSDL PHÂN TÁN VÀ KẾT QUẢ THỰC NGHIỆM...40
4.1. Hệ thống mô phỏng ứng dụng thuật toán IDP+ trong tối ưu truy vấn CSDL
phân tán: ................................................................................................................40
vii


4.1.1. Môi trường ứng dụng: .............................................................................40
4.1.2. Mô tả hệ thống: .......................................................................................40
4.1.3. Các chức năng chính của hệ thống mô phỏng: .......................................46

4.2. Dữ liệu mô phỏng: .........................................................................................51
4.3. Kết quả thực nghiệm: .....................................................................................58
4.3.1. Thực nghiệm 1: .......................................................................................58
4.3.2. Thực nghiệm 2: .......................................................................................64
4.2.3. Đánh giá: .................................................................................................67
CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .....................................69
5.1. Kết luận: .........................................................................................................69
5.2. Hướng phát triển: ...........................................................................................69
TÀI LIỆU THAM KHẢO ......................................................................................71

viii


MỞ ĐẦU
Hiện nay, quy mô hoạt động, sản xuất, kinh doanh của các tổ chức, doanh nghiệp
được mở rộng một cách mạnh mẽ, cơ cấu tổ chức không còn tập trung mà phân tán
trên phạm vi rộng, hệ thống thông tin của họ cũng được đầu tư tương ứng. Với sự
phát triển của hệ thống mạng truyền thông, cơ sở dữ liệu phân tán ngày càng được
triển khai phổ biến, tận dụng những ưu điểm của dữ liệu phân tán nhằm đáp ứng nhu
cầu khai thác dữ liệu từ nhiều chi nhánh khác nhau của các tổ chức, doanh nghiệp.
Cùng với sự lớn mạnh về quy mô của tổ chức, doanh nghiệp, kích thước cơ sở
dữ liệu cũng tăng lên. Các truy vấn dữ liệu ngày càng phức tạp khi số lượng các quan
hệ và số lượng các phép kết trong truy vấn tăng lên. Do đó, tối ưu truy vấn đóng một
vai trong quan trọng trong hệ thống quản trị cơ sở dữ liệu, thực hiện tối ưu truy vấn
trên cơ sở của ba thành phần quan trọng gồm không gian tìm kiếm, mô hình chi phí,
các chiến lược tìm kiếm, giúp tìm ra các phương án thực thi truy vấn với chi phí thấp.
Tối ưu truy vấn trong một môi trường cơ sở dữ liệu phân tán là một vấn đề khó khăn
để giải quyết.
Nhiều nghiên cứu về các chiến lược tìm kiếm trong tối ưu truy vấn đã được thực
hiện, trong đó chiến lược tìm kiếm đầy đủ, mà điển hình là thuật toán tìm kiếm dựa

trên quy hoạch động có thể giúp tìm ra một phương án thực thi truy vấn có chi phí
thấp nhất trong số tất cả các phương án trong không gian tim kiếm, tuy nhiên khi phải
tối ưu truy vấn có nhiều quan hệ, quy hoạch động tốn rất nhiều thời gian và tài nguyên
bộ nhớ cho việc tối ưu. Một chiến lược tìm kiếm khác được dùng trong tối ưu truy
vấn đó là chiến lược tìm kiếm heuristic, cụ thể là giải thuật tham lam có thể giúp tìm
ra phương án thực thi trong thời gian nhanh chóng, tuy nhiên chiến lược tìm kiếm
này hay đưa ra các quyết định thay đổi hướng đi và không xem xét lại các quyết định
cũ, do đó có thể bỏ sót các phương án tốt và thường không tìm ra được phương án tối
ưu.
Một thuật toán đã được Donald Kossmann và Konrad Stocker [12] đề xuất với
tên gọi Iterative Dynamic Programming được xem như một sự kết hợp của quy hoạch
động và heuristic tham lam bởi vì nó kết hợp các ưu điểm của cả hai: có thể tìm ra
phương án thực thi truy vấn tốt như quy hoạch động đối với các truy vấn đơn giản,
1


và khi cần tối ưu truy vấn phức tạp liên quan đến nhiều quan hệ một cách nhanh
chóng thì thuật toán có thể tìm ra phương án có chất lượng ở mức chấp nhận được
như khi sử dụng ý tưởng của thuật toán heuristic tham lam, hoặc cân bằng giữa hai
yếu tố: thời gian dành cho tối ưu và chất lượng phương án. Ý tưởng chính của IDP là
áp dụng nhiều lần quy hoạch động trong quá trình tối ưu một truy vấn. Ở mỗi bước
lặp lại quy hoạch động, thuật toán sẽ chọn một phương án con tốt nhất tại thời điểm
đó để tiếp tục ở bước lặp tiếp theo, xóa đi các phương án không cần thiết và tiếp tục
cho đến khi tìm ra kết quả cuối cùng.
Tuy nhiên, do sử dụng cách tiếp cận tham lam nên ở mỗi bước lặp quy hoạch
động, thuật toán IDP chỉ đánh giá chỉ đánh giá hướng đi một cách cục bộ bằng cách
chọn một phương án con tốt nhất tại mỗi bước lặp, mà không có sự ước lượng, đánh
giá về kết quả toàn cục. Đôi khi, điều này có thể khiến cho thuật toán IDP sai lầm khi
chọn những phương án cục bộ tốt nhưng lại dẫn đến kết quả sau cùng không tối ưu.
Trong luận văn này, một hệ tối ưu được xây dựng để có thể tối truy vấn kết

trong cơ sở dữ liệu phân tán bằng cách ứng dụng thuật toán IDP đã được Donald
Kossmann và Konrad Stocker đề xuất, với một sự cải tiến ở cách tiếp cận khác với
cách tiếp cận tham lam đã được sử dụng, giúp cho thuật toán có sự đánh giá kết quả
toàn cục ở mỗi bước lặp lại quy hoạch động. Hệ thống tối ưu này gồm các thành phần
chính: phân tích truy vấn, khởi tạo input, tối ưu truy vấn, viết lại phương án hoàn
chỉnh và thực thi phương án. Hệ thống nhận một truy vấn kết được viết dưới dạng TSQL, chuyển đổi truy vấn thành các dữ liệu đầu vào của thuật toán và tiến hành tối
ưu bằng cách ứng dụng thuật toán IDP với cách tiếp cận mới để tạo nên một phương
án thực thi truy vấn. Sau đó hệ thống sẽ thực thi phương án này để trả về kết quả cho
truy vấn cho người dùng. Ngoài ra, trong hệ tối ưu này, một tùy chọn việc thực thi
truy vấn không sử dụng kỹ thuật tối ưu nào cũng được tạo ra để có thể so sánh hiệu
quả tối ưu. Các kết quả trong phần thực nghiệm sẽ chứng minh rằng việc áp dụng
thuật toán IDP với cách tiếp cận mới để tối ưu truy vấn CSDL phân tán mang lại hiệu
quả tốt hơn so với khi sử dụng cách tiếp cận cũ, cũng như khi không sử dụng phương
pháp tối ưu truy vấn nào.

2


Nội dung báo cáo này gồm 5 chương như sau:
 Chương 1: Tổng quan về tối ưu truy vấn CSDL phân tán
 Chương 2: Các thành phần quan trọng trong tối ưu truy vấn CSDL phân tán
 Chương 3: Ứng dụng thuật toán IDP với sự cải tiến cách tiếp cận
 Chương 4: Hệ thống mô phỏng ứng dụng thuật toán IDP+ tối ưu truy vấn
CSDL phân tán và kết quả thực nghiệm
 Chương 5: Kết luận và hướng phát triển.

3


CHƯƠNG 1. TỔNG QUAN VỀ TỐI ƯU TRUY VẤN

CƠ SỞ DỮ LIỆU PHÂN TÁN
1.1. Giới thiệu về tối ưu truy vấn:
Mỗi truy vấn của người dùng thường tồn tại nhiều phương án thực thi truy vấn
khác nhau, mỗi phương án mô tả cách thức mà truy vấn có thể được thực thi để trả
về kết quả cho người dùng. Các phương án này trả về cùng một kết quả truy vấn, tuy
nhiên, chi phí của chúng thường khác nhau. Hệ tối ưu truy vấn là một thành phần rất
quan trọng của hệ quản trị CSDL, giúp mang lại một phương án thực thi truy vấn tối
ưu trong số rất nhiều phương án. Các kỹ thuật tối ưu truy vấn có thể được chia ra theo
hai kỹ thuật chính: tối ưu tĩnh và tối ưu động.
Tối ưu tĩnh sẽ được thực hiện trước thời điểm truy vấn được thực thi, việc thực
thi truy vấn sẽ dựa vào một phương án là kết quả của quá trình tối ưu truy vấn. Bởi
vì kích thước của các kết quả trung gian trong mỗi phương án thực thi truy vấn không
được biết trước cho đến khi nó được thực hiện, do đó, cần thiết phải ước lượng kích
thước các kết quả trung gian và chi phí của chúng thông qua một mô hình chi phí, sử
dụng các thông số thống kê của CSDL. Những sai sót trong quá trình ước lượng nêu
trên có thể dẫn đến việc lựa chọn một phương án không tối ưu, thậm chí là một
phương án sai lầm. Các chiến lược tìm kiếm thường được sử dụng trong tối ưu tĩnh
đó là tìm kiếm đầy đủ, tìm kiếm heuristic và tìm kiếm ngẫu nhiên.
Kỹ thuật tối ưu động sẽ kết hợp hai giai đoạn tối ưu và thực thi truy vấn lại với
nhau, tức việc tối ưu sẽ được thực hiện ngay lúc thực thi truy vấn. Tại tất cả các điểm
trong quá trình thực thi truy vấn, việc lựa chọn hoạt động tốt nhất tiếp theo có thể
được dựa vào những hiểu biết chính xác của kết quả từ hoạt động trước đó. Do đó,
các thông số thống kê về CSDL là không cần thiết để ước lượng kích thước của các
kết quả trung gian, và mô hình chi phí sẽ không được sử dụng. Tuy nhiên, các thông
số thống kê này vẫn có thể hữu dụng để chọn hoạt động đầu tiên. Lợi thế chính của
tối ưu truy vấn động so với tối ưu tĩnh đó là kích thước của các quan hệ trung gian là
sẵn có, thay vì phải ước lượng bằng mô hình chi phí như ở kỹ thuật tối ưu tĩnh, từ đó
giảm đi khả năng dẫn đến một lựa chọn sai lầm.
4



Chương 1: Tổng quan về tối ưu truy vấn cơ sở dữ liệu phân tán

Ngoài ra, có một dạng tối ưu lai giữa tối ưu tĩnh và tối ưu động bằng cách kết
hợp hai kỹ thuật tĩnh và động lại với nhau nhằm tận dụng những lợi thế của tối ưu
tĩnh, đồng thời hạn chế những sai sót trong quá trình ước lượng kích thước và chi phí
của các quan hệ trung gian. Kỹ thuật tối ưu hybrid này cơ bản dựa trên tối ưu tĩnh,
tuy nhiên, khi có sự khác biêt lớn giữa kích thước thực tế của các quan hệ trung gian
so với kích thước được ước lượng, tối ưu động sẽ được thực hiện tại thời điểm này.

1.2. Các nghiên cứu về tối ưu truy vấn cơ sở dữ liệu phân tán:
Một thuật toán tối ưu truy vấn CSDL phân tán sử dụng phương pháp tối ưu
động đó là thuật toán INGRESS phân tán, là phiên bản mở rộng của thuật toán tối ưu
INGRES [28, 20] cho CSDL tập trung. Thuật toán INGRES phân nhỏ truy vấn thành
các thành phần nhỏ hơn và cố gắng làm giảm kích thước của các kết quả trung gian.
Đầu tiên, một truy vấn q gồm n quan hệ sẽ được phân rã thành n truy vấn con q1 →
q2 → … → qn, trong đó, mỗi qi là một truy vấn đơn quan hệ, và kết quả của truy vấn
qi sẽ được sử dụng bởi truy vấn qi+1. Sau đó, mỗi truy vấn sẽ được tối ưu một cách
độc lập để cố gắng làm giảm kích thước của kết quả trung gian. Hai kỹ thuật được sử
dụng cho việc phân rã truy vấn là tách và thay thế bộ. Giả sử ta có truy vấn q như
sau:
q:

SELECT

R2.A2, R3.A3, ..., Rn.An

FROM

R1, R2, ..., Rn


WHERE

P1(R1.A’1)

AND

P2(R1.A1, R2.A2, ..., Rn.An)

với Ai, A’i là danh sách các thuộc tính của quan hệ Ri, P1 là vị từ liên quan đến các
thuộc tính của quan hệ R1, P2 là vị từ liên quan đến các các thuộc tính của các quan
hệ R1, R2, …, Rn. Truy vấn q có thể được tách thành 2 truy vấn con q’ và q’’ dựa vào
quan hệ chung R’1 là kết quả của truy vấn q’.
q’:

SELECT
FROM
WHERE

R1.A1 INTO R’1
R1
P1(R1.A’1)

q'’:

SELECT
FROM
WHERE

R2.A2, R3.A3, ..., Rn.An

R’1, R2, ..., Rn
P2(R1.A1, R2.A2, ..., Rn.An)

5


Chương 1: Tổng quan về tối ưu truy vấn cơ sở dữ liệu phân tán

Việc phân nhỏ truy vấn q như trên sẽ làm giảm kích thước của kết quả trung
gian R’1, từ đó có thể giảm chi phí truyền thông trong mạng.
Đối với các truy vấn đa quan hệ mà không thể tối giản được nữa, kỹ thuật thay
thế bộ có thể được sử dụng để chuyển đổi về dạng truy vấn đơn quan hệ. Việc này
được thực hiện bằng cách chọn một quan hệ R1 trong q để thay thế bộ, với mỗi bộ
trong R1, thay thế các thuộc tính trong R bởi các giá trị thực tế của nó. Cách này sẽ
tạo ra một tập hợp các truy vấn con q’ có n - 1 quan hệ, tức là q(R1, R2, …, Rn) được
thay thế bởi {𝑞 ′ (𝑡1𝑖 , 𝑅2 , … , 𝑅𝑛 ), 𝑡1𝑖 ∈ 𝑅1 }.
Thuật toán INGRES phân tán hoạt động rất giống với thuật toán INGRES cho
môi trường tập trung, với sự bổ sung quá trình phân rã mỗi truy vấn qi thành các truy
vấn con mà thực thi trên các phân mảnh, tuy nhiên, chỉ có phân mảnh ngang được xử
lý. Thuật toán INGRES phân tán tối ưu với mối quan hệ kết hợp giữa chi phí truyền
thông và thời gian phản hồi.
Thuật toán INGRES phân tán được đặc trưng bởi một sự tìm kiếm hạn chế trong
không gian tìm kiếm, một quyết định tối ưu được thực hiện cho mỗi bước mà không
xem xét hệ quả của quyết định này đối với kết quả tối ưu toàn cục. Hướng tiếp cận
tìm kiếm đầy đủ mà trong đó tất cả các phương án trong không gian tìm kiếm đều
được đánh giá để xác định phương án tốt nhất là một sự thay thế cho hướng tiếp cận
tìm kiếm hạn chế [26].
Một ý tưởng khác được đưa ra là tìm cách làm giảm tối đa kích thước dữ liệu
được truyền tải giữa các trạm, và semi-join [14] có thể giúp thực hiện ý tưởng này.
Semi-join làm việc như một toán tử rút gọn kích thước của một quan hệ trước khi

truyền. Khi kết hai quan hệ R và S trên thuộc tính A, lưu tại trạm 1 và trạm 2 tương
ứng, có thể thực hiện phép kết bằng cách truyền một trong hai quan hệ (hoặc cả hai
quan hệ) đến trạm mà truy vấn được thực thi và trả về kết qua truy vấn. Một cách
khác để thực hiện phép kết này là làm giảm kích thước của một hoặc cả hai quan hệ
sử dụng semi-join trước khi truyền chúng đi, sử dụng quy tắc:

6


Chương 1: Tổng quan về tối ưu truy vấn cơ sở dữ liệu phân tán

𝑅 ⋈𝐴 𝑆  (R
với R

A S:

A S)

⋈𝐴 S  R⋈𝐴 (S

A R)

 (R

A S)

⋈𝐴 (S

A R)


(1.1)

S semi-join R trên thuộc tính A. Ví dụ sau sẽ minh họa cho cách thức hoạt

động của semi-join:

Hình 1.1: Ví dụ hoạt động của semi-join

Trong ví dụ trên, hai quan hệ R và S sẽ thực hiện phép kết trên thuộc tính A tại
trạm 2, thay vì phải truyền quan hệ R từ trạm 1 về trạm 2, semi-join sẽ giúp làm giảm
kích thước quan hệ R trước khi truyền về trạm 2, các bước thực hiện như sau:
 Thực hiện phép chiếu đối với quan hệ S trên thuộc tính A tạo thành S’, truyền
S’ sang trạm 1.
 Thực hiện phép kết giữa R với S’, tạo thành R’, truyền R’ sang trạm 2. Khi
đó, R’ là kết quả của việc loại bỏ các bộ trong R mà không liên quan đến
truy vấn giữa R và S, giúp giảm chi phí truyền thông.
 Cuối cùng, thực hiện phép kết giữa S và R’ và trả về kết quả truy vấn.
Thuật toán tối ưu được sử dụng trong SDD-1 [21], hay còn được gọi là thuật
toán SDD-1, dựa trên giải thuật tối ưu leo đồi, thực hiện các phép kết dựa trên semijoin. Thuật toán SDD-1 đánh giá chi phí và lợi ích của tất cả các semi-join, trong đó,
chi phí được nhắc đến là chi phí truyền tải các giá trị thuộc tính semi-join, lợi ích là
chi phí nếu truyền tải các bộ không liên quan đến phép kết, lần lượt được biểu diễn
bằng hai đại lượng C và B như sau:
Chi phí: C(R

A S)

= TMSG + TTR * size(∏𝐴(𝑆))

7


(1.2)


Chương 1: Tổng quan về tối ưu truy vấn cơ sở dữ liệu phân tán

Lợi ích: B(R

A S)

=(1 – SFSJ(S.A)) * size(R) * TTR

(1.3)

với TMSG là thời gian truyền các thông điệp phục vụ semi-join, TTR là thời gian truyền
một đơn vị dữ liệu của quan hệ, SFSJ(S.A) là tỉ lệ các giá trị riêng biệt của thuộc tính
A chứa trong S trên miền giá trị của thuộc tính A.
Thuật toán chọn một semi-join có hiệu số (B – C) lớn nhất, thực hiện nó và cập
nhật thông tin về số lượng các giá trị riêng biệt của quan hệ mà đã được rút gọn kích
thước bởi semi-join. Quá trình này được lặp lại cho đến khi không còn semi-join nào
có (B – C) lớn hơn 0. Cuối cùng, thuật toán chọn trạm nào chứa lượng dữ liệu nhiều
nhất (trạm mà sẽ cho ra chi phí truyền thông nhỏ nhất nếu truyền tải tất cả các quan
hệ còn lại về đây) và truyền tải tất cả các quan hệ còn lại về trạm này và thực hiện
các phép kết để tạo ra kết quả cuối cùng của truy vấn. Mặc dù thuật toán SDD-1 có
thể cắt giảm chi phí truyền thông một cách hiệu quả, nó vẫn có một số hạn chế, ví dụ
như độ phức tạp thuật toán. Khi số lượng các bản ghi là rất lớn, thì chi phí cho việc
tìm kiếm và thực thi truy vấn sẽ tăng lên một cách nhanh chóng. Hơn nữa, việc thực
hiện tuần tự các semi-join sẽ làm tăng thời gian phản hồi của truy vấn [8].
Với kỹ thuật tối ưu tĩnh, có sự tách biệt rõ ràng giữa quá trình tối ưu tạo ra một
phương án thực thi truy vấn và quá trình thực thi truy vấn dựa vào phương án này. Vì
thế, một mô hình chi phí chính xác sẽ giúp dự đoán chi phí của các phương án trong

không gian tìm kiếm. Nhiều nghiên cứu khác nhau liên quan đến tối ưu tĩnh cũng đã
được thực hiện, tập trung vào việc tối ưu chi phí truyền thông giữa các trạm trong hệ
thống phân tán. Một thuật toán tối ưu tĩnh được sử dụng trong hầu hết các CSDL
thương mại là thuật toán tối ưu dựa trên quy hoạch động được sử dụng đầu tiên trong
dự án IBM’s System R [10, 22], hay còn được gọi là thuật toán System R, là một
thuật toán tìm kiếm đầy đủ. Thuật toán này tạo ra tất cả các phương án thực thi truy
vấn, mỗi phương án sẽ có một chi phí thực thi được ước lượng dựa vào mô hình chi
phí, và phương án có chi phí nhỏ nhất sẽ được tìm thấy. Các phương án thực thi nói
trên được tạo ra bằng cách hoán vị thứ tự các phép kết của các quan hệ có trong truy
vấn. Thách thức mà thuật toán tối ưu này phải đối mặt cũng chính là việc lựa chọn
thứ tự thực hiện phép kết khi xây dựng phương án thực thi truy vấn, được chứng minh
là một NP-Khó [29], tức là không thể tìm ra phương án tối ưu cho truy vấn có kích

8


Chương 1: Tổng quan về tối ưu truy vấn cơ sở dữ liệu phân tán

thước bất kỳ trong một khoảng thời gian đa thức. Trong môi trường phân tán, thuật
toán System R* được sử dụng để tối ưu, là sự mở rộng của thuật toán System R. Ưu
điểm của thuật toán quy hoạch động là tìm ra phương án tốt nhất có thể có, tuy nhiên,
nhược điểm của là nó có độ phức tạp 𝓞(3𝑛 ) [11], với n là số lượng quan hệ trong truy
vấn. Do đó, với các truy vấn có số lượng quan hệ đủ lớn, thuật toán quy hoạch động
mất rất nhiều thời gian để tìm ra phương án tối ưu. Hơn nữa, trong hệ thống CSDL
phân tán, độ phức tạp của thuật toán quy hoạch động còn tăng lên đáng kể khi có sự
tồn tại của các bản sao của các quan hệ được đặt tại các trạm khác nhau trong hệ
thống phân tán.
Một số thuật toán tối ưu dựa vào Heuristic tham lam được nêu trong các nghiên
cứu [13, 19, 23] có độ phức tạp đa thức, có thể nhanh chóng tìm ra phương án thực
thi cho truy vấn có nhiều quan hệ, tuy nhiên chúng thường tạo ra các phương án có

chi phí cao hơn so với phương án được tìm ra bởi thuật toán tìm kiếm đầy đủ, ví dụ
như thuật toán dựa trên quy hoạch động, thậm chí, đôi khi Heuristic tham lam có thể
dẫn đến phương án sai lầm.
Trong nghiên cứu [9], các tác giả đã cải tiến thuật toán đàn kiến để áp dụng vào
bài toán tối ưu truy vấn nhằm tìm ra giải pháp tối ưu. Trong các thực nghiệm được
nêu trong nghiên cứu, giải thuật tối ưu đàn kiến cải tiến được so sánh với giải thuật
dựa trên Heuristic tham lam và giải thuật tối ưu đàn kiến nguyên bản, các kết quả
thực nghiệm cho thấy giải thuật tối ưu đàn kiến cải tiến có thời gian xử lý truy vấn
nhanh hơn, đồng thời giúp rút ngắn thời gian phản hồi kết quả truy vấn đến người
dùng so với hai giải thuật trong so sánh.
Trong nghiên cứu [24], các tác giả đã cải tiến giải thuật di truyền để khắc phục
thiếu sót về sự hội tụ sớm, tạo ra một giải thuật mới bằng cách kết hợp tìm kiếm cục
bộ của giải thuật di truyền với tìm kiếm tổng quát của giải thuật SA (simulated
annealing). Các kết quả thực nghiệm được trình bày trong nghiên cứu cho thấy giải
thuật mới cần nhiều thời gian hơn để tạo ra phương án thực thi truy vấn, tuy nhiên nó
thường trả về phương án có chất lượng tốt hơn, do đó thời gian phản hồi truy vấn
được rút ngắn so với giải thuật di truyền.

9


Chương 1: Tổng quan về tối ưu truy vấn cơ sở dữ liệu phân tán

Một số nghiên cứu đã được thực hiện để tạo ra giải pháp tối ưu cho việc lựa
chọn thứ tự thực hiện các phép kết của truy vấn. Các thuật toán ngẫu nhiên được xem
xét trong [15] có thể làm giảm chi phí của việc tối ưu truy vấn, nhưng chúng gặp vấn
đề khi có sự cố định về một lượng bộ nhớ rất nhớ cần cho quá trình tìm kiếm và chạy
chậm hơn so với heuristic. Thuật toán Two-Phase Optimization được nêu trong
nghiên cứu [16] thực hiện việc tìm kiếm ngẫu nhiên các phương án khác nhau trong
không gian tìm kiếm, nó tạo ra một phương án tối ưu nhưng lại làm gia tăng lượng

bộ nhớ cần cho việc tối ưu truy vấn.
Trong nghiên cứu [12], các tác giả giới thiệu một thuật toán tìm kiếm mới mà
họ gọi là Iterative Dynamic Programming. Thuật toán IDP này có thể được xem như
một sự kết hợp của quy hoạch động và heuristic tham lam bởi vì nó kết hợp các ưu
điểm của cả hai: có thể tìm ra phương án thực thi truy vấn rất tốt như quy hoạch động,
và khi cần tìm kiếm nhanh hơn có thể tìm ra phương án ở mức chấp nhận được như
khi sử dụng heuristic tham lam. Ý tưởng chính của IDP là áp dụng nhiều lần quy
hoạch động trong quá trình tối ưu một truy vấn. Ở mỗi bước lặp quy hoạch động,
thuật toán sẽ chọn một phương án con tốt nhất để tiếp tục ở bước lặp tiếp theo và xóa
đi các phương án con không cần thiết. Điều này sẽ giúp giảm đáng kể lượng bộ nhớ
cần để lưu tất cả các phương án. IDP có độ phức tạp thuật toán không quá cao và có
thể tối ưu truy vấn trong những trường hợp mà quy hoạch động là không khả thi vì
độ phức tạp cao của nó. Nếu truy vấn đơn giản, IDP có thể tạo ra một phương án tối
ưu như quy hoạch động và trong cùng thời gian như quy hoạch động. Nếu truy vấn
quá phức tạp mà quy hoạch động không xử lý được, IDP có thể tạo ra các phương án
con tối ưu mà tất cả các phương án con tối ưu này sẽ tạo thành một phương án thực
thi truy vấn có chất lượng ở mức chấp nhận được tương ứng với mức độ yêu cầu rút
ngắn thời gian cần cho việc thực hiện tối ưu. Hay nói cách khác, đối với các truy vấn
có liên quan đến số lượng lớn các quan hệ, IDP vẫn có thể thực hiện tối ưu để đạt
được sự cân bằng giữa chất lượng phương án và thời gian dành cho việc thực hiện tối
ưu. Một ưu điểm khác của IDP là nó có thể được tích hợp một cách dễ dàng vào một
hệ tối ưu đang có sẵn mà đang dựa trên quy hoạch động thông qua việc thay đổi một
số ít mã nguồn của hệ thống tối ưu cũ. Một số thành phần phức tạp của hệ thống cũ
như mô hình chi phí, các qui luật liệt kê phương án… vẫn có thể được sử dụng trong
10


Chương 1: Tổng quan về tối ưu truy vấn cơ sở dữ liệu phân tán

hệ thống tối ưu sử dụng IDP mà không cần thay đổi. Tuy nhiên, do sử dụng cách tiếp

cận tham lam, ở mỗi bước lặp lại quy hoạch động, thuật toán IDP chọn một phương
án con tốt nhất tại thời điểm đó mà không có sự đánh giá nào về kết quả toàn cục. Do
đó, thuật toán IDP vẫn có thể mắc sai lầm khi chọn các phương án con mà dẫn đến
kết quả cuối cùng không tốt.
Tại Việt Nam, đã có một số nghiên cứu, luận văn về tối ưu hóa truy vấn trong
cơ sở dữ liệu phân tán. Trong các báo cáo đề tài luận văn [1-7], các báo cáo này giới
thiệu về các thuật toán tối ưu và một số trong đó có ứng dụng nguyên bản các thuật
toán INGRES phân tán, SDD – 1 hoặc System R* được trình bày phần trên để tối ưu
truy vấn mà không có sự cải tiến nào. Các kết quả trong các báo cáo trên đã chứng
minh được hiệu quả của các thuật toán tối ưu, tuy nhiên các truy vấn được sử dụng
để mô phỏng thuật toán thường đơn giản, số lượng quan hệ trong truy vấn không
nhiều. Do đó, nghiên cứu ứng dụng thuật toán IDP vào tối ưu truy vấn CSDL phân
tán còn khá mới mẻ, khác biệt so với các báo cáo luận văn nêu trên.
Với những phân tích trên, mục tiêu của đề tài luận văn là xây dựng một hệ tối
ưu truy vấn kết cơ sở dữ liệu phân tán bằng cách ứng dụng có cải tiến thuật toán
IDP đã được Donald Kossmann và Konrad Stocker đề xuất trong công trình
nghiên cứu [12], với một cách tiếp cận mới cho phép thuật toán đánh giá về kết
quả toàn cục ở mỗi bước lặp, giúp mang lại kết quả tốt hơn. Hệ tối ưu dựa trên
thuật toán IDP có khả năng tạo ra các phương án có chất lượng tốt nhất đối với các
truy vấn đơn giản, đồng thời có thể thực hiện tối ưu các truy vấn có số lượng lớn các
quan hệ (từ 10 đến 20 quan hệ) với chất lượng phương án thực thi truy vấn ở mức tốt
hoặc chấp nhận được tương ứng với thời gian tối ưu được rút ngắn mà các thuật toán
tìm kiếm đầy đủ hoặc heuristic khác có thể gặp khó khăn về thời gian tối ưu hoặc chất
lượng phương án, đồng thời không sử dụng quá nhiều tài nguyên bộ nhớ trong quá
trình tối ưu bởi khả năng loại bỏ các phương án không còn cần thiết trong quá trình
tìm kiếm. Phương án thực thi truy vấn được trả về bởi hệ tối ưu sẽ được thực thi để
có thể rút ngắn thời gian trả về kết quả truy vấn cho người dùng. Hệ tối ưu dựa trên
thuật toán IDP này cũng sẽ được nghiên cứu cài đặt để có thể tối ưu các truy vấn liên
quan đến các quan hệ được nhân bản tại nhiều trạm khác nhau trong hệ thống phân


11


Chương 1: Tổng quan về tối ưu truy vấn cơ sở dữ liệu phân tán

tán. Trong giới hạn thời gian để thực hiện đề tài luận văn, trường hợp dữ liệu của các
quan hệ được phân mảnh không được xử lý trong hệ tối ưu này do không đủ thời gian
để xây dựng một hệ thống tiền xử lý dữ liệu phân mảnh.
Trong chương 2 và chương 3, kiến trúc, mô hình chi phí, các giải thuật được
ứng dụng trong hệ thống tối ưu truy vấn cơ sở dữ liệu phân tán và một cách tiếp cận
mới sẽ được trình bày. Chương 4 sẽ trình bày về hệ thống mô phỏng việc ứng dụng
thuật toán IDP để tối ưu truy vấn CSDL phân tán.

12


CHƯƠNG 2: CÁC THÀNH PHẦN QUAN TRỌNG TRONG TỐI ƯU
TRUY VẤN CƠ SỞ DỮ LIỆU PHÂN TÁN
2.1. Giới thiệu:
Một cơ sở dữ liệu phân tán là một tập hợp của nhiều CSDL có liên quan về mặt
logic được phân bố trên một mạng máy tính. Một hệ quản trị CSDL phân tán là một
hệ thống phần mềm mà cho phép quản trị CSDL phân tán và làm cho sự phân tán trở
nên trong suốt đối với người dùng. Thuật ngữ hệ thống CSDL phân tán thường được
dùng để chỉ sự kết hợp giữa CSDL phân tán và hệ quản trị CSDL phân tán. Một cách
hiểu đơn giản, một CSDL phân tán bao gồm một số lượng các quan hệ được đặt ở các
trạm có vị trí vật lý khác nhau. Việc phân tán dữ liệu ở nhiều trạm khác nhau đem lại
lợi ích rõ rệt cho các tổ chức có quy mô lớn sở hữu nhiều văn phòng và lực lượng lao
động được phân bố ở nhiều ví trí khác nhau. Một lợi ích khác của việc phân tán dữ
liệu đó là giúp gia tăng tính sẵn sàn của dữ liệu. Chẳng hạn, trong môi trường dữ liệu
tập trung, khi máy chủ bị lỗi thì toàn bộ hệ thống sẽ không thể truy cập được dữ liệu.

Việc nhân bản dữ liệu ở một số trạm khác nhau trong hệ thống phân tán có thể giúp
tránh được trường hợp này bằng cách cung cấp khả năng truy cập đến các bản sao
của dữ liệu được lưu đồng thời ở các trạm khác khi một trạm trong hệ thống phân tán
bị lỗi. Ở một khía cạnh khác, việc nhân bản dữ liệu cũng có thể giúp giảm tải truy cập
đến trạm chứa dữ liệu bằng cách tạo ra các bản sao của dữ liệu ở những nơi có nhu
cầu sử dụng cao, giúp tăng tốc hiệu suất hệ thống tại những nơi đó. Một số đặc trưng
quan trọng trong cấu trúc và chức năng của CSDL phân tán như sau:
 Một CSDL phân tán được tổ chức theo một lược đồ xác định cấu trúc của của
dữ liệu được phân tán và các mối quan hệ giữa dữ liệu. Lược đồ được định nghĩa theo
một số mô hình dữ liệu, thường là mô hình dữ liệu quan hệ hoặc hướng đối tượng.
 Một hệ quản trị CSDL phân tán có đầy đủ chức năng của một hệ quản trị
CSDL. Nó cung cấp khả năng truy vấn mức độ cao, quản lý giao dịch (điều khiển
cạnh tranh và phục hồi), và thực thi toàn vẹn.
 Một hệ quản trị CSDL phân tán cung cấp sự truy cập một cách trong suốt đến
dữ liệu cho người dùng. Các quan hệ có thể được nhân bản hoặc được phân mảnh ở
các trạm khác nhau trong hệ thống phân tán, bên cạnh việc chúng được phân bố trên
13


Chương 2: Các thành phần quan trọng trong tối ưu truy vấn CSDL phân tán

nhiều trạm. Tất cả các điều này đều không được nhìn thấy bởi người dùng, đây là một
sự mở rộng của khái niệm về sự độc lập dữ liệu, vốn là một khái niệm quan trọng
trong CSDL tập trung. Điều này dẫn đến yêu cầu tối ưu truy vấn để xác định cần lấy
dữ liệu từ những trạm nào, thực thi truy vấn ở đâu, theo thứ tự nào,… Một mô hình
chi phí xem xét các giá trị chi phí nhập xuất, chi phí xử lý vi xử lý, chi phí truyền
thông,… có thể giúp lựa chọn một phương án thực thi truy vấn tối ưu nhằm rút ngắn
thời gian trả về kể quả truy vấn cho người dùng.

2.2. Kiến trúc hệ thống cơ sở dữ liệu phân tán:

Môi trường hệ thống CSDL phân tán bao gồm một tập (có thể rỗng) các trạm
phát sinh truy vấn và một tập không rỗng các trạm chứa dữ liệu. Trong đó, trạm phát
ra truy vấn thì không chứa dữ liệu. Bên cạnh đó, cần có một hệ thống mạng cung cấp
khả năng truy cập đến dữ liệu cũng như truyền thông giữa các trạm.

Hình 2.1: Môi trường hệ thống CSDL phân tán [20]

Có một số mô hình kiến trúc có thể được sử dụng cho việc xây dựng một hệ
quản trị CSDL phân tán, bao gồm mô hình khách-chủ [25], nơi mà trạm phát ra truy
vấn đóng vai trò là máy khách trong khi trạm chứa dữ liệu đóng vai trò máy chủ; và
mô hình ngang hàng nơi mà không có sự phân biệt giữa máy khách và máy chủ.
Hệ thống CSDL phân tán truyền thống thường sử dụng mô hình kiến trúc kháchchủ, trong đó máy khách và máy chủ có một sự tách biệt rõ ràng về nhiệm vụ. Các
máy chủ cung cấp khả năng truy cập đến dữ liệu cục bộ được lưu tại trạm đó cho các

14


Chương 2: Các thành phần quan trọng trong tối ưu truy vấn CSDL phân tán

máy khách. Các máy khách cung cấp các ứng dụng và giao diện để người dùng có
thể tương tác và dữ liệu được lưu trữ trong hệ thống. Trong kiến trúc này máy chủ
thực hiện hầu hết các công việc quản lý dữ liệu. Điều này có nghĩa rằng tất cả các quy
trình tối ưu và thực thi truy vấn, quản lý giao dịch và quản lý lưu trữ đều được thực
hiện ở máy chủ. Trong khi đó, ngoài ứng dụng và giao diện người dùng, máy khách
cần có các mô-đun nhận nhiệm vụ quản lý, sắp xếp các dữ liệu được trả về theo yêu
cầu của người dùng.

Hình 2.2: Mô hình kiến trúc client-server [25]

Đối với mô hình ngang hàng, không có sự phân biệt giữa máy khách và máy

chủ, mỗi trạm trong hệ thống có thể thực hiện cùng một chức năng. Trong trường hợp
này, dữ liệu được lưu trữ tại tất cả các trạm và có thể xảy ra trường hợp một trạm
nhận được truy vấn liên quan đến dữ liệu mà không được lưu cục bộ tại trạm đó.
Trong trường hợp này, trạm nhận được truy vấn có thể yêu cầu được truy cập đến dữ
liệu được lưu ở các trạm khác và sẽ hợp tác với các trạm thích hợp cho đến khi truy
vấn được hoàn thành.

15


Chương 2: Các thành phần quan trọng trong tối ưu truy vấn CSDL phân tán

2.3. Xử lý truy vấn trong cơ sở dữ liệu phân tán:
Để xử lý truy vấn CSDL phân tán, ngoài chi phí nhập/xuất dựa vào số lượng
truy cập đĩa cứng (đọc/ghi), hệ thống CSDL phân tán thêm vào hệ thống CSDL tập
trung một số chi phí xử lý truy vấn do có sự bổ sung thiết kế về phần cứng lẫn phần
mềm. Chi phí này là chi phí truyền dữ liệu trên mạng, có thể là dữ liệu của các quan
hệ được lưu tại các trạm, các kết quả trung gian, hoặc kết quả cuối cùng được truyền
về trạm ban đầu mà nhận được yêu cầu truy vấn. Do đó, các nhà thiết kế CSDL quan
tâm đến việc tối ưu truy vấn, với mục tiêu là tối thiểu hóa chi phí truyền dữ liệu trên
mạng. Đối với các truy vấn kết, việc xử lý truy vấn trong môi trường phân tán cần
xem xét các vấn đề quan trọng sau:
 Chi phí truyền thông.
 Nếu quan hệ được nhân bản ở nhiều trạm, cần xác định sẽ lấy dữ liệu của
quan hệ được lưu ở trạm nào.
 Kích thước lượng dữ liệu được truyền tải giữa các trạm.
 Tốc độ nhập/xuất tương đối tại mỗi trạm.
 Tốc độ truyền tải tương đối một đơn vị dữ liệu giữa các trạm.
Trong hệ thống CSDL tập trung, mỗi truy vấn thường có nhiều cách để thực thi,
điều này cũng tương tự trong hệ thống phân tán. Sẽ có nhiều phương án thực thi cho

cùng một truy vấn do dữ liệu có thể được lưu ở nhiều trạm khác nhau, tài nguyên hệ
thống và thời gian phản hồi của các phương án này cũng sẽ khác nhau. Tối ưu truy
vấn CSDL phân tán giúp tìm ra một phương án thực thi có chi phí nhỏ nhất, trong đó,
chi phí phải bao gồm chi phí truyền thông, bên cạnh chi phí nhập/xuất, chi phí vi xử
lý, nhằm giúp giảm thời gian thực thi, trả lại kết quả truy vấn cho người dùng trong
thời gian nhanh nhất có thể. Ở đây, hai đại lượng thời gian cần được xem xét đó là:
tổng thời gian và thời gian phản hồi. Tổng thời gian là tổng các khoảng thời gian tốn
hao bởi mỗi vi xử lý, cho dù chúng có thể xảy ra đồng thời. Thời gian phản hồi là
khoảng thời gian từ khi bắt đầu cho đến khi truy vấn được hoàn thành. Một trong hai
đại lượng thời gian này có thể được chọn là tiêu chí để đánh giá các phương án thực
thi truy vấn.

16