Môn C S D LI UƠ Ở Ữ Ệ
Ch ng 5:ươ Ph thu c ụ ộ
hàm và m t s ng d ngộ ố ứ ụ
2
N i dungộ
1. PH THU C HÀMỤ Ộ
Đnh Nghĩa Ph Thu c Hàmị ụ ộ
M t s tính ch t c a ph thu c hàm - h lu t d n ộ ố ấ ủ ụ ộ ệ ậ ẫ
armstrong
2. BAO ĐÓNG C A T P PH THU C HÀM F & C A Ủ Ậ Ụ Ộ Ủ
T P THU C TÍNH XẬ Ộ
Bao đóng c a t p ph thu c hàm Fủ ậ ụ ộ
Bao đóng c a t p thu c tính Xủ ậ ộ
3. THU T TOÁN TÌM BAO ĐÓNG F+ VÀ X+, BÀI Ậ
TOÁN THÀNH VIÊN
Bài toán thành viên
Thu t toán tìm bao đóng c a m t t p thu c tính (X) ậ ủ ộ ậ ộ
3
N i dung (tt)ộ
4. PH T I THI U C A M T T P PH THU C HÀMỦ Ố Ể Ủ Ộ Ậ Ụ Ộ
T p Ph Thu c Hàm T i Thi u ậ ụ ộ ố ể
T p Ph Thu c Hàm T ng Đngậ ụ ộ ươ ươ
Thu t Toán Tìm Ph T i Thi u C a M t T p Ph Thu c Hàmậ ủ ố ể ủ ộ ậ ụ ộ
5. KHÓA C A L C Đ QUAN H - M T S THU T TOÁN Ủ ƯỢ Ồ Ệ Ộ Ố Ậ
TÌM KHÓA
Đnh Nghĩa ị
Thu t toán tìm m t khóa c a m t l c đ quan h Qậ ộ ủ ộ ượ ồ ệ
Thu t Toán Tìm T t C Các Khóa C a M t L c Đ Quan H ậ ấ ả ủ ộ ượ ồ ệ
6. D NG CHU N C A L C Đ QUAN HẠ Ẩ Ủ ƯỢ Ồ Ệ
D ng chu n 1, 2, 3ạ ẩ
D ng chu n Boyce Coddạ ẩ
4
1. PH THU C HÀMỤ Ộ
Ph thu c hàm (functional dependancy) là m t công c dùng đ ụ ộ ộ ụ ể
bi u di n m t cách hình th c các ràng bu c toàn v n. ể ễ ộ ứ ộ ẹ
Đnh Nghĩa Ph Thu c Hàmị ụ ộ
Cho l c đ quan h Q v i {Aượ ồ ệ ớ 1,A2,…,An} là t p các thu c tính. X, ậ ộ
Y là hai t p con khác r ng c a Q. ậ ỗ ủ
Ta nói X xác đnh Y (hay Y ph thu c hàm vào X) n u v i r là m t ị ụ ộ ế ớ ộ
quan h trên Q và n u hai b tệ ế ộ 1,t2 b t k thu c r mà tấ ỳ ộ 1.X = t2.X ==>
t1.Y = t2.Y. Khi đó ta ký hi u là X ệ Y
Ph thu c hàm X ụ ộ X đc g i là ph thu c hàm hi n nhiên. ượ ọ ụ ộ ể
ng i ta th ng dùng F đ ch t p các ph thu c hàm đnh nghĩa ườ ườ ể ỉ ậ ụ ộ ị
trên Q. Vì Q h u h n nên F cũng h u h n, ta có th đánh s các ph ữ ạ ữ ạ ể ố ụ
thu c hàm c a F là fộ ủ 1, f2, .., fm.
Quy c r ng ch c n mô t các ph thu c hàm không hi n nhiên ướ ằ ỉ ầ ả ụ ộ ể
trong t p F (các ph thu c hàm hi n nhiên đc ng m hi u là đã có ậ ụ ộ ể ượ ầ ể
trong F}.
5
1. PH THU C HÀM (tt)Ụ Ộ
M t s tính ch t c a ph thu c hàm - h lu t d n armstrong ộ ố ấ ủ ụ ộ ệ ậ ẫ
Đ có th xác đnh đc các ph thu c hàm khác t t p ph thu c ể ể ị ượ ụ ộ ừ ậ ụ ộ
hàm đã có, ta dùng h tiên đ Armstrong (1974), g m các lu t sau:ệ ề ồ ậ
v i X,Y,Z,W ớ Q+
1. Lu t ph n x :ậ ả ạ X X
2. Lu t thêm vào:ậX Y ==> XZ YZ
3. Lu t b c c u:ậ ắ ầ X Y, Y Z ==> X Z
4. Lu t b c c u gi :ậ ắ ầ ả Cho X Y, WY Z ==> XW Z
5. Lu t h p: ậ ợ Cho X Y, X Z ==> X YZ
6. Lu t phân rã:ậCho X Y, Z Y ==> X Z
(các h tiên đ 1,2,3 đc g i chung là H lu t d n Armstrong)ệ ề ượ ọ ệ ậ ẫ