Bài giảng Cơ sở dũ liệu - Chương 10: Chuẩn hóa (Normalization)

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 CoddDạng chuẩn 4NF5Bảng chưa chuẩn hóaBả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ính6A Table in the Report FormatRepeating group7Dạng chuẩn 1(1NF – first normal form)Bảng ở dạng chuẩn 1 nếuCó khóa chínhKhô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ị)8Biến đổi về dạng chuẩn 1Quá trình chuẩn hóa gồm 3 bước:Loại bỏ các nhóm lặp lạiXác định khóa chính của bảngXác định tất cả các phụ thuộc (dependencies) trong bảngLược đồ phụ thuộc (dependency diagram): để giúp mô tả tất cả các phụ thuộc trong bảng9Ví dụ quan hệ có thuộc tính đa trị (multivalued attributes)Emp_IDNameDept_NameSalaryCourse_TitleDate_Completed100M.SimpsonMarketing48000SPSSSurveys6/19/200112/12/2002140A.BeetonAcounting52000Tax Acc12/8/2003110C.LurecoInfo System43000SPSSC++1/12/20032/6/2004190L.DavisFinance55000150S.MartinMarketing42000SPSSJava6/16/20025/7/2004Quan hệ Employee_Course10Ví dụ quan hệ có thuộc tính đa trị (multivalued attributes)Emp_IDNameDept_NameSalaryCourse_TitleDate_Completed100M.SimpsonMarketing48000SPSS6/19/2001100M.SimpsonMarketing48000Surveys12/12/2002140A.BeetonAcounting52000Tax Acc12/8/2003110C.LurecoInfo System43000SPSS1/12/2003110C.LurecoInfo System43000C++2/6/2004190L.DavisFinance55000150S.MartinMarketing42000SPSS6/16/2002150S.MartinMarketing42000Java5/7/2004 Dạng chuẩn 1 Khóa là EmpID + CourseTitle11A Dependency Diagram: First Normal Form (1NF)12Dạ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ậtVí 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 theo13Phụ 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AVí dụ: quan hệ Employee_CourseKhóa là Emp_ID,CourseEmp_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_NameEmp_ID Name, Dept_NameEmp_ID  {Emp_ID, Course }Phụ thuộc hàm riêng phần(partial FD) XA,tồn tại Y  X sao cho YA14Dạ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 1Mọi thuộc tính không khóa đều phụ thuộc đầy đủ vào mọi khóa của RNếu quan hệ R chỉ có các khóa đơn thì đương nhiên quan hệ này ở dạng chuẩn 2 15Biến đổi thành 2NFLoại bỏ các phụ thuộc hàm riêng 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 riêng phần16Second Normal Form (2NF) Conversion Results17Dạng chuẩn 2Quan hệ ở 2NF vẫn có thể có các bất thường khi cập nhậtVí dụ: xét quan hệ EMPLOYEE đã ở chuẩn 2NFKhi 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ínhKhi sửa đổi lương giờ (CHR_HOUR) của 1 loại công việc mà có nhiều nhân viên đang cùng làmKhi 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 đó18Phụ 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  XYNguyê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ệ19Dạ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 2NFMọ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á20Biến đổi thành dạng chuẩn 3Loạ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ầu21Third Normal Form (3NF) Conversion Results22Dạng chuẩn 3Quan hệ ở 3NF vẫn có thể có các bất thường khi cập nhậtVí 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ạy23Dạng chuẩn Boyce-Codd(BCNF)Một quan hệ ở dạng BCNF nếu mọi determinant (định thuộc) đều là candidate keyCho 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 R24A Table That is in 3NF but not in BCNF25Chuyển đổi thành BCNFMột quan hệ ở BCNF thì nó cũng ở dạng 3NFCó 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, 3NFLoại bỏ các định thuộc không phải là siêu khoá Tạo các quan hệ mới tương ứng với các định thuộc sao cho định thuộc trở thành siêu khoá của quan hệ mới26Ví dụXét U ={ABCD}, F ={AB CD, AC BD} có 2 khóa: AB và ACVì 2 phụ thuộc hàm này đều có phía trái là khóa, nên lược đồ ở dạng BCNF27Decomposition to BCNF28Another BCNF Decomposition29So sánh 3NF và BCNFBCNF được xem là trường hợp đặc biệt của 3NFVớ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 ở 3NF1 phần của khóa xác định 1 phần của khóa khácCột không khóa xác định 1 phần của khóa30Candidate key và BCNFMột quan niệm sai lầm khi cho rằng một bảng với nhiều candidate key sẽ vi phạm chuẩn BCNF.Nhiều candidate key không vi phạm BCNF hay 3NF, không cần phải phân chia bảng chỉ vì nó có nhiều candidate key31Ví dụ 1Xét lược đồ phụ thuộc sau:Mã_SV	Mã_Môn	Email	DiemHai candidate key: Ma_SV+Ma_Mon; Email+Ma_MonChỉ có 1 thuộc tính không khóa là DiemBất thường 1: 1 phần của khóa này xác định 1 phần của khóa khác.Bảng thuộc 3NF nhưng không là BCNFLàm thế nào để chuẩn hóa thành BCNF???32Ví dụ 1Tách bảng trên thành 2 bảng sau:TABLE1(MaMon,MaSV, Diem)TABLE2(MaSV, Email)33Ví dụ 2Xét lược đồ phụ thuộc sau: GVHD	 Mã_SV	Ma_Mon	T_TrạngHai candidate keys: Ma_Sv+GVHD; Ma_SV + Ma_MonLà 3NF vì chỉ có 1 thuộc tính không khóa là T_Trang phụ thuộc vào cả 2 candidate keyKhông là BCNF vì GVHD là 1 determinant nhưng chính nó không phải là 1 candidate key (thuộc Bất thường 2: thuộc tính không khóa xác định 1 phần của khóa) . Làm thế nào để chuẩn hóa thành BCNF???34Ví dụ 2Tách thành 2 quan hệTABLE1(GVHD, MaSV, T_Trang)TABLE2(GVHD, MaMon)35Độc lập quan hệ(relationship Independence)Nếu hai quan hệ là độc lập nhau, sẽ dư thừa nếu lưu trữ dữ liệu về 1 quan hệ thứ ba nào đó. Chỉ cần suy dẫn quan hệ thứ ba bằng cách kết hợp 2 quan hệ độc lập thông qua 1 toán tử kết nối (join)36Ví dụ về quan hệ độc lậpKhảo sát 1 loại thực thể kết hợp DangKy biểu diễn mối quan hệ 3 chiều giữa SinhVien, MonHoc và SachGK.Khoá chính của DangKy là MaSV, MaMon va MaSach, không có thuộc tính không khóaDangKy thuộc dạng BCNF, nên không gây ra bất thường do phụ thuộc hàmNhưng nếu xét về mặt độc lập quan hệ thì có dư thừa dữ liệu37Quan hệ 3 chiềuSachGKMaSachTenSachSinhVienMaSVTenSVMonHocMaMonTenMonSachGKMaSachTenSachDangKySV-DKSach-DKMon-DK38Ví dụ (tt)Chia thực thể DangKy thành 3 quan hệ 2 chiều: MaSV, MaMonMaMon, MaSachMaSV, MaSachKhảo sát xem quan hệ nào có thể được suy dẫn từ 2 quan hệ khác? 39Ví dụ (tt)Quan hệ (MaSV, MaMon) không thể được suy dẫn từ các quan hệ khác. Ví dụ sách T1 được dùng cho 2 môn học O1 và O2, và bởi 2 sinh viên S1 và S2  không đủ cơ sở để xác định S1 học môn O1 hay O2. Tương tự cho quan hệ (MaMon, MaSach)40Ví dụ (tt)Quan hệ (MaSV, MaSach) có thể suy dẫn từ 2 quan hệ còn lại. Ví dụ nếu sinh viên S1 đăng ký học môn O1 và môn O1 sử dụng sách T1, bấy giờ ta có thể suy diễn là S1 sẽ dùng sách T1Hai quan hệ SinhViên-MônHọc và MônHọc-SachGK độc lập nhau nên ta có thể biết được sách được dùng bởi 1 sinh viên nào đó mà không cần phải lưu trữ cụ thể41Ví dụ (tt)Bảng DangKy trở nên dư thừaĐể bỏ dư thừa, thay thế kiểu thực thể DangKy chỉ còn 2 quan hệ 2 chiềuBiến đổi 2 mối kết hợp thành 2 bảng tương ứng. Hai bảng không còn dư thừa dữ liệu.Dangky(MaSV, MaMon)DatMua( MaMon, MaSach)42Quan hệ 3 chiềuSachGKMaSachTenSachSinhVienMaSVTenSVSachGKMaSachTenSachMonHocMaMonTenMonDangKyDatmua43Ví dụ mở rộngGiả sử quan hệ giữa SinhVien và SachGK không còn độc lập với 2 quan hệ còn lại vì sinh viên có thể đăng ký học nhưng không mua sách giáo khoa mà chỉ mượn sách. Không còn quan hệ độc lập nữa và quan hệ 3 chiều sẽ cần được giữ lại.44Phụ thuộc đa trị (Multivalued Dependencies - MVD)Một phụ thuộc mà có thể được suy dẫn từ các phụ thuộc khác thì được gọi là phụ thuộc đa trị. MVD liên quan đến 3 cột và 3 cột này kết hợp tạo thành 1 khóa chính phức cho 1 bảng kết hợp.45Phụ thuộc đa trị(Multivalued Dependencies - MVD)Định nghĩa: phụ thuộc suy dẫn (liên quan đến cột B và C) có thể được suy dẫn từ phụ thuộc A-B và A-C. Ký hiệu: A B|CA có thể kết hợp với 1 tập hợp các giá trị của B và C (đa trị)MVD có thể dẫn đến dư thừa dữ liệu do có sự độc lập giữa các cột. 46Phụ thuộc đa trị (MVD)	MaMon	MaSV	MaSach	 O1	 S1	 T1	 O1	 S2	 T2	 O1	 S2	 T1	 O1	 S1	 T2	MVD MaMon  MaSV|MaSachTrong 2 hàng đầu, môn O1 liên quan đến 2 sinh viên S1, S2 và 2 sách T1 và T2Nếu MVD là đúng, 2 hàng bên dưới đường thẳng sẽ tồn tại và không cần lưu trữ. Chúng sẽ được suy diễn từ 2 hàng trên47So sánh FD và MVDMVD là sự khái quát hoá của FD. Mỗi FD là 1 MVD nhưng 1 MVD chưa chắc là 1 FDVới 1 MVD mà 1 giá trị của A liên hệ chỉ với 1 giá trị của B và 1 giá trị của C thì nó cũng là 1 FDMột MVD mà không phải là 1 FD còn được gọi là nontrivial MVD48Dạng chuẩn 4(Fourth Normal Form - 4NF)4NF tránh việc dư thừa do phụ thuộc đa trị Ví dụ: bảng Dangky(MaSV, MaMon, MaSach) không phải 4NF do tồn tại MVD MaMon  MaSV|MaSachĐể chuẩn hoá thành 4NF, chia bảng Dangky thành 2 bảngDangky(MaSV, MaMon)Quydinh(MaMon, MaSach)49