Xem mẫu
- 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ố rộng là: MAX HSLuong(SoPhong =
quan hệ “KT05”(NHANVIEN))
SQL (Structure Query Language) là Trong đó là phép kết hợp hàm của các
ngôn ngữ truy vấn được sử dụng trong hầu hàm: SUM, AVERAGE, MAX, MIN,
hết các hệ quản trị cơ sở dữ liệu. Quá trình COUNT…
thực thi một câu truy vấn SQL, đầu tiên câu Khối truy vấn bên ngoài SELECT
truy vấn được chuyển đổi sang một biểu HoLot, Ten, DiaChi FROM
thức đại số quan hệ tương đương được biểu NHANVIEN WHERE được chuyển sang biểu
diễn dưới dạng cấu trúc cây truy vấn, sau đó thức đại số quan hệ:
tối ưu hóa. HoLot, Ten, DiaChi(HSLuog >
Ví dụ 1: Xét câu truy vấn SQL trên c(NHANVIEN)), với C là kết quả trả về của
lược đồ quan hệ NHANVIEN như sau: khối truy vấn bên trong MAX HSLuong(SoPhong
NHANVIEN(MaNV, HoLot, Ten, = “KT05”(NHANVIEN))
NgaySinh, GioiTinh, Chucvu, DiaChi, Như vậy việc tối ưu hóa truy vấn là quá
HSLuong, SoPhong) trình lựa chọn một biểu thức đại số cho câu
SELECT HoLot, Ten, DiaChi truy vấn sao cho tốc độ truy xuất nhanh nhất
FROM NHANVIEN và không dư thừa thông tin không cần thiết.
WHERE HSLuong > ( SELECT
2. Tối ưu hóa câu truy vấn bằng phương
MAX(HSLuong)
pháp heuristic
FROM
Bài báo này tập trung thảo luận một kĩ
NHANVIEN
thuật tối ưu hóa câu truy vấn áp dụng các qui
WHERE
SoPhong = “KT05”); 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
Khối truy vấn bên trong SELECT
truy vấn. Thông thường, ta sử dụng hình
MAX(HSLuong) FROM NHANVIEN
thức một cây truy vấn hoặc một cấu trúc dữ
WHERE SoPhong = “KT05”) có thể được
liệu đồ thị truy vấn để cải tiến quá trình tối
chuyển sang biểu thức đại số quan hệ mở
ư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 SELECT P.SoDuAn, P.SoPhong,
ưu theo các qui tắc heuristic. E.Ten, E.DiaChi, E.NgaySinh
FROM DU AN AS P, PHONG
2.1. Cây truy vấn và đồ thị truy vấn
BAN AS D, NHAN VIEN AS E
Một cây truy vấn là một cấu trúc dữ liệu WHERE P.SoPhong = D.SoPBan AND
dạng cây tương ứng với một biểu thức đại số D.MaQly = E. MaNV AND P.DiaChiDuAn
quan hệ. Các quan hệ đầu vào của câu truy =”Stafford” ;
vấn được biểu diễn là các nút lá của cây, các Hình 1(a) biểu diễn cây truy vấn của
phép toán đại số quan hệ là các nút bên trong. truy vấn Q1, có ba quan hệ DU AN,
Quá trình thực hiện cây truy vấn bao gồm PHONG BAN và NHAN VIEN được thể
việc thực hiện một nút bên trong mỗi lần thực hiện bởi các nút lá P, D và E. Các phép đại
hiện các toán hạng của biểu thức quan hệ, sau số quan hệ của biểu thức được biểu diễn bởi
đó thay thế nút bên trong đó bởi quan hệ kết các nút bên trong cây. Khi cây truy vấn này
quả của phép toán. Quá trình thực hiện kết được thực hiện, nút (1) phải bắt đầu thực
thúc khi nút gốc được thực hiện và tạo ra hiện trước nút (2) bởi vì một số bộ kết quả
quan hệ kết quả cho câu truy vấn. của phép (1) phải sẵn sàng trước khi chúng
Ví dụ 2: Xét lược đồ cơ sở dữ liệu ta có thể bắt đầu thực hiện phép (2). Tương
quan hệ như sau: tự, nút (2) phải bắt đầu thực hiện và tạo ra
NHAN VIEN(MaNV, HoLot, Ten, các kết quả trước khi nút (3) có thể bắt đầu
Ngaysinh, GioiTinh, ChucVu, DiaChi, thực hiện, …
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 Hình 1(a): Cây truy vấn tương ứng với biểu
quản lí phòng ban của mọi dự án nằm ở thức đại số quan hệ
“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:
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
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 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. Hình 2 (a): Cây truy vấn ban đầu ứng
2.2. Tối ưu hoá cây truy vấn bằng với SQL.
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 Hình 2 (b): Chuyển các phép chọn
ban đầu. Tối ưu hóa câu truy vấn bằng các xuống dưới cây truy vấn.
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 Hình 2 (c): Ưu tiên áp dụng các phép
FROM NHAN VIEN, THAM GIA , DU chọn có giới hạn hơn.
AN
- Thông báo Khoa học và Công nghệ* Số 1-2013 129
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
Hình 2 (d): Thay thế tích Đề Các và các quan hệ trung gian, ví dụ sử dụng các
phép chọn bằng các phép nối. 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
Hình 2(e): Chuyển các phép chiếu xuống hai quan hệ trình bày cùng lượng thông tin
dưới cây truy vấn. thì chúng ta xem đó là các quan hệ tương
Cây truy vấn ban đầu đối với Q2 được đương. Phần này chúng ta giới thiệu một số
chỉ ra trong hình 1(a). Quá trình thực hiện qui tắc chuyển đổi có ích trong việc tối ưu
cây truy vấn này đầu tiên sẽ tạo ra một tập hóa câu truy.
hợp các bộ dữ liệu rất lớn bao gồm tích Đề 1. Gộp dãy phép chọn: C AND C2 AND …AND 1
các của các bộ dữ liệu đầu vào NHAN
Cn(R) C1 ( C2 (...( cn ( R ))...))
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ệ 2. Tính giao hoán của phép chọn:
DU AN đối với tên dự án là ‘Aquarius’ và C1 ( C2 ( R )) C2 ( C1 ( R ))
chỉ các bản ghi của NHAN VIEN có ngày 3. Gộp dãy phép chiếu:
sinh sau 31/12/1977. Hình 2(b) chỉ ra một List1( List2(…( Listn(R))…)) List1(R)
cây truy vấn cải tiến mà đầu tiên là áp dụng 4. Tính giao hoán của phép chọn với phép
các phép chọn để giảm số bộ xuất hiện trong chiếu: Nếu điều kiện chọn C chỉ bao gồm
tích Đề Các. các thuộc tính A1, …,An trong danh sách
Một sự cải tiến nữa đã đạt được là phép chiếu thì hai phép đó có thể giao hoán
chuyển vị trí của các quan hệ NHAN VIEN với nhau:
và DU AN trong cây, như đã chỉ ra trong A1 , A2 ,..., An ( c ( R )) c ( A1 , A2 ,..., An ( R ))
hình 2(c). Điều này sử dụng thông tin mà số
- 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. tính giao hoán nhưng phép - (phép trừ) thì
Phép cũng như phép đều có tính giao không có tính giao hoán.
hoán: R c S S c R ; R S S R 9. Tính kết hợp của các phép toán , ,
6. Tính giao hoán của phép chọn và phép nối và là: (R S) T R (S T)
(hoặc tích Đề Các): Nếu tất cả các thuộc 10. Tính giao hoán của phép chọn với các
tính trong điều kiện chọn C chỉ bao gồm các phép toán tập hợp: Phép giao hoán với ,
thuộc tính của một trong hai quan hệ của và – là: C (R S) ( C (R)) ( C (S))
phép thì ta có: C (R S) ( C (R)) S 11. Tính giao hoán của phép chiếu với phép
Như một sự lựa chọn, nếu điều kiện hợp: L(R S) (L(R)) (L(S))
chọn C có thể được viết lại là (c1 AND c2), ở 12. Chuyển một dãy các phép chọn, tích Đề
đây c1 chỉ bao gồm các thuộc tính của R và Các (,) thành phép nối : Nếu điều kiện
điều kiện c2 chỉ bao gồm các thuộc tính của C của một phép mà theo sau là một phép
S, ta có: C (R S) ( C 1 (R)) ( C 2 (S)) tương ứng với một điều kiện nối, có thể
7. Tính giao hoán của phép chiếu và phép chuyển dãy (,) thành một phép như sau:
nối (hoặc tích Đề Các: Giả sử rằng danh C (R S) (R c S)
sách phép chiếu là L ={A1, ..., An , B1, ...,
Từ các qui tắc trên ta có thuật toán tối
Bm}, ở đây A1, ..., An là các thuộc tính của ưu hóa truy vấn bằng phương pháp heuristic
R và B1, ..., Bm là các thuộc tính của S. Nếu thực hiện như sau:
điều kiện nối C chỉ bao gồm các thuộc tính 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
trong L thì ta có: L(R c S) (A1, ..., An(R))
dãy các phép chọn, chuyển các phép chọn
c (B1, ..., Bm(S))
xuống các nhánh khác của cây.
Nếu điều kiện nối C chứa các thuộc Bước 2: Sử dụng qui tắc 2, 4, 6 và 10
tính không thuộc L thì các thuộc tính này tức là tính giao hoán của phép chọn với các
phải được thêm vào danh sách phép chiếu và phép khác, chuyển mỗi phép chọn ở trên
một phép chiếu cuối cùng cũng được thêm xuống phía dưới cây truy vấn khi có thể.
vào. Ví dụ, nếu các thuộc tính An+1 , ..., Bước 3: Sử dụng qui tắc 5 và 9 chính
An+k của R và Bm+1, ..., Bm+p của S được là tính giao hoán và kết hợp của các phép
bao gồm trong điều kiện nối C nhưng không toán hai ngôi. Sắp xếp lại các nút lá, ưu tiên
thuộc danh sách các thuộc tính chiếu L, thì các quan hệ tương ứng với phép chọn giới
ta có: L(R c S) L((A1, ..., An,An+1, ..., 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ỏ
An+k(R)) c (B1, ..., Bm,Am+1, ..., Am+p(S))) nhất.
Đối với phép không có điều kiện C Bước 4: Sử dụng qui tắc 12, kết hợp
nên qui tắc chuyển đổi đầu tiên luôn áp dụng một phép tích Đề Các với một phép chọn
được bằng cách thay c bởi . thành một phép nối, nếu điều kiện của phép
8. Tính giao hoán của các phép toán tập chọn tương ứng với điều kiện nối.
hợp: Các phép tập hợp như và là có 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ã sắp xếp lại các nút lá của cây nhằm loại bỏ
và chuyển các danh sách thuộc tính chiếu các tích Đề Các và điều chỉnh phần còn lại
xuống phía dưới cây truy vấn đến mức có của cây một cách thích hợp.
thể bằng cách tạo ra các phép chiếu mới khi 3. Kết luận
cần thiết. Chỉ các thuộc tính cần trong kết Bài báo này đã đưa ra một cái nhìn
quả truy vấn và trong các phép toán tiếp theo tổng quan về các kỹ thuật được sử dụng bởi
trong cây truy vấn nên được giữ lại sau mỗi các hệ quản trị cơ sở dữ liêu trong việc xử lý
phép chiếu. và tối ưu hóa các truy vấn mức cao. Phương
Bước 6: Nhận ra các cây con trình bày pháp heuristic để tối ưu hóa câu truy vấn, sử
các nhóm các phép toán có thể thực hiện dụng các quy tắc heuristic và các kỹ thuật
bằng một thuật toán đơn. đại số để cải tiến hiệu quả quá trình hiện truy
Heuristic chính là áp dụng các phép vấn. Thông qua đó chúng ta cũng chỉ ra rằng
toán làm giảm kích thước của các kết quả một cây truy vấn thể hiện biểu thức đại số
trung gian. Điều này bao gồm việc thực hiện quan hệ có thể được tối ưu hóa dựa theo các
các phép chọn và phép chiếu trước có thể để qui tắc heuristic bằng cách tổ chức lại các
giảm số bộ và giảm số thuộc tính. Thêm vào nút của cây và chuyển nó thành cây truy vấn
đó, các phép chọn giới hạn nhất hoặc là các tương đương khác hiệu quả hơn để xử lý.
phép đó tạo ra một quan hệ với số bộ ít nhất Các quy tắc chuyển đổi giữ vững tính tương
hoặc là quan hệ với kích thước nhỏ nhất nên đương có thể được áp dụng cho một cây truy
được thực hiện trước các toán tử tương tự vấn và sau đó giới thiệu các kế hoạch thực
khác. Điều này được thực hiện bằng cách 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.
nguon tai.lieu . vn
