Thuật toán tối ưu hóa truy vấn trên cơ sở dữ liệu quan hệ

Thông báo Khoa học và Công nghệ* Số 1-2013 126 
THUẬT TOÁN TỐI ƯU HÓA TRUY VẤN TRÊN CƠ SỞ DỮ LIỆU QUAN HỆ 
 ThS. Trần Thái Sơn 
 Trung tâm Ngoại ngữ - Tin học, trường Đại học Xây dựng Miền trung 
Tóm tắt: Hầu hết tất cả các hệ quả trị cơ sở dữ liệu đều dùng ngôn ngữ truy vấn có cấu trúc 
SQL (Structure Query Language) để truy xuất dữ liệu, việc lựa chọn một biểu thức đại số 
quan hệ để thực thi một câu truy vấn là vấn đề cần thiết. Trong bài báo này tác giả tập 
trung thảo luận một phương pháp tối ưu hóa câu truy vấn bằng kỹ thuật heuristic nhằm 
nâng cao tốc độ truy xuất dữ liệu, giảm số bộ dữ liệu thừa, không gian lưu trữ dữ liệu trung 
gian trong bộ nhớ khi thực hiện một cây truy vấn 
Từ khóa: Truy vấn SQL, biểu thức đại số quan hệ, tối ưu hóa truy vấn.
1. Chuyển câu truy vấn SQL sang đại số 
quan hệ 
SQL (Structure Query Language) là 
ngôn ngữ truy vấn được sử dụng trong hầu 
hết các hệ quản trị cơ sở dữ liệu. Quá trình 
thực thi một câu truy vấn SQL, đầu tiên câu 
truy vấn được chuyển đổi sang một biểu 
thức đại số quan hệ tương đương được biểu 
diễn dưới dạng cấu trúc cây truy vấn, sau đó 
tối ưu hóa. 
Ví dụ 1: Xét câu truy vấn SQL trên 
lược đồ quan hệ NHANVIEN như sau: 
NHANVIEN(MaNV, HoLot, Ten, 
NgaySinh, GioiTinh, Chucvu, DiaChi, 
HSLuong, SoPhong) 
SELECT HoLot, Ten, DiaChi 
FROM NHANVIEN 
WHERE HSLuong > ( SELECT
 MAX(HSLuong) 
 FROM 
 NHANVIEN 
 WHERE
 SoPhong = “KT05”); 
Khối truy vấn bên trong SELECT 
MAX(HSLuong) FROM NHANVIEN 
WHERE SoPhong = “KT05”) có thể được 
chuyển sang biểu thức đại số quan hệ mở 
rộng là: MAX HSLuong(SoPhong = 
“KT05”(NHANVIEN)) 
Trong đó  là phép kết hợp hàm của các 
hàm: SUM, AVERAGE, MAX, MIN, 
COUNT 
Khối truy vấn bên ngoài SELECT
 HoLot, Ten, DiaChi FROM 
NHANVIEN WHERE được chuyển sang biểu 
thức đại số quan hệ: 
 HoLot, Ten, DiaChi(HSLuog > 
c(NHANVIEN)), với C là kết quả trả về của 
khối truy vấn bên trong MAX HSLuong(SoPhong 
= “KT05”(NHANVIEN)) 
Như vậy việc tối ưu hóa truy vấn là quá 
trình lựa chọn một biểu thức đại số cho câu 
truy vấn sao cho tốc độ truy xuất nhanh nhất 
và không dư thừa thông tin không cần thiết. 
2. Tối ưu hóa câu truy vấn bằng phương 
pháp heuristic 
Bài báo này tập trung thảo luận một kĩ 
thuật tối ưu hóa câu truy vấn áp dụng các qui 
tắc heuristic để thay đổi quá trình thực thiện 
biểu thức đại số quan hệ bên trong của một 
truy vấn. Thông thường, ta sử dụng hình 
thức một cây truy vấn hoặc một cấu trúc dữ 
liệu đồ thị truy vấn để cải tiến quá trình tối 
ưu. Từ một truy vấn mức cao đầu tiên tạo ra 
Thông báo Khoa học và Công nghệ* Số 1-2013 127 
các biểu thức đại số quan hệ, sau đó được tối 
ưu theo các qui tắc heuristic. 
2.1. Cây truy vấn và đồ thị truy vấn 
Một cây truy vấn là một cấu trúc dữ liệu 
dạng cây tương ứng với một biểu thức đại số 
quan hệ. Các quan hệ đầu vào của câu truy 
vấn được biểu diễn là các nút lá của cây, các 
phép toán đại số quan hệ là các nút bên trong. 
Quá trình thực hiện cây truy vấn bao gồm 
việc thực hiện một nút bên trong mỗi lần thực 
hiện các toán hạng của biểu thức quan hệ, sau 
đó thay thế nút bên trong đó bởi quan hệ kết 
quả của phép toán. Quá trình thực hiện kết 
thúc khi nút gốc được thực hiện và tạo ra 
quan hệ kết quả cho câu truy vấn. 
Ví dụ 2: Xét lược đồ cơ sở dữ liệu 
quan hệ như sau: 
NHAN VIEN(MaNV, HoLot, Ten, 
Ngaysinh, GioiTinh, ChucVu, DiaChi, 
HSLuong, Sophong) 
PHONG BAN(SoPBan, TenPhongBan, 
DienThoai, MaQly, NgayBatDauQL) 
DIA CHI PBAN( SoPBan , Diachi,) 
DU AN( SoDuAn, TenDaAn, DiaChiDuAn, 
SoPhong) 
THAM GIA(SNV, SDA, SoNgayCong) 
THAN NHAN(MaNV, HoTenTN, Phai, 
NgaySinhTN, MoiQuanHe) 
Với truy vấn Q1: Cho biết số dự án, số 
phòng ban, tên, địa chỉ và ngày sinh người 
quản lí phòng ban của mọi dự án nằm ở 
“Stafford”. Truy vấn Q1 tương ứng với biểu 
thức đại số quan hệ: 
 SoDuAn, Sophong, Ten, DiaChi, 
NgaySinh(((DiaChiDuAn=’Stafford’(DU AN)) 
 Sophong=SoPBan (PHONG BAN)) MaQly = MaNV( 
NHAN VIEN)) 
Và tương ứng với câu lệnh SQL như sau: 
SELECT P.SoDuAn, P.SoPhong, 
E.Ten, E.DiaChi, E.NgaySinh 
FROM DU AN AS P, PHONG 
BAN AS D, NHAN VIEN AS E 
WHERE P.SoPhong = D.SoPBan AND 
D.MaQly = E. MaNV AND P.DiaChiDuAn 
=”Stafford” ; 
Hình 1(a) biểu diễn cây truy vấn của 
truy vấn Q1, có ba quan hệ DU AN, 
PHONG BAN và NHAN VIEN được thể 
hiện bởi các nút lá P, D và E. Các phép đại 
số quan hệ của biểu thức được biểu diễn bởi 
các nút bên trong cây. Khi cây truy vấn này 
được thực hiện, nút (1) phải bắt đầu thực 
hiện trước nút (2) bởi vì một số bộ kết quả 
của phép (1) phải sẵn sàng trước khi chúng 
ta có thể bắt đầu thực hiện phép (2). Tương 
tự, nút (2) phải bắt đầu thực hiện và tạo ra 
các kết quả trước khi nút (3) có thể bắt đầu 
thực hiện,  
Hình 1(a): Cây truy vấn tương ứng với biểu 
thức đại số quan hệ 
Hình 1(b): Cây truy vấn ban đầu ứng với SQL. 
Thông báo Khoa học và Công nghệ* Số 1-2013 128 
Hình 1(c): Đồ thị truy vấn của Q1 
Sự biểu diễn bằng đồ thị truy vấn 
không cho biết thứ tự thực hiện trên các 
phép toán, nó chỉ gồm một đồ thị đơn tương 
ứng với mỗi truy vấn. Một số kĩ thuật tối ưu 
hoá đã dựa vào các đồ thị truy vấn, nhưng 
hầu hết chưa đưa ra thứ tự thực hiện các 
phép toán trên cây, trong khi đó việc tối ưu 
hoá câu truy vấn cần phải chỉ ra thứ tự thực 
hiện của các phép. 
2.2. Tối ưu hoá cây truy vấn bằng 
heuristic 
Thông thường, một câu truy vấn có thể 
được biểu diễn sang nhiều biểu thức đại số 
quan hệ khác nhau. Phân tích câu truy vấn sẽ 
tạo ra một cây truy vấn ban đầu chuẩn ứng 
với truy vấn SQL mà không sử dụng bất cứ 
sự tối ưu hoá nào. 
Việc tối ưu hoá bao gồm các qui tắc 
tương đương giữa các biểu thức đại số quan 
hệ mà có thể được áp dụng cho cây truy vấn 
ban đầu. Tối ưu hóa câu truy vấn bằng các 
qui tắc heuristic chính là sử dụng các biểu 
thức tương đương này để chuyển cây truy 
vấn ban đầu thành cây truy vấn cuối cùng đã 
tối ưu. 
Ví dụ 3: Xét truy vấn Q2: Tìm tên của 
tất cả các nhân viên sinh sau 1957, làm việc 
trong dự án có tên là ‘Aquarius’. Truy vấn 
này có thể viết lại bằng SQL như sau: 
SELECT Ten 
FROM NHAN VIEN, THAM GIA , DU 
AN 
WHERE TenDuAn = ‘Aquarius’AND 
SoDuAn = SDA AND SNV = MaMV AND 
NgaySinh > #31/12/1977#; 
Các bước chuyển đổi một cây truy vấn 
trong suốt quá trình tối ưu hóa bằng cách sử 
dụng heuristic. 
Hình 2 (a): Cây truy vấn ban đầu ứng 
với SQL. 
Hình 2 (b): Chuyển các phép chọn 
xuống dưới cây truy vấn. 
Hình 2 (c): Ưu tiên áp dụng các phép 
chọn có giới hạn hơn. 
Thông báo Khoa học và Công nghệ* Số 1-2013 129 
Hình 2 (d): Thay thế tích Đề Các và 
phép chọn bằng các phép nối. 
Hình 2(e): Chuyển các phép chiếu xuống 
dưới cây truy vấn. 
Cây truy vấn ban đầu đối với Q2 được 
chỉ ra trong hình 1(a). Quá trình thực hiện 
cây truy vấn này đầu tiên sẽ tạo ra một tập 
hợp các bộ dữ liệu rất lớn bao gồm tích Đề 
các của các bộ dữ liệu đầu vào NHAN 
VIEN, THAM GIA và DU AN. Tuy nhiên 
truy vấn này chỉ cần một bản ghi từ quan hệ 
DU AN đối với tên dự án là ‘Aquarius’ và 
chỉ các bản ghi của NHAN VIEN có ngày 
sinh sau 31/12/1977. Hình 2(b) chỉ ra một 
cây truy vấn cải tiến mà đầu tiên là áp dụng 
các phép chọn để giảm số bộ xuất hiện trong 
tích Đề Các. 
Một sự cải tiến nữa đã đạt được là 
chuyển vị trí của các quan hệ NHAN VIEN 
và DU AN trong cây, như đã chỉ ra trong 
hình 2(c). Điều này sử dụng thông tin mà số 
dự án là một thuộc tính khoá của quan hệ 
DU AN, vì vậy phép chọn trên quan hệ DU 
AN sẽ lấy một bản ghi duy nhất. Chúng ta có 
thể cải tiến hơn nữa cây truy vấn bằng cách 
thay thế bất cứ phép tích Đề các nào mà theo 
sau là một điều kiện nối với một phép nối, 
như đã chỉ ra trong hình 2(d). 
Một sự cải tiến khác là chỉ giữ lại các 
thuộc tính cần cho các phép theo sau trong 
các quan hệ trung gian, ví dụ sử dụng các 
phép chiếu () trước trong cây truy vấn như 
đã chỉ ra trong hình 2(e). Điều này làm giảm 
các thuộc tính của các quan hệ trung gian, 
ngược lại các phép chọn làm giảm các bộ 
cần truy xuất. 
Có nhiều qui tắc để chuyển đổi các 
phép toán đại số quan hệ thành các biểu thức 
tương đương. Ở đây chúng ta quan tâm đến 
ý nghĩa của các phép toán và các quan hệ kết 
quả. Vì vậy, nếu hai quan hệ có cùng tập 
thuộc tính theo một thứ tự khác nhau nhưng 
hai quan hệ trình bày cùng lượng thông tin 
thì chúng ta xem đó là các quan hệ tương 
đương. Phần này chúng ta giới thiệu một số 
qui tắc chuyển đổi có ích trong việc tối ưu 
hóa câu truy. 
1. Gộp dãy phép chọn: 
1C
 AND C2 AND AND 
Cn(R)  1C ( ))...))((...(2 RncC  
2. Tính giao hoán của phép chọn: 
1C
 ))((
2
RC  2C ))(( 1 RC 
3. Gộp dãy phép chiếu: 
 List1( List2(( Listn(R))))  List1(R) 
4. Tính giao hoán của phép chọn với phép 
chiếu: Nếu điều kiện chọn C chỉ bao gồm 
các thuộc tính A1, ,An trong danh sách 
phép chiếu thì hai phép đó có thể giao hoán 
với nhau: 
 ))(())(( ,...,,,...,, 2121 RR nn AAAccAAA   
Thông báo Khoa học và Công nghệ* Số 1-2013 130 
5. Tính giao hoán của phép nối / tích Đề Các. 
Phép cũng như phép đều có tính giao 
hoán: R c S S c R ; R S  S R 
6. Tính giao hoán của phép chọn và phép nối 
(hoặc tích Đề Các): Nếu tất cả các thuộc 
tính trong điều kiện chọn C chỉ bao gồm các 
thuộc tính của một trong hai quan hệ của 
phép thì ta có: C (R S)  ( C (R)) S 
Như một sự lựa chọn, nếu điều kiện 
chọn C có thể được viết lại là (c1 AND c2), ở 
đây c1 chỉ bao gồm các thuộc tính của R và 
điều kiện c2 chỉ bao gồm các thuộc tính của 
S, ta có: C (R S)  ( 1C (R)) ( 2C (S)) 
7. Tính giao hoán của phép chiếu và phép 
nối (hoặc tích Đề Các: Giả sử rằng danh 
sách phép chiếu là L ={A1, ..., An , B1, ..., 
Bm}, ở đây A1, ..., An là các thuộc tính của 
R và B1, ..., Bm là các thuộc tính của S. Nếu 
điều kiện nối C chỉ bao gồm các thuộc tính 
trong L thì ta có: L(R c S)  ( A1, ..., An(R)) 
 c ( B1, ..., Bm(S)) 
Nếu điều kiện nối C chứa các thuộc 
tính không thuộc L thì các thuộc tính này 
phải được thêm vào danh sách phép chiếu và 
một phép chiếu cuối cùng cũng được thêm 
vào. Ví dụ, nếu các thuộc tính An+1, ..., 
An+k của R và Bm+1, ..., Bm+p của S được 
bao gồm trong điều kiện nối C nhưng không 
thuộc danh sách các thuộc tính chiếu L, thì 
ta có: L(R c S)  L(( A1, ..., An,An+1, ..., 
An+k(R)) c ( B1, ..., Bm,Am+1, ..., Am+p(S))) 
Đối với phép không có điều kiện C 
nên qui tắc chuyển đổi đầu tiên luôn áp dụng 
được bằng cách thay c bởi . 
8. Tính giao hoán của các phép toán tập 
hợp: Các phép tập hợp như  và  là có 
tính giao hoán nhưng phép - (phép trừ) thì 
không có tính giao hoán. 
9. Tính kết hợp của các phép toán , ,  
và  là: (R  S)  T  R  (S  T) 
10. Tính giao hoán của phép chọn với các 
phép toán tập hợp: Phép  giao hoán với , 
 và – là: C (R  S)  ( C (R))  ( C (S)) 
11. Tính giao hoán của phép chiếu với phép 
hợp: L(R  S)  ( L(R))  ( L(S)) 
12. Chuyển một dãy các phép chọn, tích Đề 
Các (, ) thành phép nối : Nếu điều kiện 
C của một phép  mà theo sau là một phép 
tương ứng với một điều kiện nối, có thể 
chuyển dãy (, ) thành một phép như sau: 
C (R S)  (R c S) 
Từ các qui tắc trên ta có thuật toán tối 
ưu hóa truy vấn bằng phương pháp heuristic 
thực hiện như sau: 
Bước 1: Sử dụng qui tắc 1, phân rã bất 
cứ phép chọn nào có điều kiện hội thành một 
dãy các phép chọn, chuyển các phép chọn 
xuống các nhánh khác của cây. 
Bước 2: Sử dụng qui tắc 2, 4, 6 và 10 
tức là tính giao hoán của phép chọn với các 
phép khác, chuyển mỗi phép chọn ở trên 
xuống phía dưới cây truy vấn khi có thể. 
Bước 3: Sử dụng qui tắc 5 và 9 chính 
là tính giao hoán và kết hợp của các phép 
toán hai ngôi. Sắp xếp lại các nút lá, ưu tiên 
các quan hệ tương ứng với phép chọn giới 
hạn nhất, phép đó tạo ra một quan hệ với số 
bộ ít nhất hoặc là quan hệ với kích thước nhỏ 
nhất. 
Bước 4: Sử dụng qui tắc 12, kết hợp 
một phép tích Đề Các với một phép chọn 
thành một phép nối, nếu điều kiện của phép 
chọn tương ứng với điều kiện nối. 
Bước 5: Sử dụng qui tắc 3, 4, 7, và 11 
đó chính là dãy phép chiếu và tính giao hoán 
Thông báo Khoa học và Công nghệ* Số 1-2013 131 
của phép chiếu với các phép khác. Phân rã 
và chuyển các danh sách thuộc tính chiếu 
xuống phía dưới cây truy vấn đến mức có 
thể bằng cách tạo ra các phép chiếu mới khi 
cần thiết. Chỉ các thuộc tính cần trong kết 
quả truy vấn và trong các phép toán tiếp theo 
trong cây truy vấn nên được giữ lại sau mỗi 
phép chiếu. 
Bước 6: Nhận ra các cây con trình bày 
các nhóm các phép toán có thể thực hiện 
bằng một thuật toán đơn. 
Heuristic chính là áp dụng các phép 
toán làm giảm kích thước của các kết quả 
trung gian. Điều này bao gồm việc thực hiện 
các phép chọn và phép chiếu trước có thể để 
giảm số bộ và giảm số thuộc tính. Thêm vào 
đó, các phép chọn giới hạn nhất hoặc là các 
phép đó tạo ra một quan hệ với số bộ ít nhất 
hoặc là quan hệ với kích thước nhỏ nhất nên 
được thực hiện trước các toán tử tương tự 
khác. Điều này được thực hiện bằng cách 
sắp xếp lại các nút lá của cây nhằm loại bỏ 
các tích Đề Các và điều chỉnh phần còn lại 
của cây một cách thích hợp. 
3. Kết luận 
Bài báo này đã đưa ra một cái nhìn 
tổng quan về các kỹ thuật được sử dụng bởi 
các hệ quản trị cơ sở dữ liêu trong việc xử lý 
và tối ưu hóa các truy vấn mức cao. Phương 
pháp heuristic để tối ưu hóa câu truy vấn, sử 
dụng các quy tắc heuristic và các kỹ thuật 
đại số để cải tiến hiệu quả quá trình hiện truy 
vấn. Thông qua đó chúng ta cũng chỉ ra rằng 
một cây truy vấn thể hiện biểu thức đại số 
quan hệ có thể được tối ưu hóa dựa theo các 
qui tắc heuristic bằng cách tổ chức lại các 
nút của cây và chuyển nó thành cây truy vấn 
tương đương khác hiệu quả hơn để xử lý. 
Các quy tắc chuyển đổi giữ vững tính tương 
đương có thể được áp dụng cho một cây truy 
vấn và sau đó giới thiệu các kế hoạch thực 
hiện truy vấn đối với các truy vấn SQL.
TÀI LIỆU THAM KHẢO 
[1] PGS.TS, Vũ Đức Thi. 1997. “Cơ sở dữ liệu – Kiến thức và thực hành”. Nxb Khoa học 
Thống kê. 
[2] Trần Nguyên Phong. 2005. “Giáo trình thực hành SQL”, ĐHKH Huế. 
[3] Elmasri & Navathe. 2007. “Fundamentals of Database Systems”. 
[4] Ramakrishnan, R. and Gehrke. 2003. “Database Management Systems”, Third Edition, 
McGraw Hill.