Bài giảng Hệ cơ sở dữ liệu - Chương 9: Phụ thuộc hàm
lượt xem 10
download
Bài giảng "Hệ cơ sở dữ liệu - Chương 9: Phụ thuộc hàm" cung cấp cho người học các kiến thức: Dư thừa dữ liệu, phụ thuộc hàm, hệ tiên đề trong Amstrong, bao đóng của tập thuộc tính, giải thuật tìm khóa cho lược đồ quan hệ. Mời các bạn cùng tham khảo nội dung chi tiết.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Hệ cơ sở dữ liệu - Chương 9: Phụ thuộc hàm
- Ch ương 9 PhỤ thuỘc hàm (Functional Dependency) 1 Trần Thi Kim Chi
- Nội dung n Dư thừa dữ liệu n Phụ thuộc hàm n Hệ tiên đề Amstrong n Bao đóng của tập phụ thuộc hàm n Bao đóng của tập thuộc tính n 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) n 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 n 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 n 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 TenMH SoTC Điem 1111 Mai CSDL Cơ Sở Dữ Liệu 4 9 1111 Mai KTMT Kiến Trúc Máy Tính 4 8 5556 Long CSDL Cơ Sở Dữ Liệu 4 8 5556 Long KTMT Kiến Trúc Máy Tính 4 8 9876 Son CSDL Cơ Sở Dữ Liệu 4 7 n Khóa chính của bảng KETQUA? MaSv + MaMH n 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à Trần Thi Kim Chi MaSv + MaMH 4 ¨ Dị thường khi xoá bộ (Deletion anomalies): Nếu xóa bản
- Phụ thuộc hàm (Functional Dependency) n Phụ thuộc hàm mô tả mối liên hệ giữa các thuộc tính n 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 n Có thể biểu diễn RBTV bằng phụ thuộc hàm. n Ứ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) n 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. n Đị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) n Phụ thuộc hàm là 1 đặc điểm ngữ nghĩa của các thuộc tính, được xem là 1 ràng buộc giữa các thuộc tính. n Ví dụ: Một nhân viên chỉ có 1 mức lương nhưng nhiều nhân viên có thể có cùng 1 mức lương Emp_ID Salary Salary Emp_ID n Phụ thuộc hàm được xác định dựa vào quy tắc nghiệp vụ được xác định trên lược đồ quan hệ 7 Trần Thi Kim Chi 7
- Phụ thuộc hàm (Functional Dependency -FD) n Từ quy tắc bao toa ̉ ̀n thực thê ̉ nếu X là 1 candidate key thì tất cả các thuộc tính Y của lược đồ R sẽ phải phụ thuộc hàm vào X n Ví dụ: trong lược đồ PROFESSOR có ProfId là primary key nên: ProfId Name, Qualification n Có 1 số FD trong lược đồ sẽ gây ra dư thừa dữ liệu. 8 Trần Thi Kim Chi 8
- Phụ thuộc hàm (Functional Dependency -FD) Ví dụ FD và dư thừa dữ liệu n Xét lược đồ PERSON(SSN, Name, Address,Hobby) với quy tắc là 1 người có thể có nhiều sở thích (hobby) ¨ SSN,Hobby SSN, Name, Address,Hobby n Bất thường xảy ra khi một người có nhiều sở thích thay đổi địa chỉ 9 Trần Thi Kim Chi 9
- Phụ thuộc hàm (Functional Dependency -FD) n Ví dụ : Cho quan hệ phancong sau : Phancong (Phicong, maybay, ngaykh, giokh) Tùng 83 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 Trần Thi Kim Chi 10
- Phụ thuộc hàm (Functional Dependency -FD) n Quan hệ Phancong diễn tả phi công nào PC MB NKH GKH 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 Tùng 83 9/8 10:15a các điều kiện ràng buộc sau : Ø Mỗi máy bay có một giờ Tùng 116 10/8 1:25p khởi hành duy nhất. Minh 281 8/8 5:50a Ø Nếu biết phi công, biết Minh 301 12/8 6:35p ngày giờ khởi hành thì biết được máy bay do phi công Minh 83 13/8 10:15a lái. Nghia 83 11/8 10:15a Ø Nếu biết máy bay, biết Nghia 116 12/8 1:25p ngày giờ khởi hành thì biết Trần Thi Kim Chi 11 phi công lái chuyến máy bay
- Phụ thuộc hàm (Functional Dependency -FD) n 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 : PC MB NKH GKH Ø MAYBAY xác định GIOKH. Tùng 83 9/8 10:15a Ø {PHICONG, NGAYKH, GIOKH} xác định MAYBAY. Ø {MAYBAY, NGAYKH} xác định PHICONG Tùng 116 10/8 1:25p hay Minh 281 8/8 5:50a GIOKH phụ thuộc hàm vào MAYBAY. Ø Ø MABAY phụ thuộc hàm vào {PHICONG, Minh 301 12/8 6:35p NGAYKH, GIOKH} . Ø PHICONG phụ thuộc hàm vào {MAYBAY, Minh 83 13/8 10:15a NGAYKH}. Và được ký hiệu như sau : Nghia 83 11/8 10:15a Ø {MAYBAY} GIOKH Nghia 116 12/8 1:25p Ø {PHICONG, NGAYKH, GIOKH) MAYBAY Ø {MAYBAY, NGAYKH} PHICONG Trần Thi Kim Chi 12
- Phụ thuộc hàm (Functional Dependency -FD) Ví dụ n Với quan hệ này, cho biết có các phụ thuộc hàm sau không? A B C 1. A B 1 5 3 Không vì t1 [A] = t4 [A], but t1 [B] t4 2 6 4 [B]. 3 7 4 3. A C 1 4 3 Có vì t1 [A] = t4 [A], and t1 [C] = t4 [C]. 5. AB C Có vì ti [AB] tj [AB] for i j . Trần Thi Kim Chi 13
- Phụ thuộc hàm (Functional Dependency -FD) R A B C D E F A B C D E F a1 b 1 c 1 d 1 e 1 f 1 a1 b1 c1 d1 e1 f1 a1 b 1 c2 d 1 e2 f3 a1 b1 c2 d1 e2 f3 a2 b 1 c2 d3 e2 f3 a2 b1 c2 d3 e2 f3 a3 b2 c3 d4 e3 f2 a2 b 1 c3 d3 e4 f4 a2 b1 c3 d3 e4 f4 a4 b 1 c 1 d5 e 1 f 1 a3 b2 c3 d4 e3 F2 a4 b1 c1 d5 e1 f1 n Các phụ thuộc hàm của quan hệ R là: ¨A B ¨A D ¨B,C E,F n Các bộ của quan hệ r(R) Trần Thicó KimviChi phạm các FD này 14 không? 14
- Giải thuật kiểm tra phụ thuộc hàm n Thuật toán Satifies : Cho quan hệ r và X, Y là hai tập con của Q+. Thuật toán Satifies sẽ trả về giá trị True nếu X Y ngược lại là False n Bài toán: cho quan hệ r và 1 phụ thuộc hàm f:X Y. Kiểm tra xem r thỏa mãn f hay không? n Function Satisfies(r,f:X Y) ¨ Sắp thứ tự các bộ trong r theo các thuộc tính của X ¨ If mỗi tập các bộ có cùng giá trị X thì có cùng giá trị Y then n Satisfies = true ¨ Else n Satisfies = false 15 Trần Thi Kim Chi
- Thuật toán Satifies Phancong (Phicong, maybay, ngaykh, giokh) Tùng 83 9/8 10:15a Minh 83 13/8 10:15a Nghia 83 11/8 10:15a Nghia 116 12/8 1:25p Tùng 116 10/8 1:25p MAYBAY GIOKH Minh 281 8/8 5:50a Cho kết quả là True Nghia 281 98 5:50a Minh 281 13/8 5:50a Minh 301 12/8 6:35p Trần Thi Kim Chi 16
- Thuật toán Satifies SATIFIES (Phicong, maybay, ngaykh, giokh) Tùng 83 9/8 10:15a Minh 83 13/8 10:15a MAYBAY GIOKH cho kết quả Nghia 83 11/8 10:15a là False Nghia 116 12/8 1:25p Tùng 116 10/8 1:25p Minh 281 8/8 5:50a Nghia 281 98 5:50a Minh 281 13/8 1:50a Minh 301 12/8 6:35p Trần Thi Kim Chi 17
- Bài tập 1: Cách nhận biết một phụ thuộc hàm thỏa trên 1 thể hịên của quan hệ Q ? Thuật toán Satifies Phụ thuộc hàm nào sau đây thỏa r (A, B, C, D, E )? A D , AB D , AB B, AB E a1 b1 c1 d1 e1 a1 b1 c2 d1 d1 a2 b1 c3 d3 e1 a2 b1 c4 d3 e1 a3 b2 c5 d1 e1 Trần Thi Kim Chi 18
- Bài tập 2: Tìm phụ thuộc hàm thỏa trên 1 thể hịên của quan hệ R ? Thuật toán Satifies R A B C D E F A B C D E F a1 b 1 c 1 d 1 e 1 f 1 a1 b1 c1 d1 e1 f1 a1 b 1 c2 d 1 e2 f3 a1 b1 c2 d1 e2 f3 a2 b 1 c2 d3 e2 f3 a2 b1 c2 d3 e2 f3 a3 b2 c3 d4 e3 f2 a2 b1 c3 d3 e4 f4 a2 b 1 c3 d3 e4 f4 a4 b 1 c 1 d5 e 1 f 1 a3 b2 c3 d4 e3 f2 a4 b1 c1 d5 e1 f1 n Các phụ thuộc hàm của quan hệ R là: ¨ A B ¨ A D ¨ B,C E,F n Các bộ của quan hTrần ệ r(R) có vi ph Thi Kim Chi ạm các FD này không? 19
- Thuật toán Satifies Phụ thuộc hàm nào sau đây thỏa r’ A D , AB D a1 b1 c1 d1 e1 a1 b2 c2 d2 d1 Phụ thuộc hàm nào sau đây thỏa q a2 b1 c3 d3 e1 BC E , DE C,A BCDE a2 b1 c4 d3 e1 a1 b1 c1 d1 e1 a3 b2 c5 d1 e1 a2 b2 c2 d2 e2 a3 b1 c1 d1 e1 a4 b2 c2 d2 e2 a5 b1 c1 d3 e1 Trần Thi Kim Chi 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Hệ cơ sở dữ liệu: Chương 2 - ThS. Trịnh Thị Ngọc Linh
48 p | 156 | 19
-
Bài giảng Hệ cơ sở dữ liệu: Chương 1 - ThS. Trịnh Thị Ngọc Linh
33 p | 135 | 16
-
Bài giảng Hệ cơ sở dữ liệu: Chương 6 - ThS. Trịnh Thị Ngọc Linh
54 p | 109 | 16
-
Bài giảng Hệ cơ sở dữ liệu: Chương 3 - ThS. Trịnh Thị Ngọc Linh
61 p | 116 | 13
-
Bài giảng Hệ cơ sở dữ liệu - Chương 4: Mô hình quan hệ - Relational model
78 p | 94 | 13
-
Bài giảng Hệ cơ sở dữ liệu: Chương 8 - ThS. Trịnh Thị Ngọc Linh
15 p | 119 | 12
-
Bài giảng Hệ cơ sở dữ liệu: Chương 5 - ThS. Trịnh Thị Ngọc Linh
31 p | 110 | 11
-
Bài giảng Hệ cơ sở dữ liệu: Chương 7 - ThS. Trịnh Thị Ngọc Linh
18 p | 124 | 11
-
Bài giảng Hệ cơ sở dữ liệu: Chương 4 - ThS. Trịnh Thị Ngọc Linh
47 p | 93 | 10
-
Bài giảng Hệ cơ sở dữ liệu: Chương 9 - ThS. Trịnh Thị Ngọc Linh
9 p | 125 | 9
-
Bài giảng Hệ cơ sở dữ liệu: Chương 5 - Trần Thị Kim Chi
112 p | 66 | 8
-
Bài giảng Hệ cơ sở dữ liệu: Chương 0 - TS. Lê Thị Tú Kiên
9 p | 19 | 6
-
Bài giảng Hệ cơ sở dữ liệu: Chương 1 - TS. Lê Thị Tú Kiên
86 p | 26 | 6
-
Bài giảng Hệ cơ sở dữ liệu: Chương 2.1 - TS. Lê Thị Tú Kiên
56 p | 23 | 6
-
Bài giảng Hệ cơ sở dữ liệu: Chương 5.1 - TS. Lê Thị Tú Kiên
69 p | 29 | 5
-
Bài giảng Hệ cơ sở dữ liệu - Chương 1: Giới thiệu về cơ sở dữ liệu
116 p | 92 | 3
-
Bài giảng Hệ cơ sở dữ liệu - Nguyễn Việt Cường
47 p | 26 | 3
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn