1

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ
TRUYỀN THÔNG

VŨ ĐỨC MẠNH

MỘT SỐ THUẬT TOÁN TỐI ƢU HÓA 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
Thái Nguyên - 2016

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn


2

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ
TRUYỀN THÔNG

VŨ ĐỨC MẠNH

MỘT SỐ THUẬT TOÁN TỐI ƢU HÓA TRUY
VẤN TRONG
CƠ SỞ DỮ LIỆU PHÂN TÁN

- Tổ chức dữ liệu phân tán kinh tế hơn so với tổ chức dữ liệu tập
trung.
- Dễ dàng mở rộng.
1.1.4. Nhược điểm của cơ sở dữ liệu phân tán
- Độ phức tạp thiết kế và cài đặt hệ thống tăng.
- Tăng chi phí.
- Bảo mật khó khăn.
- Kiểm soát tính toàn vẹn khó khăn hơn.
1.2. Đặc điểm của cơ sở dữ liệu phân tán
1.2.1. Chia sẻ tài nguyên
Việc chia sẻ tài nguyên của hệ phân tán được thực hiện thông
qua mạng truyền thông.

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn


5
1.2.2. Tính mở
Tính mở của hệ phân tán được xem xét theo mức độ 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.
1.2.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. Trong cùng một thời
điểm nếu có N tiến trình cùng tồn tại, ta nói chúng thực hiện đồng thời.
Việc thực hiện tiến trình có thể theo cơ chế song (nhiều CPU).
1.2.4. Khả năng mở rộng
Khả năng mở rộng được đặc trưng bởi tính không thay đổi phần
mềm hệ thống và phần mềm ứng dụng khi hệ thống được mở rộng.

Mô hình kiến trúc CSDL phân tán gồm: Lược đồ tổng thể, lược
đồ phân mảnh, lược đồ định vị và lược đồ ánh xạ cục bộ
1.5. Các kĩ thuật xây dựng cơ sở dữ liệu phân tán
Có 3 chiến lược phân tán dữ liệu cơ bản: Sao lặp dữ liệu, phân
mảnh dữ liệu và phương pháp hỗn hợp.
 Sao lặp dữ liệu: CSDL được nhân thành nhiều bản từng phần
hoặc đầy đủ và được đặt ở nhiều trạm trên mạng.
 Phân mảnh dữ liệu: CSDL được chia thành các mảnh nhỏ
liên kết với nhau (không trùng lặp). Mỗi phần dữ liệu được đưa đến
các trạm thích hợp để sử dụng.
 Phương pháp hỗn hợp: CSDL được chia thành nhiều phần:
quan trọng và không quan trọng. Phần ít quan trọng được lưu trữ một
nơi, phần quan trọng được lưu trữ ở nhiều nơi khác nhau.
1.5.1. Phân mảnh dữ liệu
Sự phân mảnh là chia dữ liệu trong các bảng dữ liệu thành các bộ
hoặc các bảng dữ liệu con. Có ba kiểu phân mảnh một quan hệ tổng
thể: Phân mảnh ngang, phân mảnh dọc, phân mảnh hỗn hợp [1].
Một sự phân mảnh là đúng đắn nếu tuân thủ 3 quy tắc sau: Tính
đầy đủ; tính phục hồi; tính tách biệt.
1.5.1.1. Phương pháp phân mảnh ngang
Phân mảnh ngang là chia quan hệ thành nhiều các nhóm bộ. Kết
quả của quá trình phân mảnh ngang là các quan hệ con, số lượng quan
hệ con phụ thuộc vào điều kiện ràng buộc của các thuộc tính. Các bộ

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn


7
trong các quan hệ con là tách biệt nhau. Phân mảnh ngang thực chất là



8
1.5.1.3. Phương pháp phân mảnh hỗn hợp.
Phân mảnh hỗn hợp là sự kết hợp giữa phương pháp phân mảnh
ngang và phân mảnh dọc.
1.5.2. Nhân bản dữ liệu
a. Nhân bản dữ liệu đầy đủ: Toàn bộ CSDL sẽ được tạo trên
tất cả mỗi trạm.
b. Không có nhân bản dữ liệu: Mỗi phân mảnh chỉ được lưu
trữ trên một trạm, phương án này còn được gọi là định vị không
dư thừa dữ liệu.
c. Nhân bản dữ liệu từng phần: Một vài phân mảnh có thể được
tạo bản sao và có thể một số phân mảnh sẽ không có bản sao.
1.5.3. Định vị dữ liệu
Là quá trình gán từng phân mảnh, từng bản sao của phân mảnh
cho một trạm cụ thể trong hệ thống phân tán.
1.6. Kết luận chƣơng 1
CSDL phân tán rất quan trọng vì nhiều lý do khác nhau, nó có
thể được cài đặt trên các mạng máy tính diện rộng và các mạng cục
bộ nhỏ. Có hai lý do về tổ chức và kỹ thuật đối với sự phát triển
CSDL phân tán đó là: CSDL phân tán được xây dựng để khắc phục
các thiếu sót của cơ sở dữ liệu tập trung và nó phù hợp hơn trong cấu
trúc phân quyền của nhiều tổ chức. Kỹ thuật CSDL phân tán được mở
rộng và phát triển từ kỹ thuật của CSDL truyền thống. Trong môi
trường mới này, một số vấn đề kỹ thuật đòi hỏi các giải pháp khác và
một số giải pháp hoàn toàn mới. Tính trong suốt phân tán cung cấp sự
độc lập của các chương trình khỏi sự phân tán của CSDL. Các mức
trong suốt phân tán khác nhau có thể được cung cấp bởi một hệ quản
trị CSDL phân tán; Tại mỗi mức, tính trong suốt làm cho người lập

vào trong quá trình xử lý truy vấn. Chi phí truyền thông là một trong
các nhân tố quan trọng, được quan tâm trong CSDL phân tán.
2.1.2. Các quy tắc biến đổi cây đại số quan hệ
2.1.2.1. Tính chất giao hoán của các phép toán hai ngôi
2.1.2.2. Tính kết hợp của các phép toán hai ngôi

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn


10
2.1.2.3. Tính lũy đẳng của các phép toán đơn ngôi
2.1.2.4. Giao hoán phép chọn với phép chiếu
2.1.2.5. Giao hoán phép chọn với các phép toán hai ngôi
2.1.2.6. Giao hoán phép chiếu với phép toán hai ngôi
2.2. Quá trình xử lý truy vấn
Quá trình xử lý truy vấn bao gồm 4 tầng: phân rã truy vấn, cục
bộ hóa dữ liệu, tối ưu hóa toàn cục và tối ưu hóa cục bộ [2].
2.2.1. Phân rã truy vấn
Phân rã truy vấn là giai đoạn đầu tiên của quá trình xử lý câu
truy vấn, thực hiện việc biến đổi câu truy vấn ở dạng ngôn ngữ bậc
cao thành câu truy vấn ngôn ngữ bậc thấp thực thi cho kết quả tương
đương. Phân rã truy vấn có thể xem như bốn bước liên tiếp nhau:
Chuẩn hoá, phân tích, loại bỏ dư thừa, viết lại câu truy vấn.
2.2.1.1. Chuẩn hóa: Các câu truy vấn bằng các phép tính quan hệ
được viết lại dưới dạng chuẩn tắc thích hợp cho các bước tiếp theo.
Sự chuẩn hóa một câu truy vấn bao gồm đặt các lượng tử và lượng tử
hóa truy vấn bằng cách áp dụng độ ưu tiên các toán tử logic.
2.2.1.2. Phân tích: Câu truy vấn đã chuẩn hóa được phân tích về
mặt ngữ nghĩa nhằm loại bỏ các câu truy vấn sai càng sớm càng tốt.

phân rã.
2.2.2.1. Rút gọn cho phân mảnh ngang nguyên thủy
Để giảm các thao tác truy vấn trên quan hệ đã được phân mảnh
ngang, trước hết phải xác định rõ cần thao tác trên mảnh nào và sau
đó xây dựng lại cây con, xem xét loại bỏ các quan hệ rỗng. Phân
mảnh ngang sẽ được sử dụng để làm đơn giản hóa các phép chọn và
phép kết nối.
Rút gọn phép chọn: Chọn trên các mảnh có lượng từ mâu thuẫn
với lượng từ hoá của quy tắc phân mảnh sẽ sinh ra quan hệ rỗng, ta
loại bỏ chúng.
Rút gọn với phép kết nối: Phép kết nối thực hiện trên các phân
mảnh ngang có thể đơn giản khi kết nối dựa theo các thuộc tính kết
nối, bằng cách phân phối kết nối trên các hợp và sau đó loại bỏ các
kết nối không tác dụng. Việc phân phối các kết nối trên phép hợp

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn


12
được phát biểu như sau: ( R1  R2)

S = (R1

S)  (R2

S)

Trong đó, Ri là các mảnh của R và S là một quan hệ.
2.2.2.2. Rút gọn cho phân mảnh ngang dẫn xuất

13
2.2.3. Tối ưu hóa toàn cục
Bước này sẽ xác định thứ tự thực thi truy vấn các mảnh, trạm
nào hiệu quả để truyền dữ liệu, nơi mà từng phần của câu truy vấn sẽ
được thực thi.
2.2.4. Tối ưu hóa cục bộ
Khi các truy vấn con được gửi đến một trạm cụ thể, nó sẽ được
thực thi và tối ưu cục bộ trên trạm đó sử dụng các kỹ thuật tối ưu hóa
tập trung.
2.3. Tối ƣu hóa truy vấn phân tán
Mục tiêu của tối ưu hóa truy vấn là làm sao tìm ra một chiến
lược gần tối ưu để thực thi câu truy vấn.
2.3.1. Không gian tìm kiếm
Đối với một câu truy vấn đã cho, không gian tìm kiếm có thể
được định nghĩa như một tập các cây toán tử tương đương, có được
bằng cách áp dụng các quy tắc biến đổi.
2.3.2. Chiến lược tìm kiếm
Có hai chiến lược cơ bản:
- Chiến lược xác định (Deterministic Strategy): Chiến lược này
tiến hành bằng cách xây dựng các kế hoạch, bắt đầu từ các quan hệ
cơ sở, sau đó nối thêm một hoặc nhiều quan hệ ở mỗi bước cho đến
khi thu được mọi kế hoạch khả hữu. Có hai cách: Theo chiều rộng xây dựng tất cả các kế hoạch có thể trước khi chọn kế hoạch tốt nhất
(Quy hoạch động (Dynamic Programming)), theo chiều sâu – chỉ xây
dựng một kế hoạch (Greedy).
- Chiến lược ngẫu nhiên (Randomized Strategy): Tiến hành tìm
kiếm giải pháp tối ưu xung quanh một số điểm cụ thể. Chiến lược
này không đảm bảo kế hoạch tối ưu nhưng tránh chi phí cao trong tối
ưu hóa về bộ nhớ và thời gian thực hiện. Chiến lược này áp dụng tốt

Số hóa bởi Trung tâm Học liệu – ĐHTN

 Số liệu thống kê CSDL
Tác nhân chính ảnh hưởng đến hiệu quả hoạt động của một chiến

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn


15
lược thực thi là kích thước các quan hệ trung gian đã được tạo ra. Khi
một phép toán tiếp theo nằm tại một vị trí khác, quan hệ trung gian phải
được di chuyển đến đó. Đó chính là điều khiến chúng ta phải ước lượng
kích thước của các kết quả trung gian của các phép toán đại số quan hệ
nhằm giảm thiểu lượng dữ liệu phải truyền. Việc ước lượng này dựa
trên các thông tin thống kê về các quan hệ cơ sở và các công thức để dự
đoán lực lượng của các kết quả.
 Lực lƣợng của các kết quả trung gian
Dữ liệu thống kê rất có ích khi đánh giá lực lượng của các kết
quả trung gian. Lực lượng của các kết quả trung gian sẽ được ước
lượng theo các phép toán đại số cơ bản: phép chọn, chiếu, tích Đề
các, kết nối, phép nối nửa, phép hợp, hiệu.
2.3.4. Thứ tự kết nối
Một số thuật toán tối ưu hoá thứ tự của các phép kết nối một
cách trực tiếp không sử dụng phép nửa kết nối như thuật toán
INGRES phân tán và R*.
Xét truy vấn có kết nối R

S, trong đó R và S là hai quan hệ

được lưu trữ trên các trạm khác nhau. Sự lựa chọn hiển nhiên là sẽ
truyền quan hệ nhỏ hơn tới trạm của quan hệ lớn hơn, làm phát sinh 2

chi phí cao, lặp lại nhiều lần cho mỗi thao tác. Vì vậy, phương pháp
này sẽ rất phù hợp cho một số câu truy vấn đặc biệt.
Phần này sẽ trình bày một số thuật toán tối ưu hóa truy vấn cơ
bản trong CSDL phân tán như thuật toán INGRES phân tán, thuật
toán R* và một thuật toán mới, kết hợp giữa thuật toán quy hoạch
động (Dynamic Programming) và thuật toán đàn kiến (Ant Colony
Optimization) được gọi là DP-ACO.
2.4.1. Thuật toán INGRES phân tán
Input: MRQ: Câu truy vấn có nhiều quan hệ.
Output:Kết quả của câu truy vấn con cuối cùng.
Begin
For mỗi ORQi có thể tách ra in MRQ do

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn


17
{ORQi là truy vấn một biến}
Run(ORQi);
MRQ‘_list  REDUCE (MRQ) {MRQ‘ chứa n truy vấn không
thể rút gọn}
While n ≠ 0 do
{Chọn truy vấn không thể rút gọn tiếp theo
liên quan đến mảnh nhỏ nhất}
MRQ‘  SELECT_QUERY (MRQ‘_list);
{Xác định mảnh để truyền và trạm xử lý cho MRQ‘}
Fragment-site-list  SELECT_STRATEGY (MRQ‘);
{Chuyển các mảnh đã chọn đến trạm xử lý đã chọn}
For mỗi cặp (F,S) trong Fragment-site-list do

2.4.3. Thuật toán DP-ACO
2.4.3.1. Thuật toán tối ưu đàn kiến (ACO Metaheuristic)[10]
Thuật toán dựa trên hành vi của đàn kiến thực trong việc thiết
lập đường đi ngắn nhất giữa thức ăn và tổ của nó. Kiến có thể giao
tiếp với nhau thông qua các hóa chất phát ra từ chúng trên đường đi
từ tổ tới chỗ thức ăn và ngược lại, gọi là pheromone. Như vậy, đường
đi ngắn hơn là đường có lượng pheromone cao hơn, kiến sẽ có xu
hướng chọn con đường ngắn hơn này.
Thuật toán tối ưu đàn kiến: Trong ACO, một con kiến nhân tạo
sẽ xây dựng giải pháp bằng cách đi qua đồ thị kết nối đầy đủ GC
(V,E), trong đó V là tập các đỉnh, E là tập các cạnh. Theo Dorigo,
kiến nhân tạo sẽ di chuyển từ đỉnh tới đỉnh dọc theo các cạnh của đồ
thị để xây dựng giải pháp thành phần (partial solution). Thuật toán
ACO metaheuristic, lặp 3 giai đoạn sau:
- ConstructAntSolution: Một tập m con kiến nhân tạo xây dựng
giải pháp từ các thành phần của một tập hữu hạn các giải pháp có sẵn.
Ban đầu tập này rỗng.
- ApplyLocalSearch: Khi các giải pháp đã được xây dựng và
trước khi cập nhật pheromone, chức năng này sẽ cải thiện các giải
pháp thu được bởi các con kiến thông qua tìm kiếm cục bộ. Bước này
không bắt buộc.
- UpdatePheromones: Nó làm tăng giá trị pheromone gắn liền
với giải pháp tốt và làm giảm với các giải pháp xấu. Điều này đạt
được bằng:
+ Giảm tất cả các giá trị pheromone qua việc bốc hơi
pheromone
+ Tăng mức pheromone với tập các giải pháp tốt được chọn.

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn

là một quan hệ cơ bản, PT đc gọi là left-deep tree. Sẽ có n! cách để
phân bổ n quan hệ cơ bản tới các lá của loại PT này. Nếu ko có hạn chế
về PT thì nó đc gọi là bushy tree. Trong nghiên cứu này, sẽ sử dụng
left-deep tree.
Mô hình chi phí dựa trên tổng thời gian xử lý (CPU time + I/O
time) được sử dụng.

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn


20
Quy hoạch động tạo ra những thiết kế tốt nhất có thể nhưng có
thời gian thực hiện dài và yêu cầu bộ nhớ rất lớn khi kích thước của
các quan hệ và số lượng kết nối tăng lên trong truy vấn.
2.4.3.3. Kết hợp thuật toán tối ưu đàn kiến và quy hoạch động
để tối ưu hóa truy vấn trong CSDL phân tán [5]
Khi kết hợp với quy hoạch động, chúng ta mô phỏng các hoạt
động của kiến trên đồ thị của PT (Processing Trees). Mỗi quá trình
tính toán thời gian chạy của một kế hoạch thực hiện sẽ được coi là
một con kiến trong thuật toán. Các giải pháp đại diện cho thức ăn.
Kiến có được thức ăn càng sớm thì lượng pheromone chúng tiết ra
trên đường đi của giải pháp càng nhiều. Càng cần nhiều thời gian cho
một con kiến đi theo đường này thì thời gian bay hơi càng nhiều.
Kiến kiếm ăn liên tục tìm kiếm kế hoạch thực hiện tốt hơn. Các
đường đi là những lựa chọn thay thế tổ hợp cho các kế hoạch của DP
ở mỗi mức. Nếu có 5 trạm trong phép kết nối của (A
B
C), sẽ
có 5 đường đi khác nhau. A


. ηβij
ταil . ηβil

∑

l ϵ subsolutions

Trong đó pkij là xác suất dịch chuyển của con kiến thứ k chuyển
từ giải pháp con thứ i sang giải pháp con thứ j. l là một thành phần
của các giải pháp con. Các giải pháp con này được sắp đặt như câu
lệnh SQL, α và β kiểm soát sự quan trọng tương đối của pheromone
τij với các thông tin heuristic ηij.
DP-ACO đã được chứng minh là giải pháp khả thi bằng việc tạo
ra các kế hoạch thực thi tốt với các câu truy vấn 15 nối trong thời
gian giới hạn và không gian bộ nhớ hạn chế. Một ưu điểm khác của
DP-ACO là có thể dễ dàng thích ứng với bộ tối ưu hóa truy vấn đang
tồn tại sử dụng thuật toán dựa trên DP
2.5. Kết luận chƣơng 2
Chương này đã trình bày những vấn đề cơ bản về xử lý câu truy
vấn, các thành phần chính của tối ưu hóa truy vấn, các thuật toán tối
ưu cơ bản như Distributed INGRES, System R*, DP-ACO. Mỗi
phương pháp tối ưu đều có ưu điểm, nhược điểm của nó. Phương
pháp tối ưu phân tán tĩnh, động có ưu nhược điểm giống như trong hệ
thống tập trung, phương pháp tối ưu dựa trên phép nửa kết nối sử
dụng tốt nhất với mạng chậm, phương pháp hỗn hợp là tốt nhất trong
môi trường động ngày nay vì nó trì hoãn các quyết định quan trọng
như lựa chọn sao chép và phân phối các truy vấn con đến các trạm tại
thời điểm khởi động truy vấn. Vì vậy, nó có thể tăng tính sẵn sàng và
cân bằng tải của hệ thống tốt hơn.

3.4. Kết quả thực nghiệm
Xét câu truy vấn
SELECT
dbo.CanBo.SoHieu, dbo.CanBo.HoTen,
dbo.CanBo.TenGoiKhac, dbo.CanBo.NgaySinh,
dbo.CanBo.CoQuanQuanLyID, dbo.CanBo.CoQuanSuDungID,
dbo.CanBo.GioiTinh, dbo.CanBo.NoiSinhID,
dbo.CanBo.QueQuanID, dbo.CanBo.DanTocID,
dbo.CanBo.TonGiaoID, dbo.CanBo.HKTT, dbo.CanBo.NoiO,
dbo.CanBo.NgheNghiepID, dbo.CanBo.NgayTD,
dbo.DienBienNgachBac.BacLuong,
dbo.DienBienNgachBac.NgayHuong,
dbo.DienBienNgachBac.NgayKetThuc,
dbo.DienBienNgachBac.ThoiHanNangBac,
dbo.DienBienNgachBac.DaVuotKhung,
dbo.DienBienNgachBac.HSCLBL, dbo.DienBienNgachBac.HeSo
dbo.DienBienNgachBac.PhuCapVuotKhung,
dbo.dmNgach.MaNgach, dbo.dmNgach.TenNgach,
dbo.dmNgach.LoaiNgach, dbo.dmNgach.PCVK
dbo.DienBienChucVu.ChucVuID,
dbo.DienBienChucVu.PhuCapChucVu,
dbo.DienBienChucVu.NgayBoNhiem,
dbo.DienBienChucVu.SoQuyetDinh
FROM dbo.CanBo INNER dbo.DienBienChucVu,
dbo.DienBienNgachBac
WHERE
dbo.CanBo.ID = dbo.DienBienChucVu.CanBoID AND
dbo.CanBo.ID =.CanBoID AND dbo.DienBienNgachBac.NgachID =
dbo.dmNgach.ID AND CLS.CLS_ID=CLSKhamBenh.CLS_ID



Trạm 1

125 ms

140 ms

Trạm 2

140 ms

156 ms

Trạm 3

187 ms

130 ms

3.5. Kết luận chƣơng 3
Chương 3 trình bày về bài toán quản lý nhận sự và chương
trình cài đặt 2 thuật toán INGRES phân tán và R* bao gồm: Thiết kế
CSDL phân tán, lựa chọn ngôn ngữ lập trình, hệ quản trị CSDL và

Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn


25
kết quả thực nghiệm chạy một câu truy vấn để so sánh thời gian chạy