Bài giảng Nhập môn cơ sở dữ liệu: Chương 6 - Vũ Tuyết Trinh

Chương 6 - Tối ưu hoá câu hỏi. Chương này trình bày những nội dung như: Xử lý câu hỏi truy vấn, tối ưu hóa, kỹ thuật tối ưu hóa, tối ưu hóa logic, tối ưu dựa trên ngữ nghĩa, tính chất của phép toán. Cuối bài giảng có phần bài tập vận dụng giúp người học ôn tập và củng cố kiến thức đã học. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn cơ sở dữ liệu: Chương 6 - Vũ Tuyết Trinh Nhập môn cơ sở dữ liệu Tối ưu hoá câu hỏi Vũ Tuyết Trinh trinhvt@it-hut.edu.vn Bộ môn Các hệ thống thông tin, Khoa Công nghệ thông tin Đại học Bách Khoa Hà Nội Xử lý câu hỏi truy vấn Câu lệnh SQL Phân tích cú pháp (parser) Biểu thức ĐSQH Bộ tối ưu (optimizer) Biểu thức ĐSQH tối ưu Bộ sinh mã (code generator) Chương trình tối ưu Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 1 Nhập môn cơ sở dữ liệu Tối ưu hoá { { { { 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 ý: z z 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 Kỹ thuật tối ưu hoá { 2 kỹ thuật chính z z { Tối ưu llogic i ((rewriting) iti ) Tối ưu vật lý (access methods) TYPE Mục đích của các kỹ thuật tối ưu z z Giảm số bản ghi Giảm kích thước bản ghi NW { Ví dụ d WAGON (NW, TYPE, COND, STATION, CAPACITY, WEIGHT) TRAIN (NT, NW) WAGON (NW, TYPE...) NT = 4002 TRAIN (NT, NW) Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 2 Nhập môn cơ sở dữ liệu Nội dung 9 { { { Giới thiệu chung Tối ưu logic Tối ưu vật lý Mô hình giá Tối ưu hoá logic { Sử dụng các phép biến đổi tương đương để tìm ra biểu ể thức ĐSQH tốt ố { Gồm 2 giai đoạn z Biến đổi dựa trên ngữ nghĩa z Biến đổi dựa trên tính chất của các phép toán ĐSQH Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 3 Nhập môn cơ sở dữ liệu Tối ưu dựa trên ngữ nghĩa { Mục đích: z z { Dựa trên các ràng buộc dữ liệu để ể xác định các biểu ể thức tương đương Viết lại câu hỏi trên khung nhìn dựa trên các định nghĩa của khung nhìn Ví dụ EMPLOYEE (FirstName, LastName, SSN, Birthday, Adrresse, NoDept) DEPARTEMENT (DNO, DName, SSNManager) PROJECT (PNO, PName, PLocation, DNo) WORK-IN (ESSN, PNO, Heures) EMPLOYEE (Name, SSN, Birthday, Adrresse, NoDept) DEPARTEMENT (DNO, DName, SSNManager) PROJECT (PNO, PName, PLocation, DNo) WORK-IN (ESSN, NoProj, Heures) Tên của các nhân viên sinh sau ngày 30/01/70 và làm việc cho dự án Esprit Result WORK-IN.ESSN Name = EMPLOYEE. SSN = WORK-IN. PNO WORK-IN PROJECT.PNO NoProj = PNO ESSN=SSN EMPLOYE PROJET Birthday > “30/01/70 Đồ thị kết nối các quan hệ Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN PROJECT.PNO = PName = “Esprit” EMPLOYEE. Birthday “Esprit” > “30/01/70” Đồ thị kết nối các thuộc tính 4 Nhập môn cơ sở dữ liệu Tối ưu dựa trên ngữ nghĩa (2) { Loại bỏ các đồ thị con không liên kết trong đồ thị kết ế nối ố các quan hệ { Kiểm tra mâu thuẫn trong đồ thị kết nối các thuộc tính { Biế đổi câu Biến â hỏi ttương đ đương Tính chất của phép toán ĐSQH A ~ tập các thuộc tính, C ~ biểu thức điều kiện 1. Phép chiếu và phép chọn Π (R) => Π (Π (R) nếu A ⊆ A1 A A A1 σ C (R) => σ (σ (R)) nếu C = C1^C2 C1 C2 2. Tính giao hoán đối với phép chọn và chiếu σ (σ (R)) => σ (σ (R)) C1 C2 C2 C1 σ (Π (R)) => Π (σ (R)) C1 A2 A2 C1 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN nếu các thuộc tính của C2 thuộc A1 Π (σ (R)) => σ (Π (R)) A1 C2 C2 A1 Π (Π (R)) => Π (R) A1 A2 A1 nếu A1 ⊆ A2 5