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....

pdf10 trang | Chia sẻ: havih72 | Lượt xem: 154 | Lượt tải: 0download
Nội dung tài liệu Bài giảng Cơ sở dữ liệu - Chương 8: Chuẩn hóa cơ sở dữ liệu, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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:

  • pdfbai_giang_co_so_du_lieu_chuong_8_chuan_hoa_co_so_du_lieu.pdf