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.