Phụ thuộc hàm

1 Nội dung  Dư thừa dữ liệu  Phụ thuộc hàm  Giải thuật kiểm tra 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  Tìm khóa 2 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 (anomalies) khi cập nhật 3 Bâ ́t thường dữ liệu (Data redundancy)  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 4 Ví dụ về bất thường dữ liệu SSN Name Address Hobby 111111111 111111111 555666777 555666777 987654321 John Doe John Doe Mary Doe Mary Doe Bart Simpson 123 Main St. 123 Main St. 7 Lake Dr. 7 Lake Dr. Fox 5 TV Stamps Coins Hiking Skating Acting 5  Khóa chính của bảng PERSON?  SSN + Hobby  Thông tin cá nhân bị trùng lặp Ví dụ về bâ ́t thường dữ liệu  Nếu John thay đổi chỗ ở  update anomaly  Nếu bổ sung thêm người mới nhưng chưa biết sở thích  không thể tạo bản ghi mới được  insertion anomaly  Nếu Bart Simpson chỉ có 1 sở thích  xóa sở thích Acting như thế nào  Delete anomaly 6 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 trong 1 bảng  Dựa vào phụ thuộc hàm để tinh chỉnh CSDL, loại bỏ các dư thừa dữ liệu 7 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.  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. t1, t2  r(R): t1[X] = t2[X]  t1[Y]= t2[Y] 8 Phụ thuộc hàm (Functional Dependency)  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 9 Ví dụ phụ thuô ̣c hàm  Cho quan hệ như hình vẽ, hãy xác định các FD?  AB  C 10 Giải thuật kiểm tra phụ thuộc hàm  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?  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  Satisfies = true  Else  Satisfies = false 11 Functional Dependencies  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? 12 R A B C D E F a1 b1 c1 d1 e1 f1 a1 b1 c2 d1 e2 f3 a2 b1 c2 d3 e2 f3 a3 b2 c3 d4 e3 f2 a2 b1 c3 d3 e4 f4 a4 b1 c1 d5 e1 f1 Phụ thuộc hàm (Functional Dependency -FD) 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. Phụ thuộc hàm được xác định dựa vào quy tắc nghiệp vụ 13 Ví dụ: Phụ thuộc hàm  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 14 Phụ thuộc hàm (Functional Dependency -FD)  Từ quy tắc bảo toà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  PROFESSOR(ProfId, Name, Qualification) ProfId  Name, Qualification 15 FD và dư thừa dữ liệu  Có 1 số FD trong lược đồ gây ra dư thừa dữ liệu.  Vd: Xét lược đồ PERSON(SSN, Name, Address,Hobby)  Từ khóa chính xác định được FD: SSN,Hobby  SSN, Name, Address,Hobby  Từ quy tắc nghiệp vụ, xác định được FD: Emp_ID  Name, Dept_Name, Salary  Bất thường xảy ra khi một người có nhiều sở thích thay đổi địa chỉ 16 FD và dư thừa dữ liệu 17 SSN Name Address Hobby 111111111 111111111 555666777 555666777 987654321 John Doe John Doe Mary Doe Mary Doe Bart Simpson 123 Main St. 123 Main St. 7 Lake Dr. 7 Lake Dr. Fox 5 TV Stamps Coins Hiking Skating Acting Lược đồ phụ thuộc ha ̀m  Lược đồ phụ thuộc hàm để biểu diễn phụ thuộc hàm  Vd: Emp_ID  Name, Dept_Name, Salary 18 Lược đồ phụ thuộc ha ̀m  Emp_ID  Name, Dept_Name, Salary  Emp_ID, Course_Title  Date_Completed 19 Phụ thuộc hàm tầm thường  Phụ thuộc hàm tầm thường ( trivial FD) hay phụ thuộc hàm hiển nhiên X Y nếu Y  X  Ví dụ: Name, Address  Name 20 Tập phụ thuộc hàm  Gọi F là 1 tập phụ thuộc hàm trên R nếu mọi phụ thuộc hàm trong F đều là phụ thuộc hàm trên R  Số tập con có thể có của R = {A1,A2,...,An} là 2n.  Ứng với 2 tập con sẽ tạo thành 1 FD  Số FD có thể có được là 1 chỉnh hợp lặp chập 2 của 2n phần tử. Số FD tối đa có thể có (2n)2=22n. 21 Tập phụ thuộc hàm  FD được dùng để thể hiện các ràng buộc bảo toàn (integrity constraint), vì vậy DBMS cần phải quản lý các FD.  Với 1 tập S chứa toàn bộ các FD của 1 lược đồ, có cách nào tìm ra 1 tập T  S sao cho mọi FD của S đều ngầm suy từ các FD của T. Khi đó, DBMS chỉ quản lý các FD của T, các FD trong S sẽ được quản lý một cách tự động. 22 Hệ tiên đề Amstrong  Phụ thuộc hàm XY được suy diễn luận lý từ F nếu mọi quan hệ thỏa mãn mọi phụ thuộc hàm trong F thì cũng thỏa mãn XY  Ký hiệu F⊨XY  F bao hàm (implies) XY  XY được suy diễn theo quan hệ từ F 23 Hệ tiên đề Amstrong  Quy tắc suy diễn (inference rule): nếu 1 quan hệ thỏa mãn 1 số phụ thuộc hàm nào đó thì quan hệ này cũng thỏa mãn 1 số phụ thuộc hàm khác 24 Hệ tiên đề Amstrong  F1. Phản xạ (reflexivity): YX  XY  F2. Gia tăng (augmentation): XY  XZ YZ  F3. Bắc cầu (transitivity): XY và YZ  X Z  F4. Hợp (additivity): XY và XZ  X YZ  F5. Chiếu (projectivity): XYZ  X Y  F6. Bắc cầu giả (pseudotransitivity): XY và YZW  XZ W 25 Ví dụ  Dùng hệ tiên đề Amstrong để chứng minh Nếu X  YZ và Z  W, thì X  YZW  Chứng minh:  Từ Z  W  YZZ  YZW (luật gia tăng) hay YZ  YZW  Từ X YZ và YZ  YZW  X  YZW (luật bắc cầu) 26 Bao đóng của tập phụ thuộc hàm  Bao đóng (closure) của tập phụ thuộc hàm F là tập phụ thuộc hàm nhỏ nhất chứa F sao cho không thể áp dụng hệ tiên đề Amstrong trên tập này để tạo ra 1 phụ thuộc hàm khác không có trong tập hợp này  Ký hiệu F+ F+ là 1 tập hợp các FD được suy diễn từ F 27 Các tính chất của bao đóng của tập phụ thuộc hàm 1. Tính phản xạ: với mọi tập phụ thuộc hàm F+ ta luôn có F  F+ 2. Tính đơn điệu: nếu F  G thì F+  G+ 3. Tính lũy đẳng: với mọi tập phụ thuộc hàm F ta luôn có (F+)+ = F+. 28 Ví dụ Bao đóng của tập phụ thuộc hàm Cho F={AB C, CB} trên r(ABC) F+={AA, ABA, ACA, ABCA, BB, ABB, BCB, ABCB, CC, ACC, BCC, ABCC, ABAB, ABCAB, ACAC, ABCAC, BCBC, ABCBC, ABCABC, ABC, ABAC, ABBC, ABABC, CB,CBC, ACB, ACAB } 29 Hệ tiên đề Amstrong  Hệ tiên đề Amstrong là đúng đắn (sound)  các phụ thuộc hàm suy diễn từ F (tập phụ thuộc hàm trên r) theo hệ tiên đề Amstrong cũng là một phụ thuộc hàm trên r  Hệ tiên đề Amstrong là toàn vẹn (completeness)  bảo đảm rằng f  F+ nếu và chỉ nếu f là 1 FD được suy diễn 30 Phụ thuộc hàm tương đương  Nếu F và G là 2 tập FD. F suy diễn G ( F entails G) nếu F suy diễn được tất cả các FD có trong G.  F và G là tương đương nhau nếu F suy diễn G và G suy diễn F 31 Kiểm tra các tập FD tương đương  Input: F,G – các tập FD  Output: true nếu F tương đương G, false nếu ngược lại For each f F do if G does not entail f then return false For each g  G do if F does not entail g then return false Return true 32 Ví dụ  Hãy khảo sát 2 tập FD sau:  F={ ACB, AC, DA}  G={AB, AC, DA, DB} F và G có tương đương nhau không??? Từ AC + Tiên đề F2  AAC (1) Từ (1)+ ACB + tiên đề F3  AB Từ DA + AB + tiên đề F3  D B F suy diễn G Tương tự khi xét G suy diễn F 33 Bao đóng của tập thuộc tính  Bao đóng của tập thuộc tính X dựa trên một tập phụ thuộc hàm F (closure of X under F) là 1 tập thuộc tính sao cho: 𝑋𝐹 + = {A|XA  F+} 34 Giải thuật tìm bao đóng của tập thuộc tính trên tập phụ thuộc hàm  Input: tập thuộc tính X và tập phụ thuộc hàm F  Output: bao đóng của X dựa trên F Procedure Closure(X,F,Closure_X) Begin Closure_X:=X; repeat Old_X := Closure_X; for mỗi WZ trong F do if W  Closure_X then Closure_X :=Closure_X  Z; until Closure_X = Old_X; End; 35 Ví dụ tìm bao đóng của X  Cho R(A,B,C,D,E,F) và tập F={f1:DB, f2: AC, f3: ADE, f4:CF}  Tìm A+F:  A+F ={A}  Duyệt F lần 1: Từ f2  A+F = {AC}; Từ f4  A + F = {ACF}  Duyệt F lần 2: A+F không thay đổi A+F = {ACF}  Tìm {AD}+F ??? 36 Kiểm tra thành viên trong F+  Để xác định F ⊨ XY, cần kiểm tra X Y  F+  Giải thuật:  Input: phụ thuộc hàm XY và tập F  Output: true nếu F⊨ XY, ngược lại là false Function Member(X,Y,F) Begin if Y  Closure(X,F) then Member = true else Member = false; End 37 Ví dụ kiểm tra phụ thuộc hàm  Cho F={DB, AC, ADE, CB}. Kiểm tra F có bao hàm AB?? - Tìm A+F?  A + F = {ACB} - Do B  A+F nên F bao hàm AB 38 Giải thuật tìm khóa của lược đồ quan hệ  Input: R(U) và tập phụ thuộc hàm F  Output: tập hợp K bao gồm tất cả khóa của R  Tập thuộc tính nguồn (TN) chứa tất cả các thuộc tính xuất hiện ở vế trái và không xuất hiện ở vế phải của các phụ thuộc hàm và các thuộc tính không xuất hiện ở cả vế trái lẫn vế phải của các phụ thuộc hàm TN=U- fF right(f) 39 Giải thuật tìm khóa của lược đồ quan hệ  Tập thuộc tính đích (TD) 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 các phụ thuộc hàm TD= fF right(f) - fF left(f)  Tập thuộc tính trung gian (TG) chứa tất cả các thuộc tính xuất hiện ở cả vế trái lẫn vế phải của các phụ thuộc hàm 40 Thuật toán tìm tất cả khóa  Bước 1: tạo tập thuộc tính nguồn TN. Tập thuộc tính trung gian TG  Bước 2: if TG =  then lược đồ quan hệ chỉ có 1 khóa K K=TN Kết thúc Ngược lại qua bước 3  Bước 3: tìm tất cả các tập con Xi của tập trung gian TG .. 41 Thuật toán tìm tất cả khóa (tt)  Bước 4: tìm các siêu khóa Si bằng cách  Xi if (TN  Xi)+ = Q+ then Si = TN  Xi  Bước 5: tìm khóa bằng cách loại bỏ các siêu khóa không tối thiể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 42 Ví dụ 1 Xi Xi  TN (Xi  TN)+ Siêu khóa Khóa  AD ADBCEF=R+ AD AD C ADC ADBCEF=R+ ADC 43 Cho R(A,B,C,D,E,F) và F={DB, AC, ADE, CF}. Tìm tất cả các khóa của R B1: TN={AD}, TG={C} Xi là các tập con của TG Ví dụ 2 Xi Xi  TN (Xi  TN)+ Siêu khóa Khóa  B B C CB ABCDEF=R+ BC BC A AB ABCDEF=R+ AB AB AC ABC ABCDEF=R+ ABC 44 Cho R(A,B,C,D,E,F) và F={AD, CAF, AB EC}. Tìm khóa của R? TN={B} , TG={AC} Khóa của R là {AB} và {BC}