Bài giảng tóm tắt Cơ sở dữ liệu

g 
quan hệ MONHOC và xoá bộ {‘0310000’, ‘CT110’, ‘Nguyễn Ngọc’, ‘1 Lê 
Hồng Phong, Đà Lạt’, 9} trong quan hệ SINHVIEN. Khi đó thông tin về sinh 
viên sẽ bị mất. 
Để khắc phục những bất lợi trên, quan hệ SINHVIEN có thể tách thành 2 quan hệ 
SINHVIEN (MSSV, TenSV, DiaChi) và KETQUATHI (MSSV, MaMH, Diem). Như 
vậy, 3 quan hệ trên đều đã ở dạng chuẩn thứ 2. 
Trang 94/103 
1.3. Dạng chuẩn 3 
1.3.1. Định nghĩa 
Định nghĩa 1 
Với một lược đồ Q; X, Y là hai tập con của Q+; A là một thuộc tính. Khi đó A được gọi 
là phụ thuộc bắc cầu vào X nếu thỏa: 
(1) XÆY, YÆA 
(2) Y X 
(3) A ∉ XY 
Lược đồ Q ở dạng chuẩn 3 nếu mọi thuộc tính không khóa đều không phụ thuộc bắc cầu 
vào khóa. 
Việc kiểm tra dạng chuẩn 3 theo định nghĩa trên sẽ khó cài đặt. Ta có thể thực hiện kiểm 
tra dạng chuẩn 3 theo định nghĩa sau: 
Định nghĩa 2 
Lược đồ Q ở dạng chuẩn 3 nếu mọi phụ thuộc hàm XÆA∈F+, với A ∉ X đều có: 
(1) X là siêu khóa, hoặc 
(2) A là thuộc tính khóa 
1.3.2. Kiểm tra dạng chuẩn 3 
Từ định nghĩa 2, để kiểm tra dạng chuẩn 3 thực hiện các bước sau: 
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 để tập F trở thành tập 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 đều 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. 
Ví dụ. Cho Q (A, B, C, D), F={ABÆD, CÆD} 
Bước 1: Q có một khóa là ABC 
Trang 95/103 
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. 
1.4. Dạng chuẩn BC (Boyce Codd) 
1.4.1. Định nghĩa 
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. 
1.4.2. Kiểm tra dạng chuẩn BC 
Từ định nghĩa, để kiểm tra dạng chuẩn BC thực hiện các bước sau: 
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 để tập F trở thành tập 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 đề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. 
Ví dụ. 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 3: 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. 
1.5. Kiểm tra dạng chuẩn 
Kiểm tra dạng chuẩn của lược đồ quan hệ Q 
Bước 1: Tìm mọi khóa của Q 
Bước 2: Kiểm tra dạng chuẩn BC, nếu đúng thì Q đạt dạng chuẩn BC, 
Trang 96/103 
 ngược lại qua bước 3. 
Bước 3: Kiểm tra dạng chuẩn 3, nếu đúng thì Q đạt dạng chuẩn 3, 
 ngược lại qua bước 4. 
Bước 4: Kiểm tra dạng chuẩn 2, nếu đúng thì Q đạt dạng chuẩn 2, 
 ngược lại Q đạt dạng chuẩn 1. 
Kiểm tra dạng chuẩn của lược đồ CSDL 
Dạng chuẩn của một lược đồ CSDL là dạng chuẩn thấp nhất trong các dạng chuẩn của các 
lược đồ quan hệ con. 
2. Phép phân rã 
Mục tiêu của việc thiết kế CSDL quan hệ là tạo ra một tập các lược đồ quan hệ cho phép 
chúng ta lưu trữ thông tin không có những dư thừa không cần thiết và truy tìm thông tin 
một cách dễ dàng, chính xác. Việc phân rã một lược đồ thành những lược đồ con đều 
mong muốn đạt được bảo toàn thông tin và bảo toàn phụ thuộc. 
2.1. Phân rã bảo toàn thông tin 
Cho lược đồ quan hệ Q (TenNCC, DiaChiNCC, SanPham, DonGia) 
Phân rã Q thành Q1 và Q2 như sau: 
Q1 (TenNCC, SanPham, DonGia) 
Q2 (TenNCC, DiaChiNCC) 
Khi đó ta có các thể hiện sau: 
Q TenNCC DiaChiNCC SanPham DonGia 
 Nguyễn Mai 10 Nguyễn Công Trứ Bánh xốp 10.000 
 Nguyễn Mai 10 Nguyễn Công Trứ Kẹo mè 20.000 
 Nguyễn Mai 20 Nguyễn Văn Trỗi Kẹo mè 20.000 
Q1 TenNCC SanPham DonGia 
 Nguyễn Mai Bánh xốp 10.000 
Trang 97/103 
 Nguyễn Mai Kẹo mè 20.000 
Q2 TenNCC DiaChiNCC 
 Nguyễn Mai 10 Nguyễn Công Trứ 
 Nguyễn Mai 20 Nguyễn Văn Trỗi 
21 QQ >< TenNCC DiaChiNCC SanPham DonGia 
 Nguyễn Mai 10 Nguyễn Công 
Trứ 
Bánh xốp 10.000 
 Nguyễn Mai 10 Nguyễn Công 
Trứ 
Kẹo mè 20.000 
 Nguyễn Mai 20 Nguyễn Văn Trỗi Bánh xốp 10.000 
 Nguyễn Mai 20 Nguyễn Văn Trỗi Kẹo mè 20.000 
Như vậy kết quả thể hiện Q và 21 QQ >< là khác nhau, khi đó ta nói phép phân rã gọi là 
không bảo toàn thông tin (mất mát thông tin). 
Định nghĩa 
Q là lược đồ quan hệ, Q1, Q2 là hai lược đồ con có: 
+++
++
=∪
=∩
QQQ
XQQ
21
21
Khi đó Q được phân rã thành hai lược đồ con Q1, Q2 là phép phân rã bảo toàn thông tin 
nếu với r là thể hiện bất kỳ của Q ta có: 
 21 .. QrQrr ><= 
(r là kết quả của phép kết tự nhiên của các hình chiếu của nó trên Q1, Q2) 
2.2. Phân rã bảo toàn phụ thuộc hàm 
Một vấn đề cần quan tâm khi phân rã lược đồ Q thành các lược đồ con Qi với tập các Fi 
tương ứng được tính từ tập phụ thuộc hàm F. Phép phân rã bảo toàn phụ thuộc (giữ lại 
Trang 98/103 
phụ thuộc) nếu với ri là thể hiện của Qi thoả điều kiện: ri chỉ thoả những phụ thuộc hàm 
XÆY ∈F+ với XY⊆Qi+ 
Định nghĩa 
Gọi Q1, Q2,…, Qn là phân rã của lược đồ quan hệ Q, tập phụ thuộc hàm F trên Q. Hình 
chiếu của F trên một tập các thuộc tính Qi+ ký hiệu ΠQi+(F) là tập các phụ thuộc hàm 
XÆY ∈F+ với XY⊆Qi+ 
ΠQi+(F) = Fi+={XÆY | XÆY ∈F+ và XY⊆Qi+ } 
Khi đó phân rã là bảo toàn tập phụ thuộc hàm F nếu 
F ≡ ∪ ΠQi+(F) 
3. Thiết kế CSDL bằng cách phân rã 
3.1. Phân rã thành dạng chuẩn BC (hoặc dạng chuẩn 3) bảo toàn thông tin 
3.1.1. Thuật toán 
Bước 1: Tìm tất cả các khóa của Q 
Bước 2: Tìm phụ thuộc hàm XÆY ∈F có X không là siêu khóa và Y không chứa thuộc 
tính khóa. 
• Nếu tìm thấy thì tách Q thành Q1 và Q2 theo cách: 
o Q1 = Q[XY]; F1 ≡ ΠQ1(F) (tìm bao đóng của tất cả các tập con của XY để tính 
F1). Tiếp tục phân rã (Q1, F1). 
o Q2 = Q[Q+ - Y]; F2 ≡ ΠQ2(F) (tìm bao đóng của tất cả các tập con của (Q+ - Y) 
để tính F2). Tiếp tục phân rã (Q2, F2). 
• Nếu không tìm thấy thì xét dạng chuẩn Qi: 
o Nếu mọi phụ thuộc hàm trong Fi đều có vế trái là siêu khóa thì Qi đạt dạng 
chuẩn BC 
o Nếu có phụ thuộc hàm trong Fi có vế trái không là siêu khóa và vế phải là 
thuộc tính khóa thì Qi đạt dạng chuẩn 3 
3.1.2. Ví dụ 
Ví dụ 1 
Cho Q (SDIM), F={SIÆD, SDÆM} 
Trang 99/103 
Bước 1: Q có một khóa là {SI} 
Bước 2: Phụ thuộc hàm SDÆM có SD không là siêu khóa nên tách: 
Q1 = (SDM); F1 = {SDÆM} 
Q2 = (SDI); F2 = {SIÆD} 
Để tìm tập phụ thuộc hàm F1, F2 cần tính bao đóng của mọi tập con. 
Tìm F1: với Q1 = (SDM): bao đóng của mọi tập con 
SSF =+ 
DDF =+ 
MM F =+ 
SDMSDF =+ 
SMSM F =+ 
DMDM F =+ 
SDMSDM F =+ 
F1 = ΠQ1(F) = {SDÆM, SDÆSM, SDÆDM, SDÆSDM } 
⇒ F1 = {SDÆM} 
Tìm F2: với Q2= (SDI): bao đóng của mọi tập con 
SSF =+ 
DDF =+ 
II F =+ 
SDMSDF =+ 
SIDMSI F =+ 
DIDI F =+ 
SDIMSDI F =+ 
Trang 100/103 
F2 = ΠQ2(F) = {SIÆD, SIÆSD, SIÆDI, SIÆSDI } 
⇒ F2 = {SIÆD} 
Bước 3: Mọi phụ thuộc hàm trong F1và F2 đều có vế trái là một siêu khóa nên Q1 và Q2 
đạt dạng chuẩn BC. 
Ví dụ 2 
Cho Q (ABCDE), F = {BCÆA, CÆD, AEÆB, BÆD, BÆE} 
Bước 1: 2 khóa là {CB, CAE} 
Bước 2: Từ CÆ D tách thành: 
• Q1(CD), F1= {CÆD}, Khóa C. Đạt dạng chuẩn BC. 
• Q2(CABE), F2= {BÆE, CBÆA, AEÆB} 
Chi tiết tính F1, F2 như sau: 
Tìm F1: với Q1 = (CD) 
CDCF =+ 
DDF =+ 
CDCDF =+ 
Vậy F1 = {CÆD} 
Tìm F2: với Q2(CABE): 
 CDCF =+ 
AAF =+ 
BDEBF =+ 
EEF =+ 
CADCAF =+ 
CBADECBF =+ 
CEDCEF =+ 
Trang 101/103 
ABDEABF =+ 
AEBDAEF =+ 
BEDBEF =+ 
CABDECABF =+ 
CAEBDCAEF =+ 
CBEADCBEF =+ 
ABEDABEF =+ 
CABEDCABEF =+ 
F2= {BÆE, CBÆAE, ABÆE, AEÆB, CABÆE, CAEÆB, CBEÆA} 
Vậy F2= {BÆE, CBÆA, AEÆB} 
Xét dạng chuẩn Q2: 
Khoá Q2: {CB, CAE}. Vậy Q2 đã đạt dạng chuẩn 3. 
3.1.3. Cải tiến thuật toán 
Nhận thấy rằng trong tìm phụ thuộc hàm hình chiếu trên Qi, xét tập một con Xi, nếu 
( ) ++ = QX Fi , khi đó nếu tiếp tục xét các tập XjXiXj ⊂: , thì hiển nhiên ( ) ++ = QX Fj , và 
cuối cùng thì phụ thuộc hàm có vế trái Xj cũng sẽ bị loại để chỉ chọn phụ thuộc hàm có 
vế trái Xi. 
Do đó, khi tìm phụ thuộc hàm hình chiếu trên Qi, xét tập một con Xi, nếu ( ) ++ = QX Fi , 
thực hiện loại bỏ các tính toán cho các trường hợp XjXiXj ⊂: . 
Ví dụ: với tìm F2 như ví dụ trên: 
Q2(CABE), F = {BCÆA, CÆD, AEÆB, BÆD, BÆE} 
 CDCF =+ 
AAF =+ 
BDEBF =+ 
EEF =+ 
Trang 102/103 
CADCAF =+ 
CBADECBF =+ , loại các tập CAB, CBE, CABE 
CEDCEF =+ 
ABDEABF =+ 
AEBDAEF =+ 
BEDBEF =+ 
ABEDABEF =+ 
F2= {BÆE, CBÆAE, ABÆE, AEÆB} 
Vậy F2= {BÆE, CBÆA, AEÆB} 
3.2. Phân rã thành dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc 
hàm 
Bước 1: Tìm phủ tối thiểu của F. 
Bước 2: Loại bỏ tất cả các thuộc tính của Q không liên quan đến một phụ thuộc hàm nào 
của PTT(F). 
Bước 3: Nếu có một phụ thuộc hàm trong PTT(F) liên quan đến mọi thuộc tính của Q thì 
không thể phân rã. Ngược lại, qua bước 4. 
Bước 4: Gom nhóm những phụ thuộc hàm có cùng vế trái. Với mỗi nhóm phụ thuộc hàm 
có cùng vế trái, tạo thành một lược đồ con. 
Bước 5: Kiểm tra các lược đồ con có thoả dạng chuẩn 3 chưa, nếu chưa thì áp dụng bước 
4 để phân rã tiếp. 
Ví dụ. Cho Q (CTHRSG), F={CÆT, HRÆC, HTÆR, CSÆG, HSÆR} 
PTT(F) = F = {CÆT, HRÆC, HTÆR, CSÆG, HSÆR} 
Ta có kết quả phân rã Q1(CT), Q2(HRC), Q3(HTR), Q4(CSG), Q5(HRS) 
4. Bài tập 
Bài tập 7, 8, 9 trong chương 7, với yêu cầu: 
- Phân rã thành dạng chuẩn BC hoặc dạng chuẩn 3 bảo toàn thông tin 
Trang 103/103 
- Phân rã thành dạng chuẩn 3 bảo toàn thông tin và bảo toàn phụ thuộc hàm 
Tài Liệu Tham Khảo 
1. Bài giảng Cơ sở dữ liệu, Nguyễn Hữu Tân, Đại Học Đà Lạt, 2004. 
2. Bài tập cơ sở dữ liệu, Nguyễn Xuân Huy – Lê Hoài Bắc, NXB thống kê, 2003. 
3. Giáo trình Cơ sở dữ liệu, Nguyễn Đăng Tỵ - Đỗ Phúc, Đại Học Quốc gia Tp. Hồ Chí 
Minh, 2001. 
4. Nhập môn Cơ sở dữ liệu quan hệ, Lê Tiến Vương, NXB Khoa học và Kỹ thuật, 1994. 
5. David Maier, The theory of Relational Databases, Computer Science Press, 
Rockville, 1983.