Bài giảng Nhập môn cơ sở dữ liệu - Bài 6: Tối ưu hoá câu hỏi - Vũ Tuyết Trinh
Tối ưu hoá câu hỏi
Vũ Tuyết Trinh
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
Biểu thức
ĐSQH
tối ưu
Bộ tối ưu
(optimizer)
Bộ sinh mã
(code generator)
Chương trình
tối ưu
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
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ớ, ...
{ ư
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
TYPE
z ốư
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
NW
{ Ví dụ
WAGON
(NW, TYPE...)
WAGON (NW, TYPE, COND, STATION,
CAPACITY, WEIGHT)
TRAIN (NT, NW)
NT
=
4002
TRAIN
(NT, NW)
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
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 ếđổựấủĐ
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
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)
EMPLOYEE (Name, SSN, Birthday, Adrresse, NoDept)
DEPARTEMENT (DNO, DName, SSNManager)
PROJECT (PNO, PName, PLocation, DNo)
WORK-IN (ESSN, NoProj, 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"
=
S
Name
=
=
P
NoProj = PNO
ESSN=SSN
PName = “Esprit”
>
B
Birthday > “30/01/70
Đồ thị kết nối các quan hệ
Đồ thị kết nối các thuộc tính
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
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
{ ến đổỏươ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
Π (R) => Π (Π (R) nếu A ⊆ A1
A
A A1
σ
(R) => σ (σ (R)) nếu C = C1^C2
C
C1 C2
2. Tính giao hoán đối với phép chọn và chiếu
nếu các thuộc tính của C2 thuộc A1
σ
(σ (R))
σ
(σ (R))
C2 C1
=>
Π
(σ (R))
σ
(Π (R))
=>
C1 C2
(Π (R))
A1 C2
C2 A1
σ
Π
(σ (R))
=>
Π
(Π (R))
Π
(R)
C1 A2
A2 C1
=>
A1 A2
A1
nếu A1 ⊆ A2
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
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 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 *, ∩,
∪
Nếu C = (CR ^ CS) và nếu Attr(CR) ⊆ R và Attr(CS) ⊆ S thì :
σ
(R * S) => σ (R) *
σ
(S)
JC
JC
C
CR
CS
(S)
σ
(R X S) => σ
(R) X
σ
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
Biến đổi biểu thức ĐSQH
T1
_________________________________________________________________
T2 (R[Y]) [Z] R[Z] n u Z ⊆ Y
_________________________________________________________________
R: F1 ∧ F2 ∧ ... Fn
((...(R:F1) : F2 ):...):Fn
T3
(R[Y]) :F (X)
(R :F(X)) [Y] n u X ⊆ Y
(R: F(X)) [Y]
(R[X ∪ Y]) : F(X) ) [Y] n u X ⊄ Y
_________________________________________________________________
T4 (R(X) x S(Y)) : F(Z) (R(X):F) x S(Y) n u Z ⊆ X
(R(X) x S(Y)) : F(Z1)∧ F(Z2) (R(X):F(Z1)) x (S(Y): F(Z2))
n u Z1 ⊆ X và Z2 ⊆ Y
_________________________________________________________________
T5
_________________________________________________________________
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])
(R ∪ S): F
(R:F) ∪ (S:F)
_________________________________________________________________
Trình tự áp dụng
{ Khai triển phép lựa chọn dựa trên nhiều điều
ệ
{ 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
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
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
NW
nối
z Lựa chọn 1 giải thuật.
WAGON
(NW, TYPE...)
z Lựa chọn cách truy
NT
=
4002
nhập các quan hệ
TRAIN
(NT, NW)
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
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
Matching
Tuple R
{ Các mở rộng của thuật toán
z Tuple-based NLJ, block-
based NLJ, index-based NLJ
Tuple R
Tuple S
SOURCE
R
SOURCE
S
Thực hiện như thế nào?
TYPE
NW
=
WAGON
(NW, TYPE...)
NT
4002
TRAIN
(NT, NW)
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
Thông tin về các quan hệ
{ Kích thước của các quan hệ và bản ghi
Relation
WAGON
TRAIN
Cardinality
200000
Record size
60
30
20
60000
TRAFFIC
80000
{ề ộ
Attribute
NW
Cardinality
200000
200
Size
20
5
min -max
TYPE
COND
CAPACITY
NT
5
400
2000
800
15
15
10
6
5-45
DATE
{Thông tin về các chỉ số
Relation
WAGON
WAGON
WAGON
WAGON
TRAIN
TRAFFIC
TRAFFIC
Relation
Attributes
NW
TYPE
COND
CAPACITY
NT
NT
DATE
Cardinality
Unique
Yes
No
No
No
No
No
no
Type
Num of pages
Principal
Secondary
Secondary
Secondary
Principal
Principal
Principal
45
25
30
25
18
20
40
Record size
(num of rec./page)
Num. of pages
(NP’)
WAGON
TRAIN
TRAFFIC
200000
60000
80000
60(100)
30 (200)
20 (300)
1500(375)
225(60)
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ý
zề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
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
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 để
ựện mộỏ
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
ũ Tuyết Trinh, b/m Các hệ thống thông tin,
11 trang
21120
Free
Bạn đang xem tài liệu "Bài giảng Nhập môn cơ sở dữ liệu - Bài 6: Tối ưu hoá câu hỏi - Vũ Tuyết Trinh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_nhap_mon_co_so_du_lieu_bai_6_toi_uu_hoa_cau_hoi_vu.pdf
