ƯƠCH NG 3 ƯƠ CH NG 3 THI T K CSDL PHÂN TÁN Ế THI T K CSDL PHÂN TÁN Ế
Ế Ế
Nguyễn Mậu Hân Nguyễn Mậu Hân
Khoa CNTTĐHKH HUẾ Khoa CNTTĐHKH HUẾ
CH NG 3: THI T K CSDL PHÂN TÁN ƯƠ Ế Ế
Ộ
ỘN I DUNG N I DUNG
3.1 N i dung thi t k các h th ng phân tán ộ ế ế ệ ố
3.2 Các chi n l c phân tán d li u ế ượ ữ ệ
3.3 Ph ng pháp thi t k CSDL phân tán ươ ế ế
3.4 Phân m nh d li u ả ữ ệ
3.5 C p phát tài nguyên trong h phân tán ệ ấ
i l p trình ng d ng các
Ụ ườ ậ
ụ
ph
ỤM C ĐÍCH M C ĐÍCH ứ t k m t c s d li u phân tán
2
Cung c p cho ng ấ ng pháp thi ươ ế ế ộ ơ ở ữ ệ
CH NG 3: THI T K CSDL PHÂN TÁN ƯƠ Ế Ế
c khi thi c Yêu c uầ : • Ph i qua b ả ướ
c phân tích tr ướ này ph i đ c l p v i m i gi ớ
ọ • Ch n nh ng v trí đ cài đ t d li u và các ch ng ả ộ ậ ị t k . Các b ướ ế ế i pháp cài đ t ặ ả ặ ữ ệ ữ ể ọ ươ
trình trên m ng máy tính. ạ
• Đ i v i DBMS phân tán, vi c phân tán các ng d ng ứ ụ ệ
ố ớ ỏ ề
đòi h i hai đi u: 1. Phân tán DBMS 2. Phân tán các ch ươ ng trình ng d ng ch y trên ụ ứ ạ
3
DBMS đó.
3.1 N i dung thi t k m t h th ng phân tán ộ ế ế ộ ệ ố
t k h th ng : Nh n xét ậ • Có nhi u đi m t ề ể ươ ng đ ng v i vi c thi ớ ệ ồ ế ế ệ ố
t p trung. ậ
• Đi u khác nhau c b n là h th ng đ c phân b trên ệ ố ơ ả ượ ố
m t s đ a đi m khác nhau ể
ẳ ở ố
ề ộ ố ị ả ế ế • Tính kh thi, chu kỳ s ng, tính m , tính s n sàng,... • Thi t k ph n c ng: máy tr m, máy ch , m ng ,... ạ ủ ứ ầ ạ
4
C th ? ụ ể
5
3.1 N i dung thi t k m t h th ng phân tán ộ ế ế ộ ệ ố
3.1.1 Các công vi c c n ph i làm đ thi t k HT phân ể ệ ầ ả ế ế
tán:
• Xác đ nh ki n trúc mô hình phân tán t ng th ể ế ổ ị
ng c n phân tán, lo i hình phân tán • Đ nh v các đ a ph ị ị ị ươ ầ ạ
ng (toàn b , b n sao, lai,...). s d ng cho m i đ a ph ử ụ ỗ ị ươ ộ ả
• Ti n hành cân đ i các y u t đ c phân tán bao g m các ế ố ượ ế ố ồ
ph n t d li u và các ho t đ ng x lý trên m i tr m. ầ ử ữ ệ ạ ộ ỗ ạ ử
6
• Thi t k c s d li u phân tán. ế ế ơ ở ữ ệ
• Thi t k các ch ế ế ươ ng trình ng d ng. ứ ụ
3.1 N i dung thi t k m t h th ng phân tán ộ ế ế ộ ệ ố
3.1.2 Các s n ph m yêu c u sau khi phân tích thi ẩ ầ ả t k ế ế
1. Mô t các tr m ả ạ
. Thông tin đ a lý ị
. Thi t b v t lý ế ị ậ
. Thông tin h t ng ạ ầ
. Đ c tr ng v con ng i (trình đ , k năng,,...) ư ề ặ ườ ộ ỹ
2. Mô t ả ề ử ụ v s d ng d li u cho m i tr m ữ ệ ỗ ạ
. Các ph n t d li u s d ng t h th ng ầ ử ữ ệ ử ụ ừ ệ ố
. Các ph n t d li u c n ph i t o ra ầ ử ữ ệ ả ạ ầ
. Các ph n t ầ ử ữ ệ d li u c p nh t ậ ậ
7
. Các ph n t d li u xóa ầ ử ữ ệ
3.1 N i dung thi t k m t h th ng phân tán ộ ế ế ộ ệ ố
3.1.2 Các s n ph m yêu c u sau khi phân tích thi t k (ti p) ẩ ầ ả ế ế ế
3. Mô t quá trình nghi p v cho m i tr m ả ỗ ạ ụ ệ
. Danh sách các x lý (s đ ch c năng) các tr m ơ ồ ứ ử ở ạ
. Mô t các x lý ả ử
4. Các th a thu n v ph
ỏ
ề
ậ
ươ
ỗ ạ ng án ki n trúc h th ng cho m i tr m, ệ ố
ế
cho nhu c u v d li u và x lý c a tr m đó
ề ữ ệ
ủ
ử
ầ
ạ
. Có c n hay không v các tr giúp không ph i k thu t ả ỹ ề ầ ậ ợ
. Có c n hay không v h th ng đ a ph ề ệ ố ầ ị ươ ng, v n i m ng ề ố ạ
8
. Có c n hay không v các c u hình phân tán khác ề ầ ấ
3.2 Các chi n l c phân tán d li u ế ượ ữ ệ
3.2 Các chi n l ế ượ ữ ệ c phân tán d li u
• Vi c đ nh v và phân tán d li u các nút trong m t ữ ệ ở ệ ị ị ộ
m ng máy tính s quy t đ nh tính hi u qu và đúng ế ị ẽ ệ ả ạ
đ n c a h th ng phân tán. ệ ố ủ ắ
• Có 4 chi n l c phân tán d li u c b n: ơ ả ữ ệ
ế ượ T p trung d li u ậ
ữ ệ Chia nh d li u
ỏ ữ ệ Sao l p d li u ặ ữ ệ
9
Ph ươ ng th c lai ứ
3.2 Các chi n l c phân tán d li u ế ượ ữ ệ
3.2.1 T p trung d li u: T t c các d li u đ c t p trung m t ch . Cách này ữ ệ ữ ệ ộ ổ
ượ ượ ậ c đi m: ể
đ n gi n nh ng có 3 nh ư ơ • D li u không s n sàng cho ng i s d ng truy nh p ẵ ườ ử ụ ậ
t ậ ấ ả ả ữ ệ xaừ
ng làm c c đ i vi c truy ệ ườ ự ạ
• Chi phí truy n thông l n, th ề nh p d li u t ậ
ơ ở ữ ệ ị ự ố
c chia thành các ph n nh liên k t ớ i n i t p trung. ữ ệ ớ ơ ậ • Toàn b h th ng ng ng khi c s d li u b s c ừ ộ ệ ố 3.2.2 Chia nh d li u: • C s d li u đ ơ ở ữ ệ ỏ ữ ệ ượ ầ ỏ ế
10
c đ a đ n các tr m m t cách nhau (không trùng l p). ặ ượ ỗ ư ế ạ ộ
thích h p đ s d ng. • M i ph n d li u đ ầ ợ ữ ệ ể ử ụ
3.2 Các chi n l c phân tán d li u ế ượ ữ ệ
3.2.3 Sao l p d li u ặ ữ ệ :
• CSDL đ c nhân thành nhi u b n ượ ả t ng ph n ầ ho c ặ đ y ầ ừ ề
c đ t nhi u tr m trên m ng. đủ và đ ượ ặ ở ề ạ ạ
• N u b n sao c a CSDL đ c l u gi ủ ế ả ượ ư t ữ ạ i m i tr m c a h ệ ọ ạ ủ
th ng ta có tr ng h p ố ườ ợ sao l p đ y đ ặ ầ ủ.
• Hi n nay có nhi u k thu t m i cho phép t o b n sao ậ ề ệ ả ạ ớ ỹ
m i tr m và không đ y đ phù h p v i yêu c u d li u ợ ữ ệ ở ỗ ạ ủ ầ ầ ớ
m t b n đ y đ đ server. ộ ả ủ ượ ầ c qu n lý ả ở
• Sau m t kho ng th i gian nh t đ nh các b n sao đ c ấ ả ả ờ ộ ị ượ
11
làm đ ng b v i b n chính b ng m t ng d ng nào đó. ộ ớ ả ộ ứ ụ ằ ồ
:
c phân thành nhi u ph n:
3.2 Các chi n l c phân tán d li u ế ượ ữ ệ
ng th c lai 3.2.4 Ph ứ ươ • C s d li u đ ơ ở ữ ệ
ượ
ầ quan
ề
tr ngọ và không quan tr ngọ .
c l u gi
ầ
ọ
ượ ư
m t n i ữ ộ ơ
• Ph n ít quan tr ng đ • Ph n quan tr ng đ
c l u tr
ầ
ọ
ượ ư
ữ ở
nhi u n i khác. ơ
ề
12
3.3 PH ƯƠ NG PHÁP THI T K CSDL PHÂN TÁN Ế Ế
ơ ồ
ộ ỹ ộ
ộ
t k CSDL phân tán theo ể
3.3.1 S đ thi t k t ng th c s d li u phân tán ế ế ổ ể ơ ở ữ ệ Hi n nay ch a có m t k thu t c th nào nói m t cách ậ ụ ể ư t k m t CSDL phân tán. Tuy nhiên, m t chi ti ế ế ộ cách t ng quát chúng ta có th thi ế ế các b c sau: ệ t vi c thi ệ ế ổ ướ
Thi
t k l
c đ quan h t ng th
ế ế ượ ồ
ệ ổ
ể
Thi
t k phân đo n
ế ế
ạ
Thi
ạ
ế ế ị (T o các nh v t lý) ả
t k đ nh v các đo n ị ạ
ậ
Thi
t k CSDL v t lý
ế ế
ậ
S đ thi t k t ng th
ơ ồ ế ế ổ
ể
13
3.3 PH ƯƠ NG PHÁP THI T K CSDL PHÂN TÁN Ế Ế
1. Thi ồ ệ ổ ể:
c đ quan h t ng th ệ ổ
• Thi • Mô t ệ ố
1. Thi t k phân đo n: ự
t k l ế ế ượ t k các quan h t ng th ể ế ế toàn b d li u s đ c dùng trong h th ng ẽ ượ ộ ữ ệ ả ạ th c hi n chia nh d li u thành ỏ ữ ệ ệ ế ế các ph n.ầ
2. Thi • ạ ạ ệ ạ t k đ nh v các đo n: ị ự ạ
ạ ạ
ế ế ị là quá trình th c hi n ánh x các đo n vào các tr m khác nhau • T o các nh v t lý t ả • Các đo n d li u đ ạ ư ữ
i các tr m. c đ a vào các v trí l u tr thích ị ự ế ủ ớ
: thi 1. Thi h p v i yêu c u ho t đ ng th c t ế ế ơ ở ữ ệ ư c a h th ng. ệ ố t k d li u v t lý ậ ế ế ữ ệ
14
cho các quan h t ậ ữ ệ ầ ợ t k c s d li u v t lý i các tr m ệ ạ ạ ượ ạ ộ ậ ạ
3.3 PH ƯƠ NG PHÁP THI T K CSDL PHÂN TÁN Ế Ế
3.3.2 Các ph
ng pháp thi
t k CSDL phân tán
ươ
ế ế
Có 2 ph
ng pháp thi
t k CSDL phân tán
ươ
ế ế
• Ph
ng pháp ti p c n t
trên xu ng
ươ
ậ ừ
ế
ố
• Ph
ng pháp ti p c n t
d
i lên.
ươ
ậ ừ ướ
ế
15
3.3 PH ƯƠ NG PHÁP THI T K CSDL PHÂN TÁN Ế Ế
a. Ph ng pháp thi trên xu ng ươ t k t ế ế ừ ố
• Thi t k t ế ế ừ ổ t ng th đ n riêng bi ể ế t ệ
• Phân rã m t h th ng l n thành các h th ng con ớ ộ ệ ố ệ ố
• Phân tích các yêu c u nh m đ nh nghĩa môi tr ằ ầ ị ườ ng h ệ
th ngố
• Thu th p các yêu c u v d li u và nhu c u x lý c a các ề ữ ệ ử ủ ầ ầ ậ
16
tr m có s d ng CSDL. ử ụ ạ
3.3 PH ƯƠ NG PHÁP THI T K CSDL PHÂN TÁN Ế Ế
• Thi t k view : xây d ng khung nhìn d li u cho ng ế ế ữ ệ ự i ườ
các tr m. s d ng ử ụ ở ạ
• Thi t k m c quan ni m ế ế ứ ệ : là m t ti n trình ki m tra và ộ ế ể
xác đ nh rõ hai nhóm quan h : ệ phân tích th c thự ị ể và
phân tích ch c năng . ứ
+ Phân tích th c thự ể: xác đ nh các t p th c th , các ậ ự ể ị
thu c tính và các m i quan h gi a chúng. ố ệ ữ ộ
+ Phân tích ch c năng : xác đ nh các ch c năng c a ứ ứ ủ ị
17
h th ng và đ a ra các ch c năng c s . ệ ố ơ ở ư ứ
3.3 PH ƯƠ NG PHÁP THI T K CSDL PHÂN TÁN Ế Ế
• Thi t k phân tán : bao g m hai ph n: ế ế ầ ồ
+ Thi t k phân đo n ế ế ạ
+ Thi t k đ nh v ế ế ị ị
• Thi c đ quan ni m đ a ph ng t k l ế ế ượ ồ ệ ị ươ : t o ra các ạ
c đ m c quan ni m t ng l ượ ồ ứ ệ ạ i các đ a ph ị ươ
• Thi t k v t lý c đ m c quan ế ế ậ : th c hi n ánh x l ệ ạ ượ ự ồ ứ
ng ra các đ n v l u tr v t lý ni m t ệ ạ i các đ a ph ị ươ ữ ậ ị ư ơ
• Quan sát và ki m tra : ki m tra các giai đo n c a quá ể ủ ể ạ
18
trình thi t k c s d li u ế ế ơ ở ữ ệ
19
3.3 PH ƯƠ NG PHÁP THI T K CSDL PHÂN TÁN Ế Ế
3.3 PH ƯƠ NG PHÁP THI T K CSDL PHÂN TÁN Ế Ế
ng pháp thi t k t d i lên ế ế ừ ướ ươ
b. Ph Nh n xét ậ • Ph t k trên xu ng th c s có hi u qu khi ố ả ệ ự ự ươ
xây d ng m t h th ng m i. ớ ng pháp thi ự
• Trong th c t c, đ i tr ự ế ồ ạ ướ
ứ , m t s CSDL đã t n t ậ
ế ằ
ị
ớ ượ Cách thi 1. Ch n m t mô hình d li u chung đ mô t ế ế ộ ệ ố c t ượ ổ ộ ố ng t p trung và CSDL phân tán đ c ch c trong môi tr ượ ườ i thành m t CSDL phát tri n b ng cách liên k t chúng l ộ ạ ể m i th ng nh t (Các DBMS đ a ph ng khác nhau đã ấ ươ ố c s d ng) đ ử ụ t k ế ế ộ c đ t ng ồ ổ l ả ượ ữ ệ ể
ọ thể
ng theo mô hình d li u 2. Chuy n m i l ể c đ đ a ph ồ ị ươ ữ ệ
20
3. Tích h p các l ng vào l ỗ ượ chung đã ch n ọ ợ ượ c đ đ a ph ồ ị ươ ượ c đ t ng th ồ ổ ể
3.4 PHÂN M NH D LI U Ả Ữ Ệ
0. Nh c l i các phép toán đ i s quan h và ngôn ng SQL ắ ạ ạ ố ữ ệ
1. T i sao c n ph i phân m nh? ả ạ ả ầ
2. Làm th nào đ th c hi n phân m nh? ể ự ế ệ ả
3. Phân m nh nên th c hi n đ n m c đ nào? ự ứ ệ ế ả ộ
4. Có cách gì ki m tra tính đúng đ n c a vi c phân m nh? ủ ệ ể ắ ả
5. Vi c c p phát các m nh d li u nh th nào? ả ư ế ữ ệ ệ ấ
6. Nh ng thông tin nào s c n thi t cho vi c phân m nh và ẽ ầ ữ ế ệ ả
21
c p phát? ấ
SQL
c v ngôn ng SQL (Structured query language)
ữ c g i là SEQUEL
ộ
S l ề ơ ượ • SQL tr c kia đ ướ ọ ượ • San Jose, IBM phát tri n ể ở • Là m t ngôn ng phi th t c ủ ụ ữ • M c đích đ s d ng trong CSDL th nghi m System R ể ử ụ ụ ử ệ
Câu l nh SELECT ệ
Cú pháp: SELECT R1.A1, R2.A2,. . ., Ri.Ai FROM R1, R2 ,. . . , Rk WHERE Y
P · Ý nghĩa:
...·
y (R1
Rk))
(s R1.A1, R2.A2,. . ., Ri.Ai
22
3.4 PHÂN M NH D LI U Ả Ữ Ệ
ả ệ
c ỏ ơ ệ ệ ề ượ
Phân m nh quan h là gì? Vi c chia m t quan h thành nhi u quan h nh h n đ ộ g i là phân m nh quan h . ệ ả ệ ọ
3.4.1 Các lý do phân m nhả • Khung nhìn ho c đ n v truy xu t c a các ng d ng không ấ ủ ứ ụ ơ
ị ệ ườ
ặ ph i là toàn b quan h mà th ộ ộ ộ ả ệ ề ả
ng là m t ph n quan h . ệ ầ • Vi c phân rã m t quan h thành nhi u m nh, m i m nh c x lý nh m t đ n v , s cho phép th c hi n nhi u ị ẽ ả ệ ượ ỗ ệ ự ề ử
đ ư ộ ơ giao d ch đ ng th i. ờ ồ ị
ả ệ ệ ẽ ự ệ
ộ ậ ấ ộ
23
• Vi c phân m nh các quan h s cho phép th c hi n song song m t câu v n tin b ng cách chia nó ra thành m t t p các câu v n tin con ho t tác trên các m nh. ằ ạ ả ấ
3.4 PHÂN M NH D LI U Ả Ữ Ệ
• N u các ng d ng có các khung nhìn đ c đ nh nghĩa ứ ụ ế ượ ị
trên m t quan h cho tr ệ ộ ướ c n m t ằ ạ i nh ng v trí khác ị ữ
thì có hai cách ch n l a đ n v phân tán: ọ ự ơ ị
+ ho c là toàn b quan h ệ ặ ộ
+ ho c quan h đ m t v trí có ch y ng c l u ệ ượ ư ở ộ ị ạ ứ ặ
d ng. ụ
ng l n các Nh n xét ậ : Ch n l a th nh t gây ra m t s l ấ ộ ố ượ ọ ự ứ ớ
truy xu t không c n thi t đ n d li u xa. Ch n l a ầ ấ ế ế ữ ệ ở ọ ự
sau s gây ra nhi u v n đ khi c p nh t và lãng phí ề ề ẽ ấ ậ ậ
24
không gian l u tr . ữ ư
3.4 PHÂN M NH D LI U Ả Ữ Ệ
ệ ể ủ
ệ ế ế ứ
ả ề ữ ả ầ ử ụ
Khuy t đi m c a vi c phân m nh: • N u ng d ng có nh ng yêu c u ngăn c n vi c phân rã ả c s d ng đ c quy n, thì nh ng c đ nh nghĩa trên nhi u ề ụ ộ ị
ượ ạ ộ
• N u m t khung nhìn đòi h i thông tin nhi u m nh thì ấ ỏ ẽ ị ả ộ ữ ụ thành các m nh đ đ ể ượ ứ m nh s b gi m hi u su t ho t đ ng. ệ ở ề
ả i s có chi phí cao.
ể ố ạ ẽ ữ ệ
ộ
ể ị ả
25
ụ ượ ợ ệ ả ộ
ng d ng có các khung nhìn đ ả ế vi c truy xu t d li u đ n i l ệ ấ ữ ệ • Ki m soát ng nghĩa d li u (semantic data control): Do ể ữ k t qu c a phân m nh, các thu c tính tham gia vào m t ộ ế ả ả ủ ph thu c có th b phân rã vào các m nh khác nhau và ộ ng đ c c p phát cho nh ng v trí khác nhau. Trong tr ườ ị ấ h p này, m t nhi m v đ n gi n nh ki m tra các ph ụ nhi u v trí. thu c cũng ph i th c hi n truy tìm d li u ư ể ữ ệ ở ữ ụ ơ ệ ự ề ả ộ ị
3.4 PHÂN M NH D LI U Ả Ữ Ệ
3.4.2 Các ki u phân m nh ể ả
• Phân m nh ngang (horizontal fragmentation) ả
• Phân m nh d c (vertical fragmentation). ả ọ
• Phân m nh h n h p (hibrid fragmentation) ả ợ ỗ
Chú ý: Quá trình phân m nh ph i đ ả ượ ả c g n li n v i v n đ ề ớ ấ ề ắ
26
c p phát d li u và bài toán c th nh th nào. ấ ư ế ụ ể ữ ệ
3.4 PHÂN M NH D LI U Ả Ữ Ệ
3.4.2.1 Phân m nh ngang ả ệ ổ ả ộ
ộ ể ệ
: phân m nh ngang m t quan h t ng ộ 1, R2, ..., Rk các quan h ệ
ằ ợ th n-b R là tách R thành các quan h con n-b R c khôi ph c l i t sao cho quan h R có th đ ụ ạ ừ ể ượ ệ ... ¨ R2 ¨ 1 ¨ Rk con này b ng phép h p: R = R
ả
Có hai lo i phân m nh ngang: Phân m nh ngang nguyên th y ạ ả
ả ủ ủ ủ (primary horizontal fragmentation): c th c ự ộ
phân m nh ngang nguyên th y c a m t quan h đ hi n d a trên các v t c đ nh nghĩa trên quan h đó. ệ ượ ệ đ ị ừ ượ ự ệ ị
Phân m nh ngang d n xu t ả ẫ
ấ (derived horizontal fragmentation): c th c hi n ệ ự ộ
c đ nh nghĩa trên quan h khác. phân m nh ngang d n xu t c a m t quan h đ ệ ượ ả d a trên các v t ệ ẫ đ ị ừ ượ ấ ủ ị ự
ậ ị ừ
đóng m t vai trò ộ 27 Nh v y, trong phân m nh ngang t p các v t ả ư ậ quan tr ng.ọ
3.4 PHÂN M NH D LI U Ả Ữ Ệ
3.4.2.2 Phân m nh d c
ả ọ ộ
ể ượ ệ ệ
các quan h con này b ng phép n i: ọ : Phân m nh d c m t quan h t ng th n-b R là tách R thành ể ệ ổ ộ ả c 1, R2, ..., Rk sao cho quan h R có th đ các quan h con R ằ ố ụ ạ ừ
i t khôi ph c l ệ R = R1 R2 ..., Rk
ợ : ả
28
3.4.2.3 Phân m nh h n h p là k t h p c phân m nh ngang và phân m nh d c ọ ỗ ả ế ợ ả ả
3.4 PHÂN M NH D LI U Ả Ữ Ệ
3.4.3 Các yêu c u c a vi c phân m nh ủ ệ ả ầ
Vi c phân m nh m t quan h t ng th cũng ph i tuân theo ệ ổ ệ ể ả ả ộ
m t s quy t c nh t đ nh đ khi tái thi ộ ố ấ ị ể ắ t l ế ạ i quan h cũ v n ệ ẫ
b o đ m ng nghĩa c a nó. ủ ữ ả ả
ng pháp thi t k các phân m nh đúng đ n ph i th a M t ph ộ ươ ế ế ả ắ ả ỏ
mãn ba tính ch t sau: ấ
a. Tính đ y đ (completeness) ủ ầ
b. Tính tái thi c (reconstruction) t đ ế ượ
29
c. Tính tách bi t (disjointness): ệ
3.4 PHÂN M NH D LI U Ả Ữ Ệ
ế ủ: N u m t quan h R đ ượ ệ ộ
ữ ệ ả c phân rã thành các 1, R2, ..., Rk thì m i m c d li u có trong R ph i có
ấ ả ộ a. Tính đ y đầ m nh Rả ụ ỗ i nào đó. trong ít nh t m t m nh R
t đ
1,
c phân rã thành các m nh R b. Tính tái thi ộ ế ế ượ : c ệ ượ
i m t toán t ả ồ ạ ộ • N u m t quan h R đ R2, ..., Rk thì ph i t n t ả ử q sao cho R = q (Ri),
"
ạ ổ
ượ ả ả
i. • Toán t • Trong th c t ự ế ợ ả
30
ử q thay đ i tùy theo t ng lo i phân m nh. ừ khi các m nh đ ọ q là phép n a n i . ả c phân m nh ngang thì q là phép n i và phân q là phép h p, phân m nh d c thì ố m nh h n h p thì ố ỗ ử ả ợ
3.4 PHÂN M NH D LI U Ả Ữ Ệ
tệ :
c. Tính tách bi • N u m t quan h R đ c phân m nh ngang thành các ế ệ ộ ượ ả
i
ụ ả quan h Rệ 1, R2, ..., Rk và m c d li u t ữ ệ i n m trong m nh R
thì nó s không n m trong m t m nh R i. ẽ ả ằ ộ ằ k, k„
c tách • Tiêu chu n này b o đ m các m nh ngang ph i đ ả ả ượ ả ẩ ả
r i nhau. ờ
• N u quan h đ c phân m nh d c thì thu c tính chung ệ ượ ế ả ộ ọ
ph i đ c l p l i trong m i m nh. Do đó, trong tr ng ả ượ ặ ạ ả ỗ ườ
h p phân m nh d c tính tách bi t ch đ c đ nh nghĩa ả ợ ọ ệ ỉ ượ ị
trên các tr ng không ph i là thu c tính chung c a quan ườ ủ ả ộ
31
h .ệ
3.4 PHÂN M NH D LI U Ả Ữ Ệ
c Ví d :ụ Xét c s d li u c a m t công ty ph n m m đ ủ ơ ở ữ ệ ề ầ ộ ượ
t ch c nh sau: ổ ư ứ
• NHANVIEN (MANV, TENNV, CHUCVU): quan h này ệ
ch a d li u v nhân viên c a công ty. ữ ệ ủ ứ ề
• TLUONG (CHUCVU, LUONG): quan h này ch a d li u ữ ệ ứ ệ
liên quan v l ề ươ ng và ch c v c a nhân viên. ụ ủ ứ
• DUAN (MADA, TENDA, NGANSACH): quan h này ch a ứ ệ
d li u v các d án mà công ty đang th c hi n. ữ ệ ự ự ệ ề
• HOSO (MANV, MADA, NHIEMVU, THOIGIAN): quan h ệ
này ch a d li u v h s c a nhân viên đ c phân công ề ồ ơ ủ ữ ệ ứ ượ
32
th c hi n d án). ệ ự ự
C s d li u c a m t công ty máy tính ơ ở ữ ệ ủ ộ
NHANVIEN (E)
HOSO (G)
MANV TENNV
CHUCVU
MANV MADA
NHIEMVU
THOIGIAN
ậ
ỹ ậ
A1 A2 A3 A4 A5 A6 A7 A8
Nam Trung Đông B cắ Tây Hùng Dũng Chi nế
ỹ
t k DL
Phân tích HT L p trình ậ viên Phân tích HT Phân tích HT L p trình ậ viên K s đi n ỹ ư ệ Phân tích HT Thi ế ế
A1 A2 A2 A3 A3 A4 A5 A6 A7 A8
D1 D1 D2 D3 D4 D2 D2 D4 D3 D3
Qu n lý ả Phân tích Phân tích K thu t L p trình Qu n lý ả Qu n lý ả K thu t ậ Qu n lý ả L p trình
12 34 6 12 10 6 20 36 48 15
ậ
DUAN (J)
MADA
TENDA
NGANSACH
LUONG
TLUONG (S) CHUCVU
Ả
D1 D2 D3 D4
20000 12000 28000 25000
CSDL CÀI Đ TẶ B O TRÌ PHÁT TRI NỂ
K s đi n ỹ ư ệ Phân tích HT L p trình viên ậ Thi
t k DL
1000 2500 3000 4000
ế ế
33
34
3.4 PHÂN M NH D LI U Ả Ữ Ệ
3.4 PHÂN M NH D LI U Ả Ữ Ệ
$1,$2
35
Xem l iạ
3.5.1 Bài toán c p phát
(allocation problem):
Gi
s có m t t p các m nh F = {F
ấ ộ ậ
ả ử
ả
m ng máy tính bao g m các v trí S= {S
ạ
ồ
ị
ứ
ộ ậ
ụ
1, F2, ..., Fk } và m t ộ 1, S2, ..., Sm } 1, Q2, ..., Qq }
i u các m nh F cho các v trí
ố ố ư
ả
ị
trên đó có m t t p các ng d ng Q={Q đang th c thi. ự Hãy tìm m t phân ph i t ộ S.
3.5 C p phát tài nguyên trong h phân tán ệ ấ
36
M t phân ph i đ i u n u th a mãn hai y u t sau: ố ượ ộ c g i là t ọ ố ư ế ố ế ỏ
3.5 C p phát tài nguyên trong h phân tán ệ ấ
a. Chi phí nh nh t
ấ : hàm chi phí bao g m:ồ
ỏ
ữ ệ
ư
ả
ạ ị
• Chi phí l u m i m nh d li u F ỗ
i t
i v trí S j
ấ
ạ ị
• Chi phí v n tin F
i t
i v trí S j
t c các v trí có ch a nó
i t
ậ
ạ ấ ả
ứ
ị
ậ i t • Chi phí c p nh t F
• Chi phí truy n d li u.
ữ ệ
ề
Bài toán c p phát s tìm m t l
ộ ượ
ẽ
ấ
c đ c p phát v i ớ
ồ ấ
hàm chi phí là c c ti u.
ự ể
c c p phát đ
c thi
t k nh m
b. Hi u qu ệ
ả: chi n l
ế ượ
ấ
ượ
ế ế
ằ
i đa l u
c c ti u hóa th i gian th c hi n và tăng t ự ể
ự
ệ
ờ
ố
ư
37
l ượ
ng h th ng t ệ ố
ạ
i m i v trí. ỗ ị
3.5 C p phát tài nguyên trong h phân tán ệ ấ
Bài toán c p phát t ng quát, ký hi u DAP (Database ệ ấ ổ
Allocation Problem), là m t bài toán ộ NP-đ y đầ ủ. Vì th h u ế ầ
h t các nghiên c u đã đ c dành cho vi c tìm ra đ c các ứ ế ượ ệ ượ
i heuristic đ có đ i gi i u cho lo i bài i t thu t gi ậ ả ể c l ượ ờ ả ố ư ạ
toán này.
Hi n nay ch a có m t mô hình heuristic t ng quát nào ư ệ ổ ộ
nh n m t t p các m nh và sinh ra m t chi n l c c p phát ộ ậ ế ượ ậ ả ộ ấ
g n t i u ng v i các ràng bu c cho tr c mà ch m i đ a ầ ố ư ứ ộ ớ ướ ỉ ớ ư
ra m t s gi thi ộ ố ả ế ơ t đ n gi n hóa và d áp d ng cho m t s ộ ố ễ ụ ả
38
cách đ t v n đ đ n gi n. ặ ấ ề ơ ả
3.5 C p phát tài nguyên trong h phân tán ệ ấ
3.5.2 Thông tin c p phát ấ
giai đo n c p phát, chúng ta c n các thông tin đ nh Ở ầ ấ ạ ị
l ượ ng v c s d li u, v các ng d ng ch y trên đó, v ề ứ ề ơ ở ữ ệ ụ ề ạ
i h n l u tr c a c u trúc m ng, v kh năng x lý và gi ấ ử ề ả ạ ớ ạ ư ữ ủ
m i v trí trên m ng. ỗ ị ạ
a. Thông tin v c s d li u ề ơ ở ữ ệ
b. Thông tin v ng d ng ề ứ ụ
c. Thông tin v v trí ề ị
39
d. Thông tin v m ng ề ạ
Câu h i cu i ch ng ố ỏ ươ
1. Các v n đ c n ph i làm đ thi t k m t HT phân tán ề ầ ể ả ấ ế ế ộ
t k m t HT 2. Các s n ph m yêu c u sau khi phân tích thi ầ ẩ ả ế ế ộ
phân tán
3. Các chi n l c phân tán d li u ế ượ ữ ệ
4. N i dung c a ph ng pháp thi trên xu ng ủ ộ ươ t k t ế ế ừ ố
5. Các ki u phân m nh và các yêu c u c a vi c phân m nh. ủ ể ệ ả ầ ả
Cho ví d .ụ
40
6. Bài toán c p phát ấ
CH NG I. T NG QUAN V CSDL PHÂN TÁN ƯƠ Ổ Ề
HẾT CHƯƠNG 3
41
