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

Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 1
Tối ưu hoá câu hỏi
Vũ Tuyết Trinh
trinhvt@it-hut.edu.vn
Bộ môn Các hệ thống thông tin, Khoa Công nghệ thông tin
Đại học Bách Khoa Hà Nội
Xử 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
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 2
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 ý: 
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ật tối ưu hoá
{ 2 kỹ thuật chính
Tối l i ( iti ) TYPEz ưu og c rewr ng
z Tối ưu vật lý (access methods)
{ Mục đích của các kỹ thuật tối ưu
z Giảm số bản ghi 
z Giảm kích thước bản ghi
Ví d
NW
{ ụ
WAGON (NW, TYPE, COND, STATION, 
CAPACITY, WEIGHT)
TRAIN (NT, NW)
WAGON 
(NW, TYPE...)
TRAIN
(NT, NW)
NT = 4002
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 3
Nội dung
9 Giới thiệu chung
{ Tối ưu logic
{ Tối ưu vật lý
{ Mô hình giá
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
z Biến đổi dựa trên ngữ nghĩa
z Biến đổi dựa trên tính chất của các phép toán ĐSQH 
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 4
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)
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
EMPLOYEE (Name, SSN, Birthday, Adrresse, NoDept)
DEPARTEMENT (DNO, DName, SSNManager)
PROJECT (PNO, PName, PLocation, DNo)
WORK-IN (ESSN, NoProj, Heures)
PROJET PName = “Esprit”
WORK-IN
ESSN=SSN
NoProj = PNO
Name WORK-IN.ESSN
EMPLOYEE.
SSN
PROJECT.PNO WORK-IN.
PNO
PROJECT.PNO “Esprit”
=
=
=
EMPLOYE Birthday > “30/01/70
Đồ thị kết nối các quan hệ
EMPLOYEE.
Birthday “30/01/70”
Đồ thị kết nối các thuộc tính
>
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 5
Tối ưu dựa trên ngữ nghĩa (2)
{ Loại bỏ các đồ thị con không liên kết trong đồ
ế ốthị k t n i các quan hệ
{ Kiểm tra mâu thuẫn trong đồ thị kết nối các
thuộc tính
Biế đổi â hỏi t đ{ n c u ương ương
Tính chất của phép toán ĐSQH 
A ~ tập các thuộc tính, C ~ biểu thức điều kiện
1. Phép chiếu và phép chọn
2. Tính giao hoán đối với phép chọn và chiếu
Π (R) => Π (Π (R) nếu A ⊆ A1A A A1
σ (R) => σ (σ (R)) nếu C = C1^C2
C C1 C2
σ (σ (R))
C1 C2
σ (σ (R))
C1C2
=>
σ (Π (R))
C1 A2
Π (σ (R))
C1A2=>
Π (σ (R))
A1 C2
σ (Π (R))
A1C2
=>
nếu các thuộc tính của C2 thuộc A1
Π (Π (R))
A1 A2
Π (R)
A1
=>
nếu A1 ⊆ A2
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 6
Tính chất của phép toán ĐSQH (2)
3. Tính giao hoán và kết hợp của các phé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)C1 C2 C1 C2 chỉ nếu Attr(C2) ⊆ Attr(S) U Attr(T)
Tính chất củ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
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 7
Biến đổi biểu thức ĐSQH
T1 R: F1 ∧ F2 ∧ ... Fn ((...(R:F1) : F2 ):...):Fn 
_________________________________________________________________ 
T2 (R[Y]) [Z] R[Z] nu Z ⊆ Y 
_________________________________________________________________ 
T3 (R[Y]) :F (X) (R :F(X)) [Y] nu X ⊆ Y 
 (R: F(X)) [Y] (R[X ∪ Y]) : F(X) ) [Y] nu X ⊄ Y 
_________________________________________________________________ 
T4 (R(X) x S(Y)) : F(Z) (R(X):F) x S(Y) nu Z ⊆ X 
(R(X) x S(Y)) : F(Z1)∧ F(Z2) (R(X):F(Z1)) x (S(Y): F(Z2)) 
 nu Z1 ⊆ X và Z2 ⊆ Y 
_________________________________________________________________ 
T5 (R ∪ S): F (R:F) ∪ (S:F) 
_________________________________________________________________ 
T6 (R - S): F (R:F) - S 
_________________________________________________________________ 
T7 (R(X) x S(Y))[Z] R[X ∩ Z] x S[Y ∩ Z] 
_________________________________________________________________ 
T8 (R ∪ S) [Z] (R[Z]) ∪ (S[Z]) 
_________________________________________________________________ 
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
{ Hoán vị phép chiếu với tích đề-các, hợp : T2, 
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
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 8
Bài tập
Lựa chọ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 
nối
NW
z Lựa chọn 1 giải thuật. 
z Lựa chọn cách truy 
nhập các quan hệ 
WAGON 
(NW, TYPE...)
TRAIN
(NT, NW)
NT = 4002
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 9
Relation S
Nested-loop-join (NLJ)
{ Nguyên tắc
z 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
z Tuple-based NLJ, block-
based NLJ, index-based NLJ Tuple R
Tuple R
Tuple S
Matching
SOURCE
S
SOURCE
R
Thực hiện như thế nào?
TYPE
NW
WAGON 
(NW, TYPE...)
TRAIN
(NT, NW)
NT = 4002
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 10
Thông tin về các quan hệ
{ Kích thước của các quan hệ và bản ghi
{Thông tin về các thuộc tính
Relation Cardinality Record size 
WAGON 200000 60 
TRAIN 60000 30 
TRAFFIC 80000 20 
{Thông tin về các chỉ số
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
Relation Attributes Unique Type Num of pages 
WAGON NW Yes Principal 45 
WAGON TYPE N S d 25 
o econ ary
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 rec./page) 
Num. of pages 
(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ớ ngoà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ông 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
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, 
khoa CNTT, ĐHBKHN 11
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:
z Chi phí cho liệt kê các phương án trả lời câu hỏi
z 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 
Kết luận
{ Tối ưu hoá nhằm tìm phương án tốt nhất để
th hiệ ột â hỏiực n m c u 
z Cần lưu ý: chí phí thực hiện tối ưu hoá và chi phí thực
hiện câu hỏi
{ Các kỹ thuật tối ưu
z Logic : kiểm tra điều kiện ràng buộc của các thuộc 
tính/quan hệ và điều kiện lựa chọn trong câu hỏi, biến 
đổi tương đương các biểu thức ĐSQH 
z Vật lý : tổ chức vật lý của dữ liệu trên đĩa, mô hình giá
¾ Không nhất thiết phải áp dụng tất cả các kỹ thuật trên 
khi thực hiện tối ưu hoá 1 câu hỏi