Bài giảng Cơ sở dữ liệu: Chương 5 - ThS. Trần Quang Hải Bằng

Chia sẻ: May Trời Gio Bien | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST

Báo xấu

81
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cơ sở dữ liệu - Chương 5: Dạng chuẩn và chuẩn hóa" cung cấp cho người đọc các kiến thức: Dạng chuẩn, chuẩn hóa lược đồ cơ sở dữ liệu, bài tập dạng chuẩn và chuẩn hóa. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu: Chương 5 - ThS. Trần Quang Hải Bằng

CƠ SỞ DỮ LIỆU ( Databases ) Chương 5: Dạng chuẩn và Chuẩn hóa bangtqh@utc2.edu.vn Nội dung 1. Dạng chuẩn 2. Chuẩn hóa lược đồ CSDL 3. Bài tập bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 2
5.1. Dạng chuẩn Chuẩn hóa là gì? – Chuẩn hóa là kỹ thuật dùng để tạo ra một tập các quan hệ có các đặc điểm mong muốn dựa vào các yêu cầu về dữ liệu của 1 enterprise – Chuẩn hóa là 1 cách tiếp cận từ dưới lên (bottom-up approach) để thiết kế CSDL, bắt đầu từ các mối liên hệ giữa các thuộc tính Mục đích của chuẩn hóa – Loại bỏ các bất thường của 1 quan hệ để có được các quan hệ có cấu trúc tốt hơn, nhỏ hơn Quan hệ có cấu trúc tốt (well-structured relation): – Là quan hệ có sự dư thừa dữ liệu là tối thiểu và cho phép người dùng thêm, sửa, xóa mà không gây ra mâu thuẫn dữ liệu bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 3 5.1.1.Sự dư thừa dữ liệu Sự phụ thuộc giữa các thuộc tính gây ra sự dư thừa – Ví dụ: • Điểm các môn học Điểm trung bình xếp loại • Địa chỉ zip code TENPHG MAPHG TRPHG NG_NHANCHUC MANV TENNV HONV … Nghien cuu 5 333445555 05/22/1988 333445555 Tung Nguyen … Dieu hanh 4 987987987 01/01/1995 987987987 Hung Nguyen … Quan ly 1 888665555 06/19/1981 888665555 Vinh Pham … bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 4
5.1.1.Sự dư thừa dữ liệu (tt) Thuộc tính đa trị trong lược đồ ER nhiều bộ số liệu trong lược đồ quan hệ Ví dụ: NHANVIEN(TENNV, HONV, NS,DCHI,GT,LUONG, BANGCAP) TENNV HONV NS DCHI GT LUONG BANGCAP Tung Nguyen 12/08/1955 638 NVC Q5 Nam 40000 Trung học Nhu Le 06/20/1951 291 HVH QPN Nu 43000 Trung học Nhu Le 06/20/1951 291 HVH QPN Nu 43000 Đại học Hung Nguyen 09/15/1962 Ba Ria VT Nam 38000 Thạc sỹ bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 5 5.1.1.Sự dư thừa dữ liệu (tt) Sự dư thừa sự dị thường – Thao tác sửa đổi: cập nhật tất cả các giá trị liên quan – Thao tác xóa: người cuối cùng của đơn vị mất thông tin về đơn vị – Thao tác thêm: TENPHG MAPHG TRPHG NG_NHANCHUC MANV TENNV HONV … Nghien cuu 5 333445555 05/22/1988 333445555 Tung Nguyen … Dieu hanh 4 987987987 01/01/1995 987987987 Hung Nguyen … Quan ly 1 888665555 06/19/1981 888665555 Vinh Pham … bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 6
5.1.1.Sự dư thừa dữ liệu (tt) Các giá trị không xác định – Đặt thuộc tính Trưởng phòng vào quan hệ NHANVIEN thay vì vào quan hệ PHONGBAN Các bộ giả – Khi sử dụng các phép nối bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 7 5.1.1.Sự dư thừa dữ liệu (tt) Một số quy tắc khi thiết kế CSDL quan hệ – NT1: Rõ ràng về mặt ngữ nghĩa, tránh các sự phụ thuộc giữa các thuộc tính với nhau – NT2: Tránh sự trùng lặp về nội dung đảm bảo tránh được các dị thường khi thao tác cập nhật dữ liệu • Phải có một số thao tác khi thêm mới và cập nhật vào lược đồ quan hệ, cũng như có thể gây sai hỏng trong trường hợp xóa bỏ các bộ – NT3: Tránh sử dụng các thuộc tính có nhiều giá trị Null • Khó thực hiện các phép nối và kết hợp – NT4: Thiết kế các lược đồ quan hệ sao cho chúng có thể được nối với điều kiện bằng trên các thuộc tính là khoá chính hoặc khoá ngoài theo cách đảm bảo không sinh ra các bộ “giả” bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 8
5.1.2. Các dạng chuẩn Mỗi một dạng chuẩn là một tập các điều kiện trên lược đồ nhằm đảm bảo các tính chất của nó (liên quan tới dư thừa và bất thường trong cập nhật) Chuẩn hóa dữ liệu: quá trình phân tích lược đồ quan hệ dựa trên các FD và các khóa chính để đạt được – Cực tiểu sự dư thừa – Cực tiểu các phép cập nhật bất thường bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 9 5.1.2. Các dạng chuẩn (tt) Phân loại – Dạng chuẩn 1 (1NF – first normal form) – Dạng chuẩn 2 (2NF – second normal form) – Dạng chuẩn 3 (3NF – third normal form) – Dạng chuẩn BCNF (Boyce-Codd normal form) – Dạng chuẩn 4NF bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 10
Dạng chuẩn 1 Định nghĩa: quan hệ R được gọi là ở dạng 1NF nếu miền giá trị của một thuộc tính chỉ chứa giá trị nguyên tố đơn, ko phân chia được) và giá trị của mỗi thuộc tính cũng là một giá trị đơn lấy từ miền giá trị của nó Ví dụ PHONGBAN( MaPHG, TenPHG, DDIEM) Thuộc tính đa trị PHONGBAN(MaPHG, TenPHG) DDIEM_PHG(MaPHG, DDIEM) bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 11 Dạng chuẩn 1 (tt) Table (Key1, . . . (Key2, . . . (Key3, . . .) ) ) Table1(Key1, . . .) TableA (Key1,Key2 . . .(Key3, . . .) ) Table2 (Key1, Key2 . . .) Table3 (Key1, Key2, Key3, . . .) Lược đồ gốc: Table (Key1, aaa. . . (Key2, bbb. . . (Key3, ccc. . .) ) ) Để thỏa mãn 1NF chúng ta thực hiện – Table1(Key1, aaa . . .) – Table2(Key1, Key2, bbb . .) – Table3(Key1, Key2, Key3, ccc. . .) bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 12
Dạng chuẩn 1 (tt) Vấn đề còn tồn tại trong 1NF Xét lược đồ DDIEM_PHG(MaPHG, DDIEM) MAPHG DIADIEM – Vẫn bị lặp lại 1 TP HCM 4 HA NOI – Ẩn chứa các phụ thuộc hàm 5 VUNGTAU 5 NHATRANG bộ phận 5 TP HCM bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 13 Dạng chuẩn 2 Phụ thuộc hàm đầy đủ: Một phụ thuộc hàm X → Y là một phụ thuộc hàm đầy đủ nếu loại bỏ bất kỳ thuộc tính A nào ra khỏi X thì phụ thuộc hàm không còn đúng nữa. ∀ A, A ∈ X, (X – {A}) → Y : là sai. Phụ thuộc hàm bộ phận: Một phụ thuộc hàm X → Y là phụ thuộc bộ phận nếu có thể bỏ một thuộc tính A∈ X, ra khỏi X phụ thuộc hàm vẫn đúng, điều đó có nghĩa là với ∃A∈ X, (X – {A}) → Y bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 14
Dạng chuẩn 2 (tt) 2NF: – Thỏa mãn 1NF – Phụ thuộc hàm đầy đủ vào khóa chính Với các quan hệ có thuộc tính khóa đơn thì ko phải xét Chỉ kiểm tra các lược đồ có chứa phụ thuộc hàm bộ phận bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 15 Dạng chuẩn 2 (tt) Ví dụ Phụ thuộc vào cả 2 MaNV, MaDA NV_DA(MaNV, MaDA, Sogio, TenDA, DDiemDA) Chỉ phụ thuộc vào MaDA bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 16
Dạng chuẩn 2 (tt) Ví dụ Phụ thuộc vào cả 2 MaNV, MaDA NV_DA(MaNV, MaDA, Sogio, TenDA, DDiemDA) Chỉ phụ thuộc vào MaDA NV_DA(MaNV, MaDA, Sogio) DUAN(MaDA, TenDA) DUAN(MaDA, DDiemDA) bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 17 Dạng chuẩn 3 3NF dựa trên khái niệm phụ thuộc bắc cầu. Định nghĩa: Một lược đồ quan hệ R là ở 3NF nếu nó: – Thỏa mãn 2NF – Không có thuộc tính không khoá nào của R là phụ thuộc bắc cầu vào khoá chính. bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 18
Dạng chuẩn 3 (tt) Phụ thuộc vào MaNV NV_DV(MaNV, TenNV, NS, DCHI, MaDV, TenDV, TruongPHG) Phụ thuộc vào MaDV Tất cả các thuộc tính phải phụ thuộc vào thuộc tính khóa - Một vài thuộc tính phụ thuộc vào thuộc tính ko phải là khóa - Chuẩn hóa Tách nhóm các thuộc tính đó thành quan hệ mới bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 19 Dạng chuẩn 3 (tt) Phụ thuộc vào MaNV NV_DV(MaNV, TenNV, NS, DCHI, MaDV, TenDV, TruongPHG) Phụ thuộc vào MaDV NHANVIEN(MaNV, TenNV, NS, DCHI, MaDV) DONVI(MaDV, TenDV, TruongPHG) bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 20
Tóm tắt 3 dạng chuẩn 1-3 NF Nhận biết Cách chuẩn hóa 1 Quan hệ ko có thuộc tính đa Chuyển tất cả quan hệ lặp trị và quan hệ lặp hoặc đa trị thành 1 quan hệ mới 2 Phụ thuộc 1 phần vào thuộc Tách thuộc tính phụ thuộc 1 tính khóa phần thành lược đồ mới, đảm bảo quan hệ với lược đồ liên quan 3 Phụ thuộc ẩn, tồn tại phụ Tách các thuộc tính đó thành thuộc hàm giữa các thuộc lược đồ mới tính ko phải là khóa bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 21 Dạng chuẩn Boyce-Codd Một lược đồ quan hệ R được gọi là ở dạng chuẩn Boyce-Codd (BCNF) nếu nó – Thỏa mãn dạng chuẩn 3NF – Không có thuộc tính phụ thuộc hàm vào thuộc tính không khóa. Ví dụ R A B C D FD1 FD2 FD5 bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 22
Dạng chuẩn Boyce-Codd(tt) Ví dụ: R (A1,A2,A3,A4,A5) Với các phụ thuộc hàm: A1,A2 → A3,A4,A5 A4 → A2 bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 23 Dạng chuẩn Boyce-Codd(tt) Nếu một lược đồ quan hệ không thoả mãn điều kiện BCNF, thủ tục chuẩn hóa bao gồm: – 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ệ – 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. Ví dụ trên: R (A1,A2,A3,A4,A5) Với các phụ thuộc hàm: – A1,A2 → A3,A4,A5 – A4 → A2 lược đồ được tách ra như sau: – R1( A4, A2) – R2(A1, A4, A3, A5) bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 24
Dạng chuẩn Boyce-Codd(tt) Ví dụ Phụ thuộc vào cả 2 MaSV, MaMH SV_MH_GV(MaSV, MONHOC, GIANGVIEN) Phụ thuộc vào MONHOC bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 25 Dạng chuẩn Boyce-Codd(tt) Ví dụ Phụ thuộc vào cả 2 MaSV, MaMH SV_MH_GV(MaSV, MaMH, MaGV) Phụ thuộc vào MONHOC SV_MH(MaSV, MaMH) MH_GV(MaGV, MaMH) bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 26
5.1.3. Phân rã lược đồ quan hệ Lược đồ quan hệ chung R(A1, …, An) – Tập hợp tất cả các thuộc tính của các thực thể. Xác định tập phụ thuộc hàm F trên R. Phân rã – Sử dụng các thuật toán chuẩn hóa để tách R thành tập các lược đồ D = {R1, …, Rm}. Yêu cầu – Bảo toàn thông tin – Các lược đồ Ri phải ở dạng chuẩn 3 hoặc BCNF. bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 27 Phân rã bảo toàn thông tin Sau phân rã, CSDL không còn lưu trữ quan hệ R nữa mà chỉ lưu lại các quan hệ chiếu của nó R1, R2,..,Rn. CSDL phải có khả năng khôi phục lại quan hệ gốc R từ các quan hệ chiếu này. Nếu không khôi phục lại được quan hệ R thì việc phân rã không biểu diễn cùng 1 thông tin với CSDL gốc → Phân rã mất mát (lossy decomposition) bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 28
Phân rã bảo toàn thông tin (tt) Phân rã lược đồ R = (U,F) thành 1 tập hợp các lược đồ: R1 = (U1,F1) R2= (U2, F2)…. Rn = (Un,Fn) Phân rã không mất mát thông tin nếu với mỗi thể hiện r hợp lệ của R thì: r = r1 r2 ….. rn Với r1 = πU1(r) r2 = πU2(r),…. rn = πUn(r) bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 29 Phân rã bảo toàn thông tin (tt) Thực tế sẽ nhận được nhiều bộ (tuple) từ phép kết các r1, r2,…,rn hơn là các bộ gốc ban đầu Vậy tại sao lại gọi là mất mát (lossy) ?? Tuy nhiều bộ hơn nhưng lại thiếu thông tin và không có cách nào biết được bộ nào là đúng, bộ nào là không đúng với bộ gốc. Nhiều bộ hơn nhưng không đúng ≡ mất mát thông tin bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 30
Phân rã bảo toàn thông tin (tt) Định lý 5.1 – Phân rã D = {R1(U1), R2(U2)} của R(U) không mất thông tin đối với tập PTH F nếu và chỉ nếu: • (U1 ∩ U2) → (U1) ∈ F+, hoặc • (U1 ∩ U2) → (U2) ∈ F+. Định lý 5.3 – Nếu phân rã D = {R1, …, Rm} của R không mất thông tin đối với F và phân rã Di = {Q1, …, Qk} của Ri không mất thông tin đối với πRi(F) thì D’ = {R1, …, Ri-1, Q1, …, Qk, Ri+1, …, Rm} của R cũng không mất thông tin. bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 31 Ví dụ Xét lược đồ quan hệ PERSON(SSN, Name, Address,Hobby) SSN Name Address Hobby 1111111 John 123 Main St. Stamps 1111111 John 123 Main St. Coins 5556667 Mary 7 Lake Dr. Hiking 5556667 Mary 7 Lake Dr. Skating 9876543 Simpson Fox 5 TV Acting Nếu phân rã lược đồ trên thành 2 lược đồ: PERSON1(SSN, Name, Address) HOBBY(SSN, Hobby) Việc phân rã này có mất thông tin không? bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 32
Ví dụ Ta có: PERSON1 ∩ HOBBY = {SSN} mà SSN là khóa chính của PERSON1, do đó PERSON1 ∩ HOBBY PERSON1 Vậy: Phân rã này không mất thông tin 33 bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa Phân rã bảo toàn phụ thuộc hàm Xét lược đồ quan hệ sau: HASACCOUNT(ClientId, OfficeId, AccountNumber) Với các PTH sau: ClientId, OfficeId AcountNumber AccountNumber OfficeId Nếu phân rã lược đồ trên thành 2 lược đồ sau: ACCTOFFICE (AccountNumber, OfficeId) ACCTCLIENT (AccountNumber, ClientId) Phân rã trên có mất mát thông tin không??? bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 34
Phân rã bảo toàn PTH (tt) Phân rã trên không mất mát thông tin vì: ACCTOFFICE ∩ ACCTCLIENT ={AccountNumber} Do AccountNumber là Primary Key của CCTOFFICE nên: ACCTOFFICE ∩ ACCTCLIENT ACCTOFFICE Nhưng phân rã này không bảo toàn phụ thuộc hàm bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 35 Phân rã bảo toàn PTH (tt) Phụ thuộc hàm gốc: ClientId, OfficeId AcountNumber không tồn tại trong các phụ thuộc hàm của các lược đồ phân rã vì: – Cả hai phụ thuộc hàm phân rã đều không chứa đủ các thuộc tính của phụ thuộc hàm gốc (1) nên không thể suy diễn lại được phụ thuộc hàm này bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 36
Phân rã bảo toàn PTH (tt) Cho lược đồ R = (U,F) D = {R1(U1,F1) , R2(U2, F2),.., R (Un, Fn) } là phân rã của R. Phân rã này được gọi là bảo toàn phụ thuộc hàm nếu và chỉ nếu F và ∪ Fi là tương đương nhau. Nếu 1 phụ thuộc hàm f ∈ F nhưng không thuộc bất kỳ Fi nào không có nghĩa là phân rã không bảo toàn phụ thuộc hàm nếu f có thể được suy diễn từ ∪ Fi – Chỉ khi nào f không thể suy diễn từ ∪ Fi thì phân rã đó mới không bảo toàn PTH bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 37 Ví dụ Phân rã quan hệ HASACCOUNT AccountNumber ClientId OfficeId B123 111111 SB01 A908 123456 MN08 AccountNumber OfficeId Account Number ClientId B123 SB01 B123 111111 A908 MN08 A908 123456 bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 38
Ví dụ HASACCOUNT và phân rã của nó sau khi chèn thêm 1 hàng AccountNumber ClientId OfficeId Sau B123 khi join 2 lược đồ phân 111111 rã lại, phụ SB01 thuộc hàm ClientId, B567 OfficeId AcountNumber 111111 bị vi phạm SB01 A908 123456 MN08 AccountNumber OfficeId Account Number ClientId B123 SB01 B123 111111 B567 SB01 B567 111111 A908 MN08 A908 123456 bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 39 Phép chiếu của tập phụ thuộc hàm Xét lược đồ quan hệ R =(U,F) và tập S ⊆ U Phép chiếu của F lên tập các thuộc tính S được định nghĩa như sau: πS(F) = {X Y|X Y ∈F+ và X ∪ Y⊆ S} bangtqh@utc2.edu.vn Chương 5 - Dạng chuẩn và chuẩn hóa 40