Giáo trình cơ sở dữ liệu - Chương 8: Tối ưu truy vấn - ĐH Khoa học tự nhiên HCM

Chương 8 Tối ưu truy vấn Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 2 Nội dung chi tiết  Giới thiệu  Nguyên tắc tối ưu  Các qui tắc chuyển đổi  Biểu thức tương đương  Ví dụ Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 3 Giới thiệu  Tối ưu truy vấn - Là biến đổi câu hỏi này sang câu hỏi khác (nhưng có cùng kết quả) nhằm giảm thiểu thời gian tính toán  Quan tâm - Cách cài đặt câu hỏi • Giải thuật – độ phức tạp • Không gian lưu trữ – ít /nhiều • Thời gian xử lý – nhanh/chậm Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 4 Giới thiệu (tt)  Giả sử - Xử lý 1000 records mất 1 giây - Xử lý 4.000.000 records mất 4.000 giây  Khó chấp nhận khi phải chờ đợi kết quả truy vấn  Xử lý thông tin - Ưu tiên tối ưu hóa thời gian hơn tối ưu hóa lưu trữ • Bỏ qua dạng chuẩn để đạt tốc độ xử lý nhanh hơn • Dung lượng HDD ngày càng nhiều, nhưng có khả năng thiếu không gian tính toán  Phép tích Cartesian hay phép kết Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 5 Nguyên tắc tối ưu  Ví dụ - R(A, B) có u bộ - S(C, D) có v bộ - Cho biết giá trị của A sao cho B=C và D=50 A( (B=C)  (D=50) (R  S)) A( B=C (R  D=50(S))) A(R B=C (D=50(S)) Biến đổi tương đương Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 6 Nguyên tắc tối ưu (tt)  Chiến lược (J. D. Ullman) - Thực hiện phép chọn/chiếu càng sớm càng tốt • Giảm bớt kích thước của kết quả trung gian • Giảm chi phí truy cập bộ nhớ phụ và chi phí lưu trữ của bộ nhớ chính Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 7 Qui tắc chuyển đổi  (1) Giao hoán - E1 E2 = E2 E1 - E1  E2 = E2  E1  (2) Kết hợp - (E1 E2) E3 = E1 (E2 E3) - (E1  E2)  E3 = E1  (E2  E3) Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 8 Qui tắc chuyển đổi (tt)  (3) Dãy các phép chiếu -  (4) Dãy các phép chọn -  (5) Chọn và chiếu - X = tập thuộc tính con của R - Z = tập thuộc tính con của R xuất hiện trong điều kiện p A1, A2, , An(A1, A2, , Am(R)) = A1, A2, , An (R) , với n  m  p1 ( p2 (R)) =  p2 ( p1 (R)) =  p1  p2 (R) X [p (R)] = {p [X (R)]} X XZ Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 9 Qui tắc chuyển đổi (tt)  (6) Chọn và tích Cartesian -  (7) Chọn và hội -  (8) Chọn và trừ - C(R)  S = C(R  S) C(R  S) = C(R) C(S) C(R  S) = C(R) C(S) Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 10 Qui tắc chuyển đổi (tt)  (9) Chiếu và tích Cartesian -  (10) Chiếu và hội - A1, A2, , An (R  S) = A1, A2, , Ak (R)  Ak+1, , An (S) A1, A2, , An (R  S) = A1, A2, , An (R)  A1, A2, , An (S) Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 11 Biểu thức tương đương  (1) Kết tự nhiên  Tích cartesian, chọn và chiếu  (2) Kết the-ta  Tích cartesian, chọn  (3) Phép giao  Phần bù của hội 2 phần bù R(A,B) S(B,C) = A,B,C(R.B=S.B(R  S)) R C S = C(R  S) R  S = RS  ((RS)  (SR)) Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 12 Biểu thức tương đương (tt)  (4) Phần bù  (5) Phép chia Q(A1,A2,...,An) = (A1(Q)A2(Q)An(Q)  Q(A1,A2,...,An)) R(A,B)  S(A) = B(R)  B(((B(R)  A(S))  R )) Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 13 Tối ưu truy vấn  Input/Output - Cây truy vấn ĐSQH/Cây truy vấn tối ưu  Bước 1 - Áp dụng 5 biểu thức tương đương  Bước 2 - Dùng qui tắc 4 tách phép chọn thành các phép chọn con  Bước 3 - Với mỗi phép chọn, áp dụng các qui tắc 5, 6, 7, và 8 để đưa phép chọn xuống càng sâu càng tốt Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 14 Tối ưu truy vấn (tt)  Bước 4 - Với mỗi phép chiếu, áp dụng các qui tắc 3, 9 và 10 để đưa phép chiếu xuống càng sâu càng tốt  Bước 5 - Tập trung các phép chọn (qui tắc 4) - Loại bỏ các phép chiếu vô ích (qui tắc 3) Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 15 Ví dụ  Customer(cusID, cusNm, cusStreet, cusCity)  Account(accID, cusID, balance) cusNm Customer.cusID=Account.cusID  balance=100 Customer Account x Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 16 Ví dụ (tt) cusNm balance=100 Customer Account x Customer.cusID=Account.cusID Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 17 Ví dụ (tt) cusNm balance=100 Customer Account Customer.cusID=Account.cusID Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 18 Ví dụ (tt) cusNm balance=100Customer Account Customer.cusID=Account.cusID Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 19 Ví dụ (tt) cusNm balance=100Customer Account Customer.cusID=Account.cusID cusNm, cusID cusID Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 20 Bài tập  SÁCH (Tên-sách, Tác-giả, Nhà-XB, Mã-sách)  NHÀ-XUẤT-BẢN (Nhà-XB, Địa-chỉ, Thành-phố)  ĐỘC-GIẢ (Tên-ĐG, ĐChỉ-ĐG, TPhố-ĐG, Số-thẻ)  MƯỢN-SÁCH (Số-thẻ, Mã-sách, Ngày-mượn)  Cho biết các sách của nhà xuất bản ABC được mượn trên 2 lần bởi độc giả X Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 21