›
›

Hệ quản trị cơ sở dữ liệu - Chương VI: Chuẩn hóa cơ sở dữ liệu

pdf 67 trang vanle 2780
Download
Bạn đang xem 20 trang mẫu của tài liệu "Hệ quản trị cơ sở dữ liệu - Chương VI: Chuẩn hóa cơ sở dữ liệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfhe_quan_tri_co_so_du_lieu_chuong_vi_chuan_hoa_co_so_du_lieu.pdf

Nội dung text: Hệ quản trị cơ sở dữ liệu - Chương VI: Chuẩn hóa cơ sở dữ liệu

  1. CHƯƠNG VI: CHUẨN HÓA CSDL
  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ệ Cơ sở dữ liệu 2
  3. I. Nguyên tắc thiết kế CSDL Cơ sở dữ liệu 3
  4. Cơ sở dữ liệu 4
  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 5
  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 6
  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 7
  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 8
  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 9
  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 10
  11. VD: Cho bảng quan hệ GD (Ten_GV, MON_GD) Ten_GV Mon_GD Không ở 1NF Lan PASCAL, NM CSDN Hà C, VISUAL BASIC, TK WEP Ten_GV Mon_GD Lan PASCAL Lan NM CSDN Hà C ở 1NF Hà VISUAL BASIC Hà TK WEP Cơ sở dữ liệu 11
  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 12
  13. 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ơ đồ: R(A1,A2,A3, A4, A5) 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 Cơ sở dữ liệu 14
  14. Cơ sở dữ liệu 15
  15. 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 16
  16. 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 17
  17. 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 18
  18. 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 19
  19. 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 20
  20. 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 21
  21. 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 22
  22. 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) Cơ sở dữ liệu 23
  23. 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
  24. 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 25
  25. 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 26
  26. 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 27
  27. 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 28
  28. 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 29
  29. 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 30
  30. 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 31
  31. 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 32
  32. 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ơ đồ: R(A1,A2,A3, A4, A5) Ví dụ: Sinhvien(MaSV, TenSV, Ngaysinh) Cơ sở dữ liệu 33
  33. 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 34
  34. 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 35
  35. 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 36
  36. 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 37
  37. * Quá trình chuẩn hóa Cơ sở dữ liệu 38
  38. Chuẩn hóa: đưa bảng chuẩn thấp lên chuẩn cao hơn (1NF) R(A1,A2,A3, A4, A5) R1(A2, A4) R(A1,A2,A3, A5) Ví dụ: NV(MaNV,MaPhong,TenNV,Gioitinh,Diachi,TenPhong) Kết quả là gì? Cơ sở dữ liệu 39
  39. Chuẩn hóa: đưa bảng chuẩn thấp lên chuẩn cao hơn (2NF) R(A1,A2,A3, A4, A5) R1(A2, A4) R(A1,A2,A3, A5) Ví dụ: NV(MaNV,MaPhong,TenNV,Gioitinh,Diachi,TenPhong) Kết quả là gì? Cơ sở dữ liệu 40
  40. Chuẩn hóa: đưa bảng chuẩn thấp lên chuẩn cao hơn (3NF) R(A1,A2,A3, A4, A5) R1(A4, A2) R(A1,A4,A3, A5) Ví dụ: Hoc(MaSV,MaMon,Diem,MaGV) Kết quả là gì? Cơ sở dữ liệu 41
  41. 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 42
  42. 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 43
  43. Cơ sở dữ liệu 44
  44. 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 45
  45. 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 46
  46. 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 47
  47. 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 48
  48. S N A I P Lập bảng: 3 hàng – 6 cột SNA a1 a2 a3 b14 b15 SIP a b b a a 1 22 23 4 5 Xét S NA: - Có hai hàng bằng nhau tại thuộc tính S S N A I P - làm bằng nhau các kí hiệu đối với thuộc tính N và A a1 a2 a3 b14 b15  làm b thành a 22 2 a1 b22 b23 a4 a5  làm b23 thành a3 a2 a Bảng có một hàng bao gồm 3 các ký hiệu a => phép tách không mất mát thông tin Cơ sở dữ liệu 49
  49. 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 50
  50. 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 51
  51. 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 A B C D E a1 b12 b13 a4 b15 a1 a2 b23 b13 b24 b25 b31 a2 b33 b34 a5 b41 b42 a3 a4 a5 a1 b52 b53 b13 b54 a5 Cơ sở dữ liệu 52
  52. 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 A B C D E a1 b12 b13 a4 b15 a1 a2 b13 b24 b25 b31 a2 b33 b13 b34 a5 b41 b42 a3 a4 a5 a1 b52 b13 b54 a5 Cơ sở dữ liệu 53
  53. 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 A B C D E a1 b12 b13 a4 b15 a1 a2 b13 b24 a4 b25 b31 a2 b13 b34 a4 a5 b41 b42 a3 a4 a5 a1 b52 b13 b54 a4 a5 Cơ sở dữ liệu 54
  54. 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 A B C D E a1 b12 b13 a4 b15 a1 a2 b13 a4 b25 b31 a2 b13 a3 a4 a5 b41 b42 a3 a4 a5 a1 b52 b13 a3 a4 a5 Cơ sở dữ liệu 55
  55. 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 A B C D E a1 b12 b13 a4 b15 a1 a2 b13 a4 b25 b31 a1 a2 a3 a4 a5 b41 a1 b42 a3 a4 a5 a1 b52 a3 a4 a5 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 Cơ sở dữ liệu 56
  56. 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 57
  57. A B C D E Bước 1: Lập bảng: Bước 2: R1 a1 b12 a3 b14 b15 Xét pth A C, trên bảng có hai R2 b21 b22 a3 a4 b25 hàng 1 và 5 bằng nhau trên cột R3 b31 a2 b33 b34 a5 A, làm bằng nhau trên cột C R4 b41 a2 a3 b44 b45 (bằng a3). Xét pth B C, trên bảng có hai R5 a1 b52 b53 b54 a5 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). A B C D E Xét pth C D, trên bảng cả 5 R1 a1 b12 a3 b14 a4 b15 hàng bằng nhau trên cột C, làm bằng nhau trên cột D (bằng a4). R2 b21 b22 a3 a4 b25 Xét pth CE A, trên bảng có R3 b31 a1 a2 b33 a3 b34 a4 a5 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 R4 b41 a2 a3 b44 a4 b45 (bằng a1). R5 a1 b52 b53 a3 b54 a4 a5 Cơ sở dữ liệu 58
  58. 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 59
  59. 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 60
  60. 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 61
  61. 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 62
  62. 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 63
  63. Quá trình tách có thể được biểu diến qua sơ đồ : R(CTHRSG) C T, HR C, HC R, CS G, Khoá =HS HS R R1(CT) R2(CHRSG) HR C, HC R, Khoá =C Khoá =HS CS G, HS R C T HR C, HC R21(CSG) R22(CHRS) R, HS R Khoá =CS Khoá =HS CS G R221(HRC) R222(HSR) Khoá =HR,HC Khoá =HS HR C, HC R HS R Cơ sở dữ liệu 64
  64. 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 65
  65. Sơ đồ các bước tách lược đồ R(ABCDEF) Khoá =A, BC B→ F, D→ E, D→ B R1(BF) R2(ABCDE) D→ E, D→ B Khoá =B Khoá =A, BC B F R21(DE) R22(ABCD) D→ B Khoá =D Khoá =A, BC D E R221(DB) R222(ACD) Khoá =D Khoá =A D B Cơ sở dữ liệu 66
  66. 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 67
  67. 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. Cơ sở dữ liệu 68