Giáo trình Cơ sở dữ liệu - Nguyễn Thị Thùy Linh

 lược đồ quan hệ Q(A,B,C) và F={A B,B C,C A}. Phép phân rã =(Q1,Q2) 
tách Q thành hai lược đồ quan hệ Q1(A,B) và Q2(B,C). Có bảo toàn phụ thuộc hàm không 
(không tính F+) 
Vào: Q(A,B,C), F={A B,B C,C A},Q1(A,B) và Q2(B,C) 
Hiển nhiên 
Ta xác định C Acó thuộc 
6.3 Thiết kế CSDL bằng cách phân rã 
6.3.1 Thiết kế CSDL bằng cách phân rã theo các thuật toán thông thường 
a. Thiết kế CSDL bằng cách phân rã 
 Tức là phân rã thành dạng chuẩn BC(hay chuẩn 3) bảo toàn thông tin 
b. Trình tự phân rã Q, F thành dạng chuẩn BC (hay chuẩn 3) bảo toàn thông tin 
b1. Thuật toán thông thường 
 Bước 1:Tìm tất cả khóa của Q 
 Bước 2:Tìm phụ thuộc hàm X Y Fcó 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 quy tắc sau: 
 tìm bao đóng của tất cả tập con của XY để suy ra 
 tìm bao đóng của tất cả tập con của Q+-Yđể suy ra 
 60 
 thực hiện thuật toán phân rã (Q1,F1) 
 thực hiện thuật toán phân rã (Q2,F2) 
 Ngược lại nếu không tìm thấy thì có hai trường hợp: 
 Trường hợp 1: mọi phụ thuộc hàm trong Fi đều có vế trái là siêu khóa thì Qi đạt 
 chuẩn BC 
 Trường hợp 2: nếu có phụ thuộc hàm 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 chuẩn 3. 
b2. Thuật toán cải tiến 
Thuật toán phân rã Q, F thành dạng chuẩn BC (hay chuẩn 3) bảo toàn thông tin 
 Bước 1: Tìm tập tất cả khóa SK của Q 
 Bước 2: Tìm phụ thuộc hàm X Y Fcó 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 quy tắc sau: 
 Q1=Q[XY]; Tính F1 bằng cách tính bao đóng tất cả tập con của XY 
 +
 Q2=Q[Q -Y] SK cũng là tập khóa của Q2 
 thực hiện bước 1 cho Q1 
 thực hiện bước 2 cho Q2 
 Ngược lại nếu không tìm thấy thì có hai trường hợp: 
 Trường hợp 1: mọi phụ thuộc hàm trong Fi đều cóvế trái là siêu khóa thì Qi đạt 
 chuẩn BC 
 Trường hợp 2: nếu có phụ thuộc hàm 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 chuẩn 3. 
Chú ý: Thuật toán này chỉ tiện trong trường hợp khối lượng tính toán trong việc tìm tất cả 
khóa của lược đồ quan hệ Q không lớn. Nói cách khác tập trung gian TG có ít thuộc tính. 
Ngược lại ta phải dùng thuật toán của phần tiếp theo. 
b3. Thuật toán phân rã không cần tìm tất cả các khóa của LĐQH Q 
Thuật toán phân rã sau không cần tìm tất cả khóa của lược đồ quan hệ Q 
Thuật Toán phân rã Q, F thành dạng chuẩn BC bảo toàn thông tin 
Bước 1: Z’ = Q+ 
Bước 2: phân rã Z’ theo thuật toán chi tiết để được 2 lược đồ Z’-A và XA trong đó XA ở 
dạng chuẩn BC và X A 
 Nếu thuật toán chi tiết cho kết quả thì qua bước 3 
 Ngược lại kết thúc thuật toán 
Bước 3: nhận XA là một lược đồ con của các lược đồ kết quả Q1,...,Qk 
Bước 4: thực hiện phân rã Z’-A, F 
Thuật toán chi tiết 
Bước 1: nếu Z’ không chứa AB sao cho (Z’-AB) A. thì 
báo không phân rã được. 
Ngược lại qua bước 2 
Bước 2: đặt Y’ = Z’ 
Bước 3: nếu Y’chứa AB sao cho (Y’-AB) A. thì gán Y’ = Y’–B thực hiện lại bước 2 
Bước 4: bước 3 cho kết quả Y’ = XA với XA ở dạng chuẩn BC và X A.Trả về XA 
Nhận xét 
 + +
Ở mỗi bước 2 của thuật toán phân rã Q, F ta thu được 2 lược đồ Qi =Z’-A, Q1 = XA với 
 + + + 
Qi Q1 = (Z’-A) XA = X và X Q1 và Q1 là lược đồ ở dạng chuẩn BC. Thuật toán lại 
tiếp tục phân rã Qi theo đúng cách đã làm thuật toán phân rã bảo toàn thông tin và các 
lược đồ con Qi đạt dạng chuẩn BC. 
 61 
 + 
Thuật toán chi tiết tìm Ql đạt chuẩn BC sao cho Ql chứa nhiều thuộc tính nhất. Để tìm 
 + +
được Ql như vậy thuật toán chi tiết tìm hai thuộc tính AB Q sao cho (Q -AB) A. Nếu 
tìm thấy chứng tỏ Q chưa đạt chuẩn BC và thuật toán giảm B trong Q với hy vọng thu 
 +
được lược đồ con Ql đạt chuẩn BC và thỏa phụ thuộc hàm (Q -AB) A. Thuật toán chi 
tiết tiếp tục tìm và giảm cho tới khi thu được lược đồ con không có hai thuộc tính AB sao 
 +
cho (Q -AB) A Ql là lược đồ con đạt chuẩn BC cần tìm. 
c. Thực hành 
1. Cho Q(S,D,I,M) F={SI D;SD M}hãy phân rã Q thành các lược đồ con đạt chuẩn 
BC bảo toàn thông tin (Bằng thuật toán thông thường) 
Giải: 
Bước 1: tìm tất cả khóa của Q 
Bước 2: phụ thuộc hàm SD M Fcó SD không là siêu khóa. 
Chú ý: để tính được F1,F2,K1,K2 như hình trên, ta phải tính bao đóng của tất cả tập con 
của {SDM} và {SDI} F1,F2 rồi tìm tất cả khóa của Q1 và Q2. 
Q1 và Q2 đều đạt dạng chuẩn BC vì trong Qi chỉ có phụ thuộc hàm có vế trái là khóa. F1 
được tạo thành bằng cách lấy các phụ thuộc hàm của  Q1(F) có vế phải một thuộc tính. 
Tương tự cho F2 
Ví dụ 17: cho Q(CTHRSG), F={C T;HR C;HT R;CS G;HS R}hãy phân rã Q 
thành các lược đồ con đạt chuẩn BC bảo toàn thông tin. (giải như ví dụ trên) 
Tính chất: Theo thuật toán trên, khi phân rã Q thành Q1(XY)với X Y và Q2 thì tập khóa 
SQ 
của Q luôn luôn bằng với tập khóa SQ2 của Q2. 
2. Phân rã lược đồ ở ví dụ trên thành các lược đồ con ở dạng chuẩn BC bảo toàn thông tin 
(Theo thuật toán cải tiến) 
 62 
 Trong F có 4 phụ thuộc hàm C T,HR C,HT R,CS G làm Q không đạt dạng 
chuẩn 3 hay BC và phép phân rã trên đã chọn ngẫu nhiên phụ thuộc hàm C T để phân 
rã thành Q1 và tập thuộc tính của Q12 chính là tập thuộc tính của Q bỏ thuộc tính T. Tập 
phụ thuộc hàm F12 sẽ chứa các phụ thuộc hàm của F bỏ đi các phụ thuộc hàm có vế trái 
hay vế phải chứa thuộc tính T. Như vậy tùy theo cách chọn phụ thuộc hàm để phân rã 
thành Q1 mà số lượng phụ thuộc hàm mang xuống Q12 khác nhau và chất lượng phân rã 
cũng khác nhau. Kết quả của phép phân rã trên chính là Q1, Q2, Q3 của hình trên. Phép 
phân rã bảo toàn thông tin, và các lượcđồ con đạt chuẩn BC nhưng phép phân rã không 
bảo toàn phụ thuộc hàm vì G = F1 F2 F3 = {C T; HR C; CH R; HS RG} 
không tương đương với F (HT R G+ và CS G G+). Ta hãy xem phép phân rã sau 
sẽ cho kết quả tốt hơn. 
Phép phân rã cũng cho kết quả phép phân rã bảo toàn thông tin, các lược đồ con 
Q1,Q2,Q3,Q4 đạt 
chuẩn BC và phép phân rã không bảo toàn phụ thuộc hàm vì G = F1 F2 F3 
 +
 F4={CS G;HR C;CH R;C T;HS C} không tương đương với F(HT R G ). 
Phép phân rã này tốt hơn vì chỉ có một phụ thuộc hàm HT R không thuộc G+ trong khi 
phép phân rã trên có tới 2 phụ thuộc hàm HT R và CS G không thuộc G+. Sở dĩ phép 
phân rã thứ 2 tốt hơn vì ở bước chọn phụ thuộc hàm để phân rã thành Q1 phép phân rã đã 
chọn phụ thuộc hàm sao cho khi chiếu F xuống Q12 số phụ thuộc hàm mang xuống càng 
nhiều càng tốt. 
Ví dụ 19: cho Q(A,B,C,D,E,G), F={AE C;CG A;BD G;GA E} hãy phân rã Q 
thành các lược đồ con đạt chuẩn BC bảo toàn thông tin. 
Nếu Q được phân rã thành: 
 (Q1(BDG), Q2(A,B,C,D,E)) lược đồ cơ sở dữ liệu đạt chuẩn 3 
 (Q1(BDG), Q2(A,C,E), Q3(A,B,D,E)) lược đồ cơ sở dữ liệu đạt chuẩn BC 
Bổ đề: 
Nếu Q không ở dạng chuẩn BC thì có thuộc tính A,B thuộc Q+ sao cho (Q+-AB) A 
3. Cho quan hệ Q(B,O,S,Q,I,D) và tập phụ thuộc hàm F 
F = {S D, I B IS Q B O} 
 63 
Hãy phân rã Q thành các lược đồ con đạt dạng chuẩn BC và bảo toàn thông tin. (theo 
thuật toán 3) 
Giải 
***Đặt Z’= Q+= BOSQID 
Thực hiện thuật toán chi tiết 
Y’= BOSQID 
Chọn 2 thuộc tính . Tìm bao đóng của tập hợp thuộc tính còn lại. Nếu bao đóng chứa 1 
trong 2 thuộc tính chọn chẳng hạn A, nghĩa là ta đã tìm được 2 thuộc tính AB sao cho 
(Y’-AB) A 
Chọn BO:(SQID)+  B 
Giảm O trong Y’ ta được Y’= BSQID 
Chọn BS:(QID)+  B 
Giảm S trong Y’ ta được Y’= BQID 
Chọn BQ:(ID)+ B 
Giảm Q trong Y’ ta được Y’= BID 
Chọn BD: I+ B 
Giảm D trong Y’ ta được Y’= BI Q1=(BI)và F1={I B} 
Để tính F1 ta phải tính bao đóng của tất cả tập con của {BI} F1 
***Giảm B trong Z’ ta được Z’= OSQID 
Đặt Y’=OSQID 
Chọn OD: (SQI)+ D; 
Giảm O trong Y’ ta được Y’= SQID 
chọn QD: (SI)+ D; 
giảm Q trong Y’ ta được Y’= SID 
chọn ID: S+ D; 
giảm I trong Y’ ta được Y’= SD Q2=(SD) và F2={S D} 
Để tính F2 ta phải tính bao đóng của tất cả tập con của {SD} F2 
*** Giảm D trong Z’ ta được Z’= OSQI 
Đặt Y’=OSQI 
chọn OQ: (SI)+ D; 
giảm O trong Y’ ta được Y’= SQI Q3=(SQI) và F3={SI Q} 
Ở bước trên không chọn AB để bao đóng tập hợp thuộc tính còn lại chứa A hay B 
Để tính F3 ta phải tính bao đóng của tất cả tập con của {SQI} F3 
*** Giảm Q trong Z’ ta được Z’= OSI 
Đặt Y’=OSI 
Chọn OS: I+=IBO O 
giảm S trong Y’ ta được Y’= OI Q4=(OI) và F4={I O} 
*** Giảm O trong Z’ ta được Z’= SI Q5=(SI) và F5={PTHHN} 
Ta có thể hiểu Q3(SQI)là tổ hợp của 2 lược đồ con Q5(SI) và Q3(SQI) 
Vậy kết quả phân rã là: 
1:Q1(BI) F1={I B} 
2:Q2(SD) F2={S D} 
3:Q3(SQI) F3={SI Q} 
 64 
4:Q4(OI) F4={I O} 
Chú ý 
+ Nên tránh phân rã nếu lược đồ đã ở dạng chuẩn mong muốn. 
+ Nên xem xét tổ hợp các lược đồ quan hệ con thành lược đồ lớn hơn nếu lược đồ lớn 
hơn vẫn đạt dạng chuẩn mong muốn. 
+ Một kết quả phân rã bảo toàn phụ thuộc hàm sẽ có giá trị hơn kết quả phân rã không 
bảo toàn phụ thuộc hàm. Giữa hai kết quả phân rã đều không bảo toàn phụ thuộc hàm thì 
kết quả phân rã thỏa nhiều phụ thuộc hàm trong F sẽ có giá trị hơn . 
+ Không có thuật toán phân rã lược đồ Q thành các lược đồ con ở dạng chuẩn BC vừa 
bảo toàn thông tin vừa bảo toàn phụ thuộc hàm. 
+ Vẫn có lược đồ Q được phân rã thành các lược đồ con ở dạng chuẩn BC vừa bảo toàn 
thông tin vưa bảo toàn phụ thuộc hàm. 
Ví dụ 20: cho lược đồ Q(CSZ)có F={CS Z,Z C}. Q không thể phân rã thành các lược 
đồ con ở dạng chuẩn BC vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm. Thật vậy: 
 TN={S} TG={CZ} 
Tất cả khóa của Q là: 
Vậy Q đạt dạng chuẩn 3 nhưng không ở dạng chuẩn BC vì có Z C có vế trái không là 
siêu khóa. Nhưng nếu ta phân rã Q thành các lược đồ con có ít hơn 3 thuộc tính thì phụ 
thuộc CS Z không suy ra được từ các phụ thuộc hình chiếu. 
6.3.2 Thiết kế CSDL bằng cách phân rã theo các thuật toán mới 
a. Khái niệm 
 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. Trình tự phân rã 
Thuật Toán phân rã Q, F thành dạng chuẩn 3, bảo toàn thông tin, bảo toàn phụ thuộc 
hàm 
Dữ liệu vào: lược đồ quan hệ Q và tập phụ thuộc hàm F. 
Dữ liệu ra: một phân rã sao cho mỗi lược đồ quan hệ con đều đạt chuẩn 3 vừa bảo toàn 
thông tin vừa bảo toàn phụ thuộc hàm. 
Tìm phủ tối thiểu Ftt của F 
Nếu có một phụ thuộc hàm nào của Ftt mà liên quan đến tất cả các thuộc tính của Q thì 
kết quả phân rã chính là Q ( Q không thể phân rã) 
Nếu có những thuộc tính của Q không nằm trong một phụ thuộc nào của Ftt - dù ở vế phải 
hay vế trái của F thì chúng tạo thành một lược đồ cần tìm. 
Cứ mỗi phụ thuộc hàm X A Ftt thì XA là một lược đồ cần tìm 
Nếu có một lược đồ con chứa khóa K của Q thì kết thúc thuật toán 
Ngược lại tạo một lược đồ con K 
 65 
c. Thực hành 
1. Cho lược đồ Q(CTHRSG), F={C T,HR C,TH R,CS G,HS R}. Hãy phân rã Q 
thành các lược đồ con đạt 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. 
Gỉai: 
+ F=Ftt={C T,HR C,TH R,CS G,HS R} là phủ tối thiểu. 
+ Áp dụng thuật toán trên Q được phân rã thành các lược đồ con Q1(CT), Q2(HRC), 
Q3(THR), Q4(CSG), Q5(HSR) 
+ Khóa của Q 
+ Q5 chứa khóa của Q nên Q1, Q2, Q3, Q4, Q5 là kết quả của phân rã. 
2. Cho Q(ABCDEGH), F={AB D; EH G; G C; D C} hãy phân rã Q thành các 
lược đồ con ở dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc. 
Giải: 
Tìm phủ tối thiểu Ftt của F 
 Ftt = F={AB D; EH G; G C; D C} 
Áp dụng thuật toán, Q được phân rã thành lược đồ CSDLsau: 
 Q1{ABD), Q2(EHG), Q3(GC), Q4(DC) 
Tìm khóa của Q 
TN={ABEH} TG={GD} 
Q1,Q2,Q3,Q4 không chứa khóa để bảo toàn thông tin ta cần có Q5(A,B,E,H). Vậy kết 
quả của phân rã là Q1,Q2,Q3,Q4,Q5 
 66 
 BÀI TẬP CHƯƠNG 6 
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); F={AB C, C B, ABD E, G A} 
e) Q(ABCDEGHI); F={AC B,BI ACD,ABC D,H I,ACE BCG,CG AE} 
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 
 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ã KeHoachthà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; E C; 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 
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. 
 67 
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 
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} 
b) Q(MSCD,MSSV,CD,HG) 
F= {MSCD CD; 
 CD MSCD; 
 CD,MSSV HG; 
 MSCD,HG MSSV; 
 CD,HG MSSV; 
 MSCD,MSSV HG} 
c) Q(A,B,C,D) F={ AB C; C B} 
 ----oOo---
 68 
 TÀI LIỆU THAM KHẢO 
5.1. J. Date, An Introduction to database systems, 7th edition, Addion Wesley 
Longman Inn., 2000 
5.2. Raghu Ramakrishnan & Johannes Gehrke, Database Management Systems, 2nd 
edition.