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