Bài giảng Cơ sở dữ liệu: Chương 9 Tối ưu hóa câu hỏi do TS. Nguyễn Quốc Tuấn với các nội dung chính như: Nguyên tắc tối ưu hóa câu hỏi, biểu thức tương đương, quy tắc biến đổi tương đương, .! | Tối ưu hóa câu hỏi Biên soạn: TS. Nguyễn Quốc Tuấn Bm. Mạng và Các HTTT Tối ưu hóa câu hỏi Biến đổi biểu thức ĐSQH để tìm 1 biểu thức hiệu quả Tối ưu dựa trên cấu trúc và nội dung của dữ liệu Nâng cao hiệu quả thực hiện câu hỏi trên 1 hay nhiều tiêu chí: thời gian, sử dụng bộ nhớ, . Lưu ý: Không nhất thiết phải tìm biểu thức tối ưu nhất Chú ý tới tài nguyên sử dụng cho tối ưu Mục đích của các kỹ thuật tối ưu Giảm số bản ghi Giảm kích thước bản ghi Nguyên tắc tối ưu hóa câu hỏi Sáu chiến lược tổng quan của J. D. Ullman 1. Thực hiện phép chọn càng sớm càng tốt 2. Tổ hợp những phép chọn xác định với phép tích Đề-các thành phép kết nối 3. Tổ hợp dãy các phép toán quan hệ một ngôi như các phép chọn và phép chiếu 4. Tìm các biểu thức con chung trong một biểu thức 5. Tiền xử lý các quan hệ / bảng (Table Preprocessing) 6. Đánh giá trước khi thực hiện tính toán Biểu thức tương đương Sử dụng các phép biến đổi tương đương để tìm ra biểu thức ĐSQH tốt Biểu thức trong ngôn ngữ ĐSQH có các hạng thức là biến quan hệ R1,., Rn; các quan hệ hằng, được xác định như là một ánh xạ từ các k-bộ của các quan hệ (r1, ., rk) trong đó ri là quan hệ trên lược đồ Ri và thay thế ri vào Ri khi đánh giá biểu thức. Hai biểu thức E1 và E2 được gọi là tương đương (Equivalent), viết tắt là E1 E2, nếu chúng biểu diễn cùng một ánh xạ, nghĩa là, nếu chúng ta thay thế cùng các quan hệ cho tên các lược đồ tương ứng ở hai biểu thức E1 và E2, thì chúng sẽ cho ra cùng một kết quả. Quy tắc biến đổi tương đương 1. Quy tắc giao hoán của phép kết nối và tích Đề-các E1, E2 là các biểu thức quan hệ E1 E2 E2 E1 // Tính giao hoán của kết nối E1 * E2 E1 * E2 // Tính giao hoán của kết bằng E1 x E2 E1 x E2 // Tính giao hoán của tích Đề-các. 2. Quy tắc kết hợp của phép kết nối và tích Đề-các Nếu E1, E2 và E3 là các biểu thức quan hệ: F1, F2 là điều kiện thì: (E1 E2) E3 E1 (E2 E3) (E1 * E2) * E3 E1 * (E2 * E3) (E1 x E2) x E3
