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

 TRƯỜNG CAO ĐẲNG NGHỀ ĐẮK LẮK 
KHOA ĐIỆN TỬ TIN HỌC 
---------------oOo--------------- 
GIÁO TRÌNH 
CƠ SỞ DỮ LIỆU 
NGHỀ: Công nghệ thông tin 
TRÌNH ĐỘ: Cao đẳng nghề, Trung cấp nghề 
 Người biên soạn: NGUYỄN THỊ THÙY LINH 
Lưu hành nội bộ - 2014 
LỜI MỞ ĐẦU 
Cơ sở dữ liệu là một lĩnh vực phát triển mạnh của công nghệ thông tin. Cùng với 
sự phát triển công nghệ thông tin ở nước ta, việc sử dụng các kiến thức về cơ sở dữ liệu 
vào thực tiễn ngày càng trở lên cần thiết. 
Để đáp ứng nhu cầu học tập của sinh viên chuyên ngành Công nghệ Thông tin, 
giáo trình Cơ sở dữ liệu được biên soạn theo chương trình khung của Trường Cao đẳng 
Nghề Đắk Lắk, cung cấp các kiến thức cơ bản về lý thuyết cơ sở dữ liệu. 
 Trong giáo trình này chúng tôi cung cấp cho sinh viên những kiến thức cơ bản 
nhất về cơ sở dữ liệu. Mục tiêu chính là với kiến thức cơ bản này sinh viên có thể ứng 
dụng các kiến thức về cơ sở dữ liệu vào thực tiễn và tiếp tục nghiên cứu học tập được các 
môn tin học khác. 
 Trong quá trình biên soạn sẽ không tránh khỏi những thiếu sót, rất mong được sự 
đóng góp ý kiến của đồng nghiệp để giáo trình ngày càng hoàn thiện hơn. 
MỤC LỤC 
CHƯƠNG 1. MÔ HÌNH QUAN HỆ ................................................................................. 1 
1.1. Nguyên nhân ra đời của mô hình quan hệ ............................................................... 1 
1.2. Hệ quản trị cơ sở dữ liệu ......................................................................................... 1 
1.2.1 CSDL là gì ........................................................................................................ 1 
1.2.2 Hệ quản trị CSDL ............................................................................................. 2 
1.2.3 Người dùng (User) ............................................................................................ 2 
1.3. Mô hình quan hệ ..................................................................................................... 3 
1.3.1 Mô hình quan hệ là gì? ..................................................................................... 3 
1.3.2 Các khái niệm cơ bản của mô hình quan hệ ...................................................... 3 
1.3.3 Các phép toán tập hợp ...................................................................................... 4 
1.3.4 Các phép toán quan hệ ...................................................................................... 5 
1.4. Mô hình thực thể kết hợp ........................................................................................ 7 
1.4.1 Giới thiệu mô hình thực thể kết hợp ER ........................................................... 7 
1.4.2 Giới thiệu một số ví dụ về mô hình thực thể kết hợp ER. ................................. 9 
1.4.3 Chuyển từ mô hình thực thể kết hợp sang lược đồ cơ sở dữ liệu .................... 10 
BÀI TẬP THỰC HÀNH CHƯƠNG 1............................................................................. 11 
CHƯƠNG 2 . NGÔN NGỮ TRUY VẤN SQL ............................................................... 14 
2.1 Cách tạo quan hệ bằng Access ............................................................................... 14 
2.1.1. Giới thiệu MS Access .................................................................................... 14 
2.1.2 Tạo CSDL bằng MS Access ........................................................................... 14 
2.2 Câu lệnh truy vấn .............................................................................................. 15 
2.2.1. Biểu thức (Expression) ............................................................................... 15 
2.2.2 Câu lệnh SQL ................................................................................................. 17 
BÀI TẬP CHƯƠNG 2 ..................................................................................................... 22 
CHƯƠNG 3. RÀNG BUỘC TOÀN VẸN QUAN HỆ .................................................... 25 
3.1. Ràng buộc toàn vẹn-Các yếu tố của ràng buộc toàn vẹn ....................................... 25 
3.1.1. Ràng buộc toàn vẹn ....................................................................................... 25 
3.1.2. Các yếu tố của ràng buộc toàn vẹn ................................................................ 25 
3.2. Phân loại ràng buộc toàn vẹn ................................................................................ 26 
3.2.1 Ràng buộc toàn vẹn liên bộ ........................................................................... 26 
3.2.2 Ràng buộc toàn vẹn về phụ thuộc tồn tại ....................................................... 26 
3.2.3 Ràng buộc toàn vẹn về miền giá trị ................................................................ 27 
3.2.4 Ràng buộc toàn vẹn liên thuộc tính ................................................................ 27 
3.2.5 Ràng buộc toàn vẹn liên thuộc tính liên quan hệ ............................................ 27 
BÀI TẬP CHƯƠNG 3 ..................................................................................................... 29 
CHƯƠNG 4: PHỤ THUỘC HÀM .................................................................................. 31 
4.1 Khái niệm phụ thuộc hàm .......................................................................... 31 
4.1.1. Định nghĩa phụ thuộc hàm ......................................................................... 31 
4.1.2. Phụ thuộc hàm hiển nhiên .......................................................................... 32 
4.1.3. Thuật toán Satifies ..................................................................................... 32 
4.1.4 Các phụ thuộc hàm có thể có ..................................................................... 33 
4.2. Hệ luật dẫn Armstrong (Armstrong inference rule).................................... 35 
4.2.1 Phụ thuộc hàm được suy diễn logic từ F ........................................................ 35 
4.2.2 Hệ luật dẫn Armstrong .................................................................................. 35 
BÀI TẬP CHƯƠNG 4 ..................................................................................................... 40 
CHƯƠNG 5: PHỦ CỦA TẬP PHỤ THUỘC HÀM ........................................................ 41 
5.1 Định nghĩa ......................................................................................................... 41 
5.2 Phủ tối thiểu của một tập phụ thuộc hàm ........................................................... 41 
5.2.1 Phụ thuộc hàm có vế trái dư thừa ................................................................... 41 
5.2.2 Phụ thuộc hàm có vế phải một thuộc tính ....................................................... 42 
5.2.3 Tập phụ thuộc hàm không dư thừa ................................................................. 42 
5.2.4 Tập phụ thuộc hàm tối thiểu ........................................................................... 42 
5.3 Khóa của lược đồ quan hệ ................................................................................. 44 
5.4 Thuật toán cải tiến tìm khóa của LĐQH ............................................................ 45 
BÀI TẬP CHƯƠNG 5 ..................................................................................................... 47 
CHƯƠNG 6: CHUẨN HÓA CƠ SỞ DỮ LIỆU .............................................................. 49 
6.1. Dạng chuẩn của lược đồ quan hệ .......................................................................... 49 
6.1.1. Dạng chuẩn một ........................................................................................ 49 
6.1.2. Dạng chuẩn hai ......................................................................................... 49 
6.1.3. Dạng chuẩn ba ........................................................................................... 50 
6.1.4. Dạng chuẩn Boyce – Codd (Boyce-Codd Normal Form) .......................... 52 
6.1.5. Dạng chuẩn của một lược đồ quan hệ ....................................................... 53 
6.2. Phép tách kết nối bảo toàn ........................................................................ 53 
6.2.1. Phép tách kết nối bảo toàn thông tin (lossless-join decomposition) .......... 53 
6.2.2 Phép tách bảo toàn phụ thuộc hàm (decompositions that preserve 
dependencies) .......................................................................................................... 56 
6.3 Thiết kế CSDL bằng cách phân rã ..................................................................... 60 
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 ............. 60 
6.3.2 Thiết kế CSDL bằng cách phân rã theo các thuật toán mới ............................ 65 
BÀI TẬP CHƯƠNG 6 ..................................................................................................... 67 
 VỊ TRÍ, TÍNH CHẤT CỦA MÔN HỌC: 
 Cơ sở dữ liệu là môn học cơ sở nghề bắt buộc của chương trình đào tạo Cao đẳng 
nghề Công nghệ thông tin (ứng dụng phần mềm). Môn học này được học sau môn Tin 
học. 
MỤC TIÊU CỦA MÔN HỌC: 
 Hiểu được nguyên lý thiết kế cơ sở dữ liệu quan hệ; 
 Hiểu về các mô hình dữ liệu và các công cụ mô tả dữ liệu; 
 Hiểu về các khái niệm, tính năng và các phương thức xử lý dữ liệu của hệ quản trị cơ 
sở dữ liệu SQL; 
 Biết cách xây dựng các ràng buộc, các phụ thuộc hàm, cách chuẩn hóa các cơ sở dữ 
liệu quan hệ; 
 Thiết kế được một số cơ sở dữ liệu quan hệ thông dụng: quản lý nhân sự, quản lý bán 
hàng,...; 
 Nghiêm túc, tỉ mỉ, sáng tạo trong quá trình tiếp thu kiến thức và vận dụng vào việc 
xây dựng các cơ sở dữ liệu cụ thể. Chủ động, tích cực tìm hiểu các tài liệu và nguồn bài 
tập liên quan. 
NỘI DUNG MÔN HỌC: 
1. Nội dung tổng quát và phân bổ thời gian: 
Số 
TT 
Tên chương, mục 
Thời gian 
Tổng số Lý 
thuyết 
Thực 
hành, 
Bài tập 
Kiểm tra* 
(LT hoặc 
TH) 
I. Mô hình quan hệ 10 3 7 0 
 Nguyên nhân ra đời của mô 
hình quan hệ 
0.5 0.5 0 0 
 Hệ quản trị cơ sở dữ liệu 0.5 0.5 0 0 
 Mô hình quan hệ 4 1 3 0 
 Mô hình thực thể kết hợp 5 1 4 0 
II. Ngôn ngữ truy vấn SQL 17 4 11 2 
 Cách tạo quan hệ bằng Access 2 1 1 0 
 Câu lệnh truy vấn 13 3 10 0 
 Kiểm tra 2 0 0 2 
III. Ràng buộc toàn vẹn quan hệ 7 2 5 0 
 Ràng buộc toàn vẹn-Các yếu 
tố của ràng buộc toàn vẹn 
0.5 0.5 0 0 
 Phân loại ràng buộc toàn vẹn 6.5 1.5 5 0 
IV. Phụ thuộc hàm 6 2 4 0 
 Khái niệm phụ thuộc hàm 5 1 4 0 
 Hệ luật dẫn Armstrong 1 1 0 0 
V. Phủ của tập phụ thuộc hàm 8 3 5 0 
 Định nghĩa 0.5 0.5 0 0 
 Phủ tối thiểu của một tập phụ 
thuộc hàm 
1.5 1.5 0 0 
 Khóa của lược đồ quan hệ 6 1 5 0 
VI. Chuẩn hóa Cơ sở dữ liệu 12 4 6 2 
 Các dạng chuẩn của lược đồ 
quan hệ 
6 2 4 0 
 Phép tách kết nối bảo toàn 2 1 1 0 
 Thiết kế cơ sở dữ liệu bằng 
cách phân rã 
2 1 1 0 
 Kiểm tra 2 0 0 2 
 Tổng cộng 60 18 38 4 
ĐIỀU KIỆN THỰC HIỆN 
 Vật liệu: Giáo trình, tài liệu về Cơ sở dữ liệu, một số cơ sở dữ liệu thực tiễn; 
 Dụng cụ và trang thiết bị: Phòng học, máy tính, máy chiếu,....
 1 
CHƯƠNG 1. MÔ HÌNH QUAN HỆ 
MỤC TIÊU CỦA BÀI: 
Sau khi học xong bài này người học có khả năng: 
- Trình bày được các khái niệm về cơ sở dữ liệu, hệ quản trị cơ sở dữ liệu và mô 
hình quan hệ; 
- Trình bày được cách chuyển đổi từ lược đồ CSDL sang mô hình quan hệ dữ liệu; 
- Áp dụng các phép toán đại số quan hệ (các phép toán tập hợp) để biểu diễn trên 
lược đồ quan hệ; 
- Chuyển đổi được từ lược đồ CSDL sang mô hình quan hệ dữ liệu 
- Nghiêm túc, tỉ mỉ trong việc học và làm bài tập. 
NỘI DUNG BÀI HỌC 
1.1. Nguyên nhân ra đời của mô hình quan hệ 
Trong nhiều năm, công nghệ tính toán và thông tin phát triển từ những hệ thống 
lớn, đắt tiền, độc quyền đến các hệ thống mở mạnh và không đắt tiền. Sự pháttriển này 
mang lại lợi ích to lớn cho người dùng cuối bởi sự phát triển của các gói ứng dụng số như 
xử lý văn bản, bảng tính điện tử, văn phòng xuất bản, hệ quản lý cơ sở dữ liệu, máy tính 
trợ giúp công nghệ phần mềm.... 
Trước khi máy tính hóa cơ sở dữ liệu đươc giới thiệu, dữ liệu được lưu trữ theo 
kiểu điện tử thành nhiều tập tin riêng biệt sử dụng hệ tập tin (từ đây về sau ta gọi hệ tập 
tin theo lối cũ). Những tập tin này được xử lý bằng các ngôn ngữ thế hệ thứ ba như 
COBOL, FORTRAN, PASCALvà ngay cả BASICđể tạo ra các giải pháp cho các vấn đề 
của doanh nghiệp. Mỗi ứng dụng, chẳng hạn như hệ tính lương, hệ kho hay hệ thống kế 
toán sẽ có một tập các tập tin riêng chứa dữ liệu riêng. Các ứng dụng như vậy tạo ra ba 
vấn đề sau: 
- Có sự liên kết chặt chẽ giữa cấu trúc luận lý và cấu trúc vật lý của các tập tin và 
chương trình ứng dụng khai thác chúng. Điều này khiến việc tạo nên các ứng dụng này 
rất khó khăn, tốn nhiều thời gian và do vậy mà tốn kém trong bảo trì hệ thống. 
- Có sự dư thừa dữ liệu rất lớn qua việc trùng lắp các tập tin trong các ứng dụng 
khác nhau. Điều này tạo ra những vấn đề như: dữ liệu thiếu nhất quán, không gian đĩa bị 
lãng phí, thời gian bảo trì và lưu phòng hờ các tập tin gia tăng, vấn đề về quản trị như 
không chú trọng 
bảo mật và tổ chức dữ liệu thiếu thống nhất. 
- Người sử dụng có ít khả năng khai thác trực tiếp dữ liệu 
1.2. Hệ quản trị cơ sở dữ liệu 
Khởi đầu, sự giới thiệu CSDL và HQTCSDL nhằm giải quyết các vấn đề của hệ 
thông tin dựa trên các tập tin theo lối cũ (C1.I). Điều này tạo raviệc phát triển trên hai 
mươi lăm năm qua một hệ CSDL quan hệ thương mại xuất hiện cuối những năm thập 
niên 70 và các năm đầu của thập niên 80. Trước khi xem xét CSDL và hệ QTCSDLQH 
giải quyếtmột vài vấn đề của hệ thông tin theo lối cũ như thế nào chúng ta cần làm rõ vài 
khái niệm. 
1.2.1 CSDL là gì 
Một cơ sở dữ liệu có thể định nghĩa tạm như sau: một chỗ chứa có tổ chức tập hợp 
các tập tin dữ liệu có tương quan, các mẫu tin và các cột. 
Ngày nay CSDL tồn tại trong mỗi ứng dụng thông dụng, ví dụ: 
 2 
- Hệ kho và kiểm kê. 
- Hệ đặt chỗ máy bay 
- Hệ nguồn nhân lực. 
- hệ dịch vụ công cộng như cấp nước, điện, khí đốt 
- Điều khiển quá trình chế tạo và sản xuất 
1.2.2 Hệ quản trị CSDL 
Một hệ quản trị CSDL (HQTCSDL) là: 
- một tập các phần mềm quản lý CSDL và cung cấp các dịchvụ xử lý CSDL cho 
các những người phát triển ứng dụng và người dùng cuối. 
- HQTCSDL cung cấp một giao diện giữa người sử dụng và dữ liệu. 
- HQTCSDL biến đổi CSDL vật lý thành CSDL logic. 
Hình 1.1 
Dựa vào cách tổ chức dữ liệu, HQTCSDL được chia thành năm loại: 
- loại phân cấp như hệ IMS của IBM 
- loại mạng như IDMS của Cullinet Software 
- Loại tập tin đảo như ADABAS của Software AG 
- Loại quan hệ như như ORACLE của Oracle, DB2 của IBM, ACCESS của Ms 
Access 
- Loại đối tượng là một tiếp cận khá mới trong thiết kế HQTCSDL và việc sử 
dụng loại này sớm trở nên phổ biến 
Hiện tại, loại HQTCSDL chính được sử dụng trong công nghệ là loại HQTCSDL 
quan hệ (RDBMS). Loại này đã chiếm lĩnh trong công nghệ trên 10-15 năm cuối cùng 
khi đánh bật loại 
HQTCSDL phân cấp và gần đây là HQTCSDL mạng. 
1.2.3 Người dùng (User) 
Người dùng khai thác CSDL thông qua HQTCSDL có thể phân thành ba loại: 
người quản trị CSDL, người phát triển ứng dụng và lập trình, người dùng cuối. 
- Người quản trị CSDL, hàng ngày, chịu trách nhi ...  phụ thuộc hàm không? 
Vào: Q(C,S,Z), F={CS Z,Z C},Q1(S,Z) và Q2(C,Z) 
 Đương nhiên Z C G =  Q1(F) Q2(F) Z C  Q1(F) Q2(F))+ 
1. Z’=CS 
2. gán 
Bước 1 và 2 có Z’không thay đổi, ta sang lược đồ Q2và tính tiếp Z’ 
3. 
Z’không thay đổi và hết lược đồ quan hệ ?ngưng không tính tiếp Z’ 
4. Vậy phép phân rã không bảo toàn phụ 
thuộc 
hàm. 
bt2. Cho 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 
 61 
 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. 
 62 
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) 
 63 
 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} 
 64 
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} 
 65 
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 
 66 
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 
 67 
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. 
 68 
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---
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.