Bài Giảng Nhập Môn Cơ Sở Dữ Liệu: Chương 4.1: Chuẩn Hóa Cơ Sở Dữ Liệu Quan Hệ

huộc hàm (tt)ĐN bao đóng: Nếu F là tập các FD trong lược đồ R và f là FD khác cũng trong R, thì F được coi là bao f nếu với mọi thể hiện r của R nếu thỏa mãn FD trong F thì cũng thỏa mãn f. Ví dụ F={AB, BC} và f={AC}F={ĐToan, DLy, DHoaDTB, DTBXepHang},f={DT,DL,DHXepHang} Bao đóng của tập F(Ký hiệu F+) là tập các FD có thể suy diễn được từ F F và G được coi là tương đương nếu F bao G và G bao F Nhập môn Cơ sở dữ liệu - Khoa CNTT13Phụ thuộc hàm (tt)Ký hiệu F |= X Y: phụ thuộc hàm X Y được suy diễn từ tập các phụ thuộc hàm FQT1 (quy tắc phản xạ) : Nếu X  Y thì X  YQT2 (quy tắc tăng)	: { X Y } |= XZ YZQT3 (quy tắc bắc cầu)	: { X Y, Y Z } |= X Z QT4 (quy tắc chiếu)	: { XYZ } |= X Y và X ZQT5 (quy tắc hợp)	: { X Y , X Z } |= X YZQT6(quy tắc tựa bắc cầu): {XY,WYZ }|=WX Z Nhập môn Cơ sở dữ liệu - Khoa CNTT14Hệ suy diễn AmstrongQuy tắc suy diễn Amstrong đưa ra cách thức để tính toán và kiểm tra các thuộc tính trong tập FDBao gồm 3 quy tắc 1-3(phản xạ, tăng, bắc cầu)QT1 (quy tắc phản xạ) : TenNV, DChi TenNVQT2 (quy tắc tăng)	: MaNVTenNV thì MaNV, NSTenNV, NS QT3 (quy tắc bắc cầu)	: { X Y, Y Z } |= X YNếu DT,DL,DHDTB,DTBXepL thì DT, DL, DHXepL Nhập môn Cơ sở dữ liệu - Khoa CNTT15Hệ suy diễn Amstrong (tt)Hệ Ams là đúng: nếu FD f:XY có thể được suy diễn từ tập các FD F sử dụng các quy tắc suy diễn thì f nằm trong các quan hệ mà thỏa mãn tất cả các FD trong FVí dụ Cho biết XY và XZ thì XXY (quy tắc tăng theo X)YXYZ (quy tắc tăng theo Y)XYZ (bắc cầu)Vậy XYZ thỏa mãn tất cả các quan hệ mà thỏa mãn FD XY và XZNhập môn Cơ sở dữ liệu - Khoa CNTT16Hệ suy diễn Amstrong (tt)Hệ Ams là đầy đủ: Nếu F bao f, thì f có thể suy diễn được từ F sử dụng hệ các quy tắc suy diễnKết quả rút ra được từ tính đầy đủ này là chúng ta có thuật toán để xác định xem F có bao f hay khôngBản chất thuật toán là sử dụng hệ suy diễn theo tất cả các cách có thể nhằm tìm F+, sau đó kiểm tra xem f có nằm trong F+ hay khôngNhập môn Cơ sở dữ liệu - Khoa CNTT17Hệ suy diễn Amstrong (tt)Hệ Ams là chính xác: Khái niệm đúng và đầy đủ đã liên kết thành một chuỗi ý nghĩa đầy đủ về tính chính xác của hệ suy diễn Amstrong (định nghĩa này chỉ đúng trong các thể hiện của quan hệ)Điều này đồng thời cho biết một cách chính xác rằng thuật toán tìm bao dựa trên hệ suy diễn là chính xácNhập môn Cơ sở dữ liệu - Khoa CNTT18Hệ suy diễn Amstrong (tt)Tìm F+Tất cả các FD bao gồm ABBD, ABBCD, BCDBCDE, ABCDE là các phần tử của F+Nhập môn Cơ sở dữ liệu - Khoa CNTT19Thuật toán tìm bao đóng X+FXác định thuộc tính đóng là cách hiệu quả nhất để tìm bao đóngTập các thuộc tính đóng của tập các thuộc tính (X) với điều kiện thỏa mãn tập các FD (F) (ký hiệu X+F) là tập tất cả các thuộc tính (A) sao cho XA Gọi là tập các thuộc tính phụ thuộc hàm vào X trên FX+F1 không nhất thiết phải bằng X+F2 nếu F1F2Tập các thuộc tính đóng và suy diễnThuật toán: Cho biết tập các FD F ta có XY nếu và chỉ nếu X+F  YNhập môn Cơ sở dữ liệu - Khoa CNTT20Ví dụAB E có suy diễn được từ F không?DC có suy diễn được từ F không?Nhập môn Cơ sở dữ liệu - Khoa CNTT21Thuật toán tìm bao đóng X+F(tt)X+ = X;RepeatOld X+ = X+ ;Với mỗi phụ thuộc hàm Y  Z trong F thực hiệnnếu X+  Y thì X+ = X+  Z;until ( X+ = Old X+ ); Nếu T thuộc X+ thì XT là suy diễn được từ FNhập môn Cơ sở dữ liệu - Khoa CNTT22Ví dụXác định bao đóng Bài toán: Tìm bao đóng của AB với các phụ thuộc hàm sau GiảiKhởi tạo: X+ ={AB}Dùng (a): X+ ={ABC}Dùng (b): X+ ={ABCD}Dùng (c): X+ ={ABCDE}Nhập môn Cơ sở dữ liệu - Khoa CNTT23Phụ thuộc hàm tối thiểuĐịnh nghĩa: 1 tập FD gọi là tối thiểu nó thỏa mãn các điều kiện sauVế phải của các FD trong F chỉ có 1 thuộc tínhKhông thể thay thế XA bằng YA với điều kiện Y là tập con của X và vẫn giữ được tập các phụ thuộc mà tương đương với FKhông thể bớt được bất kỳ phụ thuộc hàm nào sao cho bảo toàn được tập các phụ thuộc hàm trong FNhập môn Cơ sở dữ liệu - Khoa CNTT24Phụ thuộc hàm tối thiểu (tt)Thuật toán tìm phủ tối thiểuG := F;Thay thế X  {A1, A2, ..., An} trong G bằng n phụ thuộc hàm X  A1, X  A2,  , X  An.Với mỗi X  A trong G Với mỗi thuộc tính B là một phần tử của XNếu ((G – (X  A)((X  {B})  A) là tương đương với Gthì thay thế XA bằng (X – {B})A ở trong GVới mỗi phụ thuộc hàm XA còn lại trong GNếu (G  {X  A}) là tương đương với Gthì loại bỏ X  A ra khỏi GNhập môn Cơ sở dữ liệu - Khoa CNTT25Các dạng chuẩnMỗi một dạng chuẩn là một tập các điều kiện trên lược đồ nhằm đảm bảo các tính chất của nó (liên quan tới dư thừa và bất thường trong cập nhật)Chuẩn hóa dữ liệu: quá trình phân tích lược đồ quan hệ dựa trên các FD và các khóa chính để đạt đượcCực tiểu sự dư thừaCực tiểu các phép cập nhật bất thườngNhập môn Cơ sở dữ liệu - Khoa CNTT26Các dạng chuẩn (tt)Thủ tục chuẩn hoá cung cấp Một cơ cấu hình thức để phân tích các lược đồ quan hệ dựa trên các khoá của nó và các phụ thuộc hàm giữa các thuộc tính của nó. Một loạt các kiểm tra dạng chuẩn có thể thực hiện trên các lược đồ quan hệ riêng rẽ sao cho cơ sở dữ liệu quan hệ có thể được chuẩn hoá đến một mức cần thiết. Tính chấtNối không mất mát (hoặc nối không phụ thêm)- vd:bộ giảBảo toàn sự phụ thuộc nó đảm bảo rằng từng phụ thuộc hàm sẽ được biểu hiện trong các quan hệ riêng rẽ nhận được sau khi tách.Nhập môn Cơ sở dữ liệu - Khoa CNTT27Các dạng chuẩn (tt)Phân loạiBoyce Codd đề nghị 3 dạng 1NF (first normal form): tương đương với định nghĩa của lược đồ quan hệ (quan hệ và bộ)2NF: ko có giá trị trong thực tiễn3NF  BCNF: thường sử dụng nhiều nhất4NF, 5NF do tính đa trị và phụ thuộc hàm nốiNhập môn Cơ sở dữ liệu - Khoa CNTT28Dạng chuẩn 1Đn: gọi là 1NF nếu miền giá trị của một thuộc tính chỉ chứa giá trị nguyên tử (đơn, ko phân chia được) và giá trị của mỗi thuộc tính cũng là một giá trị đơn lấy từ miền giá trị của nóVí dụ PHONGBAN( MaPHG, TenPHG, DDIEM)PHONGBAN(MaPHG, TenPHG) DDIEM_PHG(MaPHG, DDIEM)Thuộc tính đa trịNhập môn Cơ sở dữ liệu - Khoa CNTT29Dạng chuẩn 1 (tt)Lược đồ gốc: 	Table (Key1, aaa. . . (Key2, bbb. . . (Key3, ccc. . .) ) )Để thỏa mãn 1NF chúng ta thực hiệnTable1(Key1, aaa . . .)Table2(Key1, Key2, bbb . .)Table3(Key1, Key2, Key3, ccc. . .)Table (Key1, . . . (Key2, . . . (Key3, . . .) ) )Table1(Key1, . . .)TableA (Key1,Key2 . . .(Key3, . . .) )Table2 (Key1, Key2 . . .)Table3 (Key1, Key2, Key3, . . .)Nhập môn Cơ sở dữ liệu - Khoa CNTT30Dạng chuẩn 1 (tt)Vấn đề còn tồn tại trong 1NFXét lược đồ DDIEM_PHG(MaPHG, DDIEM)Vẫn bị lặp lạiẨn chứa các phụ thuộc hàm bộ phận DIADIEMMAPHG1455TP HCMVUNGTAUNHATRANGHA NOI5TP HCMNhập môn Cơ sở dữ liệu - Khoa CNTT31Dạng chuẩn 2 Phụ thuộc hàm đầy đủ: Một phụ thuộc hàm X  Y là một phụ thuộc hàm đầy đủ nếu loại bỏ bất kỳ thuộc tính A nào ra khỏi X thì phụ thuộc hàm không còn đúng nữa. 	∀ A, A  X, (X – {A})  Y : là sai. Phụ thuộc hàm bộ phận: Một phụ thuộc hàm X  Y là phụ thuộc bộ phận nếu có thể bỏ một thuộc tính A X, ra khỏi X phụ thuộc hàm vẫn đúng, điều đó có nghĩa là với 	∃A X, (X – {A})  Y Nhập môn Cơ sở dữ liệu - Khoa CNTT32Dạng chuẩn 2 (tt)2NF: Thỏa mãn 1NFPhụ thuộc hàm đầy đủ vào khóa chínhVới các quan hệ có thuộc tính khóa đơn thì ko phải xétChỉ kiểm tra các lược đồ có chứa phụ thuộc hàm bộ phậnNhập môn Cơ sở dữ liệu - Khoa CNTT33Dạng chuẩn 2 (tt)Ví dụ	NV_DA(MaNV, MaDA, Sogio, TenDA, DDiemDA)Phụ thuộc vào cả 2 MaNV, MaDAChỉ phụ thuộc vào MaDANhập môn Cơ sở dữ liệu - Khoa CNTT34Dạng chuẩn 2 (tt)Ví dụ	NV_DA(MaNV, MaDA, Sogio, TenDA, DDiemDA)Phụ thuộc vào cả 2 MaNV, MaDAChỉ phụ thuộc vào MaDANV_DA(MaNV, MaDA, Sogio)DUAN(MaDA, TenDA)DUAN(MaDA, DDiemDA)Nhập môn Cơ sở dữ liệu - Khoa CNTT35Dạng chuẩn 33NF dựa trên khái niệm phụ thuộc bắc cầu. ĐN: Một lược đồ quan hệ R là ở 3NF nếu nó thoả mãn ( theo Codd)Thỏa mãn 2NF Không có thuộc tính không khoá nào của R là phụ thuộc bắc cầu vào khoá chính. Nhập môn Cơ sở dữ liệu - Khoa CNTT36Dạng chuẩn 3 (tt)NV_DV(MaNV, TenNV, NS, DCHI, MaDV, TenDV, TruongPHG)Phụ thuộc vào MaNVPhụ thuộc vào MaDVTất cả các thuộc tính phải phụ thuộc vào thuộc tính khóaMột vài thuộc tính phụ thuộc vào thuộc tính ko phải là khóaChuẩn hóa  Tách nhóm các thuộc tính đó thành quan hệ mớiNhập môn Cơ sở dữ liệu - Khoa CNTT37Dạng chuẩn 3 (tt)DONVI(MaDV, TenDV, TruongPHG)Phụ thuộc vào MaNVPhụ thuộc vào MaDVNHANVIEN(MaNV, TenNV, NS, DCHI, MaDV)NV_DV(MaNV, TenNV, NS, DCHI, MaDV, TenDV, TruongPHG)Nhập môn Cơ sở dữ liệu - Khoa CNTT38Tóm tắt 3 dạng chuẩn 1-3NFNhận biếtCách chuẩn hóa1Quan hệ ko có thuộc tính đa trị và quan hệ lặpChuyển tất cả quan hệ lặp hoặc đa trị thành 1 quan hệ mới2Phụ thuộc 1 phần vào thuộc tính khóaTách thuộc tính phụ thuộc 1 phần thành lược đồ mới, đảm bảo quan hệ với lược đồ liên quan3Phụ thuộc ẩn, tồn tại phụ thuộc hàm giữa các thuộc tính ko phải là khóaTách các thuộc tính đó thành lược đồ mớiNhập môn Cơ sở dữ liệu - Khoa CNTT39Dạng chuẩn Boyce-CoddMột lược đồ quan hệ R được gọi là ở dạng chuẩn Boyce-Codd (BCNF) nếu nó Thỏa mãn dạng chuẩn 3NF Không có các thuộc tính khóa phụ thuộc hàm và thuộc tính không khóa. Ví dụNhập môn Cơ sở dữ liệu - Khoa CNTT40Dạng chuẩn Boyce-Codd(tt)Ví dụ: 	R (A1,A2,A3,A4,A5) Với các phụ thuộc hàm: A1,A2  A3,A4,A5A4  A2 Nhập môn Cơ sở dữ liệu - Khoa CNTT41Dạng chuẩn Boyce-Codd(tt)Nếu một lược đồ quan hệ không thoả mãn điều kiện BCNF, thủ tục chuẩn hóa bao gồm: Loại bỏ các thuộc tính khóa phụ thuộc hàm vào thuộc tính không khóa ra khỏi quan hệ tách chúng thành một quan hệ riêng có khoá chính là thuộc tính không khóa gây ra phụ thuộc. Ví dụ trên: R (A1,A2,A3,A4,A5) Với các phụ thuộc hàm: A1,A2  A3,A4,A5A4  A2 lược đồ được tách ra như sau:R1( A4, A2)R2(A1, A4, A3, A5)Nhập môn Cơ sở dữ liệu - Khoa CNTT42SV_MH_GV(MaSV, MONHOC, GIANGVIEN)Dạng chuẩn Boyce-Codd(tt)Phụ thuộc vào MONHOCVí dụ	Phụ thuộc vào cả 2 MaSV, MaDANhập môn Cơ sở dữ liệu - Khoa CNTT43Dạng chuẩn Boyce-Codd(tt)Phụ thuộc vào MONHOCSV_MH_GV(MaSV, MaMH, MaGV)Ví dụ	Phụ thuộc vào cả 2 MaSV, MaMHMH_GV(MaGV, MaMH)SV_MH(MaSV, MaMH)Nhập môn Cơ sở dữ liệu - Khoa CNTT44Tài liệu tham khảoGiáo trình CSDLChương 4Database management systemChapter 15Fundamentals of Database SystemsChapter 14Nhập môn Cơ sở dữ liệu - Khoa CNTT45Nhập môn Cơ sở dữ liệu - Khoa CNTT46