Bài giảng môn học Cơ sở dữ liệu - Chương 8: Tối ưu truy vấn

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