1
TRƯ Ờ NG ĐẠ I HỌ C SƯ PHẠ M KỸ THUẬ T HƯ NG YÊN
KHOA CÔNG NGHỆ THÔNG TIN
ĐỀ CƯ Ơ NG BÀI GIẢ NG
HỌ C PHẦ N: CƠ SỞ DỮ LIỆ U
Trình độ đào tạ o
Hệ đào tạ o
:
:
Đạ i họ c
Chính quy
NĂM 2010
TRƯ Ờ NG ĐẠ I HỌ C SƯ PHẠ M KỸ THUẬ T HƯ NG YÊN
KHOA CÔNG NGHỆ THÔNG TIN
ĐỀ CƯ Ơ NG BÀI GIẢ NG
HỌ C PHẦ N: CƠ SỞ DỮ LIỆ U
Trình độ đào tạ o
Hệ đào tạ o
:
:
Đạ i họ c
Chính quy
NĂM 2012
2
MỤ C LỤ C
BÀI 1: CÁC KHÁI NIỆ M CƠ BẢ N VỀ HỆ CƠ SỞ DỮ LIỆ U ..............................9
1.1. Cơ sở dữ liệ u ....................................................................................................9
1.2. Hệ quả n trị cơ sở dữ liệ u.................................................................................10
1.2.1. Đị nh nghĩa hệ quả n trị cơ sở dữ liệ u ............................................................10
1.2.2.Các chứ c năng củ a mộ t hệ quả n trị cơ sở dữ liệ u ..........................................11
1.2.3.Các đặ c trư ng củ a giả i pháp cơ sở dữ liệ u.....................................................12
1.2.4.Ví dụ về mộ t cơ sở dữ liệ u............................................................................14
1.3.Mô hình cơ sở dữ liệ u......................................................................................16
1.3.1.Các loạ i mô hình cơ sở dữ liệ u......................................................................16
1.3.2.Lư ợ c đồ và trạ ng thái cơ sở dữ liệ u...............................................................17
1.4.Con ngư ờ i trong hệ cơ sở dữ liệ u.....................................................................18
1.4.1.Ngư ờ i quả n trị hệ cơ sở dữ liệ u (Database Administrator – DBA) ................18
1.4.2.Ngư ờ i thiế t kế cơ sở dữ liệ u (Database Designer) .........................................19
1.4.3.Nhữ ng ngư ờ i sử dụ ng (End User) .................................................................19
1.4.4.Ngư ờ i phân tích hệ thố ng và lậ p trình ứ ng dụ ng ...........................................19
1.4.5.Ngư ờ i thiế t kế và cài đặ t hệ quả n trị dữ liệ u..................................................19
1.4.6.Nhữ ng ngư ờ i phát triể n công cụ ....................................................................20
1.4.7.Các thao tác viên và nhữ ng ngư ờ i bả o trì......................................................20
1.5.Ngôn ngữ cơ sở dữ liệ u và giao diệ n................................................................20
1.5.1.Các ngôn ngữ hệ quả n trị cơ sở dữ liệ u.........................................................20
1.5.2.Các loạ i giao diệ n hệ quả n trị cơ sở dữ liệ u...................................................21
1.6.Câu hỏ i củ ng cố ...............................................................................................21
1. Đị nh nghĩa các thuậ t ngữ : cơ sở dữ liệ u, hệ quả n trị cơ sở dữ liệ u, hệ cơ sở dữ
liệ u, từ điể n cơ sở dữ liệ u, mô hình cơ sở dữ liệ u...................................................21
BÀI 2: MÔ HÌNH THỰ C THỂ- LIÊN KẾ T.........................................................22
2.1.Sử dụ ng mô hình quan niệ m bậ c cao cho việ c thiế t kế cơ sở dữ liệ u................22
2.2.Các thành phầ n cơ bả n củ a mô hình ER...........................................................24
2.2.1.Thự c thể và thuộ c tính ..................................................................................24
2.2.2.Kiể u thự c thể , tậ p thự c thể , khóa và tậ p giá trị ..............................................26
2.2.3.Kiể u liên kế t, tậ p liên kế t và các thể hiệ n......................................................28
2.2.4.Cấp liên kế t, tên vai trò và kiể u liên kế t đệ quy.............................................29
2.2.5.Các ràng buộ c trên các kiể u liên kế t..............................................................30
2.2.6.Thuộ c tính củ a các kiể u liên kế t....................................................................31
2.2.7.Các kiể u thự c thể yế u ...................................................................................31
2.3.Ví dụ về thiế t kế mô hình ER...........................................................................32
3
Xác đị nh các kiể u thự c thể , các thuộ c tính và các kiể u liên kế t..............................33
2.4.Tổ ng kế t mô hình thự c thể - liên kế t ................................................................ 35
2.4.1 Tóm tắ t.........................................................................................................35
2.4.2.Câu hỏ i luyệ n tậ p.......................................................................................... 36
a)Câu hỏ i lí thuyế t................................................................................................. 36
BÀI 3: BÀI TẬ P VÀ THẢ O LUẬ N VỀ THIẾ T KẾ CSDL E-R........................... 38
3.1. Tóm tắ t lý thuyế t ............................................................................................ 38
3.2. Bài tậ p áp dụ ng............................................................................................... 38
3.3. Thả o luậ n .......................................................................................................38
BÀI 4 : MÔ HÌNH QUAN HỆ- CHUYỂ N MÔ HÌNH E –R SANG MÔ HÌNH
QUAN HỆ . ........................................................................................................... 38
4.1.Các khái niệ m củ a mô hình quan hệ................................................................ 38
4.1.1.Miề n, thuộ c tính, bộ và quan hệ.................................................................... 38
4.1.2.Các đặ c trư ng củ a các quan hệ ...................................................................... 40
a)Thứ tự củ a các bộ trong mộ t quan hệ ..................................................................40
4.2.Các ràng buộ c quan hệ , lư ợ c đồ cơ sở dữ liệ u quan hệ .....................................42
4.2.1.Các ràng buộ c miề n......................................................................................42
4.2.2.Ràng buộ c khoá và ràng buộ c trên các giá trị không xác đị nh (null) .............42
4.2.3.Cơ sở dữ liệ u quan hệ và lư ợ c đồ cơ sở dữ liệ u quan hệ ................................ 44
4.2.4.Toàn vẹ n thự c thể , toàn vẹ n tham chiế u và khoá ngoạ i .................................46
4.3.Các phép toán trên mô hình quan hệ................................................................ 48
4.3.1.Các phép toán cậ p nhậ t................................................................................. 48
4.3.2. Các phép toán khác...................................................................................... 50
4.4.Chuyể n đổ i mô hình ER thành mô hình quan hệ..............................................50
4.4.1.Các quy tắ c chuyể n đổ i................................................................................. 51
4.4.2.Các nguyên tắ c thiế t kế lư ợ c đồ quan hệ ....................................................... 54
Các nguyên tắ c thiế t kế lư ợ c đồ quan hệ ................................................................54
Ngữ nghĩa củ a các thuộ c tính quan hệ ................................................................... 54
Thông tin dư thừ a trong các bộ và sự dị thư ờ ng cậ p nhậ t.......................................55
Các giá trị không xác đị nh trong các bộ ................................................................. 56
Sinh ra các bộ giả ..................................................................................................57
Chuyể n đổ i mô hình cụ thể ....................................................................................58
4.5.Tổ ng kế t và câu hỏ i ôn tậ p............................................................................... 58
4.5.1.Tổ ng kế t .......................................................................................................58
4.5.2. Các câu hỏ i ôn tậ p: ...................................................................................... 59
BÀI 5: BÀI TẬ P VÀ THẢ O LUẬ N VỀ THIẾ T KẾ CSDL QUAN HỆ................ 61
4
5.1. Nhắ c lạ i lý thuyế t ...........................................................................................61
5.2. Bài tậ p............................................................................................................61
5.3. Thả o luậ n .......................................................................................................61
BÀI 6: CÁC PHÉP TOÁN ĐẠ I SỐ QUAN HỆ ....................................................61
6.1.Các phép toán đạ i số quan hệ ...........................................................................62
6.1.1.Phép chọ n (SELECT) ...................................................................................62
6.1.2.Phép chiế u (PROJECT) ................................................................................64
6.1.3.Phép đặ t lạ i tên (RENAME) .........................................................................65
6.1.4.Các phép toán lý thuyế t tậ p hợ p....................................................................66
6.1.5.Phép nố i (JOIN)............................................................................................68
6.1.6.Tậ p hợ p đầ y đủ các phép toán quan hệ .........................................................70
6.1.7.Phép chia......................................................................................................70
BÀI 7: ĐẠ I SỐ QUAN HỆ (TIế P) – BÀI TẬ P Ứ NG DỤ NG ...............................71
7.1.Các phép toán quan hệ bổ sung........................................................................71
7.1.1.Các hàm nhóm và các phép nhóm.................................................................71
7.1.2.Các phép toán khép kín đệ quy .....................................................................72
7.2.Mộ t số ví dụ về truy vấ n trong đạ i số quan hệ ..................................................73
7.3. Bài tậ p............................................................................................................74
BÀI 8: TỐ I Ư U HÓA CÂU HỎ I TRUY VẤ N......................................................74
8.1 Mở đầ u ............................................................................................................74
8.2 Tổ ng quan về tố i ư u hóa câu hỏ i......................................................................74
8.3. Phư ơ ng pháp ư ớ c lư ợ ng cây đạ i số quan hệ ....................................................76
8.4 Nguyên tắ c tố i ư u hóa......................................................................................77
8.5.Kỹ thuậ t tố i ư u hoá các biể u thứ c đạ i số quan hệ . ............................................77
8.5.1. Biể u thứ c quan hệ........................................................................................77
8.5.2.Biế n đổ i biể u thứ c quan hệ ...........................................................................78
8.5.3.Các quy tắ c tư ơ ng đư ơ ng..............................................................................78
8.5.4 Mộ t số nhậ n xét khi thự c hiệ n tố i ư u hóa câu hỏ i..........................................81
8.6. Ví dụ tố i ư u hóa các câu hỏ i ...........................................................................82
BAI 9: THẢ O LUẬ N BÀI TẬ P VỀ TỐ I Ư U HÓA CÂU HỎ I TRUY VẤ N ........85
9.1. Tóm tắ t về lý thuyế t........................................................................................85
9.2. Bài tậ p............................................................................................................85
BÀI 10: PHỤ THUỘ C HÀM ................................................................................88
5
10.1. Khái niệ m.....................................................................................................88
10.2. Mộ t số tính chấ t củ a phụ thuộ c hàm..............................................................89
10.3. Đị nh nghĩa suy dẫ n theo quan hệ..................................................................91
10.4. Hệ tiên đề Amstrong (Armstrong’s Axioms) ................................................ 92
10.5. Đị nh nghĩa suy dẫ n theo hệ tiên đề Amstrong...............................................92
10.6. Bao đóng củ a tậ p thuộ c tính (closures of attribute sets) ................................ 93
10.6.1Thuậ t toán tìm bao đóng củ a mộ t tậ p thuộ c tính ..........................................95
10.6.2. Thuậ t toán cơ bả n tìm F+............................................................................ 99
BÀI 11: PHỦ CỦ A TẬ P PHỤ THUỘ C HÀM .................................................... 101
11.1. Đị nh nghĩa tư ơ ng đư ơ ng............................................................................. 101
11.2. Các tậ p phụ thuộ c hàm tư ơ ng đư ơ ng .......................................................... 102
11.3. Phụ thuộ c hàm không dư thừ a .................................................................... 103
11.3.1. Phụ thuộ c hàm dư thừ a ............................................................................ 103
11.3.2. Phủ không dư .......................................................................................... 103
11.4 Phủ thu gọ n ................................................................................................. 104
11.4.1. Phụ thuộ c hàm có vế trái dư thừ a:............................................................ 104
11.4.2. Tậ p phụ thuộ c hàm có vế phả i mộ t thuộ c tính:......................................... 105
11.4.3. Tậ p phụ thuộ c hàm không dư thừ a (phủ không dư ):................................. 105
11.4.4. Tậ p phụ thuộ c hàm tố i thiể u: ................................................................... 106
BÀI 12: BÀI TẬ P VỀ PHỤ THUỘ C HÀM VÀ CÁC VẤ N ĐỀ LIÊN QUAN ... 106
12.1. Nhắ c lạ i lý thuyế t. ...................................................................................... 106
12.2. Bài tậ p. .......................................................................................................106
12.3. Thả o luậ n.................................................................................................... 106
BÀI 13: KHÓA CỦ A LƯ Ợ C ĐỒ QUAN HỆ..................................................... 106
13.1. Siêu khóa và khóa....................................................................................... 106
13.2. Họ Sperner và khóa .................................................................................... 108
13.3. Mộ t số vấ n đề về khóa................................................................................ 109
13.3.1. Kiể m tra mộ t tậ p cho trư ớ c có phả i là khoá hay không?........................... 109
13.3.2.Tìm mộ t khoá củ a lư ợ c đồ quan hệ ........................................................... 109
13.3.3. Giao củ a tấ t cả các khoá .......................................................................... 110
13.3.4. Thuậ t toán kiể m tra mộ t lư ợ c đồ đã cho có mộ t hay nhiề u khoá............... 113
13.3.5. Thuậ t toán tìm tấ t cả các khoá củ a lư ợ c đồ quan hệ ................................. 113
BÀI 14: THẢ O LUẬ N BÀI TẬ P VỀ KHÓA CỦ A LƯ Ợ C ĐỒ QUAN HỆ ........115
14.1. Tóm tắ t về lý thuyế t.................................................................................... 115
