1
THIẾT KẾ
CƠ SỞ DỮ LIỆU QUAN HỆ
2
Tập PTH tối thiểu
• Tập PTH F là tối thiểu nếu thỏa các điều kiện sau
– Mọi PTH của F chỉ có một thuộc tính ở vế phải.
– Không thể thay X  A thuộc F bằng Y  A với Y  X
mà tập mới tương đương với F.
– Nếu bỏ đi một PTH bất kỳ trong F thì tập PTH còn lại
không tương đương với F.
• Phủ tối thiểu (Minimal Covers) của tập PTH E là
tập PTH tối thiểu F tương đương với E.
• Nhận xét
– Mọi tập PTH có ít nhất một phủ tối thiểu.
3
Thuật toán tìm phủ tối thiểu (Bernstein, 1976)
Thuật toán 3.3:
Nhập: tập PTH E.
Xuất: phủ tối thiểu F của E.
Phương pháp :
– B1: F := .
– B2: (Tách các PTH để có vế phải là 1 thuộc tính)
Với mọi X  Y  E, Y = {A
1
, …, A
k
}, A
i
 U
F := F  {X  {A

– B1: F = .
– B2: F = {A  B, A  C, B  C, AB  C}.
– B3: Xét AB  C
(B)
F
+
= C
F = {A  B, A  C, B  C}.
– B4: A  C thừa.
F = {A  B, B  C}.
5
Chuẩn hóa lược đồ CSDL
Các dạng chuẩn
– Dạng 1 (1 Normal Form - 1NF).
– Dạng 2 (2 Normal Form - 2NF).
– Dạng 3 (3 Normal Form - 3NF).
– Dạng Boyce - Codd
(Boyce - Codd Normal Form - BCNF).
6
Dạng chuẩn 1
Định nghĩa 3.5: Quan hệ r(U) được gọi thuộc dạng chuẩn 1 nếu
và chỉ nếu mọi thuộc tính của r là thuộc tính đơn.
Go Vap9876543214Hanh chinh
Go Vap,
Thu Duc
3334455555
Kinh doanh
CacTrusoTrPhgMaPTenP
PHONG
PHONG

DiadiemTenDATenNVSoGioMaDAMaNV
FD3
NVIEN_DUAN
NV_DA1
MaNV MaDA SoGio
FD1
NV_DA2
MaNV TenNV
FD2
NV_DA3
MaDA TenDA Diadiem
FD3
3 lược đồ NV_DA1, NV_DA2, NV_DA3 thuộc dạng chuẩn 2
9
Dạng chuẩn 2 theo khóa chính (3)
Nhận xét
– Mọi lược đồ quan hệ thuộc dạng chuẩn 2 cũng thuộc
dạng chuẩn 1.
– Còn xuất hiện sự trùng lặp dữ liệu. Do đó gây ra các dị
thường về cập nhật dữ liệu.
NHANVIEN_PHONGBAN
TenNV MaNV NgSinh DChi MaPB TenPB TrPhong
FD1
FD2
Thuộc dạng
chuẩn 2
10
Dạng chuẩn 3 theo khóa chính (1)
Định nghĩa 3.7: Quan hệ r(U) được gọi là thuộc dạng chuẩn 3 nếu
– r thuộc dạng chuẩn 2.

đầy đủ vào các khóa của R.
Cho R(ABCDEF) có 2 khóa là A và BC.
FD3
FD2
FD1
FEDCBA
FD4
R
FD5
Lược đồ R không thuộc dạng chuẩn 2
13
Dạng chuẩn 3 tổng quát
Định nghĩa 3.9: Lược đồ quan hệ R được gọi là thuộc dạng
chuẩn 3 nếu PTH X  A đúng trên R thì
– X là siêu khóa của R, hoặc
– A là thuộc tính khóa của R.
R1(ABCDE) có 2 khóa là A và BC.
FD2
FD1
EDCBA
FD4
R1
Lược đồ bên
thuộc dạng
chuẩn 2,
nhưng không
thuộc dạng
chuẩn 3
FD5
14

• Đặt 
Ri
(F) = {X  Y  F
+
: X  Y  R
i
}.
• D được gọi là phân rã bảo toàn phụ thuộc hàm đối với F nếu
(
R1
(F)  …  
Rm
(F))
+
= F
+
.
Ví dụ
FD2
FD5
FD1
DCBA
R11
R111
A C D
FD1
R112
B D
FD5
16

– B3: Giả sử xong B2 ta có các lược đồ R
1
, …, R
m
.
Nếu U
1
 …  U
m
 U thì xây dựng thêm lược đồ
R
m+1
(U
m+1
), U
m+1
= U - (U
1
 …  U
m
).
Khóa của R
m+1
là U
m+1
.
– B4: Xuất các lược đồ R
i
.
17

– F = {B  A, D  C, D  EB, DF  G}
Tách về dạng chuẩn 3, bảo toàn PTH
– B1:
• Phủ tối thiểu G = {B  A, D  C, D  B, D  E, DF  G}.
– B2:
– B3:
• Vì U
1
 U
2
 U
3
= {ABCDEFG} nên đặt R
4
(HI).
– B4:
• D = {R
1
, R
2
, R
3
, R
4
}.
R(ABCDEFG)
R
1
(BA)
R

+
= ADEBC  K = ADE.
• Lặp 4: (AE)
F
+
= AEBC  K = ADE.
• Lặp 5: (AD)
F
+
= ADBCE  K = AD.
AD là khoá.
21
- Khóa là AD, R không đạt 2NF vì A  B
- Tìm một phép phân rã tách lược đồ trên thành các lược đồ
con đạt dạng chuẩn 3.
Cho lược đồ quan hệ R(ABCDE) và tập phụ thuộc hàm:
F=F
tt
= {A -> B; CD -> E; B -> C}
R(ABCDE)
R1(BC) R2(ADEB)
{A -> B}
R21(AB) R22(ADE)
22
- Khóa là AD, R không đạt 2NF vì A  B
- Tìm một phép phân rã tách lược đồ trên thành các lược đồ
con đạt dạng chuẩn 3.
Cho lược đồ quan hệ R(ABCDE) và tập phụ thuộc hàm:
F=F
tt

+
= R  K = BCEGHIJK.
• Lặp 5: (BCGHIJK )
F
+
= R  K = BCGHIJK
• Lặp 6: (BCGHIJK )
F
+
 R  K = BCGHIJK
• Lặp 7: (BCGIJK )
F
+
= R  K = BCGIJK
• Lặp 8: (BCGJK )
F
+
= R  K = BCGJK
• Lặp 9: (BCGK )
F
+
 R  K = BCGJK
• Lặp 10: (BCGJ )
F
+
= R  K = BCGJ
25
2. Tìm tất cả các khóa của lược đồ
Có 2 khóa:
K1=(BCGJ)