Bài giảng Cơ sở dữ liệu - Chương 6: Tối ưu hoá câu hỏi - Vũ Tuyết Trinh

Nội dung text: Bài giảng Cơ sở dữ liệu - Chương 6: Tối ưu hoá câu hỏi - Vũ Tuyết Trinh

1. Nhập môn cơ sở dữ liệu Tối ưu hoá { Biến đổibiểuthức ĐSQH để tìm 1 biểuthức hiệuquả { 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ý:u ý: z Không nhất thiết phải tìm biểu thức tối ưu nhất z Chú ý tới tài nguyên sử dụng cho tối ưu Kỹ thuậttối ưu hoá { 2 kỹ thuật chính TYPE z Tối ưu li(logic (rewr iti)iting) z Tối ưu vật lý (access methods) { Mục đích củacáckỹ thuậttối ưu z Giảmsố bản ghi z Giảmkíchthướcbản ghi NW { Ví d ụ WAGON WAGON (NW, TYPE, COND, STATION, (NW, TYPE ) CAPACITY, WEIGHT) NT = 4002 TRAIN (NT, NW) TRAIN (NT, NW) Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 2
2. Nhập môn cơ sở dữ liệu Tối ưu dựa trên ngữ nghĩa { Mục đích: 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 z 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 = EMPLOYEE. Name SSN WORK-IN = PROJECT.PNO WORK-IN. NoProj = PNO PNO = ESSN=SSN PROJECT.PNO “Esprit” PROJET PName = “Esprit” EMPLOYEE. > EMPLOYE Birthday > “30/01/70 “30/01/70” Birthday Đồ thị kết nối các quan hệ Đồ thị kết nối các thuộc tính Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 4
3. Nhập môn cơ sở dữ liệu Tính chấtcủa phép toán ĐSQH (2) 3. Tính giao hoán và kết hợp của các ppphép toán ∗, ∩, ∪, −, x R X S => S X R R * S => S * R R ∩ S => S ∩ R R ∪ S => S ∪ R (R X S) X T => R X (S X T) (R ∩ S) ∩ T => R ∩ (S ∩ T) (R ∪ S) ∪ T => R ∪ (S ∪ T) (R * S) * T => R * (S * T) chỉ nếu C1 C2 C1 C2 Attr(C2) ⊆ Attr(S) U Attr(T) Tính chấtcủa phép toán ĐSQH (3) 4. Tính phân phối σ và Π trên các phép toán *, ∩, ∪, -, X Nếu C = (CR ^ CS) và nếu Attr(CR) ⊆ R và Attr(CS) ⊆ S thì : σ (R * S) => σ (R) * σ (S) C JC CR JC CS σ (R X S) => σ (R) X σ (S) C CR CS Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 6
4. Nhập môn cơ sở dữ liệu Bài tập Lựachọn cách truy nhập dữ liệu { Giả thiết TYPE z TRAIN : có chỉ số trên NT z WAGON : có chỉ số trên NW { Thực hiện phép kết NW nối z Lựa chọn 1 giải thuật. WAGON (NW, TYPE ) z Lựa chọn cách truy nhập các quan hệ NT = 4002 TRAIN (NT, NW) Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 8
5. Nhập môn cơ sở dữ liệu Thông tin về các quan hệ { Kích thước của các quan hệ và bản ghi Relation Cardinality Record size WAGON 200000 60 TRAIN 60000 30 TRAFFIC 80000 20 {Thông tin v ề các thuộc tính Attribute Cardinality Size min -max NW 200000 20 TYPE 200 5 COND 5 15 CAPACITY 400 15 5-45 NT 2000 10 DATE 800 6 {Thông tin về các chỉ số Relation Attributes Unique Type Num of pages WAGON NW Yes Principal 45 WAGON TYPE No SdSecondary 25 WAGON COND No Secondary 30 WAGON CAPACITY No Secondary 25 TRAIN NT No Principal 18 TRAFFIC NT No Principal 20 TRAFFIC DATE no Principal 40 Relation Cardinality Record size Num. of pages (num of rec./page) (NP’) WAGON 200000 60(100) 1500(375) TRAIN 60000 30 (200) 225(60) TRAFFIC 80000 20 (300) 200(60) Mô hình giá { Chí phí thực hiện câu hỏi phụ thuộc: z đọc/ghi bộ nhớ ng(goài (số trang nhớ) zKích thước dữ liệu phải xử lý {Chi phí truy nhập dữ liệu zĐọc ghi dữ liệu zxử lý zTruyền thônggg giữa các trạm làm việc CTA = σ * NBPAGES + τ ∗ NBNUPLETS (+ µ ∗ NBMESSAGES) {Trọng số {σ = trọng số đọc/ghi dữ liệu (ví dụ = 1) {τ = trọng số xử lý của CPU (ví dụ = 1/3) {µ = trọng số truyền dữ liệu Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 10