Bài 4:
TỐI ƯU TRUY VẤN
TRÊN HỆ CƠ SỞDỮLIỆU PHÂN TÁN
Khoa Hệthống thông tin
Trường Đại học Công nghệ thông tin, ĐHQG-HCM
2
NỘI DUNG
MỞ ĐẦU
I. TỔNG QUAN VỀXỬLÝ TRUY VẤN PHÂN TÁN
1. Bài toán xửlý truy vấn phân tán
2. Mục tiêu củatốiưutruyvấn phân tán
3. Độ phứctạpcủa các phép toán đạisốquan hệ
4. Các vấnđề củatốiưutruyvấn phân tán
5. Các tầng xửlý truy vấn phân tán
II. XỬLÝ TRUY VẤN PHÂN TÁN
1. Phân rã truy vấn
2. Cụcbộhoá dữliệuphântánIII.
III.TỐI ƯU TRUY VẤN PHÂN TÁN
1. Tốiưu hoá truy vấn
2. Các thuậttoántốiưu hoá truy vấn phân tán
KẾT LUẬN
3
MỞ ĐẦU
•Vấnđề tốiưuhoátrênhệCSDL phân tán là rất quan trọng do tính
phân mảnh, nhân bản, tốn kém chi phí cho việctruyềndữliệu.
•Thuậttoántốiưutruyvấnphântáncổđiểnlàvétcạnvàleođồi:
–Thuậttoánvétcạn không phù hợpvớisựbùng nổdữliệu.
–Thuậttoánleođồichỉtìm kiếmđượctốiưucụcbộ.
•Để khắcphục, các giảithuậttìmkiếmngẫu nhiên và Heuristic được
đề xuấtcóthểtìm ra các giảiphápgầntốiưuchấpnhậnđược.
4
I. TỔNG QUAN VỀXỬLÝ TRUY VẤN PHÂN TÁN
Xét mộtCSDL mẫumôhìnhhoáchomột công ty máy tính.
Các thuộctínhcủaCSDL baogồm:
ENO: mã sốnhân viên
ENAME: tên nhân viên
TITLE: chứcvụtrong công ty
SALE: mứclương
RESP: nhiệmvụtrong dựán
DUR: thờigianđược phân công trong dựán
PNO: mã sốdựán
PNAME: tên dựán
BUDGET: ngân sách dựán
BÀI TOÁN XỬLÝ TRUY VẤN PHÂN TÁN
5
CÁC QUAN HỆ ĐÃ CHUẨN HOÁ
EMP ASG
ENO ENAME TITLE ENO PNO RESP DUR
E1
E2
E3
E4
E5
E6
E7
E8
J. Doe
M. Smith
A. Lee
J. Miller
B. Casey
L. Chu
R. David
J. Jones
Elect. Eng.
Syst. Anal.
Mech. Eng.
Programmer
Syst. Anal.
Elect. Eng.
Mech. Eng.
Syst. Anal.
E1
E2
E2
E3
E3
E4
E5
E6
E7
E8
P1
P1
P2
P3
P4
P2
P2
P4
P3
P3
Manager
Analyst
Analyst
Consultant
Engineer
Programmer
Manager
Manager
Engineer
Manager
12
24
6
10
48
18
24
48
36
40
PROJ PAY
PNO PNAME BUDGET TITLE SAL
P1
P2
P3
P4
Instrumentation
Database Develop
CAD/CAM
Maintenance
150000
135000
250000
310000
Elect. Eng.
Syst. Anal.
Mech. Eng.
Programmer
40000
34000
27000
24000