Download miễn phí Bài giảng Cơ sở dữ liệu - Kỹ thuật tối ưu hoá
Biến đổi dựa trên ngữ nghĩa
Mục đích:
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
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)
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Tối ưu hoá câu hỏiXử lý câu hỏi truy vấn
Câu lệnh
SQL
Phân tích
cú pháp
(parser)
Biểu thức
ĐSQH
Bộ tối ưu
(optimizer)
Biểu thức
ĐSQH
tối ưu
Bộ sinh mã
(code generator)
Chương trình
tối ưu
Tối ưu hoá
Biến đổi biểu thức ĐSQH để tìm 1 biểu thức
hiệu quả
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 ý:
Không nhất thiết phải tìm biểu thức tối ưu nhất
Chú ý tới tài nguyên sử dụng cho tối ưu
Kỹ thuật tối ưu hoá
2 kỹ thuật chính
Tối ưu logic (rewriting)
Tối ưu vật lý (access methods)
Mục đích của các kỹ thuật tối ưu
Giảm số bản ghi
Giảm kích thước bản ghi
Ví dụ
WAGON (NW, TYPE, COND, STATION,
CAPACITY, WEIGHT)
TRAIN (NT, NW)
WAGON
(NW, TYPE...)
TRAIN
(NT, NW)
NW
NT = 4002
TYPE
Nội dung
Giới thiệu chung
Tối ưu vật lý
Mô hình giá
Tối ưu logic
Lựa chọn cách truy nhập dữ liệu
Giả thiết
TRAIN : có chỉ số trên NT
WAGON : có chỉ số trên NW
Thực hiện phép kết nối
Lựa chọn 1 giải thuật.
Lựa chọn cách truy nhập các
quan hệ
WAGON
(NW, TYPE...)
TRAIN
(NT, NW)
NW
NT = 4002
TYPE
Relation S
Nested-loop-join (NLJ)
Nguyên tắc
Duyệt 1 lần trên quan hệ
ngoài R & lặp trên quan hệ
trong S
Các mở rộng của thuật toán
Tuple-based NLJ, block-
based NLJ, index-based NLJ
SOURCE
S
SOURCE
R
Tuple R
Tuple R
Tuple S
Matching
Mô hình giá
Chi phí thực hiện câu hỏi truy vấn phụ thuộc:
Đọc/ghi bộ nhớ ngoài (số trang nhớ)
Kích thước dữ liệu phải xử lý
Chi phí :
Đọc/ghi dữ liệu
Xử lý
Truyền thông giữa các trạm
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
Tối ưu hoá dựa trên mô hình giá
Mục đích: Chọn phương án thực hiện câu hỏi
với chi phí thấp nhất
Nhận xét:
Chi phí cho liệt kê các phương án trả lời câu hỏi
Chi phí cho lượng hoá các phương án theo mô hình
giá
Có thể sử dụng các « mẹo » (heuristics) để giảm
không gian tìm kiếm của câu hỏi
Đánh giá các biểu thức ĐSQH
Vật chất hóa:
Ghi các kết quả trung gian
Chi phí đánh giá câu hỏi: + thời gian đọc/ghi DL trung
gian
Đường ống (pipelining):
Tổ chức các phép toán trong 1 đường ống
Kết quả ra của phép toán này được lấy ngay làm đầu
vào cho phép toán kế tiếp
Không mất thời gian đọc/ghi DL trung gian
Không phải trường hợp nào cũng có thể thực hiện
được
Nội dung
Giới thiệu chung
Tối ưu vật lý
Mô hình giá
Tối ưu logic
Tối ưu hoá logic
Sử dụng các phép biến đổi tương đương để tìm
ra biểu thức ĐSQH tốt
Gồm 2 giai đoạn
Biến đổi dựa trên ngữ nghĩa
Biến đổi dựa trên tính chất của các phép toán ĐSQH
Biến đổi dựa trên ngữ nghĩa
Mục đích:
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
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)
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"
EMPLOYE Birthday > “30/01/70
PROJECT
PName = “Esprit”
WORK-IN
ESSN=SSN
NoProj = PNO
Result
Name
Đồ thị kết nối các quan hệ
WORK-IN.ESSN EMPLOYEE.
SSN
PROJECT.PNO WORK-IN.
PNO
PROJECT.PName “Esprit”
EMPLOYEE.
Birthday
“30/01/70”
Đồ thị kết nối các thuộc tính
=
=
=
>
EMPLOYEE (Name, SSN, Birthday, Adrresse, NoDept)
DEPARTEMENT (DNO, DName, SSNManager)
PROJECT (PNO, PName, PLocation, DNo)
WORK-IN (ESSN, NoProj, Heures)
Biến đổi dựa trên ngữ nghĩa ..
Định nghĩa khung nhìn: V = R * S
Câu truy vấn của client : Q = V * (T * U)
Viết lại câu truy vấn dựa trên định nghĩa khung
nhìn:
Q = (R * S) * (T * U)
Biến đổi dựa trên t/chất của ĐSQH
Tính chất của phép toán ĐSQH
A ~ tập các thuộc tính, F ~ biểu thức điều kiện
1. Phép chiếu và phép chọn
21^))(()(
21
FFFifRR
FFF
1))(()( 1 AAifRR AAA
Tính chất của phép toán ĐSQH (2)
A ~ tập các thuộc tính, F ~ biểu thức điều kiện
2. Tính giao hoán đối với phép chọn và chiếu
))(())((
))(())((
1221
1221
RR
RR
FAAF
FFFF
))(())(( 1221 RR AFFA
Nếu các thuộc tính của F2 thuộc A1 :
)())(( 121 RR AAA
Nếu A1 A2 :
Tính chất của phép toán ĐSQH (3)
3. Tính giao hoán và kết hợp của các phép toán
chỉ nếu
Attr(F2) Attr(S) U Attr(T)
)()(
)()(
)()(
**
TSRTSR
TSRTSR
TSRTSR
RSSR
RSSR
RSSR
RSSR
)()(
2121
TSRTSR
FFFF
Tính chất của phép toán ĐSQH (4)
4. Tính phân phối và trên các phép toán *, ,
, -, X
Nếu F = (FR ^ FS) và nếu Attr(FR) R và Attr(FS) S thì :
)()()( SRSR FS
JC
FR
JC
F
)()()( SRSR FSFRF
F ( S) F (R) F (S)
_________________________________________________________________
F (R - S) F (R) – F (S)
_________________________________________________________________
ΠZ ( R(X) x S(Y) ) Π X Z (R) x Π Y Z(S)
_________________________________________________________________
ΠZ (R S) ΠZ (R) ΠZ (S)
_________________________________________________________________
T1 F1 F2 ... Fn (R) F1( F2 ... ( Fn (R) ) )
_________________________________________________________________
T2 ΠZ (ΠY (R)) ΠZ (R) nếu Z Y
_________________________________________________________________
T3 F(X) (ΠY (R)) ΠY ( F(X) (R)) nếu X Y
T3’ ΠY ( F(X) (R)) ΠY ( F(X) (ΠX Y (R))) nếu X Y
_________________________________________________________________
T4 F(Z) (R(X) x S(Y)) F(Z) (R(X)) x S(Y) nếu Z X
F(Z1) F(Z2) (R(X) x S(Y)) F(Z1) (R(X)) x F(Z2) (S(Y))
nếu Z1 X và Z2 Y
_________________________________________________________________
T5 F (R S) F (R) F (S)
_________________________________________________________________
T6 F (R - S) F (R) – F (S)
_________________________________________________________________
T7 ΠZ ( R(X) x S(Y) ) Π X Z (R) x Π Y Z(S)
_________________________________________________________________
T8 ΠZ (R S) ΠZ (R) ΠZ (S)
_________________________________________________________________
Biến đổi biểu thức ĐSQH
Trình tự áp dụng
Khai triển phép lựa chọn dựa trên nhiều điều
kiện: T1
Hoán vị phép chọn với tích đề-các, hợp, trừ: T3,
T4, T5, T6 : đẩy phép chọn để có thể thực hiện
sớm nhất có thể
Hoán vị phép chiếu với tích đề-các, hợp : T2,
T3’,T7, T8
Nhóm các điều kiện chọn bởi T1 và áp dụng T2
để loại các phép chiếu dư thừa
Biểu diễn dạng cây của ĐSQH
))((
))*((
..21
21
SR
SR
BSBRFA
FA
A1
F2
R
S
R.B=S.B
x
Bài tập
EMPLOYEE (FirstName, LastName, SSN, Birthday,
Adrresse, NoDept)
DEPARTEMENT (DNO, DName, SSNManager)
PROJECT (PNO, PName, PLocation, DNo)
WORK (ESSN, PNO, 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"
PROJECT
WORKEMPLOYEE
ESSNWorkSSNEmployee
EspritPNameBirthday
LastNameFirstName
*
)(
..
'''70/01/30'
...