Cơ sở dữ liệu - Chương 5: Phụ thuộc hàm và một số ứng dụng

Nội dung text: Cơ sở dữ liệu - Chương 5: Phụ thuộc hàm và một số ứng dụng

1. 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) 2
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 3
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 {A1,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ộ t1,t2 bất kỳ thuộc r mà t1.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à f1, 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}. 4
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) 5
6. 2. BAO ĐÓNG Bao đóng của tập phụ thuộc hàm F ◼ Bao đóng của tập phụ thuộc hàm F (thường ký hiệu là F+) là tập hợp tất cả các phụ thuộc hàm có thể suy ra từ F dựa trên các tiên đề Armstrong. Ví dụ: Cho r là quan hệ trên lược đồ quan hệ Q(A,B,C,D) và tập F được cho như sau: F = {A → B; B → C; A → D ; B → D} khi đó F+= { A → B; B → C; A → D ; B → D;A → BD; A → BCD; A → C; A → CD; A → BC; B → CD; .} Rõ ràng F  F+ ◼ Các tính chất của tập F+ u Tính phản xạ: Với mọi tập phụ thuộc hàm F+ ta luôn luôn có F  F+ u Tính đơn điệu: Nếu F  G thì F+  G+ u Tính lũy đẳng: Với mọi tập phụ thuộc hàm F ta luôn luôn có F++ = F+. 6
7. 2. BAO ĐÓNG (tt) Bao đóng của tập thuộc tính X ◼ Cho r là quan hệ trên lược đồ quan hệ Q. giả sử F là tập các phụ thuộc hàm trong Q, X  Q+. Bao đóng của tập thuộc tính X đối với F ký hiệu là X+ + (hoặc X F) là tập tất cả các thuộc tính A của Q được suy ra từ X dựa vào hệ tiên đề Armstrong và các phụ thuộc hàm trong F. X+ = {A : A Q và X → A F+} 7
8. 2. BAO ĐÓNG (tt) Bao đóng của tập thuộc tính X – Ví dụ Q(A,B,C,D,E,G); F={A → C; A → EG; B → D; G → E}; X={A,B}; Y={C,G,D} Thì X+ = {A,B,C,D,E,G}; Y+ = {C,G,D,E} Tương tự như tập bao đóng của tập PTH F+, tập bao đóng X+ cũng chứa các phần tử của X+, tức là X  + X . 8
9. 2. BAO ĐÓNG (tt) Bao đóng của tập thuộc tính X – Ví dụ Nếu X,Y là các tập con của tập thuộc tính Q thì ta có các tính chất sau đây: Tính phản xạ:X  X+ Tính đơn điệu: Nếu X  Y thì X+  Y+ Tính lũy đẳng: X++ = X+ (XY)+  X+Y+ (X+Y)+ = (XY+)+ = (X+Y+)+ X → Y F+ Y  X+ X → Y Y+  X+ X → X+ và X+ → X + + X = Y X → Y và Y → X 9
10. 3. TT TÌM BAO ĐÓNG F+ VÀ X+ Bài toán thành viên ◼ Trên đây ta nhận thấy rằng X+ được định nghĩa thông qua F+. Một vấn đề quan trọng khi nghiên cứu lý thuyết CSDL là: Cho trước tập các PTH F và một phụ thuộc hàm f, có hay không một khẳng định f F+ ? bài toán này được gọi là bài toán thành viên. ◼ Để trả lời câu hỏi này (bài toán thành viên) không đơn giản, vì mặc dù F là rất nhỏ nhưng F+ thì có thể rất lớn. ◼ Tuy nhiên để giải bài toán thành viên, chúng ta có thể dùng tính chất 6 của tập bao đóng X+. đó là tính chất X → Y F+ Y  X . Do vậy chỉ cần tính X+ và so sánh với tập Y, ta có ngay câu trả lời X → Y F+ hay không ? Do đó, việc tính X+ được giải quyết đơn giản hơn rất nhiều. 10
11. 3. TT TÌM BAO ĐÓNG F+ VÀ X+ (tt) Thuật toán tìm bao đóng của một tập thuộc tính (X) (độ phức tạp O(N2), với N là số thuộc tính của Q) Dữ Liệu Vào Q, F, X  Q+ Dữ Liệu Ra X+ ◼ Bước 1: Đặt X+ = X ◼ Bước 2: Temp = X+  f U → V F Neáu U  X+ thì X+ = X+  V ◼ Bước 3: Nếu X+=Temp thì X+ chính là kết quả cần tìm và kết thúc thuật toán. Ngược lại trở lại bước 2. 11
12. 3. TT TÌM BAO ĐÓNG F+ VÀ X+ (tt) Thuật toán tìm bao đóng với độ phức tạp tuyến tính ◼ Bước 1: Xây dựng mảng một chiều COUNT Với COUNT(i) là số thuộc tính vế trái của phụ thuộc hàm thứ i ◼ Bước 2: Xây dựng mảng LIST với LIST(A) = {X → Y| F, A X} (lưu chỉ số PTH) ◼ Bước 3: X+ = X ◼ Bước 4: Mọi thuộc tính A X+ Giảm COUNT|X → Y| đi một nếu A X Nếu COUNT|X → Y| = 0 thì X+ = X+  Y Quay lại duyệt thuộc tính kế tiếp trong X+ cho đến khi nào duyệt hết mọi phần tử của X+ thì dừng lại. Kết quả X+ là bao đóng cần tìm. 12
13. 4. PHỦ TỐI THIỂU CỦA MỘT TẬP PTH Tập Phụ Thuộc Hàm Tối Thiểu Để có thể phục vụ quá trình thiết kế cơ sở dữ liệu, cần đưa ra thêm khái niệm tập PTH tối thiểu. Bổ đề: Mỗi tập các phụ thuộc hàm F đều được phủ bởi tập các phụ thuộc hàm G mà vế phải của các phụ thuộc hàm G chỉ gồm một thuộc tính. F được gọi là một tập phụ thuộc hàm tối thiểu nếu F thỏa đồng thời ba điều kiện sau: (a) Vế phải của F chỉ có một thuộc tính. (b) Không  X → A F và Z  X mà: F + = (F − (X → A)  (Z → A))+ (c) Không  X → A F mà: F + = (F → (X → A))+ 13
14. 4. PHỦ TỐI THIỂU CỦA MỘT TẬP PTH (tt) Trong đó điều kiện (c)bảo đảm cho tập F không có một phụ thuộc hàm nào là dư thừa, và điều kiện (b) bảo đảm không có một thuộc tính nào tham gia vế trái của phụ thuộc hàm là dư thừa. Vế phải của mỗi phụ thuộc hàm ở điều kiện (a) chỉ có một thuộc tính, nên bảo đảm không có thuộc tính nào trên vế phải là dư thừa. 14
15. 4. PHỦ TỐI THIỂU CỦA MỘT TẬP PTH Một tập PTH luôn tìm ra ít nhất một phủ tối thiểu và nếu thứ tự các phụ thuộc hàm trong tập F là khác nhau thì có thể sẽ thu được những phủ tối thiểu khác nhau. Tập Phụ Thuộc Hàm Tương Đương ◼ Cho F và G là hai tập phụ thuộc hàm, ta nói F và G tương đương (hay F phủ G hoặc G phủ F ) ký hiệu là F + = G + nếu và chỉ nếu mỗi phụ thuộc hàm thuộc F đều thuộc G + và mỗi phụ thuộc hàm thuộc G đều thuộc F + . 15
16. 4. PHỦ TỐI THIỂU CỦA MỘT TẬP PTH Thuật Toán Tìm Phủ Tối Thiểu Của Một Tập PTH ◼ Dữ liệu vào : Lược đồ quan hệ ban đầu (lược đồ quan hệ phổ quát) Q và tập phụ thuộc hàm F, số lượng phụ thuộc hàm trong F là cardF. ◼ Dữ liệu ra :Lược đồ quan hệ Q và tập phụ thuộc hàm tối thiểu của F và số lượng phụ thuộc dữ liệu trong phủ tối thiểu. Bước 1: Tách vế phải mỗi phụ thuộc hàm trong F sao cho vế phải của mỗi phụ thuộc hàm chỉ chứa một thuộc tính (đều này luôn thực hiện được do bổ đề trên)  f: X → Y F  A Y g = X → A F = F  g Cardf = Cardf + 1 Cuối  Cuối  16
17. 4. PHỦ TỐI THIỂU CỦA MỘT TẬP PTH Thuật Toán Tìm Phủ Tối Thiểu Của Một Tập PTH ◼ Bước 2: Tìm tập phụ thuộc hàm đầy đủ bằng cách loại bỏ các thuộc tính dư thừa ở vế trái của từng phụ thuộc hàm.  f X → A F  B X X' =X − B If X'→ A F+ then X = X' Cuối  Cuối  ◼ Bước 3: Loại bỏ các phụ thuộc hàm dư thừa trong F.  f F G = F – f {loại f ra khỏi F. và lưu { F – f } vào G } If F + =G + then {gọi thủ tục kiểm tra F, G tương đương ở dưới} F = G {cập nhật lại F mới} Cuối  . 17
18. 5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ Định Nghĩa ◼ Cho quan hệ Q(A1,A2, ,An) được xác định bởi tập thuộc tính Q+ và tập phụ thuộc hàm F định nghĩa trên Q, cho K  Q +. ◼ K là một khóa của Q nếu thỏa đồng thời cả hai điều kiện sau: + + + + K → Q F (hay K F= Q ) (K chỉ thỏa điều kiện 1 thì được gọi là siêu khóa) Không tồn tại K'  K sao cho K'+ = Q + ◼ Một lược đồ quan hệ có thể có nhiều khóa và tập thuộc tính không khóa cũng có thể bằng rỗng. 18
19. 5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ Thuật toán tìm một khóa của một lược đồ quan hệ Q K=Q+; Với mỗi A K do if (K-A)+ = Q then K=K-A ◼ Nếu muốn tìm các khóa khác (nếu có) của lược đồ quan hệ, ta có thể thay đổi thứ tự loại bỏ các phần tử của K. 19
20. 5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ Thuật Toán Tìm Tất Cả Các Khóa Của Một Lược Đồ Quan Hệ (Thuật toán cơ bản) ◼ Bước 1:Xác định tất cả các tập con của Q Để xác định tất cả các tập con của một lược đồ quan hệ n Q(A1,A2, ,An) ta lần lượt duyệt tất cả 2 -1 tập hợp con khác rỗng của Q+ (n là số thuộc tính của lược đồ quan hệ Q),kết quả tìm được giả sử là các tập thuộc tính: S={X1, X2, ,X2n-1 } ◼ Bước 2: Chọn trong S ra tập siêu khóa của Q Nếu một tập con Xi (i=1 ,2n-1) của Q+ có bao đóng đúng bằng Q+ thì tập con dó (theo định nghĩa trên) là một siêu khóa của Q. Giả sử ta đã có các siêu khóa là S = {S1,S2, ,Sm} ◼ Bước 3:Xây dựng tập chứa tất cả các khóa của Q từ tập S Xét mọi Si,Sj con của S (i j), nếu Si  Sj thì ta loại Sj (i,j=1 n), kết quả còn lại của S chính là tập tất cả các khóa cần tìm. 20
21. 5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ Thuật Toán Tìm Tất Cả Các Khóa Của Một Lược Đồ Quan Hệ (Thuật toán cải tiến) ◼ Một số khái niệm: Tập thuộc tính nguồn(TN) chứa tất cả các thuộc tính có xuất hiện ở vế trái và không xuất hiện ở vế phải của tập phụ thuộc hàm. Tập thuộc tính đích chứa tất cả các thuộc tính có xuất hiện ở vế phải và không xuất hiện ở vế trái của tập phụ thuộc hàm. Tập thuộc tính trung gian(TG) chứa tất cả các thuộc tính thuộc Q+ và không thuộc tập thuộc tính nguồn và cũng không thuộc tập thuộc tính đích. ◼ Dữ liệu vào: Lược đồ quan hệ phổ quát Q và tập phụ thuộc dữ liệu F 21 ◼ Dữ liệu ra: Tất cả các khóa của quan hệ
22. 5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ Thuật Toán Tìm Tất Cả Các Khóa Của Một Lược Đồ Quan Hệ (Thuật toán cải tiến) ◼ Bước 1: Tìm tập thuộc tính nguồn(TN), tập thuộc tính trung gian(TG) ◼ Bước 2: Tìm tất cả các tập con của tập trung gian gọi là Xi (bằng phương pháp duyệt nhị phân) ◼ Bước 3: If tập trung gian=  then Tập Khóa = Tập thuộc tính nguồn ; Kết thúc Ngược lại Qua bước 4 22
23. 5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ Thuật Toán Tìm Tất Cả Các Khóa Của Một Lược Đồ Quan Hệ (Thuật toán cải tiến) ◼ Bước 4: S=  Xi tập trung gian if (Tập nguồn Xi)+ = Q+ then S = S  { Tập nguồn  Xi} {S là tập các siêu khóa cần tìm} ◼ Bước 5: Loại bỏ các siêu khóa không tối tiểu  SI, Sj S if Si  Sj then Loại Sj ra khỏi Tập siêu khóa S S còn lại chính là tập khóa cần tìm. 23
24. 6. DẠNG CHUẨN CỦA LƯỢC ĐỒ Q.HỆ ◼ Chất lượng thiết kế của một lược đồ CSDL có thể được đánh giá dựa trên nhiều tiêu chuẩn trong đó sự trùng lắp thông tin và chi phí kiểm tra các ràng buộc toàn vẹn là hai tiêu chuẩn quan trọng. ◼ Thuộc tính khóa/không khóa: A là một thuộc tính khóa nếu A có tham gia vào bất kỳ một khóa nào của quan hệ, ngược lại A gọi là thuộc tính không khóa. ◼ Thuộc tính phụ thuộc đầy đủ: A là một thuộc tính phụ thuộc đầy đủ vào tập thuộc tính X nếu X → A là một phụ thuộc hàm đầy đủ (tức la không tồn tai X'  X sao cho X' → A F) 24
25. 6. DẠNG CHUẨN CỦA LĐ QH (tt) Định Nghĩa Dạng Chuẩn Một (First Normal Form) ◼ Cho lược đồ quan hệ Q, Q được gọi là đạt dạng chuẩn 1 (1NF) nếu và chỉ nếu toàn bộ các thuộc tính của Q đều mang giá trị đơn. Lược đồ quan hệ này không đạt dạng chuẩn 1 Đưa quan hệ trên về dạng chuẩn 1: 25
26. 6. DẠNG CHUẨN CỦA LĐ QH (tt) Định Nghĩa Dạng Chuẩn Hai ◼ Một lược đồ quan hệ Q đạt dạng chuẩn 2 nếu Q đạt dạng chuẩn 1 và tất cả các thuộc tính không khóa của Q đều phụ thuộc đầy đủ vào khóa. ◼ VD: Lược đồ quan hệ sau đạt chuẩn 2: Q(G,M,V,N,H,P) F={G → N; G → H; G → P; M → V; N,H,P → M} ◼ Hệ quả: Q đạt 2NF nếu Q là 1NF và tập thuộc tính không khóa của Q bằng rỗng. Nếu khóa của quan hệ chỉ có một thuộc tính thì quan hệ đó ít nhất đạt chuẩn 2. 26
27. 6. DẠNG CHUẨN CỦA LĐ QH (tt) Định Nghĩa Dạng Chuẩn Ba ◼ Một lược đồ quan hệ Q đạt dạng chuẩn 3 nếu mọi phụ thuộc hàm X→A F+ (là tập phụ thuộc không hiển nhiên định nghĩa trên Q, A là thuộc tính đơn, X là tập thuộc tính), thì một trong hai điều kiện sau được thỏa: Hoặc X chứa một khóa của Q Hoặc A là một thành viên của một khóa bất kỳ của Q ◼ Dạng chuẩn 3 còn được định nghĩa:" lược đồ quan hệ Q đạt dạng chuẩn 3 nếu Q đạt dạng chuẩn 2 và mọi thuộc tính không khóa của Q đều không phụ thuộc hàm bắc cầu vào một khóa bất kỳ của Q + " ◼ Hai định nghĩa là tương đương, tuy nhiên việc cài đặt thuật toán kiểm tra dạng chuẩn 3 theo cách thứ nhát thì hiệu quả hơn nhiều vì không phải kiểm tra tính phụ thuộc hàm bắc cầu. ◼ Hệ quả: Nếu lược đồ quan hệ Q,F mà Q không có thuộc tính không khóa thì Q đạt chuẩn 3. 27
28. 6. DẠNG CHUẨN CỦA LĐ QH (tt) Định Nghĩa Dạng Chuẩn BCK ◼ Một lược đồ quan hệ Q ở dạng chuẩn BCK nếu với mỗi phụ thuộc hàm không hiển nhiên X → A F thì X chứa một khóa của Q. ◼ (Nếu Q đạt chuẩn BC thì Q đạt chuẩn 3) ◼ ĐỊNH LÝ : Các lớp dạng chuẩn của một lược đồ quan hệ có quan hệ lồng nhau: nghĩa là lớp sau nằm trọn trong lớp trước. BCNF  3NF  2NF  1NF VD: Q(A,C,D,E,I,B) F={A,C,D→E,B,I; C,E→A,D} 28