Cơ sở dữ liệu phân tán (Dùng cho sinh viên hệ đào tạo Đại Học từ xa)
MỤC LỤC
LỜI NÓI ĐẦU . 1
CHƯƠNG 1: KHÁI NIỆM CƠBẢN VỀCƠSỞDỮLIỆU PHÂN TÁN. 3
1.1 MỞ ĐẦU . 3
1.2 XỬLÝ PHÂN TÁN VÀ HỆTHỐNG XỬLÝ PHÂN TÁN. 3
1.2.1 Khái niệm xửlý phân tán . 3
1.2.2 Hệthống phân tán. 4
1.3 HỆCƠSỞDỮLIỆU PHÂN TÁN LÀ GÌ. 4
1.4 SỰCẦN THIẾT CỦA HỆCƠSỞDỮLIỆU PHÂN TÁN. 5
1.4.1 Sựphát triển của các cơcấu tổchức . 5
1.4.2 Giảm chi phí truyền thông. 6
1.4.3 Hiệu quảcông việc . 6
1.4.4 Độtin cậy và tính sẵn sàng. 6
1.5 CÁC ĐẶC ĐIỂM CỦA CƠSỞDỮLIỆU PHÂN TÁN . 6
1.5.1 Điểu khiển tập trung . 6
1.5.2 Độc lập dữliệu . 7
1.5.3 Giảm dưthừa dữliệu. 7
1.5.4 Độtin cậy qua các giao dịch phân tán . 8
1.5.5 Cải tiến hiệu năng. 8
1.5.6 Dễdàng mởrộng hệthống . 9
1.6 CÁC MÔ HÌNH CƠSỞDỮLIỆU CLIENT/SERVER. 9
1.6.1 Mô hình cơsởdữliệu tập trung: . 9
1.6.2 Mô hình cơsởdữliệu theo kiểu File Server: . 9
1.6.3 Mô hình xửlý từng phần cơsởdữliệu . 10
1.6.4 Mô hình cơsởdữliệu Client/Server . 10
1.6.5 Distributed database model (Mô hình cơsởdữliệu phân tán). 11
1.7 MÔ HÌNH THAM CHIẾU CƠSỞDỮLIỆU PHÂN TÁN . 11
1.7.1 Lược đồtoàn cục . 11
1.7.2 Lược đồphân mảnh. 12
1.7.3 Lược đồcấp phát. 12
1.7.4 Lược đồánh xạcục bộ. 13
1.7.5 DBMS ởcác site cục bộdộc lập . 14
1.8 CẤU TRÚC LOGIC CỦA CƠSỞDỮLIỆU PHÂN TÁN. 14
1.9 LỢI ÍCH PHÂN TÁN DỮLIỆU TRÊN MẠNG. 14
1.10 HỆQUẢN TRỊCƠSỞDỮLIỆU QUAN HỆ. 15
1.10.1 Kiến trúc tổng quát. 15
150
1.10.2 Chức năng của hệquản trịcơsởdữliệu quan hệ. 16
1.11 TỔNG QUAN VỀHỆQUẢN TRỊCƠSỞDỮLIỆU PHÂN TÁN. 17
1.11.1 Mở đầu. 17
1.11.2 Hệquản trịCSDL phân tán thuần nhất. 19
1.11.3 Hệquản trịCSDL phân tán không thuần nhất. 19
1.12 MÔ HÌNH KIẾN TRÚC HỆQUẢN TRỊCSDL PHÂN TÁN. 20
1.12.1 Tính tựvận hành. 21
1.12.2 Tính phân tán dữliệu. 22
1.12.3 Tính hỗn hợp. 22
1.12.4 Các kiểu kiến trúc . 22
1.13 KIẾN TRÚC HỆQUẢN TRỊCSDL PHÂN TÁN. 24
1.13.1 Các hệClient/Server . 24
1.13.2 Các hệphân tán ngang hàng( Peer to Peer) . 25
1.14 KIẾN TRÚC TỔNG QUAN CỦA MỘT HỆQUẢN TRỊPHỨC HỆCSDL PHÂN TÁN
(Multi Database Management System). 29
1.14.1 Mô hình kiến truc tổng quan của một phức hệ. 29
1.14.2 Phân loại các phức hệdựa vào cấu trúc. 30
1.14.3 Các mô hình không sửdụng lược đồkhái niệm toàn cục. 31
CÂU HỎI TRẮC NGHIỆM . 33
CHƯƠNG II: THIẾT KẾCÁC HỆCSDL PHÂN TÁN. 38
2.1 CÁC VẤN ĐỀVỀPHÂN MẢNH DỮLIỆU . 38
2.1.1 Lý do phân mảnh . 38
2.1.2 Các kiểu phân mảnh . 39
2.1.3 Mức độphân mảnh . 40
2.1.4 Các quy tắc phân mảnh. 40
2.1.5 Các kiểu cấp phát. 40
2.1.6 Các yêu cầu thông tin . 41
2.2 PHƯƠNG PHÁP PHÂN MẢNH NGANG . 41
2.2.1 Giới thiệu . 41
2.2.2 Thông tin cần thiết của phân mảnh ngang . 41
2.2.3 Phân mảnh ngang cơsở. 44
2.2.4 Tính đầy đủvà tính cực tiểu của vịtừ đơn giản . 45
2.2.5 Thuật toán xác định tập vịtừ đầy đủvà cực tiểu từtập Pr cho trước . 46
2.2.6 Thuật toán phân mảnh ngang nguyên thuỷ. 47
2.3 PHÂN MẢNH NGANG DẪN XUẤT. 48
2.4 PHÂN MẢNH DỌC . 51
2.4.1 Khái niệm phân mảnh dọc. 51
2.4.2 Thông tin cần thiết của phân mảnh dọc. 52
151
2.4.3 Thuật toán tụnhóm. 54
2.4.4 Thuật toán phân mảnh . 58
2.4.5 Kiểm tra tính đúng đắn . 59
2.5 PHƯƠNG PHÁP PHÂN MẢNH HỖN HỢP ( HYBRID FRAGMENTATION) . 60
2.6 CẤP PHÁT . 61
2.6.1 Bài toán cấp phát (AllocationProblem) . 61
2.6.2 Thông tin cần thiết cho bài toán cấp phát. 62
2.6.3 Mô hình cấp phát. 63
2.7 KIỂM SOÁT DỮLIỆU NGỮNGHĨA . 64
2.8 QUẢN LÝ KHUNG NHÌN . 64
2.8.1 Khung nhìn trong các hệquản trịcơsửdữliệu tập trung . 64
2.8.2 Cập nhật qua khung nhìn. 66
2.8.3 Khung nhìn trong các hệquản trịcơsởdữliệu phân tán . 67
2.9 AN TOÀN DỮLIỆU . 68
2.9.1 Kiểm soát cấp quyền tập trung . 68
2.9.2 Kiểm soát cấp quyền phân tán. 70
2.10 KIỂM SOÁT TÍNH TOÀN VẸN NGỮNGHĨA . 71
2.10.1 Kiểm soát toàn vẹn ngữnghĩa tập trung. 71
2.10.2 Kiểm soát toàn vẹn ngữnghĩa phân tán . 75
2.10.3 So sánh việc kiểm soát toàn vẹn ngữnghĩa tập trung và phân tán . 79
CÂU HỎI VÀ BÀI TẬP. 79
CHƯƠNG III: XỬLÝ TRUY VẤN TRONG CƠSỞDỮLIỆU QUAN HỆPHÂN TÁN
. 84
3.1 GIỚI THIỆU. 84
3.2 VẤN ĐỀXỬLÝ TRUY VẤN. 84
3.2.1 Đặt vấn đề. 84
3.2.2 Mục đích của việc xửlý truy vấn . 87
3.2.3 Độphức tạp của các thao tác đại sốquan hệ. 87
3.3 ĐẶC TRƯNG CỦA BỘXỬLÝ TRUY VẤN . 88
3.3.1 Ngôn ngữ(Languages) . 88
3.3.2 Các kiểu tối ưu hoá (Types of Optimization) . 89
3.3.3 Thời điểm tối ưu hoá (Optimization timing) . 89
3.3.4 Sốliệu thống kê (Statistics) . 90
3.3.5 Vịtrí quyết định (Decision sites) . 90
3.3.6 Khai thác cấu hình mạng (Exploitation of Network topology) . 90
3.3.7 Khai thác các mảnh nhân bản (Exploitation of Replicated Fragments) . 90
3.3.8 Sửdụng nửa kết nối (Use of Semijoint) . 91
3.4 CÁC TẦNG CỦA QUÁ TRÌNH XỬLÝ TRUY VẤN. 91
152
3.5 PHÂN RÃ TRUY VẤN. 92
3.3.1 Bước chuẩn hoá câu truy vấn . 93
3.3.2 Bước phân tích. 94
3.3.3 Bước loại bỏdưthừa . 96
3.3.3 Bước viết lại truy vấn . 96
3.6 CỤC BỘHÓA DỮLIỆU PHÂN TÁN . 100
3.6.1 Rút gọn cho phân mảnh ngang nguyên thuỷ. 101
3.6.2 Rút gọn cho phân mảnh dọc . 103
3.6.3 Rút gọn cho phân mảnh dẫn xuất . 104
3.6.4 Rút gọn cho phân mảnh hỗn hợp . 106
CÂU HỎI VÀ BÀI TẬP. 107
CHƯƠNG IV: XỬLÝ TRUY VẤN TRONG CƠSỞDỮLIỆU QUAN HỆPHÂN TÁN
. 111
4.1 GIỚI THIỆU . 111
4.2 VẤN ĐỀXỬLÝ TRUY VẤN. 111
4.2.1 Đặt vấn đề. 111
4.2.2 Mục đích của việc xửlý truy vấn . 114
4.2.3 Độphức tạp của các thao tác đại sốquan hệ. 115
4.3 ĐẶC TRƯNG CỦA BỘXỬLÝ TRUY VẤN . 115
4.3.1 Ngôn ngữ(Languages) . 115
4.3.2 Các kiểu tối ưu hoá (Types of Optimization) . 116
3.3.3 Thời điểm tối ưu hoá (Optimization timing) . 116
4.3.4 Sốliệu thống kê (Statistics) . 117
4.3.5 Vịtrí quyết định (Decision sites). 117
4.3.6 Khai thác cấu hình mạng (Exploitation of Network topology) . 117
4.3.7 Khai thác các mảnh nhân bản (Exploitation of Replicated Fragments). 117
4.3.8 Sửdụng nửa kết nối (Use of Semijoint) . 118
4.4 CÁC TẦNG CỦA QUÁ TRÌNH XỬLÝ TRUY VẤN . 118
4.5 PHÂN RÃ TRUY VẤN. 119
4.5.1 Bước chuẩn hoá câu truy vấn . 120
4.5.2 Bước phân tích. 121
4.5.3 Bước loại bỏdưthừa . 123
4.5.4 Bước viết lại truy vấn . 123
4.6 CỤC BỘHÓA DỮLIỆU PHÂN TÁN . 127
4.6.1 Rút gọn cho phân mảnh ngang nguyên thuỷ. 128
4.6.2 Rút gọn cho phân mảnh dọc . 130
4.6.3 Rút gọn cho phân mảnh dẫn xuất . 131
4.6.4 Rút gọn cho phân mảnh hỗn hợp. 133
153
CÂU HỎI VÀ BÀI TẬP. 134
CHƯƠNG V: TỔNG QUAN VỀCSDL SONG SONG . 138
5.1 MỞ ĐẦU . 138
5.2 CHỨC NĂNG HỆXỬLÝ SONG SONG . 138
5.2.1 Các khía cạnh chức năng . 138
5.2.2 Các ưu điểm CSDL song song . 138
5.2.3 Chức năng CSDL song song . 139
5.3 KIẾN TRÚC HỆSONG SONG . 139
5.3.1 Kiến trúc chia sẻbộnhớ(Shared- Memory) . 140
5.3.2 Kiến trúc chia sẻ đĩa (Shared-Disk). 140
5.3.3 Kiến trúc không chia sẻ. 141
5.3.4 Các kiến trúc phân cấp (Hierachical Architectures) . 141
5.3.5 Các kiến trúc NUMA . 141
5.4 CÁC KỸTHUẬT HỆQUẢN TRỊCSDL SONG SONG. 142
5.4.1 Sắp đặt dữliệu . 142
5.4.2 Phân vùng luân chuyển (Round Rrobin Partitioning) . 143
5.4.3 Phân vùng băm (Hash Partitioning): . 143
5.4.4 Phân vùng theo khoảng cách (Range Partitioning) . 143
5.4.5 Các giải pháp phân vùng . 143
5.5 TRUY VẤN SONG SONG . 145
5.5.1 Song hành nội toán tử. 145
5.5.2 Song hành liên toán tử. 145
5.5.3 Xửlý dữliệu song song. 145
CÂU HỎI TRẮC NGHIỆM . 146
MỤC LỤC . 149
.............................. 84 3.1 GIỚI THIỆU............................................................................................................................. 84 3.2 VẤN ĐỀ XỬ LÝ TRUY VẤN................................................................................................ 84 3.2.1 Đặt vấn đề........................................................................................................................ 84 3.2.2 Mục đích của việc xử lý truy vấn .................................................................................... 87 3.2.3 Độ phức tạp của các thao tác đại số quan hệ ................................................................... 87 3.3 ĐẶC TRƯNG CỦA BỘ XỬ LÝ TRUY VẤN ....................................................................... 88 3.3.1 Ngôn ngữ (Languages) .................................................................................................... 88 3.3.2 Các kiểu tối ưu hoá (Types of Optimization) .................................................................. 89 3.3.3 Thời điểm tối ưu hoá (Optimization timing) ................................................................... 89 3.3.4 Số liệu thống kê (Statistics) ............................................................................................. 90 3.3.5 Vị trí quyết định (Decision sites) ................................................................................................ 90 3.3.6 Khai thác cấu hình mạng (Exploitation of Network topology) ................................................... 90 3.3.7 Khai thác các mảnh nhân bản (Exploitation of Replicated Fragments) ...................................... 90 3.3.8 Sử dụng nửa kết nối (Use of Semijoint) ...................................................................................... 91 3.4 CÁC TẦNG CỦA QUÁ TRÌNH XỬ LÝ TRUY VẤN................................................................ 91 152 3.5 PHÂN RÃ TRUY VẤN............................................................................................................ 92 3.3.1 Bước chuẩn hoá câu truy vấn ........................................................................................... 93 3.3.2 Bước phân tích.................................................................................................................. 94 3.3.3 Bước loại bỏ dư thừa ........................................................................................................ 96 3.3.3 Bước viết lại truy vấn ....................................................................................................... 96 3.6 CỤC BỘ HÓA DỮ LIỆU PHÂN TÁN .................................................................................. 100 3.6.1 Rút gọn cho phân mảnh ngang nguyên thuỷ .................................................................. 101 3.6.2 Rút gọn cho phân mảnh dọc .......................................................................................... 103 3.6.3 Rút gọn cho phân mảnh dẫn xuất ................................................................................... 104 3.6.4 Rút gọn cho phân mảnh hỗn hợp.................................................................................... 106 CÂU HỎI VÀ BÀI TẬP................................................................................................................ 107 CHƯƠNG IV: XỬ LÝ TRUY VẤN TRONG CƠ SỞ DỮ LIỆU QUAN HỆ PHÂN TÁN ................................................................................................................................................ 111 4.1 GIỚI THIỆU ........................................................................................................................... 111 4.2 VẤN ĐỀ XỬ LÝ TRUY VẤN................................................................................................ 111 4.2.1 Đặt vấn đề ...................................................................................................................... 111 4.2.2 Mục đích của việc xử lý truy vấn .................................................................................. 114 4.2.3 Độ phức tạp của các thao tác đại số quan hệ ................................................................. 115 4.3 ĐẶC TRƯNG CỦA BỘ XỬ LÝ TRUY VẤN ..................................................................... 115 4.3.1 Ngôn ngữ (Languages) .................................................................................................. 115 4.3.2 Các kiểu tối ưu hoá (Types of Optimization) ................................................................ 116 3.3.3 Thời điểm tối ưu hoá (Optimization timing) ................................................................. 116 4.3.4 Số liệu thống kê (Statistics) ........................................................................................... 117 4.3.5 Vị trí quyết định (Decision sites).................................................................................... 117 4.3.6 Khai thác cấu hình mạng (Exploitation of Network topology) ...................................... 117 4.3.7 Khai thác các mảnh nhân bản (Exploitation of Replicated Fragments).......................... 117 4.3.8 Sử dụng nửa kết nối (Use of Semijoint) ......................................................................... 118 4.4 CÁC TẦNG CỦA QUÁ TRÌNH XỬ LÝ TRUY VẤN ........................................................ 118 4.5 PHÂN RÃ TRUY VẤN.......................................................................................................... 119 4.5.1 Bước chuẩn hoá câu truy vấn ......................................................................................... 120 4.5.2 Bước phân tích................................................................................................................ 121 4.5.3 Bước loại bỏ dư thừa ...................................................................................................... 123 4.5.4 Bước viết lại truy vấn ..................................................................................................... 123 4.6 CỤC BỘ HÓA DỮ LIỆU PHÂN TÁN ....................................................................................... 127 4.6.1 Rút gọn cho phân mảnh ngang nguyên thuỷ ............................................................................. 128 4.6.2 Rút gọn cho phân mảnh dọc ..................................................................................................... 130 4.6.3 Rút gọn cho phân mảnh dẫn xuất .............................................................................................. 131 4.6.4 Rút gọn cho phân mảnh hỗn hợp............................................................................................... 133 153 CÂU HỎI VÀ BÀI TẬP................................................................................................................ 134 CHƯƠNG V: TỔNG QUAN VỀ CSDL SONG SONG ................................................... 138 5.1 MỞ ĐẦU ................................................................................................................................ 138 5.2 CHỨC NĂNG HỆ XỬ LÝ SONG SONG ........................................................................... 138 5.2.1 Các khía cạnh chức năng................................................................................................ 138 5.2.2 Các ưu điểm CSDL song song ....................................................................................... 138 5.2.3 Chức năng CSDL song song ......................................................................................... 139 5.3 KIẾN TRÚC HỆ SONG SONG ............................................................................................. 139 5.3.1 Kiến trúc chia sẻ bộ nhớ (Shared- Memory) ................................................................. 140 5.3.2 Kiến trúc chia sẻ đĩa (Shared-Disk)............................................................................... 140 5.3.3 Kiến trúc không chia sẻ ................................................................................................. 141 5.3.4 Các kiến trúc phân cấp (Hierachical Architectures) ...................................................... 141 5.3.5 Các kiến trúc NUMA .................................................................................................... 141 5.4 CÁC KỸ THUẬT HỆ QUẢN TRỊ CSDL SONG SONG.................................................... 142 5.4.1 Sắp đặt dữ liệu............................................................................................................... 142 5.4.2 Phân vùng luân chuyển (Round Rrobin Partitioning) .................................................... 143 5.4.3 Phân vùng băm (Hash Partitioning): ............................................................................. 143 5.4.4 Phân vùng theo khoảng cách (Range Partitioning) ....................................................... 143 5.4.5 Các giải pháp phân vùng ............................................................................................... 143 5.5 TRUY VẤN SONG SONG ................................................................................................... 145 5.5.1 Song hành nội toán tử.................................................................................................... 145 5.5.2 Song hành liên toán tử ................................................................................................... 145 5.5.3 Xử lý dữ liệu song song................................................................................................. 145 CÂU HỎI TRẮC NGHIỆM .......................................................................................................... 146 MỤC LỤC ............................................................................................................................. 149
File đính kèm:
Cơ sở dữ liệu phân tán (Dùng cho sinh viên hệ đào tạo Đại Học từ xa).pdf
