Nội dung

Chương 9 phỤ thuỘc hàm (Functional dependency) Trần Thi Kim Chi 1 Nội dung       Dư thừa dữ liệu Phụ thuộc hàm Hệ tiên đề Amstrong Bao đóng của tập phụ thuộc hàm Bao đóng của tập thuộc tính Giải thuật Tìm khóa cho lược đồ quan hệ 2 Trần Thi Kim Chi Dư thừa dữ liệu - (Data redundancy)    Mục đích của thiết kế CSDL là gom các thuộc tính thành các quan hệ sao cho giảm thiểu dư thừa dữ liệu Hậu quả của dư thừa dữ liệu:  Lãng phí không gian đĩa  Các bất thường khi cập nhật Ba loại bất thường:  Bất thường khi thêm vào  Bất thường khi xóa bỏ  Bất thường khi sửa đổi 3 Trần Thi Kim Chi Ví dụ MaSv HoTen MaMH 1111 1111 5556 5556 9876 Mai Mai Long Long Son CSDL KTMT CSDL KTMT CSDL   TenMH Cơ Sở Dữ Liệu Kiến Trúc Máy Tính Cơ Sở Dữ Liệu Kiến Trúc Máy Tính Cơ Sở Dữ Liệu SoTC 4 4 4 4 4 Điem 9 8 8 8 7 Khóa chính của bảng KETQUA?  MaSv + MaMH Các bất thường:  Dư thừa dữ liệu (Redundancy): Thông tin cá nhân bị trùng lặp  Không nhất quán (Inconsistency): Nếu đổi bản ghi thứ nhất tên Mai thành Nga  Không nhất quán dữ liệu  bản ghi 2 vẫn tên Mai  Dị thường khi thêm bộ (Insertion anomalies): Nếu bổ sung thêm người mới tên là Hùng nhưng chưa thi  không thể tạo bản ghi mới được  vì khóa chính là MaSv + MaMH  Dị thường khi xoá bộ (Deletion anomalies): Nếu xóa bản ghi 4 cuối  thì thông tin về môn CSDL cũng mất Phụ thuộc hàm (Functional Dependency)     Phụ thuộc hàm mô tả mối liên hệ giữa các thuộc tính Dựa vào phụ thuộc hàm để thiết kế lại CSDL, loại bỏ các dư thừa dữ liệu Có thể biểu diễn RBTV bằng phụ thuộc hàm. Ứng dụng của phụ thuộc hàm là giải quyết các bài toán về : Tìm khóa. Tìm phủ tối thiểu. Chuẩn hoá cơ sở dữ liệu. 5 Trần Thi Kim Chi Phụ thuộc hàm (Functional Dependency)  Cho lược đồ quan hệ R(U), r là 1 quan hệ bất kỳ trên R, X và Y là 2 tập thuộc tính con.  Định nghĩa: Phụ thuộc hàm (FD) f: X  Y trên lược đồ quan hệ R nếu và chỉ nếu mỗi giá trị X trong r có quan hệ chính xác với 1 giá trị Y trong r. Nghĩa là bất kể khi nào 2 bộ của r có cùng giá trị X thì cũng có cùng giá trị Y. t1, t2  r(R): t1[X] = t2[X]  t1[Y]= t2[Y]  X là vế trái, ký hiệu left(f) hay còn gọi là determinant  Y là vế phải, ký hiệu right(f) hay còn gọi là dependent 6 Trần Thi Kim Chi Phụ thuộc hàm (Functional Dependency -FD)  Quan hệ Phancong diễn tả phi công nào lái máy bay nào và máy bay khởi hành vào thời gian nào. Quan hệ trên phải tuân theo các điều kiện ràng buộc sau :    Mỗi máy bay có một giờ khởi hành duy nhất. Nếu biết phi công, biết ngày giờ khởi hành thì biết được máy bay do phi công lái. Nếu biết máy bay, biết ngày giờ khởi hành thì biết phi công lái chuyến máy bay ấy. Trần Thi Kim Chi PC Tùng MB 83 NKH GKH 9/8 10:15a Tùng 116 10/8 1:25p Minh 281 8/8 5:50a Minh 301 12/8 6:35p Minh 83 13/8 10:15a Nghia 83 11/8 10:15a Nghia 116 12/8 1:25p 7 Phụ thuộc hàm (Functional Dependency -FD)  Các ràng buộc này là các ví dụ về phụ thuộc hàm và được phát biểu lại như sau :  MAYBAY xác định GIOKH.  {PHICONG, NGAYKH, GIOKH} xác định MAYBAY.  {MAYBAY, NGAYKH} xác định PHICONG hay GIOKH phụ thuộc hàm vào MAYBAY.  MABAY phụ thuộc hàm vào {PHICONG, NGAYKH, GIOKH} .  PHICONG phụ thuộc hàm vào {MAYBAY, NGAYKH}. Và được ký hiệu như sau :  {MAYBAY}  GIOKH NGAYKH, GIOKH)   {PHICONG, MAYBAY  {MAYBAY, NGAYKH}  PHICONG  Trần Thi Kim Chi PC Tùng MB 83 NKH GKH 9/8 10:15a Tùng 116 10/8 1:25p Minh 281 8/8 5:50a Minh 301 12/8 6:35p Minh 83 13/8 10:15a Nghia 83 11/8 10:15a Nghia 116 12/8 1:25p 8 Phụ thuộc hàm (Functional Dependency -FD) Ví dụ  Với quan hệ này, cho biết có các phụ thuộc hàm sau không? A B C 1. 1 2 5 3 6 4 Không vì t1 [A] = t4 [A], but t1 [B]  t4 [B]. 2. 3 7 4 Có vì t1 [A] = t4 [A], and t1 [C] = t4 [C]. 1 4 3 3. AB AC AB  C Có vì ti [AB]  tj [AB] for i  j . Trần Thi Kim Chi 9 Phụ thuộc hàm (Functional Dependency -FD) R   A a1 a1 a2 a3 a2 a4 B b1 b1 b1 b2 b1 b1 C c1 c2 c2 c3 c3 c1 D d1 d1 d3 d4 d3 d5 E e1 e2 e2 e3 e4 e1 F f1 f3 f3 f2 f4 f1 A B C D E F a1 b1 c1 d1 e1 f1 a1 b1 c2 d1 e2 f3 a2 b1 c2 d3 e2 f3 a2 b1 c3 d3 e4 f4 a3 b2 c3 d4 e3 F2 a4 b1 c1 d5 e1 f1 Các phụ thuộc hàm của quan hệ R là: A  B A  D B,C  E,F Các bộ của quan hệ r(R) có vi phạm các FD này không? Trần Thi Kim Chi 10