Phụ thuộc hàm & chuẩn hóa dữ liệu - Thiều Quang Trung

CHƯƠNG 3 PHỤ THUỘC HÀM & CHUẨN HÓA DỮ LIỆU GV Th.S. Thiều Quang Trung Bộ môn Khoa học cơ bản Trường Cao đẳng Kinh tế đối ngoại Nội dung • Khái niệm 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 • Định nghĩa chuẩn hóa • Các dạng chuẩn hóa 2 GV Thiều Quang Trung 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 GV Thiều Quang Trung Phụ thuộc hàm là gì ? (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 4 GV Thiều Quang Trung 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 5 GV Thiều Quang Trung Phụ thuộc hàm (Functional Dependency) 6 • Xét lược đồ quan hệ gồm n thuộc tính – R(U), U={A1, A2,, An} • Phụ thuộc hàm (FD) giữa hai tập thuộc tính X, Y U – Ký hiệu: X  Y. r  R,  t1, t2  r nếu t1[X] = t2[X] thì t1[Y] = t2[Y]. – X là vế trái (determinant) và Y là vế phải (dependent) của FD. 7 3 5 1 4 1 B A r(R) r không thỏa A  B, nhưng thỏa B  A GV Thiều Quang Trung 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. • 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  Salary Salary -/-> Emp_ID 7 GV Thiều Quang Trung Phụ thuộc hàm (Functional Dependency -FD) • Nếu X là 1 khóa dự tuyển (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, Qualification • Có một số FD trong lược đồ sẽ gây ra dư thừa dữ liệu. 8 GV Thiều Quang Trung Ví dụ FD và dư thừa dữ liệu • 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 – SSN,Hobby  SSN, Name, Address,Hobby • Bất thường xảy ra khi một người có nhiều sở thích thay đổi địa chỉ 9 GV Thiều Quang Trung 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 10 GV Thiều Quang Trung 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 • 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 • Số 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. 11 GV Thiều Quang Trung 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. 12 GV Thiều Quang Trung 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 13 GV Thiều Quang Trung 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 14 GV Thiều Quang Trung Hệ tiên đề Amstrong • Các tiên đề suy diễn: – 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 15 GV Thiều Quang Trung Hệ tiên đề Amstrong • 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 16 GV Thiều Quang Trung 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à 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ày • Ký hiệu F+, gồm: – F và – Tất cả các phục thuộc hàm được suy diễn từ F. • F gọi là đầy đủ nếu F = F+. 17 GV Thiều Quang Trung 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+. 18 GV Thiều Quang Trung 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 19 GV Thiều Quang Trung 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 20 GV Thiều Quang Trung 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 G does not entail f then return false Return true 21 GV Thiều Quang Trung Ví dụ kiểm tra tập F tương đương • 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 22 GV Thiều Quang Trung Bao đóng của tập thuộc tính 23 • Làm thế nào để biết một FD X  Y được suy diễn từ tập F cho trước ? • Bao đóng của tập thuộc tính X đối với F, ký hiệu X+, là – Tập các thuộc tính phụ thuộc hàm vào X. – X+ = {A  U | X  A  F+} • Nhận xét – X  Y  F+  Y  X+. – Nếu K là khóa của R thì K+ = U. GV Thiều Quang Trung Thuật toán tìm X+ 24 • Nhập: U, F và X  U • Xuất: X+ • Thuật toán: – Bước 1: X+ = X; – Bước 2: Nếu tồn tại Y  Z  F và Y  X+ thì X+ := X+  Z; và tiếp tục bước 2. Ngược lại qua bước 3. – Bước 3: Xuất X+. GV Thiều Quang Trung Ví dụ thuật toán tìm X+ 25 • Ví dụ 1, cho: – F = {AB  C, BC  D, D  EG}. – X = BD. • Tính X+: – X+ = BD. – Lặp 1: • Tìm các FD có vế trái là tập con của X+ = BD – D  EG, thêm EG vào X+ ta được X+ = BDEG. – Lặp 2: • Tìm các FD có vế trái là tập con của X+ = BDEG – Không có FD nào. – Vậy X+ = BDEG. GV Thiều Quang Trung Kiểm tra phụ thuộc hàm suy diễn 26 • Dựa vào tính chất: X  Y  F+  Y  X+. • Ví dụ: – Cho F = {AB  C, A  D, D  E, AC  B} – Hai phụ thuộc hàm AB  E và D  C có được suy diễn từ F hay không? DE D ABCDE AB XF + X Được suy diễn từ F GV Thiều Quang Trung Giả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 F • Xuất: 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) 27 GV Thiều Quang Trung • 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 Giải thuật tìm khóa của lược đồ quan hệ 28 GV Thiều Quang Trung 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 29 GV Thiều Quang Trung 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 30 GV Thiều Quang Trung Ví dụ tìm khóa • 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 Xi Xi  TN (Xi  TN)+ Siêu khóa Khóa  AD ADBCEF=R+ AD AD C ADC ADBCEF=R+ ADC 31 GV Thiều Quang Trung Ví dụ tìm khóa • 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} 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 32 GV Thiều Quang Trung Chuẩn hóa • Mục đích: loại bỏ các bất thường của 1 quan hệ để có được các quan hệ có cấu trúc tốt hơn, nhỏ hơn • Quan hệ có cấu trúc tốt (well-structured relation): là quan hệ có sự dư thừa dữ liệu là tối thiểu và cho phép người dùng thêm, sửa, xóa mà không gây ra mâu thuẩn dữ liệu 33 GV Thiều Quang Trung Chuẩn hóa • Quá trình chuẩn hóa được thực hiện qua nhiều bước. Mỗi bước tương ứng một dạng chuẩn • Các dạng chuẩn: – Dạng chuẩn 1(1NF – first normal form) – Dạng chuẩn 2(2NF- second normal form) – Dạng chuẩn 3(3NF – third normal form) – Dạng chuẩn BCNF – Boyce Codd 34 GV Thiều Quang Trung Bảng chưa chuẩn hóa • Bảng không ở dạng chuẩn 1 (hay chưa chuẩn hóa) nếu nó chứa một hoặc nhiều nhóm lặp lại hoặc các giá trị phức hợp • Nhóm lặp lại (Repeating group): một nhóm nhiều hàng có thể có cùng chung một thuộc tính 35 GV Thiều Quang Trung Ví dụ bảng chưa chuẩn hóa Repeating group 36 GV Thiều Quang Trung Dạng chuẩn 1 (1NF – first normal form) • Bảng ở dạng chuẩn 1 nếu – Có khóa chính – Không có nhóm lặp lại • Bảng ở 1NF nếu mọi thuộc tính của R đều chứa các giá trị nguyên tố (không có thuộc tính đa trị) 37 GV Thiều Quang Trung Biến đổi về dạng chuẩn 1 • Quá trình chuẩn hóa gồm 3 bước: – Loại bỏ các nhóm lặp lại – Xác định khóa chính của bảng – Xác định tất cả các phụ thuộc (dependencies) trong bảng • Lược đồ phụ thuộc (dependency diagram): để giúp mô tả tất cả các phụ thuộc trong bảng 38 GV Thiều Quang Trung Ví dụ quan hệ có thuộc tính đa trị (multivalued attributes) Emp_I D Name Dept_Name Salary Course_ Title Date_ Completed 100 M.Simpson Marketing 48000 SPSS Surveys 6/19/2001 12/12/2002 140 A.Beeton Acounting 52000 Tax Acc 12/8/2003 110 C.Lureco Info System 43000 SPSS C++ 1/12/2003 2/6/2004 190 L.Davis Finance 55000 150 S.Martin Marketing 42000 SPSS Java 6/16/2002 5/7/2004 Quan hệ Employee_Course 39 GV Thiều Quang Trung Ví dụ quan hệ có thuộc tính đa trị (multivalued attributes) Emp_ ID Name Dept_Name Salary Course_ Title Date_ Completed 100 M.Simpson Marketing 48000 SPSS 6/19/2001 100 M.Simpson Marketing 48000 Surveys 12/12/2002 140 A.Beeton Acounting 52000 Tax Acc 12/8/2003 110 C.Lureco Info System 43000 SPSS 1/12/2003 110 C.Lureco Info System 43000 C++ 2/6/2004 190 L.Davis Finance 55000 150 S.Martin Marketing 42000 SPSS 6/16/2002 150 S.Martin Marketing 42000 Java 5/7/2004  Dạng chuẩn 1  Khóa là EmpID + CourseTitle 40 GV Thiều Quang Trung A Dependency Diagram: First Normal Form (1NF) 41 GV Thiều Quang Trung Dạng chuẩn 1 (1NF – Normal First Form) • Nhận xét: – Dạng chuẩn 1 vẫn có thể có các bất thường khi cập nhật • Ví dụ: trong lược đồ Employee_Course, sẽ có các bất thường sau: – Thêm 1 nhân viên mới chưa tham gia khóa học nào  vi phạm quy luật bảo toàn thực thể – Thay đổi tên phòng phải thay đổi hàng loạt thông tin này cho tất cả các nhân viên của phòng đó – Xóa 1 course mà chỉ có 1 nhân viên học, thông tin course sẽ bị xóa theo 42 GV Thiều Quang Trung Phụ thuộc hàm đầy đủ (Full functional dependency) • XA là phụ thuộc hàm đầy đủ nếu không tồn tại Y  X để cho YA • Ví dụ: quan hệ Employee_Course – Khóa là Emp_ID,Course – Emp_ID, Course  Grade là phụ thuộc hàm đầy đủ – Emp_ID Name, Dept_Name là phụ thuộc hàm không đầy đủ Emp_ID, Course Name, Dept_Name Emp_ID Name, Dept_Name Emp_ID  {Emp_ID, Course } • Phụ thuộc hàm bộ phận (partial FD) XA, tồn tại Y  X sao cho YA 43 GV Thiều Quang Trung Dạng chuẩn 2 (2NF – second Normal Form) • Lược đồ quan hệ R ở dạng 2NF đối với tập phụ thuộc hàm F nếu: – R ở dạng chuẩn 1 – Mọi thuộc tính không khóa đều phụ thuộc đầy đủ vào mọi khóa của R • Nếu quan hệ R chỉ có các khóa đơn thì đương nhiên quan hệ này ở dạng chuẩn 2 44 GV Thiều Quang Trung Biến đổi thành 2NF • Loại bỏ các phụ thuộc hàm bộ phận và tạo thêm các quan hệ mới tương ứng với các phụ thuộc hàm bộ phận 45 GV Thiều Quang Trung Second Normal Form (2NF) Conversion Results 46 GV Thiều Quang Trung Dạng chuẩn 2 • Quan hệ ở 2NF vẫn có thể có các bất thường khi cập nhật • Ví dụ: xét quan hệ EMPLOYEE đã ở chuẩn 2NF – Khi thêm 1 loại công việc mới mà công việc này chưa có nhân viên nào làm sẽ vi phạm ràng buộc khoá chính – Khi sửa đổi lương giờ (CHG_HOUR) của 1 loại công việc mà có nhiều nhân viên đang cùng làm – Khi xoá 1 nhân viên đang làm công việc mà chỉ có nhân viên đó làm thì sẽ làm mất luôn thông tin về công việc đó 47 GV Thiều Quang Trung Phụ thuộc bắc cầu (Transitive dependency) • XA được gọi là phụ thuộc bắc cầu nếu tồn tại Y để cho XY, YA, Y-/->X Và A  XY • Nguyên nhân gây ra các bất thường khi cập nhật bảng 2NF là do có các thuộc tính không khóa phụ thuộc bắc cầu vào khóa của quan hệ 48 GV Thiều Quang Trung Dạng chuẩn 3 (3NF – third normal form) • Định nghĩa 1: Lược đồ quan hệ R ở 3NF đối với tập phụ thuộc hàm F nếu: – R ở dạng 2NF – Mọi thuộc tính không khóa đều không phụ thuộc bắc cầu vào khóa chính của R • Định nghĩa 2: Lược đồ quan hệ R ở 3NF đối với tập phụ thuộc hàm F nếu R ở dạng chuẩn 1 và mọi phụ thuộc hàm X->A với A X thì X là 1 siêu khoá của R hoặc A là 1 thuộc tính khoá 49 GV Thiều Quang Trung Biến đổi thành dạng chuẩn 3 • Loại bỏ các phụ thuộc bắc cầu trong quan hệ và tạo ra các quan hệ mới tương ứng với các phụ thuộc bắc cầu 50 GV Thiều Quang Trung Third Normal Form (3NF) Conversion Results 51 GV Thiều Quang Trung Dạng chuẩn 3 • Quan hệ ở 3NF vẫn có thể có các bất thường khi cập nhật • Ví dụ: xét lược đồ quan hệ EMPLOYEE_TEACHER(EmpId,Course,Teacher) Có 2 phụ thuộc hàm: EmpId, Course  Teacher Teacher Course  Thuộc dạng 3NF, bất thường xảy ra teacher thay đổi môn dạy 52 GV Thiều Quang Trung Dạng chuẩn Boyce-Codd (BCNF) • Một quan hệ ở dạng BCNF nếu mọi vế trái (xác định/determinant) của F đều là khóa dự tuyển (candidate key) • Cho 1 lược đồ quan hệ R(U,F) với U là tập thuộc tính, F là tập phụ thuộc hàm. Lược đồ ở dạng chuẩn BCNF nếu với mọi phụ thuộc hàm X Y  F, nếu 1 trong 2 điều kiện sau là đúng: – Y  X ( phụ thuộc hàm tầm thường) – X là siêu khóa của R 53 GV Thiều Quang Trung Ví dụ một quan hệ thuộc dạng chuẩn 3NF nhưng chưa là dạng chuẩn BCNF 54 GV Thiều Quang Trung Chuyển đổi thành BCNF • Một quan hệ ở BCNF thì nó cũng ở dạng 3NF • Có thể biến đổi trực tiếp bảng từ 1NF thành BCNF, mà không cần phải qua các bước chuẩn hóa 2NF, 3NF – Loại bỏ các vế trái không phải là siêu khoá – Tạo các quan hệ mới tương ứng với các vế trái sao cho vế trái trở thành siêu khoá của quan hệ mới 55 GV Thiều Quang Trung Ví dụ chuyển đổi sang dạng chuẩn BCNF • Xét U ={ABCD}, F ={AB CD, AC BD} có 2 khóa: AB và AC • Vì 2 phụ thuộc hàm này đều có vế trái là khóa, nên lược đồ ở dạng BCNF 56 GV Thiều Quang Trung Ví dụ chuyển đổi sang dạng chuẩn BCNF 57 GV Thiều Quang Trung Ví dụ chuyển đổi sang dạng chuẩn BCNF 58 GV Thiều Quang Trung So sánh 3NF và BCNF • BCNF được xem là trường hợp đặc biệt của 3NF • Với quan hệ có nhiều candidate key phức hợp thì BCNF sẽ tránh được hai bất thường có thể xảy ra ở 3NF – 1 phần của khóa xác định 1 phần của khóa khác – Cột không khóa xác định 1 phần của khóa 59 GV Thiều Quang Trung 60 GV Thiều Quang Trung