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

Trong bài viết 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.
Nội dung trích xuất từ tài liệu:
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ố 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ácngô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 SELECTtruy vấn được chuyển đổi sang một biểu HoLot, Ten, DiaChi FROMthức đại số quan hệ tương đương được biểu NHANVIEN WHERE được chuyển sang biểudiễ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ủalược đồ quan hệ NHANVIEN như sau: khối truy vấn bên trong MAX HSLuong(SoPhongNHANVIEN(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ìnhMAX(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ốichuyể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 raThông báo Khoa học và Công nghệ* Số 1-2013 127cá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, PHONG2.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 ANDdạng cây tương ứng với một biểu thức đại số D.MaQly = E. MaNV AND P.DiaChiDuAnquan 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ủaphé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 đạihiệ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 ...