Bài giảng Cơ sở dữ liệu - Chương 5: Chuẩn hóa cơ sở dữ liệu - Nguyễn Như Hoa

Chương 5 Chuẩn hóa cơ sở dữ liệu (phụ thuộc hàm & dạng chuẩn) Giáo trình & Tài liệu tham khảo: 1. Ramez Elmasri, Shamkant B. Navathe, 2011. Fundamentals of Database systems, 6th edition, Addison-Wesley. 2. Giáo trình Cơ sở dữ liệu , Trần Đắc Phiến, ĐH Công nghiệp TPHCM 3. Bộ slide bài giảng của Nguyễn Minh Thư, Khoa CNTT, ĐH KHTN TPHCM 4. Bộ slide bài giảng của Trần Thị Kim Chi, Khoa CNTT, ĐH Công nghiệp TPHCM Gv. Nguyễn Như Hoa 1 Nội dung • Giới thiệu • Phụ thuộc hàm • Dạng chuẩn và quá trình chuẩn hóa CSDL 2 Giới thiệu • Một thiết kế DB tốt là một thiết kế – Đưa ra tập các quan hệ chứa các thuộc tính biểu diễn được các dữ liệu mong muốn của bài toán – Tối thiểu hoặc loại bỏ sự dư thừa dữ liệu trong mỗi quan hệ 3 Giới thiệu • Dư thừa dữ liệu trong thiết kế sẽ dẫn tới – Tốn không gian lưu trữ – Sai dữ liệu hay dị thường dữ liệu (update anomalies) khi thực hiện Insert/Update/Delete • Ví dụ: xét 2 thiết kế DB Nhanvien( MaNV, Ten, Vitri, Luong, MaPB) Phongban(MaPB, TenPB) Nhanvien_PB(MaNV, Ten, Vitri, Luong, MaPB, TenPB) Thiết kế 1 Thiết kế 2 4 Giới thiệu MaNV TeNV Vitri Luong MaPB 0111 Nguyen An Manager 30000 B005 0112 Bui Liem Assistant 20000 B005 0201 Le Van Assistant 15000 B004 0202 Tran Mai Assistant 15000 B004 0203 Tran Tuan Manager 20000 B003 MaPB TenPB B003 Dieu hanh B004 Nghien cuu B005 To chuc MaNV TeNV Vitri Luong MaPB TenPB 0111 Nguyen An Manager 30000 B005 To chuc 0112 Bui Liem Assistant 20000 B005 To chuc 0201 Le Van Assistant 15000 B004 Nghien cuu 0202 Tran Mai Assistant 15000 B004 Nghien cuu 0203 Tran Tuan Manager 20000 B003 Dieu hanh Nhanvien_PB Nhanvien Phongban Thiết kế 2 dư thừa dữ liệu : TenPB lặp lại ở nhiều dòng Thiết kế 1 không dư thừa dữ liệu 5 Giới thiệu Bất thường khi I/U/D dữ liệu trong thiết kế 2 • Thêm một nhân viên mới (insert), phải đảm bảo TenPB tương ứng với MaPB, khớp với các bộ đã có • Thêm một phòng ban mới là không thể, vì MaNV không thể Null MaNV TeNV Vitri Luong MaPB TenPB 0111 Nguyen An Manager 30000 B005 To chuc 0112 Bui Liem Assistant 20000 B005 To chuc 0201 Le Van Assistant 15000 B004 Nghien cuu 0202 Tran Mai Assistant 15000 B004 Nghien cuu 0203 Tran Tuan Manager 20000 B003 Dieu hanh 0301 Pham Tin Assistant 20000 B005 TCHC Mâu thuẫn với MaPB, TenPB của các bộ đã có Insert bộ này là không thể MaNV TeNV Vitri Luong MaPB TenPB 0111 Nguyen An Manager 30000 B005 To chuc 0112 Bui Liem Assistant 20000 B005 To chuc 0201 Le Van Assistant 15000 B004 Nghien cuu 0202 Tran Mai Assistant 15000 B004 Nghien cuu 0203 Tran Tuan Manager 20000 B003 Dieu hanh B001 Ke toan Insert 6 Giới thiệu Bất thường khi I/U/D dữ liệu trong thiết kế 2 • Xóa một nhân viên : nếu nhân viên này là nhân viên duy nhất của một phòng ban , thao tác xóa sẽ dẫn đến xóa luôn phòng ban -> mất thông tin Xóa nhân viên 0203 sẽ dẫn tới xóa luôn phòng ban B003 MaNV TeNV Vitri Luong MaPB TenPB 0111 Nguyen An Manager 30000 B005 To chuc 0112 Bui Liem Assistant 20000 B005 To chuc 0201 Le Van Assistant 15000 B004 Nghien cuu 0202 Tran Mai Assistant 15000 B004 Nghien cuu 0203 Tran Tuan Manager 20000 B003 Dieu hanh 7 Giới thiệu Bất thường khi I/U/D dữ liệu trong thiết kế 2 • Khi sửa tên một phòng ban : phải đảm bảo sửa tên phòng ban ở tất cả các bộ tương ứng. Nếu không sẽ mất tính nhất quán dữ liệu (sai dữ liệu) MaNV TeNV Vitri Luong MaPB TenPB 0111 Nguyen An Manager 30000 B005 To chuc 0112 Bui Liem Assistant 20000 B005 Quan ly Nhan su 0201 Le Van Assistant 15000 B004 Nghien cuu 0202 Tran Mai Assistant 15000 B004 Nghien cuu 0203 Tran Tuan Manager 20000 B003 Dieu hanh Sửa Tên PB (hay sửa Mã PB) mà không sửa trên tât cả các bộ tương ứng sẽ dẫn đến mất tính nhất quán 8 Giới thiệu • Chuẩn hóa CSDL (normalization) ? – Chuẩn hóa là kỹ thuật dựa trên “dạng chuẩn”, cho phép người thiết kế đánh giá một lược đồ quan hệ và điều chỉnh thiết kế để giảm thiểu hoặc loại bỏ dư thừa dữ liệu – Chuẩn hóa dựa trên các dạng chuẩn (normal form) 1NF, 2NF, 3NF, BCNF, • Các dạng chuẩn cao hơn thì giảm/loại bỏ dư thừa dữ liệu mạnh hơn 9 Giới thiệu • Phụ thuộc hàm (functional dependency) – Mô tả mối quan hệ giữa các thuộc tính trong một quan hệ – Là khái niệm nền tảng để có thể hiểu “dạng chuẩn” 10 Phụ thuộc hàm Nội dung • Khái niệm & Ví dụ • Định nghĩa khóa • Bao đóng của tập phụ thuộc hàm • Luật dẫn Amstrong • Bao đóng của tập thuộc tính • Thuật toán tìm tất cả các khóa • Phủ tối thiểu 11 Phụ thuộc hàm- Khái niệm • Định nghĩa Cho R(A1, A2, , An ) là lược đồ quan hệ X, Y là hai tập thuộc tính của R r là quan hệ bất kỳ trên R t1, t2 là hai bộ bất kỳ trên r Phụ thuộc hàm X xác định Y : ( hay Y phụ thuộc hàm vào X )  ( t1.X = t2.X  t1.Y = t2.Y ) X  Y 12 Phụ thuộc hàm - Khái niệm • Lưu ý : – X -> Y khi và chỉ khi : t1, t2r , t1.X = t2.X  t1.Y = t2.Y nhưng không có chiều ngược lại – (*) Nếu phụ thuộc hàm X -> Y tồn tại trong một lược đồ quan hệ R, hay được xác định như thuộc tính của R, thì X -> Y phải thỏa trên mọi thể hiện của R – Các phụ thuộc hàm được nhận diện dựa vào các qui tắc nghiệp vụ , hay ngữ nghĩa của các thuộc tính => Phụ thuộc hàm là một loại ràng buộc toàn vẹn – Ta bỏ qua các phụ thuộc hàm hiển nhiên (luôn luôn đúng) • MaNV, TenNV -> TenNV • MaNV, TenNV -> MaNV • MaNV, Vitri -> MaNV . 13 Phụ thuộc hàm - Ví dụ • Các phụ thuộc hàm được nhận diện dựa vào các qui tắc nghiệp vụ , hay ngữ nghĩa của các thuộc tính – Mỗi mã phòng ban xác định duy nhất một tên phòng ban MAPB  TENPB – Mỗi mã NV xác định duy nhất một tên nv, một vị trí, tiền lương và phòng ban MANV  TENNV, VITRI, LUONG, MAPB, TENPB – Mỗi vị trí của một phòng ban xác định một mức lương MAPB, VITRI  LUONG MaNV TeNV Vitri Luong MaPB TenPB 0111 Nguyen An Manager 30000 B005 To chuc 0112 Bui Liem Assistant 20000 B005 To chuc 0201 Le Van Assistant 15000 B004 Nghien cuu 0202 Tran Mai Assistant 15000 B004 Nghien cuu 0203 Tran Tuan Manager 20000 B003 Dieu hanh NHANVIEN 14 Phụ thuộc hàm - Ví dụ • Vd(tt) : Xác định có là phụ thuộc hàm không ? Tại sao ? • LUONG  MAPB, VITRI • VITRI  MANV • TENPB  MAPB • TENPB, VITRI  LUONG MaNV TeNV Vitri Luong MaPB TenPB 0111 Nguyen An Manager 30000 B005 To chuc 0112 Bui Liem Assistant 20000 B005 To chuc 0201 Le Van Assistant 15000 B004 Nghien cuu 0202 Tran Mai Assistant 15000 B004 Nghien cuu 0203 Tran Tuan Manager 20000 B003 Dieu hanh NHANVIEN 15 Phụ thuộc hàm - Ví dụ Ví dụ - xác định các phụ thuộc hàm dựa trên các qui tắc nghiệp vụ sau : • Mỗi máy bay có một giờ khởi hành duy nhất • Một máy bay và ngày khởi hành sẽ xác định một phi công • Một phi công và một ngày, giờ khởi hành sẽ xác định được máy bay PhiCong Maybay NgayKH GioKH CHUYENBAY MAYBAY -> GIOKH MAYBAY, NGAYKH -> PHICONG PHICONG, NGAYKH, GIOKH -> MAYBAY Kiểm tra trên dữ liệu ? 16 Định nghĩa khóa • Siêu khóa/Khóa dự tuyển/ khóa chính : là một loại phụ thuộc hàm Cho R(A1, A2, , An) , với Q+ là tập thuộc tính của R, K là tập con của Q+ K là khóa dự tuyển nếu thỏa : – Tồn tại pth K-> Q+ trên R – Không tồn tại K’ K mà K’ -> Q+ là một phụ thuộc hàm trên R Siêu khóa S là tập thuộc tính thỏa K  S • Cho NHANVIEN(MANV, TenNV, Vitri, Luong, MaPB, TenPB) và 2 pth f1 : MANV, TENNV  MANV, TENNV, VITRI, LUONG, MAPB, TENPB f2 : MANV  MANV, TENNV, VITRI, LUONG, MAPB, TENPB  {MANV} là khóa dự tuyển  {MANV, TENNV} là siêu khóa 17 Bao đóng của tập phụ thuộc hàm • Dựa trên ngữ nghĩa của các thuộc tính của R, ban đầu ta xác định được tập pth F • Ta gọi f là pth được suy dẫn từ tập F, nếu với mọi r(R) thỏa các pth thuộc F thì cũng thỏa f • Tập phụ thuộc hàm chứa tất cả các phụ thuộc hàm f suy dẫn từ tập F gọi là bao đóng của tập phụ thuộc hàm F , ký hiệu F+ • Qui tắc suy dẫn ? 18 Bộ luật dẫn Armstrong • Bộ luật dẫn Armstrong Cho quan hệ R(Q+) . X,Y,Z,W là các tập con của Q+. Rule 1. Phản xạ : Nếu X  Y thì XY Rule 2. Gia tăng: XY  XZ YZ Rule 3. Bắc cầu : XY và YZ  X Z Rule 4. Hợp : XY và XZ  X YZ Rule 5. Chiếu/phân rã: XYZ  X Y và X Z Rule 6. Bắc cầu giả: XY và YZW  XZ W 19 Bộ luật dẫn Armstrong • Cho R(A,B,C,D) và tập phụ thuộc hàm trên R F = {AB, AC, BCD} Hãy chứng minh các pth sau được suy dẫn từ F : AD, ACBCD ? (hay chứng minh {AD, ACBCD}  F+ ) Chứng minh A  D  F+ : AB và AC => A  BC (luật hợp) A  BC và BCD => A  D (bắc cầu) Chứng minh AC  BCD  F+ : A  B => AC  BC (luật tăng) AC  BC và BCD => AC  D (luật bắc cầu) AC  D => AC  BCD (luật tăng) AB AC BCD AD ACBCD F F+ 20 Bao đóng của tập thuộc tính X • Bao đóng của tập thuộc tính X , ký hiệu X+ – Ứng với mỗi tập thuộc tính X, ta xác định tập X+ chứa các thuộc tính phụ thuộc hàm vào X dựa trên F X+ =  Ai với X -> Ai là phụ thuộc hàm được suy diễn từ F - Thuật toán xác định X + dựa trên F 21 Bao đóng của tập thuộc tính X • Bao đóng của tập thuộc tính X , ký hiệu X+ – Ví dụ : cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm F = { f1 : A -> B ; f2 : B -> C ; f3 : C -> D ; } Tìm bao đóng của tập X = {A} dựa trên F ? Giải : X+ = {A} X+ = X+  {B} = {A,B} , vì có A -> B , loại f1 X+ = X+  {C} = {A,B,C} , vì có B -> C , loại f2 X+ = X+  {D} = {A,B,C,D} , vì có C -> D , loại f3 Kết luận : bao đóng của tập {A} = {A,B,C,D} Tương tự, bao đóng của tập {B} = {B,C,D} Tương tự, bao đóng của tập {C} = {C,D} Tương tự, bao đóng của tập {D} = {D} 22 Tìm tất cả các khóa của R • Một định nghĩa về khóa (dựa trên bao đóng của tập thuộc tính) – Cho R (Q+), Q+ là tập thuộc tính của R, F là tập phụ thuộc hàm trên R, K là một tập con của Q+ K là một khóa của R nếu : K+ = Q+ và không tồn tại K’  K mà K’ + = Q+ 23 Tìm tất cả các khóa của R • Thuật toán tìm tất cả các khóa 24 Tìm tất cả các khóa của R • Thuật toán tìm tất cả các khóa – Ví dụ : Giải : 25 Phủ tối thiểu • Hai tập phụ thuộc hàm F và G tương đương nếu F+ = G+ (hay FG+ và G+  F ) , ký hiệu F  G • F là Tập phụ thuộc hàm tối thiểu (hay phủ tối thiểu) nếu F đồng thời thỏa 3 điều kiện : – F là tập pth có vế trái không dư thừa – F là tập pth có vế phải một thuộc tính – F là tập phụ thuộc hàm không dư thừa 26 Phủ tối thiểu • Thuật toán tìm phủ tối thiểu của tập pth F B1 : Loại khỏi F các pth có vế trái dư thừa B2 : Tách các pth có vế phải trên một thuộc tính thành các phụ thuộc hàm có vế phải một thuộc tính B3 : Loại khỏi F các pth dư thừa nhận xét : thuật toán cho phép luôn tìm được ít nhất một tập pth tương đương với F và là phủ tối thiểu của F 27 Phủ tối thiểu • Phụ thuộc hàm có vế trái dư thừa Z->Y là pth có vế trái dư thừa nếu tồn tại AZ sao cho F  F – (Z->Y)  (Z-A->Y) Vd : F = {A->BC ; B->C ; AB->D} Xét pth có vế trái 2 thuộc tính AB->D , Có A+={ABCD}, B+={C} A->D F+ thay cho AB->D trong F  F  {A->BC ; B->C ; A->D} 28 Phủ tối thiểu • F là tập pth không dư thừa nếu không tồn tại F’  F sao cho F’  F . Ngược lại, F là tập pth dư thừa Vd : F = {A->BC ; B->D ; AB->D} Thử loại A->BC có F’ = {B->D ; AB->D} => từ F’ không suy dẫn được A->BC => F’  F => ko loại A->BC Thử loại B->D có F’ = {A->BC ; AB->D} => từ F’ không suy dẫn được B->D => F’  F => ko loại B->D Thử loại AB->D có F’ = {A->BC ; B->D} => từ F’ suy dẫn được AB->D => F’  F => Loại được AB->D Kết luận : F  {A->BC ; B->C} 29 Phủ tối thiểu • Cho R(ABCD) và tập F = {AB->CD ; B->C ; C->D} Hãy tìm phủ tối thiểu của F ? • Bước 1 : xét pth có vế trái 2 thuộc tính AB->CD Có A+={A}; B+={BCD} => B->CDF+ thay cho AB->CD trong F => F  {B->CD ; B->C ; C->D } • Bước 2 : phân rã B->CD thành B->C và B->D => F  {B->D ; B->C ; C->D } • Bước 3 : Thử loại B->D, có F’={B->C; C->D} suy dẫn được B->D => loại B->D , có F  {B->C ; C->D } Thử loại B->C, có F’={B->D; C->D} không suy dẫn được B->C => không loại B->D Thử loại C->D, có F’={B->D; B->C} không suy dẫn được C->D => không loại C->D Kết luận : phủ tối thiểu của F là {B->C ; C->D } 30 Chuẩn hóa CSDL Nội dung • Các dạng chuẩn – Định nghĩa và ví dụ • Quá trình chuẩn hóa – Giới thiệu 31 Các dạng chuẩn • Một lược đồ quan hệ R ở dạng chuẩn 1 (1NF) nếu miền giá trị của các thuộc tính chỉ chứa các giá trị nguyên tử (đơn, không phân chia được) và giá trị của một thuộc tính bất kỳ trong mọi bộ phải là một giá trị đơn thuộc miền giá trị của thuộc tính • Một lược đồ quan hệ R ở dạng chuẩn 2 (2NF) nếu – R đạt dạng chuẩn 1 và – Mọi thuộc tính không khóa A đều phụ thuộc đầy đủ vào mọi khóa của R • Một lược đồ quan hệ R ở dạng chuẩn 3 (3NF) nếu – R đạt dạng chuẩn 2 và – Mọi thuộc tính không khóa đều không phụ thuộc bắc cầu vào một khóa bất kỳ của R • Một lược đồ quan hệ R ở dạng chuẩn Boyce-Codd (BCNF) nếu R đạt dạng chuẩn 3 và mọi phụ thuộc hàm X -> A  F+ thì đều có X là siêu khóa 32 Các dạng chuẩn • Định nghĩa 2 của dạng chuẩn 3 • Một lược đồ quan hệ R ở dạng chuẩn 3 (3NF) nếu – R đạt dạng chuẩn 2 và – Mọi phụ thuộc hàm đều có vế trái là siêu khóa hoặc vế phải là thuộc tính khóa 33 Dạng chuẩn 1 • Lược đồ quan hệ không đạt dạng chuẩn 1 • Lược đồ quan hệ đạt dạng chuẩn 1 MASV HOVATEN KHOA TENMONHOC DIEMTHI 99023 NGUYENTHITHU CONG NGHE THONG TIN KY THUAT LAP TRINH, TOAN ROI RAC, CO SO DU LIEU 6 , 8, 4 99030 LE VAN THANH DIEN TU VI XU LY 4 MASV HOVATEN KHOA TENMONHOC DIEMTHI 99023 NGUYENTHITHU CONG NGHE THONG TIN KY THUAT LAP TRINH 6 99023 NGUYENTHITHU CONG NGHE THONG TIN TOAN ROI RAC 8 99023 NGUYENTHITHU CONG NGHE THONG TIN CO SO DU LIEU 4 99030 LE VAN THANH DIEN TU VI XULY 4 34 Dạng chuẩn 2 • XA là phụ thuộc hàm đầy đủ nếu không tồn tại YA với Y  X • Lược đồ quan hệ đạt dạng chuẩn 2 Xác định dạng chuẩn của lược đồ quan hệ sau ? Detai(MaSV, TenDetai, TenGV , MaGV) với F = { MaSV -> TenDetai, TenGV, MaGV ; MaGV -> TenGV } Giải : Có 1 khóa là {MaSV} (*)sử dụng thuật toán tìm các khóa {MaSV} là khóa có một thuộc tính , mọi thuộc tính không khóa đều phụ thuộc đầy đủ vào khóa => lược đồ qh đạt 2NF 35 Dạng chuẩn 2 • Lược đồ quan hệ không đạt 2 NF Xác định dạng chuẩn của lược đồ quan hệ sau ? EMP_PROJ( Ssn , Pnumber, Hours, Ename, Pname, Plocation ) F = { Ssn, Pnumber -> Hours ; Ssn -> Ename ; Pnumber -> Pname, Plocation } Giải : Lược đồ quan hệ có 1 khóa {Ssn , Pnumber } (*)sử dụng thuật toán tìm các khóa Ssn, Pnumber -> Hours là pth đầy đủ , vì không tồn tại Ssn -> Hours và Pnumber -> Hours Ssn , Pnumber -> Ename là pth không đầy đủ, vì tồn tại Ssn -> Ename Ssn , Pnumber -> Pname, Plocation là pth không đầy đủ, vì tồn tại Pnumber -> Pname, Plocation => Tồn tại các thuộc tính không khóa Ename, Pname, Plocation phụ thuộc không đầy đủ vào khóa => Lược đồ qh không đạt 2NF 36 Dạng chuẩn 3 • Cho Q là lược đồ quan hệ, X và Y là hai tập con của Q+, A là một thuộc tính. Thuộc tính A phụ thuộc bắc cầu vào X , nếu – tồn tại XY, YA và – không tồn tại YX và – A  XY • Lược đồ không đạt 3NF Xác định dạng chuẩn của lược đồ quan hệ sau ? Detai(MaSV, TenDetai, TenGV , MaGV) với F = { MaSV -> TenDetai, TenGV, MaGV ; MaGV -> TenGV } Giải : Lược đồ quan hệ có 1 khóa {MaSV} (*)sử dụng thuật toán tìm các khóa MaSV ->TenGV (dựa theo luật Bắc cầu với MaSV -> MaGV và MaGV -> TenGV ) TenGV là thuộc tính không khóa, phụ thuộc bắc cầu vào khóa => lược đồ qh không đạt 3NF 37 Dạng chuẩn 3 • Lược đồ đạt 3NF Xác định dạng chuẩn của lược đồ ? SINHVIEN_HOC(MaSV, Monhoc, MaGV) với F = { MaSV, Monhoc -> MaGV ; MaGV -> Monhoc } Giải : - Lược đồ có các khóa {MaSV, Monhoc}, {MaSV,MaGV} (*)sử dụng thuật toán tìm các khóa - Mọi thuộc tính không khóa (  ) không phụ thuộc bắc cầu vào các khóa => lược đồ quan hệ đạt 3NF 38 Dạng chuẩn BCNF • Lược đồ đạt BCNF Xác định dạng chuẩn của các R ? Detai(MaSV, TenDetai, MaGV) với F = { MaSV -> TenDetai, MaGV } Giaovien(MaGV, TenGV) với F = { MaSV -> TenGV} Giải : - Mọi pth X->A trong mỗi lược đồ đều có X là siêu khóa => Các lược đồ đạt BCNF Hệ quả : Lược đồ quan hệ chỉ có hai thuộc tính thì luôn đạt BCNF 39 Dạng chuẩn BCNF • Lược đồ không đạt BCNF Xác định dạng chuẩn của R ? Cho R(A,B,C,D) với tập F = {AB->CD, C->B} Giải : - R có các khóa {AB} , {AC} (*)sử dụng thuật toán tìm các khóa - Tồn tại C-> B là phụ thuộc hàm có vế trái không phải là siêu khóa => R không đạt BCNF - Thuộc tính không khóa D : không phụ thuộc bắc cầu vào mọi khóa => R đạt 3NF => kết luận : R đạt 3NF 40 Dạng chuẩn của một lược đồ CSDL • Nhận xét từ định nghĩa các dạng chuẩn – Nếu một lược đồ quan hệ đạt BCNF thì cũng đạt 3NF, 2NF và 1NF – Nếu một lược đồ quan hệ đạt 3NF thì cũng đạt 2NF và 1NF – Nếu một lược đồ quan hệ đạt dạng chuẩn 2NF thì cũng đạt 1NF • Định nghĩa: Dạng chuẩn của một lược đồ cơ sở dữ liệu là dạng chuẩn thấp nhất trong các dạng chuẩn của các lược đồ quan hệ 41 Thuật toán kiểm tra dạng chuẩn của một lược đồ quan hệ • Vào: lược đồ quan hệ Q, tập phụ thuộc hàm F • Ra: khẳng định Q đạt chuẩn gì? • Bước 1: Tìm tất cả các khóa của Q, tách vế phải còn 1 thuộc tính • Bước 2: Kiểm tra chuẩn BC – Xét tất cả các phụ thuộc hàm nếu mọi phụ thuộc hàm đều có vế trái là siêu khóa thì Q đạt BCNF, 3NF, 2NF, 1NF, kết thúc thuật toán – Ngược lại qua bước 3 • Bước 3: Kiểm tra chuẩn 3 – Xét tất cả các phụ thuộc hàm nếu mọi phụ thuộc hàm đều có vế trái là siêu khóa hoặc vế phải là thuộc tính khóa thì Q đạt 3NF, 2NF, 1NF, kết thúc thuật toán – Ngược lại qua bước 4 • Bước 4: Kiểm tra chuẩn 2 – Với mỗi khóa K, tìm bao đóng của tất cả các tập con thật sự của mỗi khóa, nếu tất cả các bao đóng đều không chứa thuộc tính không khóa thì Q đạt 2NF, kết thúc thuật toán – Ngược lại Q đạt 1NF 42 Quá trình chuẩn hóa CSDL • Mục tiêu : thay đổi thiết kế của CSDL sao cho các lược đồ quan hệ trong CSDL có dạng chuẩn BCNF hoặc 3NF • Quá trình chuẩn hóa bao gồm một số bước – Ở mỗi bước, mỗi lược đồ quan hệ được đánh giá đạt dạng chuẩn nào – Thực hiện biến đổi để một lược đồ quan hệ đạt dạng chuẩn cao hơn bằng cách phân rã (tách) lược đồ quan hệ thành một số lược đồ quan hệ có dạng chuẩn cao hơn – Quá trình phân rã phải đảm bảo bảo toàn thông tin và bảo toàn phụ thuộc 43 Phongban(MaPB, TenPB) với F = {MAPB->TENPB} Có một khóa {MAPB} => Đạt BCNF Nhanvien_PB(MaNV, TenNV, Vitri, Luong, MaPB, TenPB) Với F = {MANV  TENNV, VITRI, LUONG, MAPB; MAPB  TENPB; MAPB, VITRI  LUONG } Có 1 khóa {MANV} => đạt 2NF Nhanvien( MaNV, TenNV, Vitri, Luong, MaPB) với F = {MANV  TENNV, VITRI, LUONG, MAPB ; MAPB, VITRI  LUONG } Có 1 khóa {MANV} => Đạt 2NF PB_LUONG (MAPB, VITRI, LUONG) với F = {MAPB, VITRI  LUONG } => đạt BNCF Nhanvien( MaNV, TenNV ) với F = {MANV  TENNV} Phongban(MaPB, TenPB) với F = {MAPB->TENPB} Nhanvien_VT(MaNV, Vitri, MaPB) với F = { MANV  VITRI, MAPB } PB_LUONG (MAPB, VITRI, LUONG) với F = {MAPB, VITRI  LUONG } => kết quả : Lược đồ CSDL với 4 lược đồ quan hệ đạt BCNF, bảo toàn thôngtin và bảo toàn phụ thuộc Nhanvien( MaNV, TenNV ) với F = {MANV  TENNV} =>Đạt BCNF Nhanvien_VT(MaNV, Vitri, MaPB) với F = { MANV  VITRI, MAPB } =>Đạt BCNF 44 Tóm tắt - Dư thừa dữ