Giáo trình Cơ sở dữ liệu

c G). Ta kết luận phép tách bảo toàn phụ thuộc hàm F. 
Cơ sở dữ liệu 
Trang: 54 
CHƢƠNG VII: 
CHUẨN HOÁ LƢỢC ĐỒ QUAN HỆ 
I. CÁC DẠNG PHỤ THUỘC HÀM 
1. Thuộc tính nguyên tố, không nguyên tố 
(prime/nonprime attribute) 
Cho sơ đồ quan hệ R(U), một thuộc tính A  R đƣợc gọi là nguyên tố nếu A là 
thành phần của một khoá trong R. Ngƣợc lại, A không là nguyên tố. 
Ví dụ: 
Trong sơ đồ quan hệ ABCD (khoá là AB, BC) với các phụ thuộc hàm: 
AB  C 
B  D 
BC  A 
Ta thấy: A, B, C là thuộc tính nguyên tố; D là không nguyên tố. 
2. Phụ thuộc từng phần 
(partial dependency) 
Phụ thuộc hàm X  A là phụ thuộc từng phần nếu X là tập con thực sự của một 
khoá của R. 
3. Phụ thuộc đầy đủ/phụ thuộc sơ cấp 
(complete dependency) 
Phụ thuộc hàm X  A là phụ thuộc đầy đủ (hay còn gọi là phụ thuộc sơ cấp/ 
nguyên tố) nếu không tồn tại tập con thực sự Y  X nào để cho Y  A xảy ra. Nhƣ vậy 
phụ thuộc đầy đủ vào khoá ngƣợc lại với phụ thuộc từng phần. 
4. Phụ thuộc truyền 
X  A là phụ thuộc hàm truyền nếu X không là tập con thực sự của một khoá 
nào, A là thuộc tính không khoá, A  X. 
5. Phụ thuộc trực tiếp 
X  A là phụ thuộc trực tiếp nếu không tồn tại tập thuộc tính Y, với Y  X, Y  
A thỏa: 
X  Y & Y  A 
6. Phụ thuộc hàm tầm thƣờng 
Phụ thuộc hàm X  Y gọi là phụ thuộc hàm tầm thƣờng nếu Y  X (hiển nhiên là 
nếu Y  X thì ta có X  Y). 
II. CÁC DẠNG CHUẨN 
1. Dạng chuẩn thứ nhất (1NF) 
a. Định nghĩa: 
Một sơ đồ quan hệ R đƣợc xem là ở dạng chuẩn thứ nhất nếu mọi thuộc tính 
của R đều khác trống, phụ thuộc hàm vào khoá và không đƣợc mang giá trị kép (tức 
không thể chia đƣợc thành các thành phần nhỏ hơn và có ý nghĩa). 
b. Ví dụ: 
Cho sơ đồ quan hệ: 
CUNG_UNG(MaNSX, MaH, SL, VonNSX, TP, Nuoc) 
với các phụ thuộc hàm: 
MaNSX, MaH  SL (a) 
MaNSX  VonNSX (b) 
MaNSX  TP (c) 
MaNSX  Nuoc (d) 
TP  Nuoc (e) 
Sơ đồ này thoả dạng chuẩn thứ nhất (1NF). 
Cơ sở dữ liệu 
Trang: 55 
2. Dạng chuẩn thứ hai (2NF) 
a. Định nghĩa: 
Một sơ đồ quan hệ R đƣợc xem là thoả dạng chuẩn 2 nếu nó ở dạng chuẩn 1 và 
không có phụ thuộc hàm từng phần. 
b. Ví dụ 1: 
Sơ đồ quan hệ SAIP (khoá SI) với các phụ thuộc hàm: SI  P và S  A đã vi 
phạm dạng chuẩn thứ 2. Do khoá là SI nên A là không nguyên tố. 
c. Ví dụ 2: 
Trong ví dụ trên, sơ đồ quan hệ CUNG_UNG không thỏa dạng chuẩn thứ 2 vì 
các phụ thuộc hàm (b), (c) và (d) là các phụ thuộc hàm từng phần. 
Ta có thể tách CUNG_UNG thành 2 sơ đồ quan hệ: 
CUNG_UNG2(MaNSX, MaH, SL) 
NSX(MaNSX, VonNSX, TP, Nuoc) 
thì cả hai sơ đồ mới này đều thỏa 2NF. 
3. Dạng chuẩn thứ ba (3NF) 
a. Định nghĩa: 
Một sơ đồ quan hệ R đƣợc xem là thỏa dạng chuẩn 3 nếu nó ở dạng chuẩn 2 và 
không có phụ thuộc hàm truyền. 
b. Ví dụ 1: 
Sơ đồ quan hệ CSZ (khoá là CS và SZ) với các phụ thuộc hàm: CS  Z và Z 
 C thỏa dạng chuẩn 3 vì mọi thuộc tính đều là nguyên tố. 
c. Ví dụ 2: 
Sơ đồ quan hệ NSX ở ví dụ trên không thỏa dạng chuẩn 3 vì có chứa phụ thuộc 
hàm truyền: 
TP  Nuoc 
Ta có thể tách NSX thành 2 sơ đồ quan hệ: 
NSX(MaNSX, VonNSX, TP) 
TP(TP, Nuoc) 
thì 2 sơ đồ này thỏa 3NF. 
4. Dạng chuẩn Boyce – Codd (BCNF) 
a. Định nghĩa: 
Một sơ đồ quan hệ R đƣợc gọi là thỏa dạng chuẩn Boyce – Codd nếu với mọi 
phụ thuộc hàm không tầm thƣờng đều có vế trái là siêu khoá. 
b. Ví dụ 1: 
Sơ đồ quan hệ CSZ (khoá là CS và SZ) với các phụ thuộc hàm: CS  Z và Z 
 C thỏa dạng chuẩn 3 nhƣng không thỏa Boyce – Codd vì phụ thuộc hàm Z  C, Z 
không là siêu khoá. 
c. Ví dụ 2: 
Xét lƣợc đồ: 
LOPHOC(Lop, MonHoc, GiaoVien) 
với 2 phụ thuộc hàm: 
GiaoVien  Monhoc 
Lop, MonHoc  GiaoVien 
Lƣợc đồ có 2 khoá: 
K1 = Lop, MonHoc và 
K2 = Lop, GiaoVien 
nên tất cả các thuộc tính đều là thuộc tính khoá  lƣợc đồ ở dạng chuẩn 3. Tuy nhiên 
lƣợc đồ không ở dạng chuẩn Boyce – Codd vì phụ thuộc hàm 
GiaoVien  MonHoc 
không thỏa yêu cầu vế trái phải là siêu khoá. 
Cơ sở dữ liệu 
Trang: 56 
5. Dạng chuẩn thứ tƣ (4NF) 
a. Định nghĩa: 
Lƣợc đồ quan hệ R thỏa dạng chuẩn thứ tƣ nếu với mọi phụ thuộc đa trị X 
 Y bất kỳ, trong đó Y khác rỗng hoặc không là một tập con của X và X  Y không 
chứa hết mọi thuộc tính của R thì X phải là một siêu khóa của R. 
b. Ví dụ: 
Xét quan hệ: SKILL(ENO, PNO, PLACE) 
ENO PNO PLACE 
E1 P1 Toronto 
E1 P1 New York 
E1 P1 London 
E1 P2 Toronto 
E1 P2 New York 
E1 P2 London 
E2 P1 Toronto 
E2 P1 New York 
E2 P1 London 
E2 P2 Toronto 
E2 P2 New York 
E2 P2 London 
Quan hệ không có phụ thuộc hàm; tất cả các thuộc tính là thuộc tính khoá. 
Quan hệ SKILL có hai phụ thuộc đa trị: 
ENO  PNO 
ENO  PLACE 
Vì quan hệ không có phụ thuộc hàm nên nó ở dạng BCNF. Tuy nhiên nó không 
ở dạng chuẩn 4 vì ENO không phải là khoá. 
III. KẾT HỢP CHUẨN HOÁ VỚI CÁC PHÉP TÁCH SƠ ĐỒ QUAN HỆ 
1. Dùng phép tách kết nối không mất thông để đƣa về dạng chuẩn BCNF 
a. Giải thuật: 
- Input: Sơ đồ quan hệ R và tập phụ thuộc hàm F. 
- Output: Một phép tách của R với kết nối không mất thông tin, sao cho mọi sơ 
đồ quan hệ trong phép tách sẽ ở dạng chuẩn Boyce – Codd và thỏa chiếu của F trên đó. 
- Method: 
Cấu trúc phép tách  trên R theo phƣơng pháp lặp liên tiếp. Tại mỗi bƣớc 
phép tách  là bảo đảm không mất mát thông tin đối với F. 
Khởi đầu:  chỉ gồm R 
Các bước kế tiếp: Nếu S là một lƣợc đồ thuộc , S chƣa ở BCNF, chọn X 
 A là phụ thuộc hàm thỏa trên S, trong đó X không chứa khoá của S, A  X. Rõ ràng 
cần phải có một số thuộc tính khác của S vừa không phải A, vừa không thuộc X hoặc 
nếu không thì X phải chứa một khoá của S. Thay thế S trong  bởi S1 và S2. 
S1 = XA, S2 = S – A 
(phép tách S thành S1 và S2 là không mất thông tin đối với tập phụ thuộc hàm trên S vì 
rằng S1  S2 = X, X  S1 – S2 = A) 
Quá trình tiếp tục cho tới khi tất cả các lƣợc đồ đều ở BCNF. Chú ý 
rằng tại mọi thời điểm  luôn bảo đảm không mất thông tin, vì rằng  ban đầu là R, mà 
bƣớc thay đổi  đều bảo toàn tính chất đó. 
b. Ví dụ: 
Cho lƣợc đồ R(CTHRSG), trong đó C: giáo trình, T: thầy giáo, H: giờ, R: 
phòng học, S: sinh viên, G: lớp. Tập phụ thuộc hàm F: 
Cơ sở dữ liệu 
Trang: 57 
C  T HR  C 
HT  R CS  G 
HS  R 
Khoá của R là HS. 
Tách lƣợc đồ R thành các lƣợc đồ BCNF: 
- Xét CS  G cho R. Vi phạm điều kiện BCNF vì CS không chứa khoá. Do 
vậy, dùng thuật toán để tách R thành R1(CSG) và R2(CTHRS). Bƣớc tiếp cần tính F
+
 và 
chiếu xuống R1 và R2, sau đó kiểm tra các lƣợc đồ đã ở BCNF chƣa. Có thể biểu diễn 
quá trình tách qua sơ đồ quan hệ sau: 
2. Dùng phép tách bảo tồn phụ thuộc hàm để đƣa về dạng chuẩn thứ 3 
a. Giải thuật: 
- Input: Lƣợc đồ quan hệ R, tập các phụ thuộc hàm F; không làm mất tính tổng 
quát giả sử rằng nó là phủ tổi thiểu. 
- Output: Một phép tách  trên R có bảo toàn phụ thuộc hàm, sao cho mọi sơ 
đồ quan hệ đều ở dạng chuẩn ba và thỏa chiếu F trên sơ đồ quan hệ đó. 
- Method: 
+ Nếu có một hoặc một số thuộc tính nào đó của R không có mặt trong tất 
cả các phụ thuộc hàm của F thì về nguyên tắc bản thân chúng sẽ tạo thành một sơ đồ 
quan hệ và ta sẽ xoá chúng ra khỏi R. 
+ Nếu có một phụ thuộc hàm của F chứa hết tất cả các thuộc tính của R thì 
kết quả cần tìm chính là R. 
CTHRSG 
Khoá = HS 
C T, HR  C 
HT  R, CS  G 
HS  R 
CSG 
Khoá = CS 
CS  G 
CTHRS 
Khoá = HS 
C  T, HR  C 
HT  R, HS  R 
CT 
Khoá = C 
C  T 
CHRS 
Khoá = HS 
HR  C, HC  R 
HS  R 
HRC 
Khoá = HR, HC 
HR  C, HC  R 
HRS 
Khoá = HS 
HS  R 
Cơ sở dữ liệu 
Trang: 58 
+ Ngƣợc lại thì kết quả sẽ chứa sơ đồ quan hệ XA cho từng phụ thuộc hàm 
X  A trong F. Tuy nhiên, nếu X  A1, X  A2,…, X  An trong F, ta có thể dùng sơ 
đồ X  A1A2...An thay vì n sơ đồ X  Ai (1 ≤ i ≤ n). Thực tế cách thay thế này đƣợc 
ƣa thích hơn. 
b. Ví dụ: 
Cho sơ đồ quan hệ: 
HOC(Mon, GV, TG, Phong, SV, KQ) 
và tập phụ thuộc hàm: 
Mon  GV Mon, SV  KQ 
TG, Phong  Mon TG, SV  Phong 
TG, GV  Phong 
Theo giải thuật ta tách HOC thành các sơ đồ quan hệ: 
H1(Mon, GV) 
H2(TG, Phong, Mon) 
H3(TG, GV, Phong) 
H4(Mon, SV, KQ) 
H5(TG, SV, Phong) 
c. Định lý: 
Giải thuật tạo ra một phép tách bảo toàn phụ thuộc hàm để đƣa về dạng chuẩn 
thứ ba. 
3. Dùng phép tách kết nối không mất thông tin và phép tách bảo tồn phụ thuộc 
hàm để đƣa về dạng chuẩn thứ 3 
a. Giải thuật: 
- Input: Một phép tách  trên R có bảo toàn phụ thuộc hàm sao cho mọi sơ đồ 
quan hệ đều ở dạng chuẩn thứ ba và thỏa chiếu của F trên sơ đồ quan hệ đó. 
- Output: Một phép tách  trên R với kết nối không mất thông tin và bảo toàn 
phụ thuộc hàm sao cho mọi quan hệ đều ở dạng chuẩn thứ ba và thỏa chiếu của F trên 
sơ đồ quan hệ đó. 
- Method: Nếu  không có lƣợc đồ con chứa khoá của R và X là khoá nào đó 
của R thì ta chỉ đơn giản là thêm vào  một sơ đồ quan hệ chứa X:  =   {X} 
b. Ví dụ: 
Xét lại ví dụ trên, ta có kết quả: 
H1(Mon, GV) 
H2(TG, Phong, Mon) 
H3(TG, GV, Phong) 
H4(Mon, SV, KQ) 
H5(TG, SV, Phong) 
và 
H6(TG, SV) 
nhƣng ta thấy H3 đã chứa TG, SV nên kểt quả là: 
H1(Mon, GV) 
H2(TG, Phong, Mon) 
H3(TG, GV, Phong) 
H4(Mon, SV, KQ) 
H5(TG, SV, Phong) 
c. Định lý: 
Gọi  là phép tách đƣa R về dạng chuẩn thứ ba bảo toàn phụ thuộc hàm, và gọi 
X là một khoá của R. Ta có  =   {X} là một phép tách R thành các sơ đồ quan hệ ở 
dạng chuẩn thứ ba, phép tách này bảo toàn phụ thuộc hàm và có kết nối không mất 
thông tin. 
Cơ sở dữ liệu 
Trang: 59 
TÀI LIỆU THAM KHẢO 
 
1. Bài giảng Cơ sở dữ liệu 
Khoa Công nghệ thông tin, Trƣờng Đại học Cần Thơ - Phạm Thị Xuân Lộc. 
2. Cơ sở dữ liệu 
NXB Đại học quốc gia Hà Nội - Đỗ Trung Tuân. 
3. Giáo trình Cơ sở dữ liệu 
Đà Nẳng - PGS.TSKH. Trần Quốc Chiến. 
4. Nhập môn các hệ cơ sở dữ liệu (tập 1&2) 
NXB Thống kê, Hà Nội 1986 - 
Ngƣời dịch: Hồ Thuần, Nguyễn Quang Vinh, Nguyễn Xuân Huy, 
Hồ Thuần hiệu đính và giới thiệu. 
5. Nhập môn Cơ sở dữ liệu quan hệ 
NXB Khoa học và Kỹ thuật, 1995 – Lê Tiến Vƣơng. 
6. Principles of Database and Knowledge – Base systems (Volume 1&2) 
Computer Science Press – Jeffrey D. Ullman – Stanford University.