Giáo trình Cơ sở dữ liệu (Mới nhất)

 có vế phải một thuộc tính. 
Ví dụ: 
 F = {A → BC,B → C,AB → D} ta suy ra 
 F ≡ {A → B, A → C ,B → C,AB → D} = G 
5.2.3. Tập phụ thuộc hàm không dư thừa: 
 84 
 Nói rằng F là tập phụ thuộc hàm không dư thừa nếu không tồn tại F’⊂ F 
sao cho F’≡ F. Ngược lại F là tập phụ thuộc hàm dư thừa. 
 Thuật toán loại khỏi F các phụ thuộc hàm dư thừa: 
 Bước 1: - Lần lược xét các phụ thuộc hàm X → Y của F 
 Bước 2: - Nếu X → Y là thành viên của F - {X → Y} thì loại X → Y 
khỏi F. 
 Bước 3: - lặp lại bước 2 cho các phụ thuộc hàm tiếp theo của F. 
5.3. Thuật toán tìm phủ tối thiểu 
 Từ điều kiện xác định phủ tối thiểu, ta có thuật toán tìm phủ tối thiểu như 
sau: 
 Thuật toán: 
 Bước 1: - Loại khỏi F các phụ thuộc hàm có vế trái dư thừa. 
 Bước 2: - Tách các phụ thuộc hàm có vế phải trên một thuộc tính 
thành các phụ thuộc hàm có vế phải một thuộc tính. 
 Bước 3: - Loại khỏi F các phụ thuộc hàm dư thừa. 
Chú ý: Theo thuật toán trên, có thể tìm được nhiều hơn một phủ tối thiểu Ftt để 
F≡Ftt và nếu thứ tự loại các phụ thuộc hàm khác nhau sẽ thu được các phủ tối 
thiểu khác nhau. 
Ví dụ: cho R(MSCD,MSSV,CD,HG) và tập phụ thuộc hàm F: 
 F = {MSCD → CD; CD → MSCD; CD,MSSV → HG; MSCD,HG → 
MSSV; CD,HG → MSSV; MSCD,MSSV → HG} 
 Hãy tìm một Ftt của F? 
 Kết quả ta có được một phủ tối thiểu sau: 
 Ftt = {MSCD → CD; CD → MSCD; CD,HG → MSSV; MSCD,MSSV 
→ HG} 
6. Dạng chuẩn của lược đồ quan hệ 
6.1. Một số khái niệm liên quan đến các dạng chuẩn 
 Thuộc tính khóa/thuộc tính không khóa: A là thuộc tính khóa nếu A có 
tham gia vào bất kỳ một khóa nào của quan hệ. Ngược lại A gọi là thuộc tính 
không khóa. 
 85 
 Thuộc tính phụ thuộc đầy đủ/ Phụ thuộc hàm đầy đủ: A là một thuộc tính 
phụ thuộc đầy đủ vào tập thuộc tính X nếu X → A là một phụ thuộc hàm đầy đủ 
(tức là không tồn tại X'  X sao cho X → A F+) 
 Chú ý rằng một phụ thuộc hàm mà vế trái chỉ có một thuộc tính là phụ 
thuộc hàm đầy đủ. 
6.2. Dạng chuẩn 1 (First Normal Form) 
 Định nghĩa: Lược đồ quan hệ R đạt dạng chuẩn 1 (1NF) nếu và chỉ nếu 
toàn bộ các thuộc tính của mọi bộ trên R đều mang giá trị đơn. 
Ví dụ: 
 Xét quan hệ KETQUA sau: 
 MASV HOVATEN KHOA TENMONHOC DIEMTHI 
 Cơ sở dữ liệu 6 
01234 Nguyễn Văn An CNTT Toán rời rạc 8 
 Lập trình web 7 
02345 Lê Văn Thịnh CNTT Cơ sở dữ liệu 7 
 Quan hệ này không đạt chuẩn 1NF vì các thuộc tính TENMONHOC, 
DIEMTHI của bộ thứ nhất không mang giá trị đơn. Ta có thể đưa quan hệ trên 
về quan hệ KETQUA1 đạt chuẩn 1 như sau: 
 MASV HOVATEN KHOA TENMONHOC DIEMTHI 
01234 Nguyễn Văn An CNTT Cơ sở dữ liệu 6 
01234 Nguyễn Văn An CNTT Toán rời rạc 8 
01234 Nguyễn Văn An CNTT Lập trình web 7 
02345 Lê Văn Thịnh CNTT Cơ sở dữ liệu 7 
 Chú ý rằng khi xét các dạng chuẩn, nếu không xét gì thêm thì mặc định 
quan hệ đang xét ít nhất đạt dạnh chuẩn 1. 
6.3. Dạng chuẩn 2 (Second Normal Form) 
 86 
 Định nghĩa: Một lược đồ quan hệ R ở dạng chuẩn 2 (2NF) nếu R đạt 
dạng chuẩn 1 và mọi thuộc tính không khóa của R đều phụ thuộc đầy đủ vào 
khóa. 
Hệ quả: 
 1. Nếu R đạt dạnh chuẩn 1 và tập thuộc tính không khóa của R bằng rỗng 
thì R đạt chuẩn 2. 
 2. Nếu tất cả các khóa quan hệ chỉ gồm một thuộc tính thì quan hệ đó ít 
nhất đạt chuẩn 2. 
Thuật toán kiểm tra dạng chuẩn 2: 
 Vào: lược đồ quan hệ R, tập phụ thuộc hàm F 
 Ra: Khẳng định R đạt hoặc không đạt chuẩn 2. 
 Bước 1: Tìm tất cả các khóa của R. 
 Bước 2: Với mỗi khóa K, tìm bao đóng của tất cả tập con thực sự của K. 
 Bước 3: Nếu có bao đóng S+ chứa thuộc tính không khóa thì R không đạt 
chuẩn 2. Ngược lại thì đạt chuẩn 2. 
Ví dụ: 
 Cho lược đồ quan hệ R(ABCD) và tập phụ thuộc hàm 
 F={AB→C; B→D; BC→A}. Hỏi R có đạt chuẩn 2 hay không? 
Giải: 
 - Tìm tất cả các khóa của R: 
 TN = {B}, TG = {AC} 
 + 
 Xi TN  Xi (TN  Xi) Siêu khóa Khóa 
  B BD - - 
 A BA BACD BA BA 
 C BC BCAD BC BC 
 AC BAC BACD BAC - 
 Tất cả các khóa của R là K1 = {BA}, K2 = {BC}. Gọi Z là tập thuộc tính 
khóa, X là tập thuộc tính không khóa, ta có: 
 Z = K1  K2 = {BAC} 
 87 
 X = R+ \ Z = {ABCD} \ {BAC} = {D} 
Ta thấy B⊂K1, B→D, mà D là thuộc tính không khóa. Vì thuộc tính không khóa 
D không phụ thuộc đầy đủ vào khóa nên R không đạt chuẩn 2. 
6.4. Dạng chuẩn 3 (Third Normal Form) 
 Định nghĩa: Một lược đồ quan hệ R đạt chuẩn 3 (3NF) nếu mọi phụ 
thuộc hàm X→A ∈ F+ với A ∉ X đều có. 
 - Hoặc X là siêu khóa. 
 - Hoặc A là thuộc tính khóa 
Hệ quả: 
 1. Nếu R đạt chuẩn 3 thì R đạt chuẩn 2. 
 2. Nếu R không có thuộc tính không khóa thì R đạt chuẩn 3. 
Định lý: 
 R là một lược đồ quan hệ. 
 F là tập các phụ thuộc hàm có vế phải một thuộc tính. 
 R đạt chuẩn 3 nếu và chỉ nếu mọi phụ thuộc hàm X→A ∈ F+ với A ∉ X 
đều có. 
 - Hoặc X là siêu khóa. 
 - Hoặc A là thuộc tính khóa 
 (Việc chứng minh định lý xem như là một bài tập nâng cao) 
Thuật toán kiểm tra dạng chuẩn 3: 
 Vào: lược đồ quan hệ R, tập phụ thuộc hàm F. 
 Ra: Khẳng định R đạt hoặc không đạt chuẩn 3. 
 Bước 1: Tìm tất cả các khóa của R. 
 Bước 2: Từ F tạo tập phụ thuộc hàm tương đương Ftt có vế phải một thuộc 
tính. 
 Bước 3: Nếu mọi phụ thuộc hàm X→A ∈ Ftt với A ∉ X đều có X là siêu 
khóa hoặc A là thuộc tính khóa thì R đạt chuẩn 3. Ngược lại R không đạt chuẩn 
3. 
Ví dụ: Cho lược đồ quan hệ R(ABCD), F = {AB→C; D→B; C→ABD}. Hỏi R 
có đạt chuẩn 3 hay không? 
 88 
Giải: 
 - Tìm tất cả các khóa của R: 
 TN={∅} TG={ABCD} 
 + 
 Xi TN  Xi (TN  Xi) Siêu khóa Khóa 
    - - 
 A A A - - 
 B B B - - 
 C C CABD C C 
 D D DB - - 
 AB AB ABCD AB AB 
 AC AC ACBD AC - 
 AD AD ADBC AD AD 
 BC BC BCAD BC - 
 BD BD BD - - 
 CD CD CDAB CD - 
 ABC ABC ABCD ABC - 
 ABD ABD ABDC ABD - 
 ACD ACD ACDB ACD - 
 BCD BCD BCDA BCD - 
 ABCD ABCD ABCD ABCD - 
 Tất cả các khóa của R là K1 = {C}, K2 = {AB}, K3 = {AD}. Gọi Z là tập 
thuộc tính khóa, X là tập thuộc tính không khóa, ta có: 
 Z = K1  K2  K3 = {CABD} 
 X = R+ \ Z = {ABCD} \ { CABD } = { } 
 Vì tập thuộc tính không khóa X = { } nên R đạt chuẩn 3 (theo hệ quả 2). 
6.5. Dạng chuẩn BC (Boyce Codd Normal Form) 
 Định nghĩa: Một lược đồ quan hệ R đạt 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. 
 89 
Hệ quả: 
 1. Nếu R đạt chuẩn BC thì R đạt chuẩn 3 (hiển nhiên do định nghĩa). 
 2. Mỗi lược đồ có hai thuộc tính đều đạt chẩn BC (xét phụ thuộc hàm có 
 thể có của R). 
Định lý: 
 R là lược đồ quan hệ. 
 F là tập phụ thuộc hàm có vế phải một thuộc tính. 
 R đạt chuẩn BC nếu và chỉ nếu mọi phụ thuộc hàm X→A ∈ F+ với A∉X 
đều có X là siêu khóa. 
 (Việc chứng minh định lý xem như là một bài tập nâng cao). 
Thuật toán kiểm tra dạng chuẩn BC: 
 Vào: lược đồ quan hệ R, tập phụ thuộc hàm F. 
 Ra: Khẳng định R đạt hoặc không đạt chuẩn BC. 
 Bước 1: Tìm tất cả các khóa của R. 
 Bước 2: Từ F tạo tập phụ thuộc hàm tương đương Ftt có vế phải một thuộc 
tính. 
 Bước 3: Nếu mọi phụ thuộc hàm X→A ∈ Ftt với A ∉ X đều có X là siêu 
khóa thì R đạt chuẩn BC. Ngược lại R không đạt chuẩn BC. 
Ví dụ: 
 Cho lược đồ quan hệ R(ABCDEI), F = {ACD→EBI; CE→AD}. Hỏi R có 
đạt chuẩn BC hay không? 
Giải: 
 - Tìm tất cả các khóa của R: 
 TN={C} TG={ADE} 
 + 
 Xi TN  Xi (TN  Xi) Siêu khóa Khóa 
  C C - - 
 A CA CA - - 
 D CD CD - - 
 E CE CEADBI CE CE 
 90 
 AD CAD CADEBI CAD CAD 
 AE CAE CAEDBI CAE - 
 DE CDE CDEABI CDE - 
 ADE CADE CADEBI CADE - 
 Tất cả các khóa của R là K1 = {CE}, K2 = {CAD}. Gọi Z là tập thuộc 
tính khóa, X là tập thuộc tính không khóa, ta có: 
 Z = K1  K2 = {CEAD} 
 X = R+ \ Z = { ABCDEI } \ { CEAD } = {BI} 
 - Tìm Ftt có vế phải một thuộc tính 
 Ftt = { ACD→E; ACD→B; ACD→I; CE→A; CE→D } 
 Ta nhận thấy mọi phụ thuộc hàm trong Ftt đều có vế trái là một siêu khóa 
nên R đạt chuẩn BC. 
Thuật toán kiểm tra dạng chuẩn của một lược đồ quan hệ. 
 Vào : lược đồ quan hệ R, tập phụ thuộc hàm F. 
 Ra : khẳng định R đạt chuẩn gì? 
 Bước 1: Tìm tất cả các khóa của R. 
 Bước 2: Kiểm tra chuẩn BC, nếu đúng R đạt chuẩn BC, kết thúc thuật 
toán. Ngược lại qua bước 3. 
 Bước 3: Kiểm tra chuẩn 3, nếu đúng R đạt chuẩn 3, kết thúc thuật toán, 
ngược lại qua bước 4. 
 Bước 4: Kiểm tra dạng chuẩn 2, nếu đúng R đạt chuẩn 2, kết thúc thuật 
toán, ngược lại R đạt chuẩn 1. 
Định nghĩa: Dạng chuẩn của một lược đồ cơ sở dữ liệu 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. 
 91 
Bài tập và sản phẩm thực hành bài 5.1 
I. Kiến thức: 
Câu 1: Phụ thuộc hàm: Định nghĩa? Cách xác định phụ thuộc hàm? Nêu tính 
chất của phụ thuộc hàm? 
Câu 2: Trình bày thuật toán tìm bao đóng của tập thuộc tính? 
Câu 3: Định nghĩa khóa của lược đồ quan hệ? Trình bày giải thuật tìm tất cả các 
khóa của lược đồ quan hệ? 
Câu 4: Nêu định nghĩa các dạng chuẩn của lược đồ quan hệ? Trình bày các giải 
thuật kiểm tra dạng chuẩn ? 
II. Kỹ năng: 
Bài 1: Cho lược đồ quan hệ R(B,C,D,E,F,G,I,J) và tập các phụ thuộc hàm 
 P = { I→B; DE→GJ; D→C; CF→J; B→I; C→G; F→J } 
 a. Tìm tất cả các khoá của lược đồ quan hệ R. 
 b. Tìm một phủ tối thiểu của tập phụ thuộc hàm P trên. 
Bài 2: Cho lược đồ quan hệ S(A,B,C,D,E,F,G) và tập các phụ thuộc hàm 
 P = {B→FG; F→CE; G→BD;B→A} 
 Chứng tỏ rằng phụ thuộc hàm AB→D được suy diễn từ P nhờ hệ luật dẫn 
Amstrong? (Nêu rõ là áp dụng luật gì) 
Câu 3: Cho lược đồ quan hệ Q(A,B,C,D,E) và tập các phụ thuộc hàm 
 F = {A→BC; C→DE} 
 - Lược đồ quan hệ Q đạt dạng chuẩn nào? 
 - Nếu chưa đạt dạng chuẩn 3 (3NF) hãy phân rã Q thành lược đồ quan hệ 
đạt tối thiểu dạng chuẩn 3 bảo toàn thông tin. 
Đánh giá kết quả học tập 
 Cách thức và Kết quả 
 Điểm 
 TT Tiêu chí đánh giá phương pháp thực 
 tối đa 
 đánh giá hiện của 
 92 
 người 
 học 
I Kiến thức 
1 Phụ thuộc hàm 2 
 Vấn đáp, đối 
1.1 Định nghĩa 
 chiếu với nội 
1.2 Cách xác định phụ thuộc hàm dung bài học 
1.3 Tính chất phụ thuộc hàm 
 Thuật toán tìm bao đóng của Vấn đáp, đối 
2 1 
 tập thuộc tính chiếu với nội 
3 Khóa của lược đồ 3 
 Vấn đáp, đối 
3.1 Định nghĩa về khóa chiếu với nội 
 dung bài học 
3.2 Giải thuật tìm tất cả các khóa 
4 Các dạng chuẩn 4 
 Vấn đáp, đối 
 chiếu với nội 
4.1 Định nghĩa các dạng chuẩn 
 dung bài học 
 Giải thuật kiểm tra các dạng 
4.2 
 chuẩn 
 Cộng: 10 đ 
II Kỹ năng 
1 + Phân tích được yêu cầu bài Làm bài tập đối 
 toán. chiếu với nội 
 10 
 + Xác định được các khóa dung bài học. 
 chính cho các quan hệ đã chỉ ra 
 93 
 trong lược đồ. 
 + Xác định được phủ tối thiểu. 
 + Xác định được dạng chuẩn 
 của lược đồ quan hệ. 
 + Chuẩn hóa bằng cách phân 
 rã (nâng cao) 
 Cộng: 10đ 
III Thái độ 
1 Tác phong công nghiệp Theo dõi việc 4 
1.1 Đi học đầy đủ, đúng giờ thực hiện, đối 1,5 
 chiếu với nội 
1.2 Không vi phạm nội quy lớp 
 quy của trường. 1,5 
 học 
1.3 Tính cẩn thận, tỉ mỉ Quan sát việc 
 1 
 thực hiện bài tập 
2 Đảm bảo thời gian thực hiện Theo dõi thời 
 bài tập gian thực hiện 
 bài tập, đối chiếu 2 
 với thời gian quy 
 định. 
3 Đảm bảo an toàn lao động và Theo dõi việc 
 4 
 vệ sinh công nghiệp thực hiện, đối 
3.1 Tuân thủ quy định về an toàn chiếu với quy 2 
 định về an toàn 
3.3 Vệ sinh phòng học đúng quy 
 và vệ sinh công 
 định 2 
 nghiệp 
 Cộng: 10 đ 
 94 
KẾT QỦA HỌC TẬP 
 Kết quả Kết qủa 
 Tiêu chí đánh giá Hệ số 
 thực hiện học tập 
 Kiến thức 0,3 
 Kỹ năng 0.4 
 Thái độ 0,3 
 Cộng: 
BÀI TẬP TỰ GIẢI: 
5.1. a) Cho lược đồ quan hệ Q(ABCD), r là một quan hệ trên Q. 
phụ thuộc hàm nào sau đây không thoả r 
a) D → A; b) AC → D; c) CD →A; d) D → B; 
b.Cho lược đồ quan hệ Q(ABCD), r là quan trên Q được cho như sau: 
Những phụ thuộc hàm nào sau đây thoả r ? 
 AB → D; C → B; B → C; BC → A; BD → A. 
 95 
 c.Cho lược đồ quan hệ Q(ABCD), r là quan hệ được cho như sau: 
 Những phụ thuộc hàm nào sau đây không thoả r ? 
A →B; A → C; B → A; C → D; D → C; D → A 
5.2. a.Cho lược đồ quan hệ Q(ABCD) và tập phụ thuộc hàm F = {A → B; 
BC→D}. 
Những phụ thuộc hàm nào sau đây thuộc F+ ? 
C → D; A → D; AD → C; AC → D; BC → A; B → CD. 
b.Cho lược đồ quan hệ Q(ABCDEGH) và tập phụ thuộc hàm 
F ={ AB → C; B →D; CD → E; CE → GH; G → A} 
Những phụ thuộc hàm nào sau đây không thuộc vào F+ ? 
AB → E; AB → GH; CGH → E; CB → E; GB → E. 
c)Cho lược đồ quan hệ Q,F như sau: với Q(ABCD) F={A → B; A → C}. 
Trong các phụ thuộc hàm sau, những phụ thuộc hàm được suy ra từ F ? 
A → D; C → D; AB → B; BC → A; A → BC 
5.3. Cho lược đồ quan hệ Q(ABCD) và tập phụ thuộc hàm 
 F={ A → D; D → A; AB→C} 
a.Tính AC+ 
b.Chứng minh BD →C 
5.4. a)Q(ABCDEG) Cho F={AB → C; C → A; BC → D; ACD → B; D → EG; 
BE → C ; CG → BD; CE → AG} 
X=[BD], X+=? 
 96 
Y=[CG], Y+=? 
b. Cho lược đồ quan hệ Q và tập phụ thuộc hàm F F={ AB → E; AG → I; BE → 
I; E → G ; GI → H }. Chứng minh rằng AB → GH. 
c. Tương tự cho tập phụ thuộc hàm 
F = { AB → C; B → D; CD → E; CE → GH; G → A} 
Chứng minh rằng AB → E; AB → G 
d. Q(ABCDEGH) 
F = {B →A; DA→CE; D → H; GH→ C; AC→D } Hãy tìm một khoá của Q ? 
5.5. Hãy tìm tất cả các khoá cho lược đồ quan hệ sau: 
Q(BROKER,OFFICE,STOCK,QUANTITY,INVESTOR,DIVIDENT) 
F={STOCK→DIVIDENT, INVESTOR → BROKER, INVESTOR, 
STOCK →QUANTITY, BROKER → OFFICE } 
5.6. Cho Q(A,B,C,D), F={AB → C; D → B; C → ABD} 
 Hãy tìm tất cả các khoá của Q 
5.7. Cho lược đồ quan hệ Q(MSCD,MSSV,CD,HG) và tập phụ thuộc F như sau: 
 F={MSCD→CD; CD→MSCD; CD,MSSV→HG; MSCD,HG→MSSV; 
CD,HG→MSSV; MSCD,MSSV→HG} 
 Hãy tìm phủ tối thiểu của F. 
5.8 Xác định phủ tối thiểu của tập phụ thuộc hàm sau: Q(ABCDEG) 
F = {AB → C; C → A; BC → D; ACD → B; D → EG; BE → C; CG → BD; 
CE → AG} 
5.9. Các nhận xét sau đúng (Đ) hay sai (S) ? (kẻ bảng sau và ghi Đ hoặc S cho 
mỗi câu trên) 
 97 
a.Cho Q và F={AB → C; A →B} thì Q đạt dạng chuẩn 1. 
b.Một lược đồ quan hệ Q luôn tìm được ít nhất một khoá. 
c.Nếu XY →Z thì X → Z và Y → Z. 
d.Các thuộc tính không tham gia vào vế phải của bất kỳ phụ thuộc hàm nào thì 
phải là thuộc tính tham gia vào khoá. 
e.Nếu X → Y và YZ → W thì XZ → W 
f.Nếu Q đạt dạng chuẩn một và khoá của Q chỉ có một thuộc tính thì Q đạt dạng 
chuẩn ba. 
g.Một tập phụ thuộc hàm F có thể có nhiều tập phủ tối thiểu. 
h.Nếu X → Y và U →V thì XU → YV. 
5.10 a.Cho Q(ABCD) và F = {AB →C; D →B; C →ABD}. 
Hãy kiểm tra xem AB → D có thuộc F+ hay không ? 
Hãy tìm tất cả các khoá của lược đồ quan hệ Q. Xác định dạng chuẩn của Q. 
b.Cho Q(A,B,C,D) và F={C →A; A →C; AD →B; BC →D; AB →D;CD→B } 
Hãy tìm phủ tối thiểu của F. 
5.11. 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] 
 98 
 TÀI LIỆU THAM KHẢO 
[1]. Lê Tiến Vương, Nhập môn cơ sở dữ liệu quan hệ, Nhà xuất bản Giáo dục, 
2000. 
[2]. Vũ Đức Thi, Cơ sở dữ liệu kiến thức và thực hành, Nhà xuất bản thống kê 
1997. 
[3]. Nguyễn An Tế, Giáo trình nhập môn cơ sở dữ liệu, ĐHKHTN- 
ĐHQGTPHCM 1996. 
[4]. Đỗ Trung Tuấn, Cơ sở dữ liệu, Nhà xuất bản giáo dục, 1998. 
 99 
PHỤ LỤC 
 100