Bài giảng Cơ sở dữ liệu - Chương 8: Chuẩn hóa cơ sở dữ liệu
Tóm tắt Bài giảng Cơ sở dữ liệu - Chương 8: Chuẩn hóa cơ sở dữ liệu: ... ĐN 7 II. Dạng chuẩn 2: Lược đồ quan hệ Q được gọi là đạt dạng chuẩn 2 (2NF) nếu Q đạt chuẩn 1 và mọi thuộc tính không khóa đều phụ thuộc đầy đủ vào khóa. Vd 1: Q(A,B,C,D) và tập PTH F = {AB → C,D; B → D; C→ A} Khoá là {A,B} và {B,C}. Do đó D là thuộc tính không khoá, A,B → D không là ...huẩn 3 nếu mọi phụ thuộc hàm X→A ∈ F+ với A ∉ X thì một trong hai ĐK sau được thỏa: y Hoặc X là một siêu khoá của Q y Hoặc A là một thuộc tính khoá Nhận xét: ¾Nếu Q đạt chuẩn 3 thì Q đạt chuẩn 2 Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 12 Dạng chuẩn 3: (định nghĩa ≠) Một lược đồ quan hệ Q...í dụ 1 Cho lược đồ quan hệ Q(ABCD) F=[AB → C ; D → B C → ABD] ta có: K1=[AB]; K2=[AD]; K3=[C] là các khoá, vậy Q không có thuộc tính không khoá nên Q đạt chuẩn 3 (K Æ A, B nhưng A, B đều là thuộc tính khoá) Hệ quả Nếu lược đồ quan hệ Q không có thuộc tính không khoá thì Q đạt chuẩn 3....
1Chương 8 Chuẩn hóa cơ sở dữ liệu Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 2 Chuẩn hóa lược đồ CSDL Dạng chuẩn: đánh giá sự trùng lắp thông tin trong CSDL - Nếu trong CSDL có sự trùng lắp thông tin thì: => phải quản lý sự trùng lắp thông tin (bảo đảm tất cả những thông tin trùng lắp phải như nhau) => phải cập nhật tất cả những nơi mà thông tin trùng lắp xuất hiện - Nếu muốn tồn tại sự trùng lắp thông tin (vì 1 mục đích nào đó) thì cần phải có cơ chế xác định tự động những nơi trùng lắp thông tin để tự động cập nhật khi cần. 2Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 3 Một số khái niệm liên quan chuẩn hóa CSDL Thuộc tính khoá/không khoá Cho lược đồ quan hệ Q(A1, A2, An) thuộc tính B được gọi là thuộc tính khoá nếu B là một thuộc tính thành phần trong một khoá nào đó của Q, ngược lại B được gọi là thuộc tính không khoá VD: Q(A, B, C, D), F = { ABÆC, BÆD, BCÆA } Q có 2 khoá là AB, BC. Khi đó A, B, C là thuộc tính khoá, D là thuộc tính không khoá. Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 4 Một số khái niệm liên quan chuẩn hóa CSDL Phụ thuộc hàm đầy đủ/Không đầy đủ X →A là một phụ thuộc hàm đầy đủ (tức là không tồn tại X' ⊂ X sao cho X' → A ∈ F+) Ví dụ: Cho lược đồ quan hệ Q(ABC) và tập phụ thuộc hàm F={A → B; A→ C; AB → C} Ta có: A →B; A → C là các phụ thuộc hàm đầy đủ. Phụ thuộc hàm AB → C không là phụ thuộc hàm đầy đủ vì có A → C. 3Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 5 I. Dạng chuẩn 1: Lược đồ quan hệ Q được gọi là đạt dạng chuẩn 1 (1NF) nếu và chỉ nếu toàn bộ các thuộc tính của Q đều mang giá trị đơn. Lược đồ trên không đạt chuẩn 1 5Kỹ Thuật Lập Trình Trần Thu HàCDTH0845 8 9 7 Kỹ Thuật Lập Trình Cơ Sở Dữ Liệu Cấu Trúc Dữ Liệu Nguyễn Văn ACDTH0845 DIEMMONHOC HOTEN MASV Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 6 Dạng chuẩn 1: (tt) Lược đồ đạt chuẩn 1 5Kỹ Thuật Lập Trình Trần Thu HàCDTH0845 7Cấu Trúc Dữ Liệu Nguyễn Văn A CDTH0845 9Cơ Sở Dữ Liệu Nguyễn Văn A CDTH0845 8Kỹ Thuật Lập Trình Nguyễn Văn A CDTH0845 DIEMMONHOCHOTENMASV 4Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 7 II. Dạng chuẩn 2: Lược đồ quan hệ Q được gọi là đạt dạng chuẩn 2 (2NF) nếu Q đạt chuẩn 1 và mọi thuộc tính không khóa đều phụ thuộc đầy đủ vào khóa. Vd 1: Q(A,B,C,D) và tập PTH F = {AB → C,D; B → D; C→ A} Khoá là {A,B} và {B,C}. Do đó D là thuộc tính không khoá, A,B → D không là phụ thuộc hàm đầy đủ vì có B → D. Vậy Q đạt chuẩn 1. Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 8 Kiểm tra dạng chuẩn 2 Bước 1: Tìm mọi khóa của Q Bước 2: Với mỗi khóa K, tìm bao đóng của tập tất cả các tập con thực sự Si của K Bước 3: Nếu tồn tại bao đóng Si+ chứa thuộc tính không khóa thì Q không đạt dạng chuẩn 2, ngược lại Q đạt dạng chuẩn 2. 5Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 9 Dạng chuẩn 2: (tt) VD 2: Xác định dạng chuẩn của lược đồ quan hệ sau. Q(GMVNHP) F={G→N; G→H; G→P; M→V; NHP→M} Dễ thấy khoá của lược đồ quan hệ Q là G. Thuộc tính không khoá là M,V,N,H,P. Do các phụ thuộc hàm G → M; G → V; G → N; G → H; G → P là các phụ thuộc hàm đầy đủ, nên lược đồ quan hệ Q đạt dạng chuẩn 2 Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 10 Dạng chuẩn 2: (tt) VD 3: Q(ABCDEH) F = { A → E; C → D; E → DH } Dễ thấy khoá của Q là K={ABC} D là thuộc tính không khoá. và C → D , vì C là tập con thực sự của khoá nên Q không đạt dạng chuẩn 2. 6Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 11 III. Dạng chuẩn 3: Một lược đồ quan hệ Q đạt dạng chuẩn 3 nếu mọi phụ thuộc hàm X→A ∈ F+ với A ∉ X thì một trong hai ĐK sau được thỏa: y Hoặc X là một siêu khoá của Q y Hoặc A là một thuộc tính khoá Nhận xét: ¾Nếu Q đạt chuẩn 3 thì Q đạt chuẩn 2 Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 12 Dạng chuẩn 3: (định nghĩa ≠) Một lược đồ quan hệ Q đạt dạng chuẩn 3 nếu: ¾Q đạt chuẩn 2 ¾Mọi thuộc tính không khóa không phụ thuộc bắc cầu vào thuộc tính khóa Cho Q(U) XÆY là thuộc tính bắc cầu nếu tồn tại Z ⊆ U, mà Z không là khóa mà cũng không là tập con khóa của Q mà XÆZ; ZÆY đúng trên Q 7Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 13 Kiểm tra dạng chuẩn 3 Bước 1: Tìm mọi khóa của Q Bước 2: Phân rã vế phải của mọi phụ thuộc hàm có vế phải một thuộc tính Bước 3: Nếu mọi phụ thuộc hàm X Æ A ∈ F, mà A ∉ X thỏa: (1) X là siêu khóa (vế trái chứa một khóa), hoặc (2) A là thuộc tính khóa (vế phải là tập con của khóa) Thì Q đạt dạng chuẩn 3, ngược lại Q không đạt dạng chuẩn 3. Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 14 Ví dụ. Cho Q (A, B, C, D), F={AB → D, C → D} Bước 1: Q có một khóa là ABC Bước 2: Mọi phụ thuộc hàm trong F đều đã có vế phải một thuộc tính. Bước 3: Với AB → D, nhận thấy rằng D ∉ ABC có • Vế trái (AB) không phải là siêu khóa. • Hơn nữa vế phải (D) không là thuộc tính khóa Vậy Q không đạt dạng chuẩn 3. 8Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 15 Dạng chuẩn 3: (tt) Ví dụ 1 Cho lược đồ quan hệ Q(ABCD) F=[AB → C ; D → B C → ABD] ta có: K1=[AB]; K2=[AD]; K3=[C] là các khoá, vậy Q không có thuộc tính không khoá nên Q đạt chuẩn 3 (K Æ A, B nhưng A, B đều là thuộc tính khoá) Hệ quả Nếu lược đồ quan hệ Q không có thuộc tính không khoá thì Q đạt chuẩn 3. Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 16 Dạng chuẩn 3: (tt) Ví dụ 2 Xác định dạng chuẩn của lược đồ quan hệ sau. Q(NGPM) có tập PTH F = { NGP→M; M→P} Dễ thấy các khoá của Q là {NGP}, {NGM} NGP → M có vế trái là siêu khoá M → P có vế phải là thuộc tính khoá. Nên Q đạt chuẩn 3. 9Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 17 IV. Dạng chuẩn BC: (Boyce Codd) Lược đồ Q ở dạng chuẩn BC nếu mọi phụ thuộc hàm X→A ∈ F+ với A ∉ X đều có X là siêu khóa Hệ quả 1: ¾Nếu Q đạt chuẩn BC thì Q đạt chuẩn 3 (hiển nhiên do định nghĩa chuẩn 3) Hệ quả 2: ¾Mỗi lược đồ có hai thuộc tính đều đạt chuẩn BC (xét phụ thuộc hàm có thể có của Q) Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 18 Kiểm tra dạng chuẩn BC Bước 1: Tìm mọi khóa của Q Bước 2: Phân rã vế phải của mọi phụ thuộc hàm trong F có vế phải một thuộc tính Bước 3: Nếu mọi phụ thuộc hàm XÆA ∈ F, mà A ∉ X đều thỏa X là siêu khóa (vế trái chứa một khóa), thì Q đạt dạng chuẩn BC, ngược lại Q không đạt dạng chuẩn BC. 10 Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 19 VD: Cho Q (A, B, C, D, E, I), F={ACDÆEBI, CEÆAD} Bước 1: Q có hai khóa là {ACD}, {CE} Bước 2: Phân rã vế phải của các phụ thuộc hàm trong F, ta có: F={ACDÆE, ACDÆB, ACDÆI, CEÆA, CEÆD} Bước 2: Mọi phụ thuộc hàm trong F đều có vế trái là một siêu khóa Vậy Q đạt dạng chuẩn BC Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 20 Thuật toán kiểm tra dạng chuẩn: Đầu vào: lược đồ quan hệ Q, tập phụ thuộc hàm F Đầu ra: khẳng định Q đạt chuẩn gì? ¾Bước 1: Tìm tất cả khóa của Q ¾Bước 2: Kiểm tra chuẩn BC nếu đúng thì Q đạt chuẩn BC, ngược lại qua bước 3 ¾Bước 3: Kiểm tra chuẩn 3 nếu đúng thì Q đạt chuẩn 3, ngược lại qua bước 4 ¾Bước 4: Kiểm tra chuẩn 2 nếu đúng thì Q đạt chuẩn 2, ngược lại Q đạt chuẩn 1
File đính kèm:
- bai_giang_co_so_du_lieu_chuong_8_chuan_hoa_co_so_du_lieu.pdf