Tập bài giảng Cơ sơ dữ liệu phân tán
MỤC LỤC
MỤC LỤC I
CÁC DANH MỤC HÌNH V
LỜI NÓI ĐẦU VII
CHƯƠNG 1 TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN 1
1.1. Các khái niệm cơ bản 1
1.1.1. Xử lý phân tán 2
1.1.2. Hệ thống phân tán 2
Có thể bạn quan tâm!
-
Cơ sơ dữ liệu phân tán - 2 -
Các Đặc Điểm Chính Của Cơ Sở Dữ Liệu Phân Tán -
Một Kiến Trúc Tham Chiếu Dùng Cho Các Csdl Phân Tán
Xem toàn bộ 312 trang tài liệu này.
1.1.3. Hệ cơ sở dữ liệu phân tán 2
1.2. Mục đích của việc sử dụng cơ sở dữ liệu phân tán 8
1.2.1. Sự phát triển của các cơ cấu tổ chức kinh tế 8
1.2.2. Sự kết nối lẫn nhau của CSDL hiện tại 9
1.2.3. Sự lớn mạnh gia tăng 9
1.2.4. Giảm chi phí truyền thông 9
1.2.5. Hiệu quả công việc 9
1.2.6. Độ tin cậy và tính sẵn sàng 10
1.3. Các đặc điểm chính của cơ sở dữ liệu phân tán 10
1.3.1. Điều khiển tập trung 10
1.3.2. Độc lập dữ liệu 11
1.3.3. Giảm dư thừa 12
1.3.4. Các cấu trúc vật lý phức tạp dùng để truy xuất hiệu quả 12
1.3.5. Tính toàn vẹn 16
1.3.6. Phục hồi 17
1.3.7. Điều khiển đồng thời 17
1.3.8. Tính riêng biệt (privacy) và tính bảo mật (security) 17
1.4. Mô hình kiến trúc tham chiếu CSDL phân tán 17
1.4.1. Lược đồ toàn cục 18
1.4.2. Lược đồ phân mảnh 18
1.4.3. Lược đồ định vị 19
1.4.4. Lược đồ ánh xạ cục bộ 20
1.4.5. Mục tiêu của kiến trúc tham chiếu CSDL phân tán 20
1.5. Cấu trúc logic của CSDL phân tán 22
1.6. Lợi ích phân tán dữ liệu trên mạng 22
1.7. Kiến trúc hệ quản trị CSDL phân tán 23
1.7.1. Các đặc tính của kiến trúc hệ quản trị CSDL phân tán 23
1.7.2. Các kiểu kiến trúc tham chiếu hệ quản trị CSDL phân tán 26
1.8. Hệ quản trị CSDL phân tán 33
1.8.1. Các thành phần của hệ quản trị CSDL phân tán 33
1.8.2. Các dịch vụ của hệ quản trị CSDL phân tán 36
1.8.3. Phương pháp truy xuất CSDL phân tán 37
1.8.4. Phân loại các hệ quản trị CSDL phân tán 38
Chương 2 CÁC MỨC TRONG SUỐT PHÂN TÁN 41
2.1. Các loại phân mảnh dữ liệu 41
2.1.1. Điều kiện đúng đắn để phân mảnh dữ liệu 42
2.1.2. Phân mảnh ngang 43
2.1.3. Phân mảnh dọc 52
2.1.4. Phân mảnh hỗn hợp 57
2.2. Tính trong suốt phân mảnh dùng cho các ứng dụng chỉ đọc 67
2.2.1. Các mức trong suốt phân tán 67
2.2.2. Chương trình cho các ứng dụng chỉ đọc 67
2.3. Tính trong suốt phân mảnh dùng cho các ứng dụng cập nhật 85
2.3.1. Cây cập nhật 85
2.3.2. Chương trình ứng dụng cho các ứng dụng cập nhật 89
2.4. Các thao tác cơ bản truy xuất CSDL phân tán 93
2.4.1. Truy xuất CSDL với mỗi giá trị 94
2.4.2. Truy xuất CSDL sau khi nhập vào tất cả các giá trị 96
2.4.3. Truy xuất CSDL trước khi nhập vào các giá trị 98
2.4.4. Truy xuất CSDL sử dụng biểu thức con chung 100
2.5. Ràng buộc trong CSDL phân tán 102
2.5.1. Ràng buộc toàn vẹn 102
2.5.2. Ràng buộc tham chiếu 103
2.5.3. Thiết kế các ràng buộc tham chiếu 104
CHƯƠNG 3 THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN 107
3.1. Vấn đề thiết kế cơ sở dữ liệu phân tán 108
3.1.1. Các bước thiết kế phân tán dữ liệu 108
3.1.2. Các mục tiêu của thiết kế phân tán dữ liệu 109
3.1.3. Chiến lược thiết kế phân tán dữ liệu 111
3.1.4. Các yêu cầu thông tin 115
3.2. Thiết kế phân mảnh cơ sở dữ liệu 116
3.3. Thiết kế phân mảnh ngang 117
3.3.1. Các yêu cầu thông tin của phân mảnh ngang 117
3.3.2. Thiết kế phân mảnh ngang chính 122
3.3.3. Thiết kế phân mảnh ngang dẫn xuất 134
3.3.4. Kiểm tra điều kiện đúng đắn khi phân mảnh ngang 139
3.4. Thiết kế phân mảnh dọc 140
3.4.1. Các chiến lược thiết kế phân mảnh dọc 140
3.4.2. Các yêu cầu thông tin của phân mảnh dọc 143
3.4.3. Giải thuật gom tụ 147
3.4.4. Giải thuật phân tách 153
3.4.5. Kiểm tra tính đúng đắn khi phân mảnh dọc 156
3.5. Thiết kế phân mảnh hỗn hợp 157
3.6. Thiết kế định vị cơ sở dữ liệu 157
3.6.1. Bài toán định vị 158
3.6.2. Các yêu cầu thông tin 160
3.6.3. Mô hình định vị 162
3.6.4. Các giải pháp 164
3.7. Kiểm soát dữ liệu ngữ nghĩa 165
3.7.1. Quản lý khung nhìn 165
3.7.2. An toàn dữ liệu 167
3.7.3. Kiểm soát tính toàn vẹn ngữ nghĩa 170
CHƯƠNG 4 BIẾN ĐỔI CÁC TRUY VẤN TOÀN CỤC THÀNH CÁC TRUY VẤN MẢNH 175
4.1. Các phép biến đổi tương đương dùng cho các truy vấn 176
4.1.1. Cây toán tử của một truy vấn 176
4.1.2. Các phép biến đổi tương đương dùng cho đại số quan hệ 177
4.1.3. Đồ thị toán tử và xác đinh biểu thức con chung 181
4.2. Biến đổi truy vấn toàn cục thành các truy vấn mảnh 184
4.2.1 Biểu thức chuẩn tắc của một truy vấn mảnh 184
4.2.2. Đại số quan hệ định tính 185
4.2.3. Đơn giản hóa các quan hệ được phân mảnh ngang 189
4.2.4. Đơn giản hóa các phép kết nối giữa các quan hệ được phân mảnh ngang chính 191
4.2.5. Đơn giản hóa cho phân mảnh ngang dẫn xuất 192
4.2.6. Đơn giản hóa các quan hệ được phân mảnh dọc 194
4.2.7. Sử dụng phép suy diễn cho các phép đơn giản hóa 196
4.2.8. Các chương trình nửa kết nối 197
4.3. Gom nhóm phân tán và định trị hàm kết hợp 198
4.3.1. Mở rộng đại số quan hệ 199
4.3.2. Các đặc tính của phép gom nhóm 199
4.4. Các truy vấn có tham số 202
4.4.1. Đơn giản hóa các truy vấn tham số và mở rộng đại số quan hệ 203
4.4.2. Sử dụng vùng nhớ tạm thời khi sử dụng nhiều lần các truy vấn tham số 205
CHƯƠNG 5 TỐI ƯU HÓA CÁC CHIẾN LƯỢC TRUY XUẤT 207
5.1. Một số cơ cấu cho tối ưu hóa truy vấn 207
5.1.1. Các vấn đề của tối ưu hóa truy vấn 207
5.1.2. Các mục tiêu của tối ưu hóa truy vấn 209
5.1.3. Một mô hình mới của các truy vấn 211
5.1.4. Tóm lược các giả sử dùng cho tối ưu hóa truy vấn phân tán 218
5.1.5. Tầm quan trọng của tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán 218
5.2. Các truy vấn kết nối 220
5.2.1. Sử dụng các chương trình nửa kết nối cho các truy vấn kết nối 220
5.2.2. Xác định các chương trình nửa kết nối trong SDD-1 224
5.2.3. Xác định các chương trình nửa kết nối bằng các giải thuật 228
5.2.4. Xử lý truy vấn bằng cách sử dụng các phép nối 231
5.3. Các truy vấn tổng quát 235
CÂU HỎI VÀ BÀI TẬP 239
PHỤ LỤC 277
TÀI LIỆU THAM KHẢO I
CÁC DANH MỤC HÌNH
Hình 1.1. Xử lý dữ liệu truyền thống 3
Hình 1.2. Xử lý cơ sở dữ liệu 3
Hình 1.3. Một cơ sở dữ liệu phân tán trên một mạng phân tán địa lý 4
Hình 1.4. Một cơ sở dữ liệu phân tán trên một mạng cục bộ 5
Hình 1.5. Một hệ thống đa xử lý (multiprossor system) 6
Hình 1.6. Sơ đồ lưu trữ phân tán 8
Hình 1.7. Một lược đồ CSDL Codasyl 13
Hình 1.8. Một chương trình tựa Codasyl-DBMS để tìm kiếm các mặt hàng được cung cấp bởi nhà cung cấp S113
Hình 1.9. Sự phân tán của tập SUPPLIER-PART 14
Hình 1.10. Ví dụ về kế hoạch truy xuất 15
Hình 1.11. Một kiến trúc tham chiếu dùng cho các CSDL phân tán 18
Hình 1.12. Các mảnh và các hình ảnh vật lý của một quan hệ toàn cục 19
Hình 1.13. Các mảnh và các hình ảnh vật lý của quan hệ dự án 20
Hình 1.14. Mô hình Client-Server nhiều lớp 22
Hình 1.15. Lựa chọn cài đặt hệ quản trị CSDL 23
Hình 1.16. Kiến trúc tham chiếu Client/Server 27
Hình 1.17. Kiến trúc tham chiếu CSDL phân tán 28
Hình 1.18. Sơ đồ chức năng của hệ quản trị CSDL phân tán tích hợp 29
Hình 1.19. Mô hình kiến trúc của một phức hệ 30
Hình 1.20. Kiến trúc phức hệ CSDL với một lược đồ khái niệm toàn cục 31
Hình 1.21. Kiến trúc phức hệ CSDL không sử dụng GCS 32
Hình 1.22. Các thành phần của một phức hệ CSDL 33
Hình 1.23. Hệ quản trị CSDL phân tán 34
Hình 1.24. Các thành phần của một hệ quản trị CSDL phân tán. 35
Hình 1.25. Các thành phần của DDBMS thương mại hóa 36
Hình 1.26. Truy xuất từ xa thông qua các thao tác cơ bản DBMS 37
Hình 1.27. Truy xuất từ xa thông qua các thao tác cơ bản DBMS 38
Hình 1.28. Kiến trúc mô hình hệ quản trị CSDL đồng nhất 39
Hình 1.29. Kiến trúc mô hình hệ quản trị CSDL không đồng nhất 39
Hình 2.1. Cây phân mảnh dẫn xuất 52
Hình 2.2. Cây phân mảnh dẫn xuất của hệ thống quản lý dự án 52
Hình 2.3. Truy xuất CSDL Quản lý dự án khi DDBMS với trong suốt phân mảnh 70
Hình 2.4. Truy xuất CSDL QL Kinh doanh khi DDBMS với trong suốt phân mảnh .71 Hình 2.5. Truy xuất CSDL QL Dự án khi DDBMS với trong suốt vị trí 74
Hình 2.6. Truy xuất CSDL QL kinh doanh khi DDBMS với trong suốt vị trí 76
Hình 2.7. Truy xuất CSDL QL Dự án khi DDBMS với trong suốt ánh xạ cục bộ 80
Hình 2.8. Truy xuất CSDL QL kinh doanh khi DDBMS với trong suốt ánh xạ cục bộ
......................................................................................................................................82
Hình 2.9. Một số ứng dụng trên một CSDL phân tán không đồng nhất không có trong suốt 85
Hình 2.10. Cây con cập nhật cho thuộc tính MAP trong cây phân mảnh của quan hệ NV 87
Hình 2.11. Cây con cập nhật khác cho thuộc tính MaP trong cây phân mảnh của quan hệ NV 88
Hình 3.1. Sơ đồ thiết kế tổng CSDL phân tán 108
Hình 3.2. Chiến lược thiết kế từ trên xuống 112
Hình 3.3. Sơ đồ thiết kế tổng CSDL phân tán 138
Hình 4.1. Đồ thị toán tử của chương trình nửa kết nối 197
Hình 5.1. Một chương trình rút gọn hoàn toàn cho quan hệ R 223
Hình 5.2. Hậu tối ưu hóa trong giải thuật SDD-1 227
Hình 5.3. kế hoạch cho quan hệ T 229
Hình 5.4. Giao hoán phép kết nối và phép hợp 236
Hình 5.5. Tối ưu hóa độc lập của một đồ thị kết nối phân tách 237
Hình 5.6. Các đồ thị tối ưu hoá khác nhau cho cùng một truy vấn 237
LỜI NÓI ĐẦU
Ngày nay, với sự phát triển nhanh chóng của công nghệ truyền thông và mạng Internet, cùng với xu thế toàn cầu hoá trong mọi lĩnh vực, dữ liệu không đơn giản chỉ được lưu trữ tập trung ở một nơi mà nó có thể được lưu trữ tại nhiều nơi. Do đó, cơ sở dữ liệu phân tán đã trở thành lĩnh vực nghiên cứu của ngành CNTT. Môn học Cơ sở dữ liệu phân tán là môn học không chỉ đề cập đến những vấn đề cơ sở lý thuyết mà còn cung cấp một số kỹ năng cần thiết để thiết kế và cài đặt các hệ cơ sở dữ liệu phân tán cụ thể. Để giúp sinh viên các ngành thuộc lĩnh vực Công nghệ thông tin trường Đại học Sư phạm Kỹ thuật Nam Định học tốt hơn môn học này và vận dụng để phân tích và thiết kế cơ sở dữ liệu phân tán thì việc xuất bản “Tập bài giảng Cơ sở dữ liệu phân tán” là rất cần thiết.
Tập bài giảng được chia làm 5 chương:
Chương 1. Tổng quan về Cơ sở dữ liệu phân tán Chương 2. Các mức trong suốt phân tán Chương 3. Thiết kế cơ sở dữ liệu phân tán
Chương 4. Biến đổi truy vấn toàn cục thành các truy vấn mảnh Chương 5. Tối ưu hóa các chiến lược truy xuất
Mỗi chương trong tập bài giảng đều hệ thống hóa các kiến thức cơ bản, cần thiết. Tương ứng với mỗi nội dung kiến thức đều có các ví dụ minh họa cụ thể, gán với các ứng dụng thực tiễn. Đặc biệt, cuối tập bài giảng, tác giả đưa ra các câu hỏi lý thuyết, các câu hỏi trắc nghiệm và một số bài tập để sinh viên vận dụng củng cố lại kiến thức và kỹ năng.
Với phần lý thuyết chi tiết, đầy đủ được trình bày một cách khoa học, logic và phần bài tập để củng cố kiến, chúng tôi hy vọng rằng tập bài giảng này sẽ mang lại cho bạn đọc nhiều điều bổ ích.
Trong quá trình biên soạn, tập bài giảng không tránh khỏi những sai sót, rất mong đồng nghiệp và các em sinh viên góp ý kiến để tập bài giảng ngày càng được hoàn thiện hơn. Mọi sự đóng góp ý kiến xin gửi về Văn phòng Khoa Công nghệ thông tin-Trường Đại học Sư phạm Kỹ thuật Nam Định-Phường Lộc Hạ-Tp Nam Định.
Nhóm biên soạn
Phạm Hùng Phú- Nguyễn Văn Thẩm
Tập bài giảng Cơ sở dữ liệu phân tán
Chương 1
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN
Với việc phân bố ngày càng rộng rãi của các công ty, xí nghiệp, dữ liệu bài toán là rất lớn và không tập trung được. Các cơ sở dữ liệu (CSDL) thuộc thế hệ một và hai không giải quyết được các bài toán trong môi trường mới không tập trung mà phân tán, song song với các dữ liệu và hệ thống không thuần nhất, thế hệ thứ ba của hệ quản trị CSDL ra đời vào những năm 80 trong đó có CSDL phân tán để đáp ứng những nhu cầu mới.
Ngày nay, CSDL phân tán đã trở thành một lĩnh vực quan trọng của xử lý thông tin và tầm quan trọng của nó ngày càng tăng nhanh. Có hai lý do về mặt công nghệ và về mặt tổ chức để đi theo hướng này:
- Các CSDL phân tán khắc phục nhiều thiếu sót của các CSDL tập trung (centralized database).
- Thích hợp một cách tự nhiên với các cấu trúc không tập trung (decentralized structure) của nhiều tổ chức (organization).
1.1. Các khái niệm cơ bản
Nguyên lý các hệ cơ sở dữ liệu phân tán được xây dựng dựa trên sự hợp nhất của hai hướng tiếp cận đối với quá trình xử lý dữ liệu, đó là lý thuyết các hệ cơ sở dữ liệu và công nghệ mạng máy tính.
Một trong những động lực thúc đẩy sự phát triển nhanh việc sử dụng các hệ CSDL là nhu cầu tích hợp các loại dữ liệu, cung cấp đa dạng các loại hình dịch vụ và các dịch vụ đa phương tiện cho người sử dụng. Mặt khác, kết nối máy tính thành mạng với mục tiêu chia sẻ tài nguyên, khai thác có hiệu quả các tài nguyên thông tin, nâng cao khả năng tích hợp và trao đổi các loại dữ liệu giữa các thành phần trên mạng.
Nhu cầu thu thập, lưu trữ xử lý và trao đổi thông tin ngày càng tăng, các hệ thống xử lý tập trung đã bộc lộ những nhược điểm sau:
- Tăng khả năng lưu trữ thông tin là khó khăn, bởi bị giới hạn tối đa của thiết bị nhớ.
- Độ sẵn sàng phục vụ của CSDL không cao khi số người sử dụng tăng.
- Khả năng tính toán của các máy tính đơn lẻ đang dần tới giới hạn vật lý.
- Mô hình tổ chức lưu trữ, xử lý dữ liệu tập trung không phù hợp cho những tổ chức kinh tế, xã hội có hoạt động rộng lớn, đa quốc gia.
Những nhược điểm này đã được khắc phục khá nhiều trong hệ thống phân tán. Những sản phẩm của các hệ thống phân tán đã xuất hiện nhiều trên thị trường và từng bước chứng minh tính ưu việt của nó hơn hẳn các hệ thống tập trung truyền thống. Các hệ thống phân tán sẽ thay thế dần các hệ thống tập trung.
1