Cơ sở dữ liệu quan hệ - Chương VI: Chuẩn hóa CSDL - Nguyễn Thị Tâm

CHƯƠNG VI: CHUẨN HÓA CSDL Cơ sở dữ liệu 2 NỘI DUNG  Nguyên tắc thiết kế CSDL  Phép tách các lược đồ quan hệ  Các dạng chuẩn của lược đồ quan hệ I. Nguyên tắc thiết kế CSDL Cơ sở dữ liệu 3 Cơ sở dữ liệu 4 Cơ sở dữ liệu 5 II. Các dạng chuẩn của lược đồ quan hệ  Chuẩn hóa là quá trình phân tích các quan hệ cho trước dựa trên tập phụ thuộc hàm và khóa chính để: - Tối thiểu việc dư thừa thông tin - Tránh dị thường thông tin - Truy cập nhanh  Chuẩn hóa các bảng: là việc áp dụng một số quy tắc để đưa các bảng từ dạng chuẩn thấp lên dạng chuẩn cao hơn  quá trình này thực hiện theo phương pháp trên xuống bằng việc đánh giá mối quan quan hệ và tách quan hệ nếu cần  Cơ sở của chuẩn hóa dựa trên: phụ thuộc hàm, phụ thuộc đầy đủ, khóa, thuộc tính không khóa, Cơ sở dữ liệu 6  Các loại dạng chuẩn gồm: - Dạng chuẩn 1 (1NF – First Normal Form) - Dạng chuẩn 2 (2NF – Second Normal Form) - Dạng chuẩn 3 (3NF) - Dạng chuẩn Boye Code (BCNF) Cơ sở dữ liệu 7 1. Một số khái niệm cơ bản  Thuộc tính khoá và không khoá: Cho lược đồ quan hệ R trên tập thuộc tính U={A1, .., An}. - Thuộc tính A U được gọi là thuộc tính khoá nếu A là một thành phần thuộc một khoá tối thiểu nào đó của R - ngược lại A được gọi là thuộc tính không khóa - Ví dụ: Cho lược đồ R = U = { A, B, C, D } F = { AB C, B D, BC A }  Ta thấy AB và BC là khoá. A, B, C là thuộc tính khoá D là thuộc tính không khoá Cơ sở dữ liệu 8  Phụ thuộc hàm đầy đủ: Cho lược đồ quan hệ R(U) với U = { A1, ... ,Ak}. X,Y U, và X ≠ Y. Nói rằng, Y là phụ thuộc hàm đầy đủ vào X nếu: - X Y thuộc F+ - với mọi tập con thực sự X’ của X thì X’ Y không thuộc F+  Y phụ thuộc hàm đầy đủ vào X nếu Y phụ thuộc hàm vào X nhưng không phụ thuộc hàm vào bất kỳ một tập con thực sự nào của X  Ví dụ: Cho tập F={AB->C; A->C} thì ta thấy AB->C là phụ thuộc hàm không đầy đủ vì C còn phụ thuộc hàm vào A. Cơ sở dữ liệu 9  Phụ thuộc bắc cầu: Cho lược đồ quan hệ R(U); X U, A U, F là phụ thuộc hàm trên R  A được gọi là phụ thuộc bắc cầu vào X trên R nếu Y, Y U sao cho X Y, Y A thuộc F+ nhưng Y X không thuộc F+  Ngược lại, nói rằng A không phụ thuộc bắc cầu vào X hay A phụ thuộc trực tiếp vào X  Ví dụ: Cho tập F={A->B; B->C; A->D} =>C phụ thuộc bắc cầu vào A Và D phụ thuộc trực tiếp vào A Cơ sở dữ liệu 10 2. Dạng chuẩn 1NF  Định nghĩa: Quan hệ được gọi là ở chuẩn 1NF nếu các giá trị của tất cả các thuộc tính đều phải là nguyên tử (đơn, không phân chia được) => không chứa các thuộc tính có giá trị lặp hoặc đa trị  Cách khác: bảng ở dạng 1NF là bảng có tồn tại PTH có nguồn là một phần của khóa (phụ thuộc bộ phận) .  Chú ý: khi xét dạng chuẩn nếu không nói gì thêm thì dạng chuẩn đang xét ít nhất là đạt dạng chuẩn một  Biểu diễn sơ đồ: R(A1,A2,A3, A4, A5) Cơ sở dữ liệu 11 VD: Cho bảng quan hệ GD (Ten_GV, MON_GD) C, VISUAL BASIC, TK WEP Hà PASCAL, NM CSDN Lan Mon_GD Ten_GV Không ở 1NF TK WEP Hà VISUAL BASIC Hà NM CSDN Lan C Hà PASCAL Lan Mon_GD Ten_GV ở 1NF Cơ sở dữ liệu 12  Kết luận: Để kiểm tra một lược đồ có là dạng 1NF không thực hiện kiểm tra nếu thỏa mãn: - Không có thuộc tính là thuộc tính đa trị - Không có thuộc tính là thuộc tính phức hợp Cơ sở dữ liệu 14 2. Dạng chuẩn 2NF  Định nghĩa: Lược đồ quan hệ R ở 2NF khi và chỉ khi - R đã là 1NF - Mọi thuộc tính không khóa của R là phụ thuộc hàm đầy đủ vào khóa chính  Cách khác: lược đồ quan hệ R được gọi là 2NF nếu tồn tại phụ thuộc hàm bắc cầu vào khóa  Biểu diễn sơ đồ:  Mục đích: - giản ước sự dư thừa dữ liệu - tránh các dị thường cập nhật gây nên do sự dư thừa dữ liệu này R(A1,A2,A3, A4, A5) Cơ sở dữ liệu 15 Cơ sở dữ liệu 16 Thuật toán kiểm tra dạng chuẩn 2  Bước 1: Tìm tất cả các khóa của quan hệ  Bước 2: Với mỗi khóa K, tìm bao đóng của tất cả các tập con thực sự S của K - Chú ý: nếu khóa có một thuộc tính đơn thì không cần phải kiểm tra  Bước 3: nếu có bao đóng S+ chứa thuộc tính không khóa thì quan hệ không đạt chuẩn 2 ngược lại thì quan hệ đạt chuẩn 2  Nhận xét: - Nếu mọi khóa của lược đồ quan hệ R chỉ có 1 thuộc tính thì R là 2NF - R là 2NF X → A F+, với X K (K là khóa của R) thì:  hoặc A là thuộc tính khóa  hoặc A X (X → A là phụ thuộc hàm tầm thường) Cơ sở dữ liệu 17  Ví dụ 1: Cho LĐQH R = {A,B,C,D,E,G} và - F = { A → BC, C → DE, E → G }  Ta thấy A là khóa vì A+ = R (tập thuộc tính của quan hệ).  Các thuộc tính không khóa là {B,C,D,E,G}.  Do khóa chỉ có một thuộc tính (các thuộc tính khác phụ thuộc đầy đủ vào khóa) => quan hệ R ở 2NF. Cơ sở dữ liệu 18  Ví dụ 2: Cho lược đồ quan hệ Q(A,B,C,D) và tập phụ thuộc hàm F = {AB C, B D, BC A}. Hỏi Q có đạt chuẩn 2 không?  Khóa là K1 = AB và K2 = BC  Ta thấy B+ = BD  Vậy: - D là thuộc tính không khóa - thuộc tính không khóa D không phụ thuộc đầy đủ vào khóa  => Q không đạt chuẩn 2 Cơ sở dữ liệu 19  Chú ý: nếu quan hệ không thỏa mãn điều kiện 2NF có thể chuẩn hóa để có 2NF như sau: - nhóm vào một quan hệ gồm các thuộc tính phụ thuộc hoàn toàn vào khoá và giữ lại khoá của quan hệ đó - nhóm vào một quan hệ khác các thuộc tính phụ thuộc vào một phần của khoá, lấy phần đó làm khoá chính cho quan hệ .  Ví dụ 1: - Cho lược đồ quan hệ Q(A,B,C,D) và tập phụ thuộc hàm F = {AB C, B D, BC A} => Không đạt chuẩn 2 - Tách thành: Q1( B,D) và Q2( A, B, C)  Ví dụ 2: - trong quan hệ R2 (Số hoá đơn, Số sản phẩm, Tên sản phẩm, Lượng yêu cầu) có phụ thuộc hàm : Số sản phẩmTên sản phẩm trong đó Số sản phẩm là một phần của khoá => quan hệ chưa ở dạng chuẩn 2 - ta tách R2 thành R3 và R4 như sau :  R3 (Số hoá đơn, Số sản phẩm, Lượng yêu cầu)  R4 (Số sản phẩm, Tên sản phẩm) Cơ sở dữ liệu 20  Ví dụ: xét lược đồ quan hệ: NHÂNVIÊN_DỰÁN( MãsốNV, MãsốDA, Sốgiờ, HọtênNV, TênDA, ĐịađiểmDA)  với các phụ thuộc hàm: - MãsốNV, MãsốDA → Sốgiờ - MãsốNV → HọtênNV - MãsốDA →TênDA, ĐịađiểmDA  NX: có những thuộc tính không khoá phụ thuộc vào một bộ phận của khoá chính, như vậy nó không thoả mãn điều kiên 2NF.  Áp dụng phương pháp chuẩn hoá trên, lược đồ được tách thành các lược đồ như sau: - N_D1(MãsốDA, TênDA, ĐịađiểmDA) - N_D2(MãsốNV , HọtênNV) - N_D3(MãsốNV, MãsốDA, Sốgiờ) Cơ sở dữ liệu 21  Ví dụ 3: cho R = {A, B, C, D, E, G}  F = { ABC, DEG, CA,BEC, BCD, CGBD, ACDB, CEAG }  Kiểm tra lược đồ có ở dạng 2NF  Nếu chưa ở dạng chuẩn 2NF thì đưa về dạng 2NF Cơ sở dữ liệu 22  Ví dụ 4: Cho R. U = { A, B, C, D } F= { B D, AC, C ABD }  Thực hiện: - Thuộc tính khóa là A và C. - Thuộc tính không khóa là B,D - Khóa chỉ có một thuộc tính B, D phụ thuộc đầy đủ vào khóa - Vậy R ở 2NF Cơ sở dữ liệu 23 3. Dạng chuẩn 3NF  Định nghĩa: Lược đồ quan hệ R được gọi là ở dạng chuẩn 3NF nếu: - R đã ở 2NF - Mọi thuộc tính không khóa ĐỀU không phụ thuộc bắc cầu vào bất kỳ khóa của quan hệ  Cách khác: lược đồ ở dạng 3NF nếu: - xét mọi pth X  A thì:  X là một khóa của R  hay A là thuộc tính khóa của R(có nguồn X là thuộc tính không khóa mà thuộc tính đích A là thuộc tính khóa)  Sơ đồ: R(A1,A2,A3, A4, A5)  Nhận xét: Nếu tồn tại phụ thuộc hàm Giáo viên-> Tên môn thì mỗi giáo viên chỉ dạy một môn – chưa giải quyết được bài toán tổng quát – giáo viên dạy nhiều môn Cơ sở dữ liệu 24 Cơ sở dữ liệu 25 Thuật toán kiểm tra dạng chuẩn 3  Output: khẳng định Q đạt chuẩn 3 hay không đạt chuẩn 3  Thuật toán: - Bước 1: tìm tất cả khóa của Q - Bước 2: từ F tạo tập phụ thuộc hàm tương đương F’ có vế phải một thuộc tính - Bước 3: Kiểm tra  Nếu mọi phụ thuộc hàm XA F’ với A X đều có X là khóa hoặc A là thuộc tính khóa thì Q đạt chuẩn 3  ngược lại Q không đạt chuẩn 3 ( X → A mà X không là khóa và A không là thuộc tính khóa  Nhận xét: quan hệ R là ở dạng 3NF khi và chỉ khi không tồn tại phụ thuộc hàm bắc cầu X → Y và Y → A với: - X là khóa - Y không là siêu khóa - A là thuộc tính không khóa và A XY Cơ sở dữ liệu 26  Ví dụ 1: Cho lược đồ quan hệ Q(A,B,C,D) và F = { AB C, D B, C ABD}. Hỏi Q có đạt chuẩn 3 không?  K1 = AB K2 = AD K3 = C là các khóa  mọi pth XA đều có A là thuộc tính khóa  Vậy đạt chuẩn 3NF Cơ sở dữ liệu 27  Ví dụ 2: Xét quan hệ CNHAN nhu sau: - CNHAN(MACN, LOAINGHE, HESOTHUONG) - Khóa của quan hệ là MACN - thấy có các pth trong quan hệ:  MACN → LOAINGHE  MACN → HESOTHUONG  LOAINGHE → HESOTHUONG - Có tồn tại Pth bắt cầu: MACN → LOAINGHE và LOAINGHE → HESOTHUONG - Thuộc tính không khóa HESOTHUONG phụ thuộc bắc cầu vào thuộc tính khóa MACN, do đó quan hệ CNHAN không phải là 3NF. Cơ sở dữ liệu 28  Chú ý: nếu quan hệ không thỏa mãn điều kiện 3NF, ta có thể chuẩn hóa thành 3NF như sau: - giữ lại trong quan hệ ban đầu các thuộc tính phụ thuộc trực tiếp vào khoá - nhóm vào một quan hệ khác các thuộc tính bắc cầu, lấy thuộc tính bắc cầu làm khoá - thuộc tính bắc cầu nằm ở hai quan hệ  Ví dụ 3:  trong quan hệ R1 (Số hoá đơn, Ngày bán, Số khách hàng, Tên khách hàng, Số sản phẩm)  Có các phụ thuộc hàm bắc cầu : Số hoá đơn --> Số khách hàng --> Tên khách hàng  Ta có thể tách R1 thành R5 và R6 như sau : - R5 (Số hoá đơn, Ngày bán, Số khách hàng, Số sản phẩm) - R6 (Số khách hàng,Tên khách hàng) Cơ sở dữ liệu 29  Ví dụ 4: Xét lược đồ quan hệ  NHÂNVIÊN_ĐƠNVỊ( HọtênNV, MãsốNV, Ngàysinh, Địachỉ, MãsốĐV, TênĐV, MãsốNQL)  Với các phụ thuộc hàm: - MãsốNV→HọtênNV, Ngàysinh,Địachỉ,MãsốĐV,TênĐV, MãsốNQL - MãsốĐV→ TênĐV, Mã sốNQL  Các thuộc tính TênĐV, MãsốNQL phụ thuộc bắc cầu vào khoá chính, lược đồ quan hệ không thoả mãn điều kiện 3NF.  Áp dụng phương pháp chuẩn hoá ở trên, lược đồ được tách ra như sau: - NV_DV1(HọtênNV, MãsốNV, Ngàysinh, Địachỉ, MãsốĐV) - NV_DV2(MãsốĐV, TênĐV, MãsốNQL) Cơ sở dữ liệu 30  Ví dụ 5: Xét LĐQH r(R) với R=ABCDE và tập pth F = {AB->CE, E->AB, C->D}  Với khóa của lược đồ là: AB và E  Dạng chuẩn cao nhất của quan hệ này là gì ? Cơ sở dữ liệu 31  Tìm khóa: AB, E - AB+ = ABCDE và E+ = ABCDE - Thuộc tính không khóa {C,D}  Xác định dạng chuẩn 2: Các thuộc tính không khóa phải phụ thuộc đầy đủ vào khóa. Đúng nên ở DC2  Xác định dạng chuẩn 3: Các thuộc tính không khóa phải không được phụ thuộc bắc cầu vào khóa Hoặc nếu có PTH X->A thì X phải là siêu khóa hoặc A là thuộc tính khóa - Ta có AB->C và C-> D, vậy D phụ thuộc bắc cầu vào khóa AB => lược đồ không ở dạng 3NF  Vậy dạng chuẩn cao nhất là 2NF Cơ sở dữ liệu 32  Ví dụ 6: Cho LĐQH r(R) với R=ABCD, F= {A->C, D->B, C->ABD}  Xác định dạng chuẩn cao nhất? Đưa về dạng 3NF  Giải:  Xác định khóa: A, C - A+ = ACBD - C+ = ACBD  Do tất cả các PTH đều có vế trái chỉ chứa 1 thuộc tính nên ở dạng chuẩn 2 - Các thuộc tính khóa A,C - Các thuộc tính không khóa B,D - Ta có C->D và D->B phụ thuộc bắc cầu: không ở DC3  Dạng chuẩn cao nhất là DC2 Cơ sở dữ liệu 33 4. Dạng chuẩn BCNF  Định nghĩa: Lược đồ quan hệ R ở dạng chuẩn BCNF nếu với mọi pth X A của R, A X thì X là một siêu khóa hay tất cả các thuộc tính phụ thuộc trực tiếp vào khóa.  Sơ đồ:  Ví dụ: Sinhvien(MaSV, TenSV, Ngaysinh) R(A1,A2,A3, A4, A5) Cơ sở dữ liệu 34 Thuật toán kiểm tra dạng chuẩn BCNF  Bước 1: Tìm tất cả các khóa của quan hệ Q  Bước 2: Từ tập pth F tạo tập pth tương đương với F gọi là F’ có vế phải một thuộc tính  Bước 3: - nếu mọi pth X A F’ đều có X là siêu khóa thì Q đạt chuẩn BCNF - ngược lại Q không đạt chuẩn BCNF ( X → A mà X không là siêu khóa) mọi pth đều có vế trái là siêu khóa thì đạt chuẩn BCNF ngược lại thì không siêu khóa: là một khóa nhỏ nhất Cơ sở dữ liệu 35  Ví dụ 1: Cho R = { C, S, Z}, Phụ thuộc hàm: CS Z, Z C - Có khóa tối thiểu: CS, SZ => không có thuộc tính không khóa => đã ở dạng chuẩn ba - Không ở dạng chuẩn BCNF vì có PTH: Z C nhưng Z không phải là một khóa Cơ sở dữ liệu 36  Chú ý: Nếu một lược đồ quan hệ không thoả mãn điều kiện BCNF, ta có thể chuẩn hoá nó để có được các lược đồ BCNF như: - 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ệ và - 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. Cơ sở dữ liệu 37  Ví dụ: Cho lược đồ quan hệ R = {A,B,C,D,E,F,G,H,I,J} có khóa chính là A,B Với tập các phụ thuộc hàm : - A,B → C,D,E,F,G,H,I,J - A→ E,F,G,H,I,J - F → I, J - D →B  có pth A→ E,F,G,H,I,J mà A là một bộ phận của khóa chính nên quan hệ R là vi phạm 2NF => tách R thành R1(A,E,F,G,H,I,J) và R2(A,B,C,D).  Trong R1, do có phụ thuộc hàm F→ I, J nên có I,J phụ thuộc bắc cầu vào khóa chính, R1 là quan hệ vi phạm 3NF.  Trong R2 ta có phụ thuộc hàm D → B trong đó B là một thuộc tính khóa, R2 vi phạm BCNF.  Tách R1 và R2 ta có: R11( F,I,J) , R12( A,E,F,G,H), R21(D,B), R22( A,D,C) Cơ sở dữ liệu 38 * Quá trình chuẩn hóa Cơ sở dữ liệu 39 Chuẩn hóa: đưa bảng chuẩn thấp lên chuẩn cao hơn (1NF) Ví dụ: Kết quả là gì? NV(MaNV,MaPhong,TenNV,Gioitinh,Diachi,TenPhong) R(A1,A2,A3, A4, A5) R1(A2, A4) R(A1,A2,A3, A5) Cơ sở dữ liệu 40 Chuẩn hóa: đưa bảng chuẩn thấp lên chuẩn cao hơn (2NF) Ví dụ: Kết quả là gì? NV(MaNV,MaPhong,TenNV,Gioitinh,Diachi,TenPhong) R(A1,A2,A3, A4, A5) R1(A2, A4) R(A1,A2,A3, A5) Cơ sở dữ liệu 41 Chuẩn hóa: đưa bảng chuẩn thấp lên chuẩn cao hơn (3NF) Ví dụ: Kết quả là gì? Hoc(MaSV,MaMon,Diem,MaGV) R(A1,A2,A3, A4, A5) R1(A4, A2) R(A1,A4,A3, A5) Cơ sở dữ liệu 42 III. Phép tách các lược đồ quan hệ  Định nghĩa: Phép tách các lược đồ quan hệ R= {A1, A2, .. An} là việc thay thế lược đồ quan hệ R bằng tập các lược đồ con {R1, R2, .., Rk}, trong đó Ri R, i= 1,..,k - Ri là các lược đồ con và R = R1 R2 ... Rk  Tính chất: - Bảo toàn thuộc tính - Bảo toàn phụ thuộc hàm  Mục đích: Loại bỏ các dị thường dữ liệu Cơ sở dữ liệu 43 Ví dụ  Cho lược đồ quan hệ: S(MCTY, ĐC, MH, GIA) và tập pth: F = {MCTY ĐC; MCTY, MH GIA} dị thường: địa chỉ một công ty phải lưu nhiều lần  Có thể được tách thành 2 lược đồ khác là: S1( MCTY, ĐC ) và S2 ( MCTY, MH, GIA ) như vậy sẽ không lưu địa chỉ của một công ty nhiều lần Cơ sở dữ liệu 44 Cơ sở dữ liệu 45 1. Tách-Kết nối không mất mát thông tin  Nếu R là một lược đồ quan hệ được tách thành các lược đồ con R1, R2, .., Rk và F là một tập pth.  Nói rằng phép tách R thành R1, R2, , Rk là tách - kết nối không mất mát thông tin đối với F nếu với mỗi quan hệ r trên R thoả F: r = R1(r) * R2 (r) * ... * Rk(r) tức là r được tạo nên từ phép kết nối tự nhiên của các hình chiếu của nó trên các Ri, i= 1..,k Cơ sở dữ liệu 46 Thuật toán kiểm tra phép tách-kết nối không mất thông tin  Input: - R ={A1, A2, .., An} – n thuộc tính tập pth F và - phép tách p = (R1, R2, .., Rk) – k lược đồ con  Output: Phép tách có phải là không mất mát thông tin hay không ? Cơ sở dữ liệu 47 Thuật toán:  Bước 1: Tạo bảng với n+1 cột và k+1 hàng - cột thứ j tương ứng với thuộc tính Aj - hàng thứ i tương ứng với lược đồ Ri. - Tại ô (i,j) điền kí hiệu aj nếu Aj Ri, ngược lại điền kí hiệu bij  Bước 2: Lần lượt xét các pth (X Y) F, áp dụng trên bảng - Nếu tồn tại các hàng mà tất cả các cột tương ứng với thuộc tính của X có giá trị như nhau thì làm cho các cột tương ứng với thuộc tính của Y cũng có giá trị như nhau theo nguyên tắc: nếu có một giá trị aj trong các cột tương ứng với các thuộc tính của Y thì đồng nhất các ký hiệu thành aj, nếu không đồng nhất thay bằng ký hiệu bij với bij nhỏ nhất - Tiếp tục áp dụng tất cả các phụ thuộc hàm cho bảng (kể cả lặp lại các phụ thuộc hàm đã áp dụng) cho tới khi không làm thay đổi bảng  Bước 3: Xem xét kết quả - Nếu xuất hiện một hàng gồm toàn kí hiệu a1, a2, .. , an thì phép tách- kết nối là không mất mát thông tin, - ngược lại là phép tách-kết nối mất mát thông tin. Cơ sở dữ liệu 48 Ví dụ 1:  Cho quan hệ: CC(S#, Sname, Add, Item, Price)  Ký hiệu: S  S, N  Sname, A  Add, I  Item, P Price  Tập phụ thuộc hàm: S NA, SI P  Kiểm tra việc tách {S, N, A, I, P} thành hai sơ đồ con {S, N, A} và {S, I, P} có mất mát thông tin? Cơ sở dữ liệu 49  Lập bảng: 3 hàng – 6 cột  Xét S NA: - Có hai hàng bằng nhau tại thuộc tính S - làm bằng nhau các kí hiệu đối với thuộc tính N và A  làm b22 thành a2  làm b23 thành a3  Bảng có một hàng bao gồm các ký hiệu a => phép tách không mất mát thông tin S N A I P SNA a1 a2 a3 b14 b15 SIP a1 b22 b23 a4 a5 a5 a4 b23 a3 b22 a2 a1 b15 b14 a3 a2 a1 P I A N S Cơ sở dữ liệu 50 Ví dụ 2:  Cho quan hệ R = ABCDE,  Tách thành các quan hệ: R1 = AD, R2 = AB, R3 = BE, R4 = CDE, R5 = AE  Tập phụ thuộc hàm F: - A C B C - C D DE C - CE A  Kiểm tra phép tách trên có mất mát thông tin không? Cơ sở dữ liệu 51  Lập bảng: - 6 hàng – 6 cột A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b23 b24 b25 BE b31 a2 b33 b34 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 b53 b54 a5 Cơ sở dữ liệu 52 Xét PTH: A C: -có các hàng bằng nhau trên thuộc tính A -Làm bằng nhau các ký hiệu đối với các thuộc tính C, cụ thể:  b23, b53 thành b13 a5 b54 b53 b13 b52 a1 a5 a4 a3 b42 b41 a5 b34 b33 a2 b31 b25 b24 b23 b13 a2 a1 b15 a4 b13 b12 a1 E D C B A Cơ sở dữ liệu 53 Xét PTH: B C: -có hai hàng bằng nhau trên thuộc tính B -Làm bằng nhau các ký hiệu đối với các thuộc tính C, cụ thể:  b33 thành b13 a5 b54 b13 b52 a1 a5 a4 a3 b42 b41 a5 b34 b33 b13 a2 b31 b25 b24 b13 a2 a1 b15 a4 b13 b12 a1 E D C B A Cơ sở dữ liệu 54 Xét PTH: C D: -có các hàng bằng nhau trên thuộc tính C -Làm bằng nhau các ký hiệu đối với các thuộc tính D, cụ thể:  b24, b34, b54 thành a4 a5 b54 a4 b13 b52 a1 a5 a4 a3 b42 b41 a5 b34 a4 b13 a2 b31 b25 b24 a4 b13 a2 a1 b15 a4 b13 b12 a1 E D C B A Cơ sở dữ liệu 55 Xét PTH: DE C: -có các hàng bằng nhau trên thuộc tính DE -Có thể làm bằng nhau các ký hiệu đối với các thuộc tính C, cụ thể:  b13 thành a3 a5 a4 b13 a3 b52 a1 a5 a4 a3 b42 b41 a5 a4 b13 a3 a2 b31 b25 a4 b13 a2 a1 b15 a4 b13 b12 a1 E D C B A Cơ sở dữ liệu 56 Xét PTH: CE A: -có hai hàng bằng nhau trên thuộc tính CE -Có thể làm bằng nhau các ký hiệu đối với các thuộc tính A, cụ thể:  b31, b41 thành a1 Kết quả: Có dòng chứa các ký hiệu a => phép tách không mất mát thông tin a5 a4 a3 b52 a1 a5 a4 a3 b42 b41 a1 a5 a4 a3 a2 b31 a1 b25 a4 b13 a2 a1 b15 a4 b13 b12 a1 E D C B A Cơ sở dữ liệu 57  Ví dụ 3: Cho lược đồ quan hệ R = với tập thuộc tính U = {A, B, C, D, E} và tập phụ thuộc hàm F = {A  C, B C, CD, DE  C, CE A}. - Kiểm tra tính không mất mát thông tin của phép tách R thành: R1(AC), R2(CD), R3(BE), R4(BC), R5(AE). Cơ sở dữ liệu 58  Bước 1: Lập bảng:  Bước 2:  Xét pth A  C, trên bảng có hai hàng 1 và 5 bằng nhau trên cột A, làm bằng nhau trên cột C (bằng a3).  Xét pth B  C, trên bảng có hai hàng 3 và 4 bằng nhau trên cột B, làm bằng nhau trên cột C (bằng a3).  Xét pth C  D, trên bảng cả 5 hàng bằng nhau trên cột C, làm bằng nhau trên cột D (bằng a4).  Xét pth CE  A, trên bảng có dòng 3 và dòng 5 bằng nhau trên cột CE, làm bằng nhau trên cột A (bằng a1). A B C D E R1 a1 b12 a3 b14 b15 R2 b21 b22 a3 a4 b25 R3 b31 a2 b33 b34 a5 R4 b41 a2 a3 b44 b45 R5 a1 b52 b53 b54 a5 A B C D E R1 a1 b12 a3 b14 a4 b15 R2 b21 b22 a3 a4 b25 R3 b31 a1 a2 b33 a3 b34 a4 a5 R4 b41 a2 a3 b44 a4 b45 R5 a1 b52 b53 a3 b54 a4 a5 Cơ sở dữ liệu 59 2. Tách quan hệ về 3NF vừa bảo toàn thông tin vừa bảo toàn PTH  Thuật toán:  Bước 1: tìm phủ tối thiểu G của F  Bước 2: - Với mỗi vế trái X của một phụ thuộc hàm xuất hiện trong G, tạo một lược đồ mới theo nguyên tắc  với các thuộc tính {X, A1, A2,, Ak}  trong đó X→A1, X→A2,, X→Ak là các phụ thuộc hàm trong G với X là vế trái  X là khóa của quan hệ này - Xét tất cả các phụ thuộc hàm của tập phủ tối thiểu G - Nếu có lược đồ con chứa khóa K thì kết thúc thuật toán ngược lại thì tạo lược đồ con K. Cơ sở dữ liệu 60  Ví dụ: - Xét lược đồ: R = { A,B,C,D} , với các phụ thuộc hàm: F = {A → BCD; BC → DA; D →B} - Tách lược đồ thành các lược đồ ở dạng 3NF Cơ sở dữ liệu 61  Trước tiên ta tìm G là phủ tối thiểu của F.  Theo thuật toán tìm phủ tối thiểu, đầu tiên ta làm cho các vế phải trong G chỉ chứa một thuộc tính, ta có:  G = {A → B; A → C; A→ D; BC → D; BC → A; D → B}  Sau đó ta bỏ đi các phụ thuộc hàm thừa (là các phụ thuộc hàm có thể suy diễn được từ các phụ thuộc hàm khác).  Vậy G = {A → C; BC → A; D → B}.  Lược đồ R sẽ được tách thành:  R1( A,C); R2(B,C,A); R3(D,B) với các khóa chính được gạch dưới. Cơ sở dữ liệu 62 3. Phép tách quan hệ về BCNF bảo toàn thông tin Phép tách một lược đồ quan hệ R với tập pth F, không làm mất mát thông tin sao cho mỗi lược đồ con đều ở BCNF. Phương pháp: Lặp liên tiếp. Tại mỗi bước phép tách p là bảo đảm không mất mát thông tin đối với F. Thuật toán: Bước đầu: p chỉ bao gồm R Các bước tiếp: Nếu S là một lược đồ thuộc p, S chưa ở BCNF, chọn X A là pth thoả trên S, trong đó X không chứa khoá của S, A X. Thay thế S trong p bởi S1 và S2 với : S1 = XA, S2 = S - A Quá trình tiếp tục cho tới khi tất cả các lược đồ đều ở dạng chuẩn BCNF Cơ sở dữ liệu 63  Ví Dụ 1: Cho lược đồ R(CTHRSG) với tập pth : C T, HR C, HC R, CS G, HS R Khoá của R là HS.  Ta lần lượt xét các pth vi phạm điều kiện BCNF.  Xét C T : vi phạm BCNF vì C không chứa khoá, dùng thuật toán trên để tách thành : R1(CT) và R2( CHRSG). Sau đó cần tính F+ và chiếu xuống R1 và R2, kiểm tra ta thấy R1 đã ở BCNF, R2 thì chưa. Ta tách tiếp R2.  Thực hiện tách liên tiếp Cơ sở dữ liệu 64 R(CTHRSG) Khoá =HS R1(CT) Khoá =C R2(CHRSG) Khoá =HS R21(CSG) Khoá =CS R22(CHRS) Khoá =HS R221(HRC) Khoá =HR,HC R222(HSR) Khoá =HS C T, HR C, HC R, CS G, HS R HR C, HC R, CS G, HS R HR C, HC R, HS R HR C, HC R HS R CS G C T Quá trình tách có thể được biểu diến qua sơ đồ : Cơ sở dữ liệu 65  Ví dụ 2: - Xét lược đồ quan hệ R = { A, B, C, D, E, F) - Với các phụ thuộc hàm: - A → BCDEF, BC → ADEF, B→ F, D→ E, D→ B - Lược đồ quan hệ này có hai khóa dự tuyển là A và BC - Tách lược đề về BCNF Cơ sở dữ liệu 66 Sơ đồ các bước tách lược đồ R(ABCDEF) Khoá =A, BC R1(BF) Khoá =B R2(ABCDE) Khoá =A, BC R21(DE) Khoá =D R22(ABCD) Khoá =A, BC R221(DB) Khoá =D R222(ACD) Khoá =A B→ F, D→ E, D→ B D→ E, D→ B D→ B D B D E B F Cơ sở dữ liệu 67 BTVN:  BÀI 1. Cho lược đồ quan hệ R= với tập thuộc tính U = ABCDEHG và tập phụ thuộc hàm F= {DE G, E A, H C, CG H, DG EA, D B} a. Xác định khoá của lược đồ quan hệ trên. b. Xác định dạng chuẩn cao nhất của lược đồ quan hệ trên.  BÀI 2. Xác định dạng chuẩn cao nhất của lược đồ quan hệ với các thuộc tính ABCDEF và tập phụ thuộc hàm {AB C, C B, ABD E, F A}  BÀI 3. Cho W= R = { A, B, C, D} F= { B D, A C, C ABD}. Hỏi W có là 2NF, 3NF không ? Cơ sở dữ liệu 68  BÀI 4. Xác định dạng chuẩn cao nhất của lược đồ quan hệ sau: H = (U,F); U=ABCD; F = { CD B, A C, B ACD }  BÀI 5. Cho lược đồ R = (BOISQD) và F = { S D, I B, IS Q, B O } a. Chứng tỏ rằng phép tách: R = (SD, IB, ISQ, BO) Là phép tách không mất mát thông tin. b. Chứng tỏ phép tách trên là ở dạng 3NF.