Ơ Ở Ữ Ệ
ươ
Môn C S D LI U Ch
ẩ Chu n hóa ng 6: ơ ở ữ ệ c s d li u
ộ
N i dung
Ố Ả
Ế
1. PHÉP K T N I B O TOÀN THÔNG TIN
ơ ở
C S Lý Thuy t ế
ố ả
ể
ế
Thu t Toán Ki m Tra Tính K t N i B o Toàn
ậ Thông Tin
Ộ
Ụ
Ả
2. PHÉP TÁCH B O TOÀN PH THU C HÀM
ơ ở
C s lý thuy t ế
ậ
Thu t toán
Ậ
Ế
Ể
Ế
Ế
3. CÁCH TI P C N PHÂN RÃ
Ợ Ể
Ổ
Ậ
Ế
Ế
Ế
4. CÁCH TI P C N T NG H P Đ THI T K CSDL
Đ THI T K CSDL
2
Ế Ố Ả
1. PHÉP K T N I B O TOÀN T.TIN
ơ ở
ế C S Lý Thuy t
ệ ượ
ộ ượ ồ
c đ quan h đ
c tách thành các ụ ậ
ộ
ằ
ố ớ
ế
ả
ớ
ỗ
ỏ
ế N u Q là m t l ượ ồ c đ con Q1,Q2,...,Qk và F là t p ph thu c l hàm, nói r ng phép tách (phân rã ) là phép tách có ệ b o toàn thông tin đ i v i F n u v i m i quan h r trên Q th a F:
Q =(cid:0) Q1(r) * (cid:0) Q2 (r)* . . * (cid:0) Qk(r)
ượ ạ
ế ố ự
ừ
ủ
T c là r đ
nhiên c a
c t o nên t ế ủ
ứ phép k t n i t các hình chi u c a nó trên Qi ( i =1..k)
3
Ế Ố Ả
1. PHÉP K T N I B O TOÀN TT (tt)
ậ ể ế ố ả
ượ ồ ệ ậ ụ c đ quan h Q(A1,A2,…An) và t p các ph : L
Thu t Toán Ki m Tra Tính K t N i B o Toàn Thông Tin D li u vào ữ ệ ộ thu c hàm F, phép tách = {Q,Q,…,Qk}.
D li u ra ữ ệ
ả : Phép tách có b o toàn thông tin hay không?
ả ế ậ ộ ứ ớ ộ ớ ộ (1)Thi
ứ ạ t l p b ng v i k + 1 dòng, n + 1 c t . C t j ng v i thu c tính c đ quan h Qi(i=1…k). T i ví trí
ớ ượ ồ ế ệ ề ộ ệ AJ(i=1...n), hàng i ng v i l hàng i, c t j ta đi n ký hi u Aj n u AJ Qi,
ặ ệ
ả i, sau đó tăng t lên m t
ạ ủ ả i c a b ng ký hi u bt theo ố ướ ư ừ trên xu ng d ề ủ ế ọ ộ i thao tác đi n bt nh trên. Cho đ n khi m i ô c a
ệ ặ ầ Đ u tiên đ t t=1 và đ t vào các ô còn l ề ừ chi u t trái sang ph i và t ặ ạ ị ơ đ n v và l p l ề ả b ng đi u đã có ký hi u.
ộ ụ ừ ớ
ụ ả ử
ả ữ ữ ế ấ ộ s xét (X Y) F, chúng ta tìm nh ng hàng t c các thu c tính c a X, n u th y nh ng hàng
ủ ệ ủ ằ ở ấ t t
ủ ộ ầ ượ t các ph thu c hàm trong F, áp d ng cho b ng v a m i (2)Xét l n l ậ ở trên. Gi thành l p ở ấ ả ố t gi ng nhau ẽ ư ậ nh v y ta s làm cho các ký hi u c a hai hàng này b ng nhau ả c các thu c tính c a Y.
4
Ế Ố Ả
1. PHÉP K T N I B O TOÀN TT (tt)
ế ố ả ể ậ Thu t Toán Ki m Tra Tính K t N i B o Toàn Thông Tin (tt)
ệ ằ ặ ườ ợ Khi làm cho 2 ký hi u này b ng nhau, ta g p 3 tr ng h p sau đây:
n u m t trong hai ký hi u là AJ thì cho ký hi u kia tr thành AJ,
ế ệ ệ ộ ở
n u hai ký hi u là bk ho c bl thì có th cho chúng tr thành bt ho c
ệ ể ặ ặ ở
ớ ế bt (v i t=min (k,l)),
ữ ỉ ố ủ nguyên (lúc đó ch s j c a các ký
n u c hai ký hi u là aj thì gi ế ả ả ệ hi u này ph i gi ng nhau)
ệ ố
ằ ướ ụ ộ Chú ý r ng b c này có th đ
i (cho các ph thu c hàm) cho ế ở
ể ượ ặ ạ ụ ấ ả c l p l ượ ữ c n a (nghĩa là cho đ n khi nào ụ ả ộ t c các ph thu c hàm trong F mà b ng không
ệ ổ ế đ n khi không còn áp d ng đ ộ ầ m t l n duy t qua t ự có s thay đ i nào.
ả ế ấ ả ộ
ả ế ậ ế ả
ấ aj (i=1..n) thì k t lu n đó là phép tách b o toàn thông tin, ng thì là phép tách m t mát thông tin. ứ (3)Xét b ng k t qu , n u th y trong b ng này có m t hàng ch a toàn ượ ạ i c l 5
Ế Ố Ả
1. PHÉP K T N I B O TOÀN TT (tt)
Ví d :ụ
6
Ả
ậ ộ ượ ồ ụ ệ c đ quan h , và t p ph
ộ ộ
(cid:0) ậ ế ủ ụ Y (cid:0)
ụ ớ ụ t t c các
ụ ộ
2. PHÉP TÁCH B O TOÀN PTH ế ơ ở C s lý thuy t ủ Cho phân rã p = {Q1,Q2,…Qk} c a m t l ộ ậ thu c hàm F. Hình chi u c a F trên m t t p các thu c tính Z ký F+ sao cho XY (cid:0) hi u ệ (cid:0) Z(Q) là t p các ph thu c hàm X ộ ợ ủ ấ ậ ế ộ ả Z . Ta nói phân rã p b o toàn t p ph thu c hàm F n u h p c a t ượ ấ ả ộ ả c t i(F) v i i=1..k suy ra đ c các ph thu c hàm trong Q ph thu c hàm trong F. ậ
ụ ả ộ
ộ
ế ễ ế
ủ ể
ể ấ ằ ỏ ả ế ệ ộ
ứ ặ ớ
ố ể ể ệ ả ậ ỗ i s ẽ ạ ằ i r ng các ràng
Lý do p c n b o toàn t p F đó là vì các ph thu c hàm trong F có ầ ệ ẹ ể ượ c xem là các ràng bu c toàn v n cho quan h Q. N u các th đ ể ượ ộ ụ c F thì khi bi u di n Q qua ph thu c hình chi u không suy ra đ ễ ị ệ p , chúng ta có th th y r ng giá tr hi n hành c a các Qi bi u di n ấ m t quan h Q không th a F, ngay c n u p là phép tách không m t ỗ thông tin ng v i F. Khi đó m i thao tác c p nh t trên m i R ộ ự ầ c n ph i th c hi n m t phép n i đ ki m tra l bu c không b vi ph m.
ạ ị
D li u vào: M t phân rã p={Q
ụ ộ ộ ữ ệ ộ ậ 1,Q2,…Qk} và m t t p các ph thu c
ộ hàm F(f1,f2,…,fm} 7 ữ ệ ụ ả ộ D li u ra: phép tách p có b o toàn ph thu c hàm hay không ?
Ả 2. PHÉP TÁCH B O TOÀN PTH (tt)
ụ
ả
ộ
Phép tách b o toàn ph thu c hàm
ắ
ề
ể
ể ễ ả
ụ
ậ
ộ
ỉ ầ
ế
ồ ợ ủ
ấ
ộ ế
ươ
ậ
ậ ng đ
ớ
V nguyên t c,chúng ta có th d dàng ki m tra xem m t ộ phân rã p = {Q1,Q2,…Qk} có b o toàn t p ph thu c F ấ t hay không. Chúng ta ch c n tính F+ r i chi u nó trên t ầ ụ ả c các thành ph n Qi. Sau đó l y h p c a các t p ph ươ ể ả ồ thu c k t qu r i ki m ra xem t p này có t ng v i F hay không ?
ộ
Tuy nhiên trong th c t
ố ượ
ộ
ự ế ng các ph thu c ch a trong nó th
ụ ướ ủ
ư
ộ
ả
ả ầ ỷ ệ ớ
ờ
l
ng pháp này có chi phí th i gian t
ướ ủ
ệ ế ứ , tính F+ là m t công vi c h t s c ườ ứ ng khó khăn vì s l ể là hàm mũ theo kích th c c a F. Nh ng có m t cách đ ể ki m tra tính b o toàn này mà không c n ph i tính F+; ươ ph v i hàm đa ứ th c theo kích th
c c a F.
8
Ả 2. PHÉP TÁCH B O TOÀN PTH (tt)
ậ Thu t toán
Chúng ta g i G là h p c a các Q
ọ ợ ủ ươ ng
i(F), đ tính xem G có t ụ ng v i F hay không chúng ta xét m i ph thu c hàm X Y F c tính ng v i G) có ch a Y hay không ?
ộ ứ ớ ị ượ ứ
ụ ộ ể ươ ỗ đ ớ và xác đ nh xem X+ (đ ộ ế n u có thì ph thu c hàm này thu c G.
ậ ứ ớ ộ
ị ụ ộ ậ ằ
ộ ượ ấ ứ ớ ố
ộ ữ ứ
ở ầ ớ
ằ ự ệ ỗ t th c hi n các phép toán Qi v i m i i, n u t
ộ ầ ặ ậ ộ
Chúng ta đ nh nghĩa phép toán Q trên t p các thu c tính Z ng v i ế m t t p ph thu c F là phép th Z b ng Z ((Z Q)+ Q) trong đó ớ bao đóng luôn đ c l y ng v i F, phép toán này n i Z v i nh ng thu c tính A sao cho (Z Q) A QF. Do đó chúng ta tính X+ ng ầ ớ v i G b ng cách kh i đ u v i X, qua danh sách các Qi, chúng ta l n ớ ượ i m t l n l p nào l ộ đó không có m t phép toán Qi nào làm thay đ i các t p thu c tính hi n có thì chúng ta đã th c hi n xong; t p k t qu là X+
ế ạ ổ ế ự ệ ệ ậ ả
ế ộ ậ ả ủ ự ủ ệ
N u Y là m t t p con c a Z, là k t qu c a th c hi n các phép trên ế ộ thì X Y G+ , n u m i ph thu c hàm trong F đ u thu c G thì là đúng, ng
ụ ề ộ
ỗ ế i là sai. ượ ạ c l
ể ả ư ộ *Chú ý: M t phân rã có th b o toàn thông tin nh ng không ch c b o ắ ả 9
ụ ậ ộ toàn t p ph thu c hàm F và ng ượ ạ c l i.
Ậ
Ế
Ể
3. TI P C N PHÂN RÃ
Đ TK CSDL
ể ệ
t đ
ơ ở ữ ệ ệ ấ
Theo quan đi m c a cách ti p c n này, các quan h con c a c u ủ ế ậ ủ ấ ữ ầ ẽ ầ ượ ượ c phân rã thành nh ng trúc c d d li u ban đ u s l n l ả ạ ơ ớ ố ế ộ quan h con v i s thu c tính ít h n, sao cho c u trúc k t qu đ t ẩ ộ ấ ở ứ ề m c cao nh t. Quá trình phân rã là m t quá các tiêu chu n đ ra ượ ặ ạ ố ớ trình đ c đánh giá là còn i đ i v i các quan h con nào đ c l p l ể có th phân rã.
ượ ệ
ƯỢ Ồ *PHÂN RÃ M T L C Đ Q THÀNH CÁC L C Đ CON
Ạ Ộ ƯỢ Ồ Ả ẩ D NG chu n BCK VA B O TOÀN THÔNG TIN
ơ ở ế C S Lý Thuy t
ổ ề B đ 1:
Gi
ả ử ộ ọ s Q là m t l c đ quan h v i t p ph thu c hàm F, g i
ụ ố ớ
ệ ớ ậ ủ ượ ồ ấ ứ ố ượ ế ộ ượ ồ ộ c phân rã thành hai l
ủ ố
ấ ấ ứ ớ p={Q1,Q2,…,Qk } là m t phân rã c a Q có n i không m t ng v i c đ con (S1.S2) có n i không Q. n u Q1 đ m t, thì phân rã c a Q thành (S1,S2,Q2,…,Qk) cũng có n i không m t ng v i F. 10
Ậ
Ế
3. TI P C N PHÂN RÃ
…(tt)
ổ ề B đ 2:
ỗ ượ ồ
ề ở ạ
ẩ
ộ
a)M i l
c đ có hai thu c tính đ u
d ng chu n BCK
ẩ
b)N u Q không đ t d ng chu n BCK thì chúng ta có th ể
ượ
ạ ạ ộ
c các thu c tính A và B trong Q sao cho (Q AB)+ ụ
ườ
ể
ộ
ng
ư
ọ
ợ
ế tìm đ A. và ph thu c (Q AB)+ B có th đúng trong tr ề h p này (nh ng đó là đi u không quan tr ng).
ề ả
ệ
ể
ệ
t
ư
ừ ể đây ta có th phát bi u thêm m nh đ đ o cho m nh ề đ này nh sau:
ế
ộ
b')N u trong Q không tìm đ
ụ
ạ
ượ c các thu c tính A và B sao ộ cho (Q AB)+ A. và ph thu c (Q AB)+ B thì Q đã ẩ đ t chu n BCK
11
Ậ
Ế
3. TI P C N PHÂN RÃ
…(tt)
ậ Thu t Toán 1
Input: Cho l
ượ ồ ụ ệ ậ ổ ộ c đ quan h ph quát Q và t p ph thu c hàm F
Output: L
ượ ồ ươ ứ ạ ạ ẩ c đ CSDL t ng ng đ t d ng chu n BCK.
ủ ụ ệ ự ư ể ệ Đ phân rã [Q,F] ta th c hi n theo th t c đ qui nh sau:
ủ ụ Th t c phân rã(Q,F)
ỏ ổ ề ứ ế ặ If N u Không tìm ra c p A,B trong Q th a b đ th 2 trên thì Exit
Y = Q
ỏ ổ ề WHILE TimAB(Y,F) {Tìm A,B th a b đ trên}
{Y=YB}
Q = Q (cid:0) A
ọ ệ {g i đ qui}
Phân rã 2(Q,F) 12
Ậ
Ế
3. TI P C N PHÂN RÃ
…(tt)
ậ
Thu t Toán 1 (tt)
ươ
ủ
ậ
Ch
ng trình chính c a thu t toán Phân rã
Do
ủ ụ
{ G i th t c Phân rã 2 (Q,F)
ọ p = p (cid:0) Q (cid:0)
Y Q (cid:0) A
}
While Not TimAB(Q,F)
p = p (cid:0)
ế
ươ
ng trình chính
K t thúc ch
13
Ậ
Ế
3. TI P C N PHÂN RÃ
…(tt)
ậ
Thu t Toán 2
phân rã(Q,F)
ụ
ạ
ộ
Xét f X Y F là ph thu c hàm làm cho [Q,F] vi ph m
ẩ
ạ
d ng chu n BC
{
ắ
Tách Q thành Q1 và Q2 theo quy t c sau:
Q1=Q[XY];
F1 = X Y
ậ ạ
ụ
ộ
i F=[F [các ph thu c hàm
ậ Q2=Q[Q+ Y] và c p nh t l ế có liên quan đ n Y]
ế ụ
ế
ệ
Phân rã (Q2,F) // công vi c này ti p t c cho đ n khi XY Q2+
}
14
Ế
Ậ
…(tt) Ạ ƯỢ Ồ C Đ CON D NG 3NF CÓ
3. TI P C N PHÂN RÃ *PHÂN RÃ M T L C Đ Q THÀNH CÁC L Ụ
Ộ
Ả
Ộ ƯỢ Ồ B O TOÀN PH THU C
ộ ượ ồ
ả
ệ
ạ
Không ph i lúc nào cũng có th phân rã m t l
ượ
ụ
c đ quan h thành d ng BC mà v n ể
ượ
ể ộ
ẫ ộ c m t
c các ph thu c hàm, tuy nhiên chúng ta luôn có th tìm đ ả
ẩ ấ
ụ
ạ
bào toàn đ ộ phân rã luôn b o toàn ph thu c hàm thành d ng chu n c p 3
ệ
ả ử ằ
ở ạ
ậ Thu t toán: D li u vào: ữ ệ L
ụ c đ quan h Q và t p ph thu c hàm F, chúng ta gi
s r ng F đã
d ng
ượ ồ ủ ự ể
ộ ấ
ẫ
ổ
ậ ph c c ti u mà v n không làm m t tính t ng quát.
ộ ủ
ả
ộ
ỗ ượ ồ
ề
ạ
ệ c đ quan h con đ u đ t
ượ ồ
ế ủ
ứ
ẩ
ớ
D li u ra: ữ ệ M t phân rã b o toàn ph thu c c a Q sao cho m i l ụ c đ đó.
chu n 3NF ng v i hình chi u c a F trên l
ữ
ủ
ụ
ằ
ộ
ộ
N u có nh ng thu c tính c a R không n m trong m t ph thu c nào c a F dù
ủ
ế
ạ
ả
ỏ
ế ấ ả
ủ
ụ
ủ
ế
ộ
ộ
ộ ủ ế ở ế v ph i hay v trái c a F thì ta lo i chúng ra kh i Q. N u có m t ph thu c hàm nào c a F mà liên quan đ n t
ộ t c các thu c tính c a
ả
ế
ể
ứ ỗ
ụ
ộ
ộ ượ ồ ầ
c đ c n tìm
Q thì k t qu ra chính là Q ( Q không th phân rã) C m i ph thu c hàm X A F thì XA là m t l
15
Ậ
Ế
3. TI P C N PHÂN RÃ
…(tt)
Ạ C Đ Q THÀNH CÁC L C Đ CON D NG
*PHÂN RÃ L Ẩ CHU N 3 V A B O TOÀN PH THU C V A B O TOÀN THÔNG TIN
ƯỢ Ồ Ộ Ừ Ả ƯỢ Ồ Ừ Ả Ụ
ể ượ ồ ộ ượ ồ ạ ạ Có th phân rã m t l
ố c đ thành các l ấ ể
ả ụ ệ
ặ
ả ấ
ươ ượ ả ấ ơ ng pháp r t đ n gi n c đi u đó thông qua ph
ẩ c đ con đ t d ng chu n ộ ượ c BCK có n i không m t, và chúng ta cũng có th phân rã m t l ể ộ ồ đ thành 3NF b o toàn ph thu c hàm. Li u chúng ta có th tìm ộ ậ ượ c m t phân rã thành 3NF mà có c hai đ c tính là bào toàn t p đ ế ố ộ ụ ph thu c và có tính k t n i không m t thông tin hay không ? Chúng ề ể ta có th làm đ ả ệ (mà hi u qu ) sau đây:
ộ ủ ớ ạ Tìm m t phân rã p c a Q có d ng 3NF nh v a m i phân tích
ư ừ ộ ủ trên ấ ả t c
ộ ượ ồ ủ ệ ề ế ố ấ ả ụ c đ quan h đ u có tính k t n i không m t và b o toàn ph
ế ố ỉ
ở ,và tìm m t khóa X c a Q, thì X p là m t phân rã c a Q mà t các l ộ thu c, phân rã cu i cùng là X p, nghĩa là X ch thêm vào p n u X ư ch a có trong p.
16
Ế
Ậ
…(tt)
3. TI P C N PHÂN RÃ ậ
ủ
Đánh giá các thu t toán phân rã Thu t toán không quan tâm v ch t l ậ
ầ ủ
ữ
ụ
ộ
ậ ộ ữ ụ
ắ ầ
ộ
ề ấ ượ ụ ng c a các ph ầ thu c hàm trong t p F ban đ u, nghĩa là có hay không nh ng ph thu c hàm không đ y đ , có hay không nh ng ph thu c hàm b c c u.
ệ ế
ấ ả
ả ề
ạ
ẩ
ứ ự
ượ
T t c các quan h k t qu đ u đ t chu n BC Tùy theo th t
ố ượ
ụ ế
c xem xét, trong ng
ộ ả ể
ệ
các ph thu c hàm đ ể quá trình phân rã, mà k t qu có th khác nhau. S l các quan h con cũng có th khác nhau.
ủ
ế
ệ
ậ
ị
Thu t toán không quan tâm đ n vi c xác đ nh khóa c a
ệ
các quan h con.
ế
ữ
ủ
ộ
K t qu có th ch a m t quan h con mà ng nghĩa c a ứ
ả ể
ệ ụ
ể ứ nó có th không có ích cho ng d ng
17
Ậ Ổ
Ợ Ể
Ế
4. TI P C N T NG H P Đ TK CSDL
ườ ỏ ả t k ph i phác i thi
Cách ti p c n t ng h p không đòi h i ng ỉ ầ
ế ậ ổ ộ ấ ế ế ị
ả ộ ầ ượ ắ
ợ ữ ệ c quan tâm và danh sách các quy t c qu n lý ộ ạ ướ ạ ườ ứ ả ụ ượ ụ ễ i d ng các ph thu c ng ng d ng đ c di n đ t d
th o m t c u trúc d li u ban đâu, ch c n xác đ nh danh sách các thu c tính c n đ ủ c a môi tr hàm.
M c tiêu c a cách ti p c n này là các quan h con t ế ậ
ủ ụ ệ ố ạ ể i thi u đ t
ụ ẩ ả ả ộ ẩ chu n 3 và b o toàn tiêu chu n b o toàn ph thu c hàm.
ệ ộ ố
ề ệ ượ ồ
ượ ổ ệ c đ quan h ph quát ượ ồ c đ CSDL C c phân rã thành l
ồ ỉ
(cid:0) ủ ệ ộ M t s khái ni m liên quan
Đi u ki n b o toàn thông tin: Cho l
ả
ả ử
s
Đi u ki n b o toàn ph thu c hàm
ụ ệ ề ả ộ
ỏ ồ ụ ế ả ờ Co và C đ ộ c g i là b o toàn ph thu c hàm n u th a đ ng th i:
QI )+ = Q+ 1.
18 ượ ọ ((cid:0) ((cid:0) FI )+ = F+ 2.
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ổ ượ ồ ậ Thu t toán Input: Cho l c đ CSDL
ươ ợ C ={
Output: Xu t các C ={
ấ
ướ B c 0:
Tách v ph i c a các ph thu c hàm sao cho các ph thu c hàm ch ỉ ư
ụ ế ộ
ả ủ ộ ở ế ả ộ ụ ủ ố ậ v ph i (nh thu t toán tìm ph t có m t thu c tính ộ ể i thi u)
ụ ậ ộ ộ F bi n f thành m t ph thu c hàm đ y đ nh trong thu t ướ B (cid:0) c 1: f (cid:0)
ế ủ ố ư ể ầ ủ ủ ố ậ i thi u(nh thu t toán tìm ph t ư ể i thi u) toán tìm ph t
ướ B c 2:
ụ ượ ủ ố ộ c m t ph t i
Lo i b t ạ ỏ ấ ả ậ ư ể thi u(nh thu t toán tìm ph t
ộ t c các ph thu c hàm d thùa, ta đ ủ ố ư ể i thi u)
G i t p ph t
ọ ậ ụ ố ể i thi u thu đ ượ ủ ướ c c a b c này là PTT 19
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ậ ướ B c 3: Thu t toán (tt)
ữ ụ ộ
ộ 1/ Gom nh ng ph thu c hàm thu c PTT thành nh ng nhóm Ni có ề ỉ ố ủ ữ ế ủ ả
ữ ụ ộ ộ cùng v trái.(Ni là m ng 2 chi u, n i dung c a nhóm là ch s c a nh ng ph thu c hàm có trong PTT)
ế ộ
(cid:0) ụ Thu t toán gom nhóm nh ng ph thu c hàm có cùng v trái: F (i (cid:0) ậ f: Xi (cid:0) Yi, g : Xj (cid:0) ữ Yj (cid:0) j)
ế {N u Xi Xj
ứ ủ ư Đ a g vào cùng nhóm c a nhóm ch a f
ạ Lo i nhóm g
}
ủ ế ệ ạ ấ ụ 2/Tìm các siêu khóa đ i di n cho m i nhóm Ni: L y v trái c a ph
ứ ấ ủ ủ
ộ ọ ề ộ ỗ ứ thu c hàm th nh t c a nhóm i (t c là N(1,i ) làm siêu khóa c a Ni ả và g i đó là Ki (Ki cũng là m t m ng 2 chi u) 20
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ướ
B
c 4:
ươ
ậ ậ
ng đ
ụ
ứ
ộ
ươ
ươ
ng vào nhóm FI và thành l p t p ng đ
ng:
Ni,Nj
ạ
j ) có các siêu khóa đ i di n t
ng ng là Ki , Kj
(cid:0)
ế
(cid:0)
ậ Thu t toán (tt) (cid:0) 1. H (cid:0) ệ ươ ạ 2. Gom các nhóm có siêu khóa đ i di n t ộ ụ ph thu c hàm H ch a các ph thu c hàm là các siêu khóa t (i (cid:0) ệ ươ ứ {
N u KI
Kj { Đ a nhóm Nj vào trong nhóm Ni {Ki (cid:0)
Kj ; Kj (cid:0)
Ki}
ư H = H (cid:0) ạ ỏ Lo i b nhóm Nj
}}
ạ ỏ
ụ
ờ
ỏ
ỏ
ộ
ồ
ộ
3. Lo i b kh i PTT nh ng ph thu c hàm thu c H+ đ ng th i lo i b kh i nhóm
ụ
ậ
ộ
(cid:0)
ạ ỏ ữ ữ Fi nh ng ph thu c hàm có trong t p H . A (cid:0) f: X (cid:0) ế { N u X
PTT = PTT {f}
PTT A (cid:0)
H {
(cid:0)
N u f ế
Fi thì Fi=FI (cid:0) {f}
}}
ặ
Đ t PTT1 = PTT
(cid:0)
21
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ậ ướ B c 5: Thu t toán (tt)
(cid:0) ụ ậ ộ 1/ Tìm t p ph thu c hàm PTT2 sao cho: (PTT2 H)+ (cid:0) (PTT1 (cid:0) H)
(cid:0) + f (cid:0) PTT1
ế { N u {{PTT1 (cid:0) f} (cid:0) H }+ = {PTT1 (cid:0) H }+ thì
{ PTT1 = PTT1 f
(cid:0) N u f ế Fi thì FI = FI (cid:0) {f}}}
PTT2 = PTT1
I t
ộ ươ ứ 2 Đ a các ph thu c hàm thu c H vào các nhóm F ế ng ng(có v
ư ộ ớ ụ ươ ứ ệ ủ ạ ng ng v i siêu khóa đ i di n c a nhóm nào thì đ a vào
(cid:0) H
22 (cid:0) ệ ạ { ư trái t nhóm đó) Y (cid:0) f: X (cid:0) nhóm FI có siêu khóa đ i di n là Ki
(cid:0) ế ư { N u X Ki (cid:0) PTT thì Đ a f vào nhóm Fi } }
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ậ Thu t toán (tt)
ướ B c 6:
Thành l p l
ậ ượ ồ c đ CSDL C = {
V i Fi là các ph thu c hàm có trong nhóm FI ộ
ụ ớ
và Qi là các thu c tính có tham gia vào các ph thu c hàm trong FI
ụ ộ ộ
ướ B c 7:
Ki m tra quá trình t ng h p nh trên có b o toàn thông tin không ? ư
ể ả ợ
ụ ả ổ ộ có b o toàn ph thu c hàm hay không ?
Tìm t
ấ ả ủ ế ạ ổ t c các khóa c a quan h ph quát, n u có siêu khóa đ i
ệ ủ ệ ệ ứ ấ ỳ ộ
ợ ổ
ượ ế ệ ầ ộ ộ
ả ớ ậ ỗ ượ ớ ừ ộ ổ di n cho nhóm nào đó ch a b t k m t khóa nào c a quan h ph ụ ả quát thì là phép t ng h p trên là b o toàn thông tin và b o toàn ph thu c hàm, n u không thì c n thêm m t quan h Q* m i vào l c ồ đ CSDL v a tìm đ c v i Q* là m t khóa, F* là t p r ng.
23
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ậ
Thu t toán (tt)
ậ
ướ
Thu t toán cho b
c 7 là:
ủ
ủ
ệ
ộ
ổ
ộ
SI , Kj (Si là siêu khóa c a m t nhóm, Kj là m t khóa c a quan h ph quát
ế
{ N u Kj Si thì
ụ
ả
ả
ộ
{
B o toàn thông tin và b o toàn ph thu c hàm =đúng
Break; }
}
ụ
ế
ả
ả
ộ
N u b o toàn thông tin và b o toàn ph thu c hàm thì
ụ
ả
ộ
ả B o toàn thông tin và b o toàn ph thu c hàm
Ng
ượ ạ c l
i
ụ
ầ
ặ
ả
ộ
ộ
"Không b o toàn thông tin ho c không bào toàn ph thu c hàm, c n thêm m t ệ quan h sau:"
Q(Q*,F*)
ủ
ệ
ổ
ộ
Q* ={M t khóa c a quan h ph quát }
C = C (cid:0) V i ớ F* = (cid:0)
24
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ệ
ậ
ụ Ví d : Cho l
c đ quan h Q(ABCDGH) vào t p PTH
F={
A, 2.AG (cid:0)
B,
A,
C,
H}
ượ ồ 1.GH (cid:0) 3.CD (cid:0) G, 4.GH (cid:0) D, 5.C (cid:0) 6.BH (cid:0) 7.CD (cid:0) ả ế ướ
ế
K t qu đ n b
c 2: PTT(F) = F
ế
B
c 3
ướ : Gom nhóm cùng v trái
Nhóm 1={1,4}; Nhóm 2={2}; Nhóm 3={3,7}; Nhóm 4={5} 25 Nhóm 5={6}
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ươ
ươ
Gom các nhóm có khóa t
ng đ
ng
ướ c 4: B H ={GH (cid:0)
CD,CD (cid:0)
GH}
Nhóm 1={1,4,3,7}; Nhóm 2={2}; Nhóm 4={5};
Nhóm 5={6}
ữ
ụ
ạ
ộ
ỏ
Tìm PTT1: Lo i kh i nhóm Fi nh ng ph thu c hàm
còn trong H
Nhóm 1={1}; Nhóm 2={2}; Nhóm 4={5}; Nhóm
5={6}
A,
AG (cid:0)
B,
C (cid:0)
A,
PTT1={ GH (cid:0) BH (cid:0)
C}
26
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ữ
ạ
B
ụ ỏ Tìm PTT2 và lo i kh i nhóm Fi nh ng ph
c 5: ộ
ướ thu c hàm có trong H
Nhóm 2={2}; Nhóm 4={5}; Nhóm 5={6} PTT2={AG (cid:0)
A; BH (cid:0)
B; C (cid:0)
C}
ư
Đ a H vào các nhóm:
Nhóm 1={1,4,3,7} Nhóm 2={2}
Nhóm 4={5} A, 4.GH (cid:0)
Nhóm 5={6} D, 3.CD (cid:0) G, 7.CD (cid:0)
F1={1.GH (cid:0)
B}; F3={5.C (cid:0)
A}; F4={6.BH (cid:0)
H} ; C} 27
F2={2.AG (cid:0)
Ậ Ổ
Ợ
Ế
4. TI P C N T NG H P … (tt)
ướ
B
c 6:
C={
ả ổ
ả
ả
ợ
B
c 7:
K t qu t ng h p b o toàn thông tin và b o ụ
ộ
ế ướ toàn ph thu c hàm
28
