Giáo trình mô đun Cơ sở dữ liệu

n 
Kiệm 
Hung 40 Nguyễn 
Oanh 
TENNCC SANPHAM DONGIA 
Hung Gạch ống 200 
Hung Gạch thẻ 250 
 TENNCC r’ = r1|><|r2 
TENNCC DIACHI SANPHAM DONGIA 
Hung 12 Nguyễn Kiệm Gạch ống 200 
Hung 12 Nguyễn Kiệm Gạch thẻ 250 
Hung 40 Nguyễn Oanh Gạch ống 200 
Hung 40 Nguyễn Oanh Gạch thẻ 250 
Kết quả là r r’ hay r r.Q1|><|r.Q2. 
Với kết quả trên, ta nói phép tách (Q1,Q2) tách Q thành Q1, Q2 là tách-kết nối 
(phân rã) mất mát thông tin. 
Nếu r = r.Q1|><|r.Q2 ta nói phép tách (Q1,Q2) là tách-kết nối không mất mát 
thông tin (tách kết nối bảo toàn thông tin hay phân rã bảo toàn thông tin). 
Vậy với điều kiện nào thì phép tách trở thành tách-kết nối không mất mát thông 
tin? 
2.1.1 Định nghĩa phép tách Q thành 2 lược đồ con 
Q là lược đồ quan hệ, Q1, Q2 hai lược đồ con có: 
Q1+ Q2+ = X 
Q1+ Q2+ = Q+ 
Nói rằng lược đồ quan hệ Q được tách thành hai lược đồ con Q1, Q2 theo phép 
tách (Q1,Q2) là phép tách kết nối không mất (hay phép tách bảo toàn thông tin) nếu 
với r là quan hệ bất kỳ của Q ta có: 
Xr = r.Q1 r.Q2 
Tức là r được tạo nên từ phép kết nối tự nhiên của các hình chiếu của nó trên các 
Q1,Q2 
2.1.2 Tính chất 
Nếu Q là một lược đồ quan hệ, Q1,Q2 là hai lược đồ quan hệ con có 
 Q1
+  Q2
+ = X 
Q1
+  Q2
+ = Q+ 
X Q2
+ 
Thì 
Chứng minh: 
Ví dụ 10: cho Q(SAIP), Q1 =(SA) , Q2 =(SIP) F={S A,SI P}. Hỏi việc tách Q 
thành Q1 và Q2 có gây ra mất mát thông tin không? Áp dụng tính chất trên, ta có 
Q1
+ Q2
+ = S 
Q1
+  Q2
+ = SAIP = Q+ 
 S  SA = Q1
+ 
Theo tính chất trên, với mọi quan hệ r của Q ta luôn có r = r.Q1 r.Q2. Suy ra 
phép tách trên là phép tách kết nối bảo toàn thông tin. 
2.1.3 Phép tách Q thành n lược đồ con 
Q là một lược đồ quan hệ, F là tập phụ thuộc hàm. Q được tách thành các 
lược đồ con Q1, Q2, Q3...,Qn theo từng bước mà ở mỗi bước một lược đồ được 
tách thành hai lược đồ con và thỏa mãn điều kiện của tính chất bảo toàn thông 
tin thì với r là quan hệ bất kỳ của Q ta luôn có: 
 r = r.Q1|><|r.Qn 
Chứng minh: 
Ta chứng minh bằng phương pháp qui nạp. 
Ở bước i = 1 thì r = r.Q1|><|r.Q1m đúng theo định lý bảo toàn thông tin Giả sử 
biểu thức trên đúng ở bước i = k nghĩa là ta có: 
r = r.Q1|><|r.Qkm (1) 
ta phải chứng minh 
r = r.Q1|><|r.Qk+1m 
Với Qkm được tách thành hai lược đồ con Qk+1 và Qk+1m theo đúng điều 
kiện của tính chất bảo toàn thông tin nghĩa nếu s là quan hệ của Qkm thì s = 
s.Qk+1|><|r.Qk+1m 
 r = r.Q1|><|r.Qk+1m 
2.1.4 Thuật toán kiểm tra phép tách kết nối bảo toàn thông tin 
2.1.4.1 Thuật toán 
Dữ liệu vào: lược đồ quan hệ Q(A1,A2,An), tập phụ thuộc hàm F, phép tách 
 =(Q1,Q2,,Qk). 
Dữ liệu ra: kết luận phép tách có phải là phép tách bảo toàn thông tin ? 
Thiết lập bảng với k+1 dòng, n+1 cột . Cột j ứng với thuộc tính Aj (j=1...n), hàng 
i ứng với lược đồ quan hệ Qi(i=1k). Tại ví trí hàng i, cột j ta điền ký hiệu Aj nếu Aj 
 Qi, nếu không ta đặt ký hiệu bt vào vị trí đó. (với t đầu tiên bằng 1) và sau đó tăng 
t lên một đơn vị. 
Xét lần lượt các phụ thuộc hàm trong F, áp dụng cho bảng vừa mới thành lập ở 
trên. Giả sử xét (X Y) F, chúng ta tìm những hàng giống nhau ở tất cả các thuộc 
tính của X, nếu thấy những hàng như vậy ta sẽ làm cho các ký hiệu của hai hàng này 
bằng nhau ở tất cả các thuộc tính của Y. Khi làm cho 2 ký hiệu này bằng nhau, nếu 
một trong hai ký hiệu là aj thì cho ký hiệu kia trở thành aj, nếu hai ký hiệu là bk hoặc bl 
thì có thể cho chúng trở thành bt hoặc bt (với t = min (k,l)). Bước này được tiếp tục 
cho các phụ thuộc hàm còn lại của F cho đến khi không còn áp dụng được nữa. 
 Xét bảng kết quả, nếu thấy trong bảng này có một hàng chứa toàn aj (i=1..n) thì 
kết luận đó là phép kết nối bảo toàn thông tin, ngược lại là phép kết nối mất mát thông 
tin. 
 Chú ý: một điều quan trọng cần phải nhớ là khi cho hai ký hiệu bằng nhau thì 
phải cho bằng nhau ở tất cả các xuất hiện của chúng trong bảng chứ không phải chỉ 
cho bằng nhau ở những ký hiệu trong phạm vi các phụ thuộc X Y F. 
Ví dụ 11: Với Q(ABCDE) 
 Q1 = (AD),Q2 =(AB), Q3 =(BE), Q4 =(CDE), Q5 =(AE) 
 F = {A C,B C,A D,DE C,CE A} 
Kiểm tra tính bảo toàn thông tin của phép phân rã Q thành Q1,Q2,Q3,Q4,Q5. 
 Bước 1: a1 a2 a3 a4 a5 Bước 2: Điền b1,b2,b3, ... 
 A B C D E 
 A B C D E 
Q1(AD) a1 a4 Q1(AD) a1 b1 b2 a4 b3 
Q2(AB) a1 a2 Q2(AB) a1 a2 b4 b5 b6 
Q3(BE) a2 a5 Q3(BE) b7 a2 b8 b9 a5 
Q4(CDE) a3 a4 a5 Q4(CDE) b10 b11 a3 a4 a5 
Q5(AE) a1 a5 Q5(AE) a1 b12 b13 b14 a5 
 Sửa bảng giá trị để nó thỏa A C Sửa b4,b13 thành b2 
 A B C D E 
Q1(AD) a1 b1 b2 a4 b3 
Q2(AB) a1 a2 b2 b5 b6 
 Q3(BE) b7 a2 b8 b9 a5 
Q4(CDE) b10 b11 a3 a4 a5 
Q5(AE) a1 b12 b2 b14 a5 
 Sửa bảng giá trị để nó thỏa B C Sửa b8 thành b2 
 A B C D E 
Q1(AD) a1 b1 b2 a4 b3 
Q2(AB) a1 a2 b2 b5 b6 
Q3(BE) b7 a2 b2 b9 a5 
Q4(CDE) b10 b11 a3 a4 a5 
Q5(AE) a1 b12 b2 b14 a5 
ửa bảng giá trị để nó thỏa A D Sửa b5,b14 thành a4 
Sửa bảng giá trị để nó thỏa DE C sửa b2 thành a3 sửa tất cả b2 thành a3 
 A B C D E 
 A B C D E 
Q1(AD) a1 b1 b2 a4 b3 Q1(AD) a1 b1 a3 a4 b3 
Q2(AB) a1 a2 b2 a4 b6 Q2(AB) a1 a2 a3 a4 b6 
Q3(BE) b7 a2 b2 b9 a5 Q3(BE) b7 a2 a3 b9 a5 
Q4(CDE) b10 b11 a3 a4 a5 Q4(CDE) b10 b11 a3 a4 a5 
Q5(AE) a1 b12 b2 a4 a5 Q5(AE) a1 b12 a3 a4 a5 
 134 
Sửa bảng giá trị để nó thỏa CE A Sửa b7,b10 thành a1 
Lần lượt xét lại các phụ thuộc hàm trong F, nếu bảng giá trị chưa thỏa phụ thuộc 
hàm nào thì tiếp tục làm cho nó thỏa. Sửa bảng giá trị để nó thỏa A D 
 A B C D E 
 A B C D E 
Q1(AD) a1 b1 a3 a4 b3 Q1(AD) a1 b1 a3 a4 b3 
Q2(AB) a1 a2 a3 a4 b6 Q2(AB) a1 a2 a3 a4 b6 
Q3(BE) a1 a2 a3 b9 a5 Q3(BE) a1 a2 a3 a4 a5 
Q4(CDE) a1 b11 a3 a4 a5 Q4(CDE) a1 b11 a3 a4 a5 
Q5(AE) a1 b12 a3 a4 a5 Q5(AE) a1 b12 a3 a4 a5 
 Dòng thứ Q3(BE) của bảng chứa toàn giá trị aj (j=1..n) nên phép phân rã trên là 
bảo toàn thông tin. 
2.1.4.2 Định lý 
Bảng kết quả của thuật toán trên cho phép ta kết luận được tính bảo toàn hay 
không bảo toàn thông tin của phép tách. 
Chứng minh: 
Ta chứng minh nếu bảng kết quả thuật toán không có hàng chỉ chứa toàn giá trị a 
thì phép tách không bảo toàn thông tin. Thật vậy: 
Ta xây dựng một quan hệ r có các giá trị như bảng kết quả của thuật toán, các 
hàng là các bộ. Quan hệ r thỏa tập phụ thuộc F vì thuật toán đã sửa các giá trị của r để 
nó khỏi vi phạm các phụ thuộc hàm trong F r là một quan hệ của lược đồ Q. Ta 
tách quan hệ r thành các quan hệ ri với ri = r.Qi và dùng phép kết tự nhiên để kết 
chúng lại. Nếu: 
+ k Qk
+Qi
+ = i r1|><|rk không tồn tại phép tách không bảo 
toàn thông tin. 
 135 
 i,k Qi
+Qk
+
 = Xik  mà mỗi ri đều có một bộ ti chứa toàn a các ti nối 
được với nhau vì có cùng giá trị trên Xik có một bộ t r1|><|rk có toàn giá trị 
a, bộ này lại không có trong r r r1|><|rk phép tách không bảo toàn 
thông tin. 
Ta chứng minh nếu bảng kết quả thuật toán có hàng chỉ chứa toàn giá trị a thì 
phép tách bảo toàn thông tin. Ta chứng minh điều này qua 2 bước: 
+ Bước 1: chứng minh nếu t r t r1|><|rk. Suy ra 
rr1|><|rk. 
Giả sử t=(a1,...,an) r . Ta tách quan hệ r thành các ri = r.Qi với ti = t.Qi. Có hai 
trường hợp: 
 i,k Qi
+Qk
+
 = Xik  các ti nối được với nhau vì có cùng giá trị trên Xik 
 bộ t r1|><|rk. k Qk
 Qi
+ = i. Suy ra bảng 
kiểm tra bảo toàn thông tin ở giai đoạn chưa thỏa các phụ thuộc hàm, có dạng: 
 A1 A2 ... AK AK+1 ... 
Q1 bk1 bk2 b.. 
Q2 b.. ... ... 
... b.. ... ... 
QK(AK,AK+1,..) b.. b.. b.. ak ak+1 ... 
Với mọi XQ+ tk.X ti.X với i k nên khi làm bằng các giá trị theo các phụ 
thuộc hàm X Y thì các giá trị b ở dòng Qk không thay đổi còn các giá trị b ở các cột 
Ak,Ak+1,... không đổi thành a được. Suy ra bảng kết quả của thuật toán không bao giờ 
chứa dòng có toàn giá trị a. Vậy trường hợp k Qk
+Qi
+ = i không xảy ra khi 
bảng kiểm tra bảo toàn thông tin có một dòng toàn a. 
+ Bước 2: chứng minh nếu t r1|><|rk t r. Suy ra 
r1|><|rkr. 
 136 
Giả sử t=(a1,...,an) r1|><|rk theo định nghĩa suy ra i ti ri sao cho t.Qi
+ 
= ti. Nhưng ri=r.Qi
+
 ti’ r sao cho ti’.Qi
+=ti=t.Qi
+ i . 
Trường hợp xấu nhất là các ti’là các dòng khác nhau. Trong trường hợp này, ta 
có thể xem ti’là dòng Qi của bảng kiểm tra bảo toàn thông tin với các giá trị b xem 
như chưa biết. Nhưng các dòng Qi phải thỏa các phụ thuộc hàm trong F, phép làm 
bằng các giá trị theo các phụ thuộc hàm đã dần dần xác định được tất cả các giá trị b 
của một dòng ti’nào đo, là dòng có toàn giá trị a. Vậy có một i’ để ti’= t t r r  
r1|><|rn (2) 
(1) và (2) r = r1|><|rn. Nói cách khác phép tách bảo toàn thông tin. 
2.2 Phép tách bảo toàn phụ thuộc hàm (decompositions that preserve 
dependencies) 
2.2.1 Tập phụ thuộc hàm Fi của Qi 
Phần trên chỉ đề cấp vấn đề tách một lược đồ quan hệ Q(A1,A2,An)thành các 
lược đồ con Q1,Q2,,Qk còn không đề cập đến tập phụ thuộc hàm của các lược đồ 
con này. Nếu 
Q(A1,A2,An) là lược đồ quan hệ, F phụ thuộc hàm, =(Q1,Q2,,Qk)là phép 
phân rã bảo toàn thông tin, ri là quan hệ của Qi thì tính chất sau thỏa: 
+ ri chỉ thỏa các phụ thuộc hàm X Y F
+ với XYQi
+ 
Nói cách khác, tập phụ thuộc hàm của Qi chính là Fi có Fi
+={X Y F+| 
XYQi
+}. Ta có thể hiểu F được phân rã thành các F1,...,Fk Chứng minh tính chất 
trên: 
Do ri được tách từ r mà r thỏa F
+ ri thỏa các phụ thuộc hàm X Y F
+ với 
XYQi
+.Theo định nghĩa phụ thuộc hàm, đương nhiên ri không thỏa các phụ thuộc 
hàm X Y F+ với XYQi
+. Ngoài ra ri không thỏa bất kỳ một phụ thuộc hàm nào 
X Y F+ . Thật vậy nếu có X Y như vậy thì r = r1|><|rn cũng phải thỏa 
X Y F+. Điều này mâu thuẫn với định nghĩa của tập F+ . 
 ii Định nghĩa: 
 137 
Cho phân rã =(Q1,Q2,,Qk) của một lược đồ quan hệ, và một tập phụ thuộc 
hàm F. 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+ sao cho XY  Z. 
Qi(F)=Fi
+={ X Y| X Y F+ và XY  Qi} 
Ta nói phân rã bảo toàn tập phụ thuộc hàm F nếu 
F Qi(F) F
+ = Qi(F))
+ với i=1..k 
Hệ quả: F+  Qi(F))
+ với i=1..k 
Nhận xét: từ hệ quả trên ta suy ra: để xác định phép phân rã =(Q1,Q2,,Qk) có 
bảo toàn phụ thuộc hàm hay không, với mỗi phụ thuộc hàm X Y F ta xác định xem 
nó có là thành viên của tập phụ thuộc hàm G = Qi(F) hay không. Ta không cần 
xác định chiều ngược lại. 
2.2.2 Thuật toán kiểm tra bảo toàn phụ thuộc hàm 
Thuật toán tìm bao đóng của tập thuộc tính X đối với G = Qi(F) 
Vào: =(Q1,Q2,,Qk),F,X 
Ra: XG
+ 
Bước 1: Với mỗi phụ thuộc hàm X Y F ta thực hiện từ bước 2 đến bước 4 
Bước 2: đặt Z’ = X 
Bước 3: thế Z’ = Z’((Z’Qi
 )+  Q
  
Bước 4: nếu ở Qi, Z’thay đổi thì thực hiện lại bước 3 cho Qđầu tiên 
Ngược lại kết thúc thuật toán và trả về Z’(là bao đóng XG
+) 
Thuật toán kiểm tra bảo toàn phụ thuộc hàm 
Vào: =(Q1,Q2,,Qk),F 
Ra: kết luận phép tách bảo toàn hay không bảo toàn phụ thuộc hàm Bước 
1: Với mỗi phụ thuộc hàm X Y F ta thực hiện từ bước 2 đến bước 3: 
Bước 2: Tìm bao đóng XG
+
 với G = Qi(F) 
Bước 3: Nếu Y  XG
+ thì X Y Qi(F)
+ 
 138 
Bước 4: Nếu tất cả phụ thuộc X Y F đều thuộc Qi(F)
+ thì ta kết luận phân 
rã bảo toàn phụ thuộc hàm ngược lại không bảo toàn phụ hàm 
3. BÀI TẬP 
1/ Cho biết dạng chuẩn của các lược đồ quan hệ sau: 
a) Q(ABCDEG); F={A BC, C DE, E G} 
b) Q(ABCDEGH); F={C AB, D E, B G} 
c) Q(ABCDEGH) F={A BC, D E, H G} 
d) Q(ABCDEG); 
e) Q(ABCDEGHI); 
F={AB C, C B, ABD E, G A} 
 F={AC B,BI ACD,ABC D,H I,ACE BCG,CG A E} 
 2/ Kiểm tra sự bảo toàn thông tin ? 
Q(ABCDE) R1(AD);R2(AB);R3(BE); R4(CDE);R5(AE) 
F={A C; B C;C D;DE C;CE A} 
 3/ Cho lược đồ quan hệ Q(A,B,C,D) và tập phụ thuộc hàm 
F = {A B;B C;A D;D C} 
Và một lược đồ CSDL như sau: C ={Q1(AB);Q2(AC);Q3(BD)} 
a) C có bảo toàn thông tin đối với F 
b) C có bảo toàn phụ thuộc hàm ? 
4/ Kiểm tra dạng chuẩn Q(C,S,Z) F={CS Z;Z C} 
 5/ Phân rã Q(G,H,A,B,C,D) F={GH AD;AG B;CD GH; C A; BH C} 
 6/ Cho lược đồ CSDL 
Kehoach(NGAY,GIO,PHONG,MONHOC,GIAOVIEN) 
F={NGAY,GIO,PHONG MONHOC 
 139 
MONHOC,NGAY GIAOVIEN 
NGAY,GIO,PHONG GIAOVIEN 
MONHOC GIAOVIEN} 
a) Xác định dạng chuẩn cao nhất của Kehoach 
b) Nếu Kehoach chưa đạt dạng chuẩn 3, hãy phân rã Kehoach thành lược đồ 
CSDL dạng chuẩn 3 vừa bảo toàn phụ thuộc hàm vừa bảo toàn thông tin. 
c) Nếu Kehoach chưa đạt dạng chuẩn BC, hãy phân rã KeHoach thành lược đồ 
CSDL dạng BC 
 7/ Cho lược đồ quan hệ Q(A,B,C,D) và tập phụ thuộc hàm F 
F = {A B;B C; D B} C = {Q1(A,C,D); Q2(B,D)} 
a) Xác định các Fi (những phụ thuộc hàm F được bao trong Qi) 
b) Lược đồ CSDL C có đạt dạng chuẩn BC ? Nếu không có thể phân rã tiếp các 
Qi của C để biến C thành dạng chuẩn BC ? 
 8/ Giả sử ta có lược đồ quan hệ Q(C,D,E,G,H,K) và tập phụ thuộc hàm F như sau; 
F = {CK H; C D; EC; E G; CK E} 
a) Từ tập F, hãy chứng minh EK  DH 
b) Tìm tất cả các khóa của Q. 
c) Xác định dạng chuẩn của Q. 
d) Hãy tìm cách phân rã Q thành một lược đồ CSDL đạt dạng chuẩn BC 
(hoặc dạng chuẩn 3). tìm tập phụ thuộc hàm và khóa cho mỗi lược đồ 
quan hệ con. 
 9/ Cho lược đồ quan hệ Q(S,I,D,M) 
F = {f1:SI DM; f2:SD M; f3:D M} 
a) Tính bao đóng D+, SD+, SI+ 
b) Tìm tất cả các khóa của Q 
c) Tìm phủ tối thiểu của F 
d) Xác định dạng chuẩn cao nhất của Q 
 140 
e) Nếu Q chưa đạt dạng chuẩn 3, hãy phân rã Q thành lược đồ CSDL dạng 
chuẩn 3 vừa bảo toàn phụ thuộc hàm vừa bảo toàn thông tin. 
f) Nếu Q chưa đạt dạng chuẩn BCNF, hãy phân rã Q thành lược đồ CSDL 
dạng BCNF 
g) Kiểm tra phép tách Q thành các lược đồ con (SID,SIM) có bảo toàn thông 
tin ? 
h) Kiểm tra phép tách Q thành các lược đồ con (SID,SIM) có bảo toàn phụ 
thuộc hàm ? 
 10/ Cho lược đồ quan hệ 
R(W,A,Z,Y,Q,P) 
R1(A,Z); 
R2(W,Y,Q,P) 
R3(Y,Q,P,A) 
F = {W AYQP, A Z, YQP A} 
Hãy kiểm tra tính kết nối không mất thông tin. 
 11/ Cho lược đồ quan hệ Q(Môn, GiảngViên,Giờ giảng, Phòng, SinhViên, 
Hạng) với 
 F ={M GV; G,P M; G,GV P; M,SV H; G,SV P} 
 C = {Q1(M,G,P); Q2(M,GV);Q3( M,SV,H)} 
 Kiểm tra xem lược đồ cơ sở dữ liệu sau đây có bảo toàn thông tin đối với F ? 
 12/ Kiểm Tra Dang Chuẩn 
a) Q(A,B,C,D) F={CA D; A B} 
b) Q(S,D,I,M) F={SI D;SD M} 
c) Q(N,G,P,M,GV) F={N,G,P M;M GV} 
d) Q(S,N,D,T,X) F={S N; S D; S T; S X} 
 13/ Phân rã lược đồ thành dạng BCK 
 141 
a) Q(S,D,I,M) F={S,I D;S,D M} 
b) Q(A,B,C,D) F={A B;B C;D B} 
c) Q(C,S,Z) F={C,S Z; Z C} 
 14/ Phân rã lược đồ thành dạng 3NF vừa bảo toàn phụ thuộc hàm vừa bảo toàn 
thông tin 
a) Q(A,B,C), F={A B;A C;B A;C A;B C} 
Q(MSCD,MSSV,CD,HG) 
F={MSCD CD; CD MSCD; 
CD,MSSV HG; 
MSCD,HG MSSV; CD,HG MSSV; 
MSCD,MSSV HG} 
b) Q(A,B,C,D) F={ AB C; C B} 
 142 
 TÀI LIỆU THAM KHẢO 
 [1] Lê tiến Vương (1999), Nhập môn cơ sở dữ liệu, NXB Khoa học Kỹ thuật. [2] 
Trần Đức Quang, Hồ Thuần (2003), Cơ sở dữ liệu và cơ sở tri thức tâp1, tập 2, NXB 
Thống kê 
[3] Đỗ Trung Tuấn (2003), Cơ sở dữ liệu, NXB Gio dục. 
[4] Tài liệu điện tử từ internet: Giáo trình Cơ sở dữ liệu Trường Cao Đẳng Công 
Nghiệp 4; ...