Dưới đây là bài giảng Cơ sở dữ liệu chương 8: Chuẩn hóa cơ sở dữ liệu trình bày nội dung chi tiết về thuộc tính khóa/không khóa, chuẩn hóa lược đồ, phụ thuộc hàm đầy đủ/không đầy đủ, lược đồ quan hệ.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cơ sở dữ liệu - Chương 8: Chuẩn hóa cơ sở dữ liệu
- Chương 8
Chuẩn hóa cơ sở dữ liệu
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.
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 2
1
- 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 3
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.
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 4
2
- 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.
MASV HOTEN MONHOC DIEM
CDTH0845 Nguyễn Văn A Kỹ Thuật Lập Trình 8
Cơ Sở Dữ Liệu 9
Cấu Trúc Dữ Liệu 7
CDTH0845 Trần Thu Hà Kỹ Thuật Lập Trình 5
Lược đồ trên không đạt chuẩn 1
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 5
Dạng chuẩn 1: (tt)
Lược đồ đạt chuẩn 1
MASV HOTEN MONHOC DIEM
CDTH0845 Nguyễn Văn A Kỹ Thuật Lập Trình 8
CDTH0845 Nguyễn Văn A Cơ Sở Dữ Liệu 9
CDTH0845 Nguyễn Văn A Cấu Trúc Dữ Liệu 7
CDTH0845 Trần Thu Hà Kỹ Thuật Lập Trình 5
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 6
3
- 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 7
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.
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 8
4
- 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 9
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.
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 10
5
- 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:
Hoặc X là một siêu khoá của Q
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 11
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
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 12
6
- 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 13
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.
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 14
7
- 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 15
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.
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 16
8
- 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 17
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.
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 18
9
- 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 19
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
Cơ sở dữ liệu - Khoa CNTT - CĐ KTCN ĐN 20
10
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
