Bài giảng Cơ sở dữ liệu - Chương 6: Chuẩn hóa - Nguyễn Việt Cường

1Chương 6 Chuẩn hóa (Normalization) 1 2Khái niệm “Chuẩn hóa” • Chuẩn hóa ñược xem như là một công cụ dùng trong các pp thiết kế CSDL – Chuẩn hóa ñược thực hiện sau khi thiết kế CSDL dùng mô hình ER • Là quá trình ñánh giá và chỉnh sửa cấu trúc bảng ñể giảm thiểu dư thừa dữ liệu – Dư thừa dữ liệu có khả năng làm cho dữ liệu không nhất quán (mâu thuẫn dữ liệu) • Các dạng chuẩn 1NF, 2NF, 3NF, BCNF 3Bảng chưa chuẩn hóa • Bảng không ở dạng chuẩn 1 ( hay chưa chuẩn hóa) nếu nó chứa một hoặc nhiều nhóm giá trị lặp • Nhóm giá trị lặp(Repeating group) 3 Annelise Jones, James J. Frommer, Anne K. Ramoras 114, 118, 104 Amber Wave18 June E. Arbough, John G. News, Alice K. Johnson 103, 101, 105 Evergreen15 EMP_NAMEEMP_NUMPROJ_NAMEPROJ_NUM Nhóm giá trị lặp 4Dạng chuẩn 1 (1NF) • Lược ñồ quan hệ R ở dạng chuẩn 1 _ First Normal Form, nếu – Có khóa chính, và – Không có nhóm lặp lại 4 Anne K. Ramoras104Amber Wave18 James J. Frommer118Amber Wave18 Annelise Jones114Amber Wave18 Alice K. Johnson105Evergreen15 John G. News101Evergreen15 June E. Arbough103Evergreen15 EMP_NAMEEMP_NUMPROJ_NAMEPROJ_NUM 5Dạng chuẩn 2 (2NF) • Lược ñồ quan hệ R(U,F) ở dạng chuẩn 2 khi : – Bảng ở dạng chuẩn 1, và – Mọi thuộc tính không khóa ñều phụ thuộc ñầy ñủ vào mọi khóa của R • Nhận xét : Nếu R chỉ có các khóa gồm một thuộc tính thì ñương nhiên R ở dạng chuẩn 2 • Phụ thuộc hàm ñầy ñủ _ Full functional dependency – X
A là phụ thuộc hàm ñầy ñủ⇔ ∃ Y ⊂ X , Y
A – Ngược lại : X
A là phụ thuộc hàm không ñầy ñủ 6Dạng chuẩn 2 (2NF) • Lược ñồ sau không ñạt 2NF Q(PROJ_NUM, EMP_NUM, PROJ_NAME, EMP_NAME) với tập F = { f1: PROJ_NUM, EMP_NUM
PROJ_NAME, EMP_NAME f2: EMP_NUM
EMP_NAME f3: PROJ_NUM
PROJ_NAME } Gọi : f1 là phụ thuộc hàm không ñầy ñủ f2, f3 là phụ thuộc riêng phần_ partial FD 7Dạng chuẩn 3 (3NF ) • ðịnh nghĩa 1: Lược ñồ quan hệ R ở 3NF ñối với tập phụ thuộc hàm F nếu: – R ở dạng 2NF, và – Mọi thuộc tính không khóa ñều không phụ thuộc bắc cầu vào khóa chính của R • ðịnh nghĩa 2: Lược ñồ quan hệ R ở 3NF ñối với tập phụ thuộc hàm F nếu: – R ở dạng chuẩn 1, và – ∀ X->A với A ∉X thì X là 1 siêu khoá của R hoặc A là 1 thuộc tính khoá 7 8Dạng chuẩn 3 (3NF ) • Lược ñồ sau không ñạt 3NF Q( EMP_NUM, EMP_NAME, JOB_CLASS, CHG_HOUR ) với tập F = { f1 : EMP_NUM
EMP_NAME,JOB_CLASS,CHG_HOUR f2 : JOB_CLASS
CHG_HOUR } => f2 là phụ thuộc hàm bắc cầu (transitive dependency) 9Dạng chuẩn BCNF • BCNF ñược xem là trường hợp ñặc biệt của 3NF • Lược ñồ quan hệ R(U,F), ñược gọi là ñạt BCNF nếu mọi X→A ∈ F , A∉X thì X là một siêu khóa của R • Lược ñồ quan hệ sau không ñạt BCNF R( Proj_name, Emp_name, Assign_hours ) với 2 phụ thuộc hàm f1: Proj_name, Emp_name
Assign_hours f2: Assign_hours
Emp_num 10 Dạng chuẩn _ nhận xét • Các qui tắc xác ñịnh các dạng chuẩn ñều dựa vào khóa • Dạng chuẩn 2NF tốt hơn 1NF; 3NF tốt hơn 2NF, – Mỗi dạng chuẩn ñưa ra các ñiều kiện bổ sung cho dạng chuẩn thấp hơn nó 1NF 2NF 3NF BCNF 11 Quá trình chuẩn hóa lược ñồ CSDL • Thực hiện chuẩn hóa từng lược ñồ quan hệ – Là quá trình biến ñổi dạng chuẩn của một lược ñồ quan hệ từ thấp nhất tới dạng chuẩn cao nhất – Phân tách một LðQH dần dần thành nhiều LðQH mới dựa trên việc nhận diện các phụ thuộc hàm • Dạng chuẩn của một lược ñồ CSDL bằng dạng chuẩn của lược ñồ quan hệ cao nhất 12 f1: PROJ_NUM, EMP_NUM
PROJ_NAME, EMP_NAME, JOB_CLASS, CHG_HOUR, HOURS f2: PROJ_NUM
PROJ_NAME f3: EMP_NUM
EMP_NAME, JOB_CLASS, CHG_HOUR f4: JOB_CLASS
CHG_HOUR Xét R(U,F) ñạt dạng chuẩn 1 R ( PROJ_NUM, EMP_NUM, PROJ_NAME, EMP_NAME, JOB_CLASS, CHG_HOUR, HOURS ) Ví dụ về chuẩn hóa 13 Ví dụ về chuẩn hóa Chuyển ñổi sang dạng chuẩn 2 Loại bỏ các phụ thuộc hàm riêng phần và tạo thêm các Lược ñồ quan hệ mới tương ứng 14 Ví dụ về chuẩn hóa Chuyển ñổi sang dạng chuẩn 3 • Loại bỏ các phụ thuộc bắc cầu trong lñqh và tạo ra các lñqh mới tương ứng 15 Sau quá trình chuẩn hóa Q, ta thu ñược một lược ñồ CSDL ñạt 3NF Lược ñồ CSDL kết quả 16ðạt BCNF Ví dụ về chuẩn hóa Chuyển ñổi sang dạng chuẩn BCNF • Giả ñịnh, trong bảng ASSIGNMENT tồn tại 2 phụ thuộc hàm f1: Proj_name, Emp_name
Assign_hours f2: Assign_hours
Emp_num 16 PROJ_NUM ASSIGN_HOURS EMP_NUM PROJ_NUM ASSIGN_HOURS EMP_NUMASSIGN_HOURS Hoặc 17 Chuẩn hóa và Thiết kế CSDL • Chuẩn hóa ñược xem như một phương pháp thiết kế CSDL ñộc lập – Có 2 cách tiếp cận : tổng hợp và phân rã • Với phần lớn các mục tiêu thiết kế DB : 3NF là dạng chuẩn cao cần ñạt tới trong quá trình chuẩn hóa – Dạng chuẩn cao nhất không phải luôn luôn là mục tiêu cần ñạt tới – Giảm dạng chuẩn 18 Chuẩn hóa LDQH bằng Phân rã • Quá trình chuẩn hóa LDQH là quá trình phân rã LDQH ban ñầu thành một số LDQH con – Các LDQH con ñạt dạng chuẩn cao hơn => giảm dư thừa dữ liệu • Về mặt lý thuyết, quá trình phân rã phải ñảm bảo 2 yêu cầu – Bảo toàn thông tin – Bảo toàn phụ thuộc hàm • Thuật toán phân rã thành BC (hay 3NF) bảo toàn thông tin và bảo toàn phụ thuộc hàm 19 Phân rã bảo toàn thông tin • Xét lược ñồ quan hệ Q và tập F, giả sử Q ñược phân rã thành D= { Q1, Q2 } Nói rằng D là phép phân rã bảo toàn thông tin nếu với mọi r là quan hệ bất kỳ của Q ta có r = r.Q1 |><| r.Q2 • Tính chất Xét lược ñồ quan hệ Q và tập F, D= { Q1, Q2 } là phân rã bảo toàn thông tin nếu và chỉ nếu (Q1+ ∩ Q2+ ) → Q2+ ∈ F+ hoặc (Q1+ ∩ Q2+ ) → Q1+ ∈ F+ • Phép tách Q thành n lược ñồ quan hệ Q1, Q2,Qn bảo toàn thông tin , nếu ở các bước trung gian tách Q thành Qi và Qik bảo toàn thông tin 20 Phân rã bảo toàn thông tin 200Gaïch oáng40 Nguyeãn OanhHung 250Gaïch theû12 Nguyeãn KieämHung 200Gaïch oáng12 Nguyeãn KieämHung DONGIASANPHAMDIACHITENNCC r 250Gaïch theûHung40 Nguyeãn OanhHung 200Gaïch oángHung12 Nguyeãn KieämHung DONGIASANPHAMTENNCCDIACHITENNCC r1 = r.Q1 +r2 = r.Q2 + 250Gaïch theû40 Nguyeãn OanhHung 200Gaïch oáng40 Nguyeãn OanhHung 250Gaïch theû12 Nguyeãn KieämHung 200Gaïch oáng12 Nguyeãn KieämHung DONGIASANPHAMDIACHITENNCC r’ = r1|><|r2 Phân rã không bảo toàn thông tin 21 Phân rã bảo toàn phụ thuộc hàm • Cho phân rã D = (Q1, Q2,, Qk) của lược ñồ Q và tập pth F, với hình chiếu của F trên Qi ký hiệu ΠQi(F) sao cho ΠQi(F)={ X→Y | X → Y ∈ F+ và XY ⊆ Qi} Ta nói phân rã D bảo toàn tập phụ thuộc hàm F nếu F ≡ ∪ ΠQi(F) ⇔ F+ = (∪ ΠQi(F))+ với i=1..k 22 Ý nghĩa của phân rã bảo toàn pth • Ví dụ Phân rã không bảo toàn phụ thuộc hàm 23 Thuật toán phân rã thành 3NF bảo toàn thông tin , bảo toàn phụ thuộc hàm • B1 : Tìm phủ tối thiểu Ftt của F • B2 : – Nếu có những thuộc tính của Q không nằm trong một phụ thuộc nào của Ftt - dù ở vế phải hay vế trái của F thì chúng tạo thành một lược ñồ. – Nếu có một phụ thuộc hàm nào của Ftt mà liên quan ñến tất cả các thuộc tính của Q thì kết quả phân rã chính là Q ( Q không thể phân rã) – Cứ mỗi phụ thuộc hàm X → A ∈ Ftt thì XA là một lược ñồ cần tìm – Nếu có một lược ñồ con chứa khóa K của Q thì kết thúc thuật toán .Ngược lại tạo một lược ñồ con K 24 Thuật toán phân rã thành 3NF bảo toàn thông tin , bảo toàn phụ thuộc hàm Ví dụ: cho lược ñồ Q(CTHRSG),F={C→T,HR→C,TH→R,CS→G,HS→R} Hãy phân rã Q thành các lược ñồ con ñạt dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm? Giải: • F = Ftt = {C→T,HR→C,TH→R,CS→G,HS→R} là phủ tối thiểu. • Áp dụng thuật toán trên Q ñược phân rã thành các lược ñồ con Q1(CT) Q2(HRC) Q3(THR) Q4(CSG) Q5(HSR) • Khóa của Q là HS • ⇒Q1,Q2,Q3,Q4,Q5 chính la ket qua phân rã 25 Tóm tắt Tồn tại nhiều phụ thuộc hàm trong một LðQH Dư thừa dữ liệu Các dạng chuẩn 1NF, 2NF, 3NF, BCNF Chuẩn hóa LðQH Chuẩn hóa bằng Phân rã