Bài giảng Cơ sở dũ liệu - Chương 9: Phụ thuộc hàm (Functional Dependency)

Chương 9: Phụ thuộc hàm(Functional Dependency)1Nội dungDư thừa dữ liệuPhụ thuộc hàmHệ tiên đề AmstrongBao đóng của tập phụ thuộc hàmBao đóng của tập thuộc tínhTìm khóa2Dư 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 đĩaCá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àoBất thường khi xóa bỏBất thường khi sửa đổi3Phụ 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 4Phụ 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]5Phụ thuộc hàm(Functional Dependency)X là vế trái, ký hiệu left(f) hay còn gọi là determinantY là vế phải, ký hiệu right(f) hay còn gọi là dependent6Phụ 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.Ví dụ: Một nhân viên chỉ có 1 tiền lương nhưng nhiều nhân viên có thể có cùng 1 mức lương	Emp_ID  SalarySalary -/-> Emp_ID7Phụ thuộc hàm(Functional Dependency -FD)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 Ví dụ: trong lược đồ PROFESSOR có ProfId là primary key nên:	ProfId  Name, QualificationCó 1 số FD trong lược đồ sẽ gây ra dư thừa dữ liệu.8Ví dụ FD và dư thừa dữ liệuXé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,HobbyBất thường xảy ra khi một người có nhiều sở thích thay đổi địa chỉ9Giải thuật kiểm tra phụ thuộc hàmBà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 XIf mỗi tập các bộ có cùng giá trị X thì có cùng giá trị Y thenSatisfies = trueElseSatisfies = false10Tập phụ thuộc hàmGọ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 RPhụ 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  XSố tập con có thể có của R = {A1,A2,...,An} là 2n. Ứng với mỗi tập con sẽ có tối đa 2n. Số FD tối đa có thể có trong 1 lược đồ là 22n.11Tập phụ thuộc hàmFD đượ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.12Hệ tiên đề AmstrongPhụ 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YKý hiệu F|=XYF bao hàm (implies) XYXY được suy diễn theo quan hệ từ F13Hệ tiên đề AmstrongQuy 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ác14Hệ tiên đề AmstrongCác tiên đề suy diễn:F1. Phản xạ (reflexivity): YX  XYF2. Gia tăng (augmentation): XY  XZ YZF3. Bắc cầu (transitivity): XY và YZ  X Z15Hệ tiên đề AmstrongF4. Hợp (additivity): XY và XZ  X YZF5. Chiếu (projectivity): XYZ  X YF6. Bắc cầu giả (pseudotransitivity): XY và YZW  XZ W16Bao đóng của tập phụ thuộc hàmBao đóng (closure) của tập phụ thuộc hàm F là 1 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àyKý hiệu F+F+ là 1 tập hợp các FD được suy diễn từ F17Các tính chất của bao đóng của tập phụ thuộc hàmTính phản xạ: với mọi tập phụ thuộc hàm F+ ta luôn có F  F+Tính đơn điệu: nếu F  G thì F+  G+Tính lũy đẳng: với mọi tập phụ thuộc hàm F ta luôn có (F+)+ = F+.18Hệ tiên đề AmstrongHệ 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 rHệ 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 19Phụ thuộc hàm tương đươngNế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 F20Kiểm tra các tập FD tương đươngInput: F,G – các tập FDOutput: 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 falseFor each g  G do	if G does not entail f then return falseReturn true21Ví 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BTừ DA + AB + tiên đề F3  D BF suy diễn GTương tự khi xét G suy diễn F22Bao đóng của tập phụ thuộc hàmVí dụ 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 }23Bao đóng của tập thuộc tínhBao đó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 Y sao cho:XY F+XZ F+: Z YHoặc = {A|XA  F+}24Giải thuật tìm bao đóng của tập thuộc tính trên tập phụ thuộc hàmInput: tập thuộc tính X và tập phụ thuộc hàm FOutput: bao đóng của X dựa trên FProcedure 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;25Ví dụ tìm bao đóng của XCho 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 đổiA+F = {ACF}Tìm {AD}+F ???26Kiể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:Nhập: phụ thuộc hàm XY và tập FXuất: true nếu F|= XY, ngược lại là falseFunction Member(X,Y,Z)	Begin	if Y  Closure(X,F) then Member = true	else Member = false;End27Ví 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B28Giải thuật tìm khóa của lược đồ quan hệNhập: R(U) và tập phụ thuộc hàm FXuất: tập hợp K bao gồm tất cả khóa của RTậ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)29Giả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àmTD= 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àm30Thuật toán tìm tất cả khóaBước 1: tạo tập thuộc tính nguồn TN. Tập thuộc tính trung gian TGBướ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 3Bước 3: tìm tất cả các tập con Xi của tập trung gian TG..31Thuậ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  XiBước 5: tìm khóa bằng cách 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 32Ví dụ 1Cho 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 RB1: TN={AD}, TG={C}Xi là các tập con của TGXiXi  TN(Xi  TN)+Siêu khóaKhóaADADBCEF=R+ADADCADCADBCEF=R+ADC33Ví dụ 2Cho 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}XiXi  TN(Xi  TN)+Siêu khóaKhóaBBCCBABCDEF=R+BCBCAABABCDEF=R+ABABACABCABCDEF=R+ABC34