Bài giảng Cơ sở dữ liệu 2 - Chương 4: Chuẩn hóa CSDL quan hệ - Nguyễn Công Thương

Nội dung text: Bài giảng Cơ sở dữ liệu 2 - Chương 4: Chuẩn hóa CSDL quan hệ - Nguyễn Công Thương

1. CƠ SỞ DỮ LIỆU 2 Giảng viên: Nguyễn Công Thương Khoa Công nghệ thông tin Đại học Sư phạm Kỹ thuật Tp. HCM
2. Chương 4: Chuẩn hóa CSDL quan hệ Giới thiệu. Phụ thuộc hàm (Functional Dependences) Chuẩn hóa CSDL. Phụ thuộc đa trị và dạng chuẩn 4. Giải thuật chuẩn hóa thành dạng chuẩn 4. Cơ sở dữ liệu 2 2
3. Quy trình thiết kế CSDL Yêu cầu của Bài toán người dùng E1 Lược đồ R1 ý niệm Lược đồ E2 quan hệ Cơ sở dữ liệu 2 3
4. Giới thiệu Mỗi lược đồ quan hệ bao gồm một số thuộc tính. Mỗi lược đồ CSDL quan hệ bao gồm một số lược đồ quan hệ. Cần một phương pháp đánh giá xem lược đồ CSDL nào là tốt hơn. Cơ sở dữ liệu 2 4
5. Giới thiệu Phương pháp đánh giá tốt: ◼ Mức độ dư thừa thông tin. ◼ Các bất thường khi cập nhật: thêm, xóa, sửa. ◼ Giảm số lượng giá trị NULL. ◼ Không cho phép việc sinh ra các dòng dữ liệu sai. ➔ Chuẩn hóa Cơ sở dữ liệu 2 5
6. Giới thiệu Chuẩn hóa giúp người thiết kế CSDL xác định được lược đồ quan hệ tốt nhất. Nó cung cấp một khung sườn để phân tích các lược đồ quan hệ dựa trên khóa và các phụ thuộc hàm giữa các khóa của chúng. Chuẩn hóa dựa trên khái niệm dạng chuẩn: 1NF, 2NF, 3NF, BCNF, 4NF, 5 NF. Chuẩn hóa đảm bảo các thuộc tính không phụ thuộc trực tiếp vào khóa chính sẽ được tách thành quan hệ mới. Cơ sở dữ liệu 2 6
7. Phụ thuộc hàm (FDs) Định nghĩa phụ thuộc hàm. Phụ thuộc hàm trực tiếp, gián tiếp, riêng phần. Luật suy diễn cho phụ thuộc hàm. Sự tương đương của các tập phụ thuộc hàm. Tập phụ thuộc hàm tối tiểu. Cơ sở dữ liệu 2 7
8. Phụ thuộc hàm (tt) Phụ thuộc hàm và khóa được dùng để định nghĩa các dạng chuẩn của quan hệ. Phụ thuộc hàm là các ràng buộc được dẫn xuất từ ngữ nghĩa và mối quan hệ tương hỗ giữa các thuộc tính. Cơ sở dữ liệu 2 8
9. Phụ thuộc hàm (tt) Cho R là một lược đồ quan hệ, X và Y là hai tập thuộc tính của R. Chúng ta nói “X xác định hàm Y” (hoặc “Y phụ thuộc hàm vào X”), ký hiệu XY và được gọi là phụ thuộc hàm nếu: u, v R: u[X] = v[X] u[Y] = v[Y] tức là với mỗi giá trị của X trong R chỉ tương ứng với một giá trị của Y. Cơ sở dữ liệu 2 9
10. Phụ thuộc hàm (tt) Trong phụ thuộc hàm XY, X được gọi là định thuộc (determinant). XY trong R quy định một ràng buộc trên tất cả thể hiện r(R). Khóa của quan hệ xác định hàm các thuộc tính không khóa của quan hệ tương ứng. Cơ sở dữ liệu 2 10
11. Phụ thuộc hàm (tt) Phụ thuộc hàm riêng phần (partial FD): X  A được gọi là phụ thuộc hàm riêng phần nếu tồn tại Y  X để Y  A. Cơ sở dữ liệu 2 11
12. Phụ thuộc hàm (tt) Phụ thuộc hàm trực tiếp (phụ thuộc hàm đầy đủ - fully FD): X  A được gọi là phụ thuộc hàm đầy đủ nếu tồn tại Y  X để Y  A. Cơ sở dữ liệu 2 12
13. Phụ thuộc hàm (tt) Phụ thuộc hàm bắc cầu (transitive FD): X  A được gọi là phụ thuộc hàm bắc cầu nếu tồn tại Y sao cho X  Y, Y  A , Y / X và A XY. Cơ sở dữ liệu 2 13
14. Luật suy diễn Hệ luật Armstrong. ◼ Phản xạ (reflexivity). ◼ Gia tăng (augmentation). ◼ Bắc cầu (transitivity). Các luật suy diễn khác: ◼ Hợp (additivity / union). ◼ Chiếu (projectivity / decomposition). ◼ Bắc cầu giả (pseudotransitivity). Cơ sở dữ liệu 2 14
15. Phụ thuộc hàm (tt) Bao đóng của tập phụ thuộc hàm (F+). Bao đóng của tập thuộc tính (X+). Hai tập phụ thuộc hàm F và G là tương đương nhau nếu F+ = G+. F được gọi là phủ của G nếu G+  F+. F và G là tương đương nếu F phủ G và G cũng phủ F. Cơ sở dữ liệu 2 15
16. Phụ thuộc hàm (tt) Phủ tối tiểu (tham khảo 14.2 [3]): ◼ Mỗi phụ thuộc hàm F chỉ có một thuộc tính đơn ở RHS. ◼ Không thể loại bỏ bất kỳ phụ thuộc hàm nào trong F mà vẫn đạt được một tập phụ thuộc hàm tương đương với F. ◼ Không thể thay thế bất kỳ phụ thuộc hàm X  A nào trong F bằng một phụ thuộc hàm Y  A với Y là tập con của X mà vẫn đạt được một tập phụ thuộc hàm tương đương với F. Cơ sở dữ liệu 2 16
17. Chuẩn hóa (normalization) Là quá trình phân rã các quan hệ bằng các tách các thuộc tính thành các quan hệ nhỏ hơn, đơn giản hơn và chuẩn hơn. Chuẩn hóa dữ liệu nhằm cải tiến một thiết kế CSDL luận lý thỏa mãn các ràng buộc toàn vẹn và tránh dữ liệu lặp không cần thiết. Mục đích của chuẩn hóa dữ liệu? Cơ sở dữ liệu 2 17
18. Chuẩn hóa (tt) Mục đích của chuẩn hóa dữ liệu: loại bỏ các bất thường (anomaly) của quan hệ để có được các quan hệ có cấu trúc tốt hơn. Quan hệ có cấu trúc tốt: ◼ Có sự dư thừa dữ liệu là tối thiểu. ◼ Cho phép người sử dụng thêm, xóa, sửa dữ liệu mà không gây ra sự mâu thuẫn dữ liệu. Quy tắc: một quan hệ không được chứa thông tin của nhiều hơn một kiểu thực thể. Cơ sở dữ liệu 2 18
19. Các dạng chuẩn Dạng chuẩn 1 (1NF): vấn đề phụ thuộc. 2NF: giải quyết vấn đề phụ thuộc riêng phần. 3NF: giải quyết vấn đề phụ thuộc bắc cầu. BCNF: các quan hệ đạt dạng chuẩn tốt. Cơ sở dữ liệu 2 19
20. Chuẩn hóa (tt) Trong thực tế, không cần phải chuẩn hóa đến dạng chuẩn cao nhất có thể. Cơ sở dữ liệu 2 20
21. Chuẩn hóa (tt) Điểm xuất phát: một lược đồ quan hệ duy nhất R = {A1, A2, , An} bao gồm tất cả thuộc tính của CSDL. D = {R1, R2, , Rn}, D được gọi là một phân rã của R. m Điều kiện bảo toàn thuộc tính của phân rã  Ri = R Bảo toàn phụ thuộc hàm. i=1 Luôn luôn tìm được một phân rã bảo toàn phụ thuộc hàm D sao cho các quan hệ trong D đạt 3NF Cơ sở dữ liệu 2 21
22. Giải thuật phân rã bảo toàn phụ thuộc hàm 1. Tìm phủ tối tiểu G của F. 2. Với mỗi LHS X của một FD trong G, tạo một lược đồ quan hệ trong D với các thuộc tính {X  {A1}  {A2}  {An}}, với Ai là RHS của các luật có X là LHS. 3. Đặt các thuộc tính còn lại vào một quan hệ mới để đảm bảo tính chất bảo toàn thuộc tính. Cơ sở dữ liệu 2 22
23. Bảo toàn join (không mất hoặc không thêm join) Đảm bảo không có bộ sai (spurious tuple) nào được sinh ra khi thực hiện phép kết trên các quan hệ đã được phân rã. Giải thuật kiểm tra tính chất bảo toàn join (15.1[3]) – homework. Tính chất: phân rã D = {R1, R2} của R thỏa mãn tính chất bảo toàn join với tập FD F khi và chỉ khi thỏa: + ◼ (R1  R2)  (R1 – R2) thuộc F , hoặc + ◼ (R1  R2)  (R2 – R1) thuộc F , Cơ sở dữ liệu 2 23
24. Giải thuật phân rã thành các quan hệ BCNF bảo toàn join 1. Gán D := {R} 2. Trong khi còn một lược đồ quan hệ Q trong D chưa đạt BCNF { chọn một lược đồ quan hệ Q chưa đạt BCNF; Tìm FD X  Y trong Q vi phạm BCNF; Thay thế Q trong D bằng 2 lược đồ quan hệ (Q – Y) và (X  Y); }; Cơ sở dữ liệu 2 24
25. Giải thuật tổng hợp bảo toàn phụ thuộc hàm và bảo toàn join 1. Tìm phủ tối tiểu G của F. 2. Với mỗi LHS X của một FD trong G, tạo một lược đồ quan hệ trong D với các thuộc tính {X  {A1}  {A2}  {An}}, với Ai là RHS của các luật có X là LHS (X là khóa của quan hệ này). 3. Nếu không tồn tại lược đồ quan hệ nào trong D chứa một khóa của R, thì tạo một hoặc nhiều lược đồ quan hệ trong D chứa cá thuộc tính tạo thành khóa của R. Cơ sở dữ liệu 2 25
26. Giải thuật tìm khóa 1. Gán K := R 2. Với mỗi thuộc tính K trong R { Tính (K – A)+ với tập phụ thuộc hàm F; Nếu (K – A)+ bao gồm tất cả thuộc tính của R thì gán K := K – {A}; }; Cơ sở dữ liệu 2 26
27. Dạng chuẩn 4 Phụ thuộc đa trị. Dạng chuẩn 4. Tham khảo 15.2 [3]. Cơ sở dữ liệu 2 27
28. Phụ thuộc đa trị (MVD) Cho lược đồ quan hệ R, X và Y là hai tập thuộc tính con không giao nhau của R và Z = R - XY. Quan hệ r(R) thỏa mãn phụ thuộc đa trị X  Y nếu với hai bộ bất kỳ t1 và t2 trong r với t1[X] = t2[X] thì cũng tồn tại hai bộ t3 và t4 trong r sao cho: t3[X] = t4[X] = t1[X] = t2[X]. t3[Y] = t1[Y] và t4[Y] = t2[Y]. t3[Z] = t2[Z] và t4[Z] = t1[Z]. Cơ sở dữ liệu 2 28
29. Phụ thuộc đa trị (tt) Cho một giá trị của X, tập giá trị của Y xác định bởi giá trị của X thì được xác định tuyệt đối bởi giá trị của X và không phụ thuộc vào giá trị của các thuộc tính Z còn lại trong R. Y là thuộc tính đa trị trong của thực thể được thể hiện bởi lược đồ quan hệ R. Cơ sở dữ liệu 2 29
30. Cơ sở dữ liệu 2 30
31. Phụ thuộc đa trị (tt) Một MVD X  Y trong R được gọi là tầm thường (trivial) nếu: ◼ Y là tập con của X. ◼ X  Y = R. Một MVD không thỏa cả hai tính chất trên được gọi là MVD không tầm thường. Một MVD tầm thường sẽ thỏa mọi thể hiện của R – Nó không đặc tả được bất kỳ ràng buộc có ý nghĩa nào trên R. Cơ sở dữ liệu 2 31
32. Phụ thuộc đa trị (tt) Nếu tồn tại một MVD không tầm thường trong một quan hệ, ta có thể phải lặp dữ liệu một cách dư thừa. ➔ Phải định nghĩa dạng chuẩn 4 (4NF) mạnh hơn BCNF. Cơ sở dữ liệu 2 32
33. Luật suy diễn cho MVD Luật bổ sung (complementation rule): { X  Y } {X  (R – (X  Y)} Luật gia tăng (augmentation rule) X  Y và W  Z WX  YZ Luật bắc cầu (transitivity rule): {X  Y, Y  Z } X  (Z – Y) Cơ sở dữ liệu 2 33
34. Luật suy diễn FD và MVD Luật nhân bản FD thành MVD (replication rule for FD to MVD): { X  Y } X  Y Luật hợp nhất (coalescence rule for FDs and MVDs): Nếu X  Y và tồn tại W thỏa tính chất (a) W  Y = , (b) W  Z và (c) Y  Z Thì X  Z. Cơ sở dữ liệu 2 34
35. Dạng chuẩn 4 Một lược đồ quan hệ R đạt dạng chuẩn 4 với tập phụ thuộc F (có thể bao gồm FD và MVD), nếu với mỗi MVD không tầm thường X  Y trong F+, X là siêu khóa của R. Cơ sở dữ liệu 2 35
36. Ví dụ Cơ sở dữ liệu 2 36
37. Phân rã bảo toàn join Tính chất: Lược đồ quan hệ R phân rã bảo toàn join thành R1 và R2 khi và chỉ khi: ◼ (R1  R2)  (R1 – R2) ◼ Đối xứng: (R1  R2)  (R2 – R1) Cơ sở dữ liệu 2 37
38. Giải thuật Giải thuật phân rã quan hệ thành 4NF: 1. D := {R}. 2. Trong khi còn một lược đồ quan hệ Q trong D chưa đạt 4NF { chọn Q trong D chưa đạt 4NF. Tìm MVD không tầm thường trong Q vi phạm 4NF. Thay thế Q bằng {Q – Y} và {X  Y}; }; Cơ sở dữ liệu 2 38
39. Dạng chuẩn 5 Homework!!! Cơ sở dữ liệu 2 39
40. Question ??? Cơ sở dữ liệu 2 40
41. Hãy tìm tất cả các phụ thuộc trong lược đồ quan hệ của hình sau Cơ sở dữ liệu 2 41
42. Bài tập Cơ sở dữ liệu 2 42
43. Bài tập 15.23. Hãy cho biết làm thế nào mà các phụ thuộc hàm ENAME  PNAME and ENAME  DNAME có thể xuất hiện trong quá trình chuẩn hóa thành 1NF với PNAME và DNAME là thuộc tính đa trị. Cơ sở dữ liệu 2 43
44. References Chapter 15 [2]. Chapter 14,15 [3]. Cơ sở dữ liệu 2 44