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
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)
21 trang |
Chia sẻ: thucuc2301 | Lượt xem: 688 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trê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 = RS ((RS) (SR))
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
Các file đính kèm theo tài liệu này:
- chap08_toi_uu_truy_van_7634_2020099.pdf