Bài giảng Cơ sở dữ liệu phân tán - Chương 3: Tối ưu hóa câu hỏi phân tán

Ng 
Duc
 Thu
an
CƠ SỞ DỮ LIỆU PHÂN TÁN
(Distributed database)
ThS. Ng ĐứcThuần
BM Hệ Thống Thông Tin
ĐẠI HỌC THỦY SẢN
KHOA CÔNG NGHỆ THÔNG TIN
Mùa Xuân 2006
Ng 
Duc
 Thu
an
Chương III: TỐI ƯU HÓA CÂU HỎI 
PHÂN TÁN
SJF, ><l
q
Nữa kết nối
theta
SLF , δFChọn
NSJ, ><lNữa kết nối
tự nhiên
PJ [X], Π [X]Chiếu
NJN, l><lKết nối tự
nhiên
DF, \Trừ
JNF, l><l
q
Kết nối thetaIN, ∩Giao
PR, xTích 
Descartes
UN, UHợp
Ký hiệuPhép toánKý hiệuPhép toán
Ng 
Duc
 Thu
an
Nhắc lại các phép biến đổi tương đương
l 1. Giao hoán: JN, PR, NJN
l 2. Kết hợp: JN, PR, NJN : (R JN S) JN T = R JN ( S JN T)
l 3. Dãy các phép chiếu: PJ [X] (PJ [Y] (R)) = PJ [X] (R) , nếu X Ì Y
l 4. Dãy các phép chọn: SL F1 (SL F2 (R)) = SL F1 L F2 (R)
l 5. Giao hoán giữa phép chọn và phép chiếu
SLF(PJ [x] (R)) = PJ [x] (SLF(R)),
nếu F chỉ liên quan đến các thuộc tính trong X
Ng 
Duc
 Thu
an
Nhắc lại các phép biến đổi tương đương
l 6. Giao hoán giữa phép chọn và phép tích Descartes
SLF (R1[X] PR R2[Y] ) = 
6.1 SLF (R1) PR R2 , nếu F chỉ liên quan đến R1
6.2 R1 PR SLF (R2) , nếu F chỉ liên quan đến R2
6.3 SLF1 (R1) PR SLF2 (R2) , nếu F = F1 L F2
F1 chỉ liên quan đến X, F2 chỉ liên quan đến Y
6.4 SLF2 (SLF1 (R1) PR (R2) , nếu F = F1[X] L F2[XY] 
Ng 
Duc
 Thu
an
Nhắc lại các phép biến đổi tương đương
l 7. Phân phối phép chọn và phép hợp
SLF(R1 UN R2) = SLF(R1) UN SLF (R2)
l 8. Phân phối phép chọn và phép trừ
SLF(R1 DF R2) = SLF(R1) DF SLF (R2)
l 9. Phân phối phép chiếu với phép tích Descartes
PJX(R1[Y] PR R2[z]) = PJFÇY(R1) PR PJF ÇZ (R2)
l 10. Phân phối phép chiếu với phép hợp
PJX(R1[Y] UN R2[z]) = PJFÇY(R1) UN PJF ÇZ (R2)
Nếu X Ì YZ
Ng 
Duc
 Thu
an
Cây toán tử câu hỏi tổng thể
l Giả sử có 2 quan hệ:
NHANCONG(E# , TEN, LUONG, THUE, D#)
PHONG(D#, TENPHG, MIEN)
Hãy đưa ra danh sách các nhân công làm việc ở MIEN=‘Bac’
PJTEN SL MIEN =‘Bac’ (NHANCONG NJN PHONG)
Ng 
Duc
 Thu
an
Cây toán tử câu hỏi tổng thể
l Cây toán tử câu hỏi
PJ TEN
SL MIEN=‘Bac’
NJN
NHANCONG PHONG
Ng 
Duc
 Thu
an
Cây toán tử câu hỏi tổng thể
l Tối ưu hóa theoa các qui tắc trên (6.1)
PJ TEN
NJN
NHANCONG SL MIEN=‘Bac’
PHONG
Ng 
Duc
 Thu
an
Dịch cây tổng thể “tối ưu” sang cây đoạn
l Với phân đoạn
PHONG
PHONG1 PHONG2 PHONG3
D# <10
10<=D# <=20
D# >20
Ng 
Duc
 Thu
an
Dịch cây tổng thể “tối ưu” sang cây đoạn
l Cây đoạn tương ứng
NHANCONG
NHCNG4
NHCG1 NHCG2 NHCG3 
Với
PHONG = PHONG1 UN PHONG2 UN PHONG3
NHANCONG = (NHCG1 UN NHCG2 UN NHCG3) NJN NHCG4
E#, LUONG, THUEE#, TEN, D#
D# 20
Ng 
Duc
 Thu
an
Cây tổng thể được vẽ lại như sau
PJTEN
NJN
NJN SL MIEN =‘Bac’
UN NHCG4 UN
NHCG1 NHCG2 NGCG3 PHONG1 PHONG2 PHONG3
Ng 
Duc
 Thu
an
Hoán đổi phép chọn và phép hợp ta có cây tổng thể
UN
SL MIEN =‘Bac’SL MIEN =‘Bac’ SL MIEN =‘Bac’
PHONG1
(D# < 10)
PHONG2
(10<= D# <= 20)
PHONG3
(D# > 20)
Ng 
Duc
 Thu
an
Đại số quan hệ định tính
l Quan hệ định tính là cặp [ R:qR ]
– R : là quan hệ
– qR : tiêu chuẩn của quan hệ định tính (các bộ của R phải 
thỏa qR)
l Các phép toán của đại số quan hệ định tính
- Chọn: SLF [R:qR] = [SLFR: qR L F]
- Kết nối: [R:qR] JNF [S:qs] = [R JNF S:qR LqS L F ] 
- Tích Descaster: [R:qR] PR [S:qs] = [R PR S:qR LqS] 
Ng 
Duc
 Thu
an
Đại số quan hệ định tính
l Chiếu : PJX [R:qR] = [PJXR: qR]
l Hợp : [R:qR] UN [S:qs] = [R UN S:qR ν qS] 
l Hiệu : [R:qR] DF [S:qs] = [R DF S:qR] 
l Giao: [R:qR] IN [S:qs] = [R IN S:qR LqS] 
l Biểu diễn lại cây tổng thể sử dụng quan hệ định 
tính
Ng 
Duc
 Thu
an
PJTEN
NJN
UN NHCG4
[NHCG1 NJN (SL MIEN =‘Bac’ PHONG1) : D#<10 L MIEN =‘Bac’
Cây tổng thể
NHCG2 NJN (SL MIEN= ‘Bac’ PHONG2) : D# >=10 L D#<=20 L MIEN =‘Bac’
NHCG3 NJN (SL MIEN= ‘Bac’ PHONG3) : D# >20 L MIEN =‘Bac’
(E#, LUONG, THUE)
Ng 
Duc
 Thu
an
Đánh giá câu hỏi phân tán
l Một số thông tin định lượng
– Số các bộ của R : Card(R)
– KÍch thước của 1 thuộc tính A : Size(A)
– Size (R) = ∑ size(A) = card (R) * length(R)
– Trạm mà Ri định vị : site (Ri)
A єR
Ng 
Duc
 Thu
an
Đánh giá các phép toán ĐSQH
l Phépchọn: 
– card (SLF(R)) = card (R) * SFS(F)
– Trong đó : SFS(F) đuợc tính bởi (Selinger et al., 1979)
l SFS(A = value) = 1/ (card (PRA (R))
l SFS(A >value) = (max(A) – value)/ (max(A) – min(A))
l SFS(A <value) = ( value – min(A))/ (max(A) – min(A))
l SFS( p(Ai) L p(Aj)) = SFS(p(Ai)) * SFS(p(Aj)) 
l SFS( p(Ai) v p(Aj)) = SFS(p(Ai)) + SFS(p(Aj)) - SFS(p(Ai)) * SFS(p(Aj))
l SFS(A є {value}) = SFS(A = value) *card({value} )
Ng 
Duc
 Thu
an
Đánh giá các phép toán ĐSQH
l Phép chiếu: 
– Card(PR [x] (R)) = card (R)), nếu x chứa 1 khóa của R
– Card(PR [x] (R)) = MAX(dom (A[R])), với Aє X
l Tích Descartes: 
– Card (RxS) =card (R)* card(S) 
l Phép kết nối:
– Card(R JNF S) = card(S),
nếu F= (A=B) , A là khóa chính của R, B là khóa ngoại của S
– Card(R NJN S) = SFJ * card(R)*card(S),
Ng 
Duc
 Thu
an
Đánh giá các phép toán ĐSQH
l Phép nữa kết nối: (Hevner and Yao, 79)
– Card(R SJA=B S) = Card(R)*SFSJ(R SJA=B S)
l SFSJ(R SJA=B S) = card(PJA(S)) / card(dom(A))
l Phép hợp:
– Card (R UN S) <= Card(R) + Card(S)
– Card (R UN S) >= Max( Card(R), Card(S))
l Phép trừ: 
-Card(R-S) <= card (R)
-Card(R-S) >= 0
Ng 
Duc
 Thu
an
ĐÁNH GIÁ CHI PHÍ CHO CÂU HỎI PHÂN TÁN
l Tối ưu hóa câu hỏi phân tán còn phụ thuộc chi phí truy vấn 
(thời gian, giá, băng thông,..)
l Ví dụ:
Cần kết quả : R JN A=B S
Nếu dịch chuyển toàn bộ R từ site 1 đến site 2:
Chi phí : C0 +C1*size(R)*card(R)
C0: Chi phí cho 1 phiên liên lạc
C1: Chi phí truyền tin theo dung lượng
SR
Site 2Site 1
Ng 
Duc
 Thu
an
ĐÁNH GIÁ CHI PHÍ CHO CÂU HỎI PHÂN TÁN
l Nếu sử dụng phép biến đổi
R JN A=B S = (R SJ A=B PJB(S)) JN A=B S
Truyền PJB(S) từ site 2 về site1 có giá :
C0 + C1*size(B)*dom(B[S])
TínhR’=(R SJ A=B PJB(S) tại site1: giá = 0 (không tính giá tại trạm)
Truyền R’ từ site 1 về site 2 giá:
C0 + C1*size(R’)*card(R’)
Tính R’ JN A=B S tại site 2 : giá =0
Tổng chi phí : C0 + C1*size(B)*dom(B[S]) +C0 + 
C1*size(B)*dom(B[S])
Ng 
Duc
 Thu
an
ĐÁNH GIÁ CHI PHÍ CHO CÂU HỎI PHÂN TÁN
l Chi phí câu hỏi truy vấn phụ thuộc ?
Sử dụng công thức phân rã
Giá
Có nhiều công trình nghiên cứu đưa ra các giải thuật 
nhằm tối ưu chi phí:
R*(Selinger& Adiba-80, Lohman et al -85), 
SDD-1(Bernstein-81), 
AHY (Apers-Hevner-Yao-83)
Ng 
Duc
 Thu
an
TÀI LIỆU THAM KHẢO
l M.Tamer Ozsu, Patrick Valdariez –Prentice-
Hall-1998
l Bài giảng TS. Trần Đình Khang – BKHN
Ng 
Duc
 Thu
an
TÌM HIỂU 
l Các thuật toán:
R*(Selinger& Adiba-80, Lohman et al -85), 
SDD-1(Bernstein-81), 
AHY (Apers-Hevner-Yao-83)