Tập bài giảng Cơ sơ dữ liệu phân tán (Phần 1)
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
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
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.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.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.8. Hệ quản trị CSDL phân tán ....................................................................................33
i
Tập bài giảng Cơ sở dữ liệu phân tán
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
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.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.1. Cây cập nhật ....................................................................................................85
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.3. Truy xuất CSDL trƣớc khi nhập vào các giá trị..............................................98
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
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.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.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
ii
Tập bài giảng Cơ sở dữ liệu phân tán
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
MẢNH.........................................................................................................................175
4.1.1. Cây toán tử của một truy vấn ........................................................................176
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.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
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
iii
Tập bài giảng Cơ sở dữ liệu phân tán
5.2. Các truy vấn kết nối .............................................................................................220
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
iv
Tập bài giảng Cơ sở dữ liệu phân tán
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.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
cấp bởi nhà cung cấp S1. ..............................................................................................13
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.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.19. Mô hình kiến trúc của một phức hệ ...........................................................30
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 2.1. Cây phân mảnh dẫn xuất..............................................................................52
suốt ...............................................................................................................................85
v
Tập bài giảng Cơ sở dữ liệu phân tán
NV................................................................................................................................87
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.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
vi
Tập bài giảng Cơ sở dữ liệu phân tán
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
vii
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
Tập bài giảng Cơ sở dữ liệu phân tán
1.1.1. Xử lý phân tán
Thuật ngữ xử lý phân tán có thể là thuật ngữ đƣợc lạm dụng nhiều nhất trong khoa
học máy tính trong những năm vừa qua. Nó thƣờng đƣợc dùng để chỉ những hệ thống
gồm nhiều loại thiết bị khác nhau chẳng hạn nhƣ: hệ đa bộ vi xử lý, xử lý dữ liệu phân
tán, mạng máy tính
Có hai khái niệm xử lý phân tán liên quan với nhau.
- Khái niệm liên quan đến việc tính toán trên Client/Server. Trong đó ứng dụng
đƣợc chia ra thành hai phần, phần của Server và phần của Client và đƣợc vận hành ở
hai nơi. Trong tính toán phân tán này cho phép truy nhập trực tiếp dữ liệu và xử lý dữ
liệu trên Server và Client.
- Khái niệm thứ hai là việc thực hiện các tác vụ xử lý phức tạp trên nhiều hệ thống.
Không gian nhớ và bộ xử lý của nhiều máy cùng hoạt động chia nhau tác vụ xử lý.
Máy trung tâm sẽ giám sát và quản lý các tiến trình này. Có trƣờng hợp thông qua
Internet, hàng nghìn máy cùng xử lý một tác vụ.
Có thể định nghĩa hệ xử lý phân tán nhƣ sau: Hệ xử lý phân tán là một tập hợp các
phần tử xử lý tự trị (không nhất thiết đồng nhất) đƣợc kết nối với nhau bởi một mạng
máy tính và cùng phối hợp thực hiện những công việc gán cho chúng. Phần tử xử lý ở
đây để chỉ một thiết bị tính toán có khả năng thực hiện chƣơng trình trên nó.
1.1.2. Hệ thống phân tán
Hệ thống phân tán là tập hợp các máy tính độc lập kết nối với nhau thành một
mạng máy tính đƣợc cài đặt các hệ cơ sở dữ liệu và các phần mềm hệ thống phân tán
tạo khả năng cho nhiều ngƣời sử dụng truy nhập chia sẻ nguồn thông tin chung. Các
máy tính trong hệ thống phân tán có kết nối phần cứng lỏng lẻo, có nghĩa là không
chia sẻ bộ nhớ, chỉ có một hệ điều hành trong toàn bộ hệ thống phân tán
Các mạng máy tính đƣợc xây dựng dựa trên kỹ thuật Web. Ví dụ nhƣ mạng
Internet, mạng Intranet… là các mạng phân tán.
1.1.3. Hệ cơ sở dữ liệu phân tán
Công nghệ các hệ CSDL phát triển từ mô hình dữ liệu, trong đó mỗi ứng dụng định
nghĩa một hay nhiều tệp dữ liệu riêng của nó đƣợc mô tả nhƣ hình 1.1, sang mô hình
định nghĩa và quản lý dữ liệu tập trung. Điều đó dẫn đến khái niệm độc lập dữ liệu,
nghĩa là tính bất biến của các hệ ứng dụng đối với sự thay đổi cấu trúc lƣu trữ và các
chiến lƣợc truy nhập dữ liệu.
2
Tập bài giảng Cơ sở dữ liệu phân tán
Hình 1.1. Xử lý dữ liệu truyền thống
Trong ngữ cảnh hệ xử lý phân tán thì hệ cơ sở dữ liệu phân tán có thể đƣợc xem
nhƣ những công cụ làm cho quá trình xử lý dữ liệu phân tán dễ dàng hơn và hiệu quả
hơn. Khái niệm hệ CSDL phân tán bao gồm cả khái niệm CSDL phân tán và hệ quản
trị CSDL phân tán.
Hình 1.2. Xử lý cơ sở dữ liệu
Một CSDL phân tán là sự tập hợp dữ liệu mà về mặt logic chúng thuộc cùng một
hệ thống nhƣng đƣợc trải rộng ở nhiều nơi (site) của một mạng máy tính.
Khái niệm này nhấn mạnh hai khía cạnh quan trọng nhƣ nhau của một CSDL phân
tán là:
- Sự phân tán (distribution): nghĩa là dữ liệu không tập trung ở cùng một nơi (hiểu
theo nghĩa bộ xử lý - processor), điều này giúp ta có thể phân biệt một CSDL phân tán
với một CSDL tập trung, đơn lẻ.
- Sự tƣơng quan logic (logical correlation): nghĩa là dữ liệu có những mối liên hệ
mật thiết với nhau, điều này giúp ta có thể phân biệt một CSDL phân tán với một tập
hợp các CSDL cục bộ (local database) hoặc các tập tin tập trung ở những nơi khác
nhau của một mạng máy tính.
Một vấn đề nảy sinh từ khái niệm trên là sự phân tán và sự tƣơng quan logic đƣợc
đƣa ra một cách quá mơ hồ để có thể luôn phân biệt đƣợc những trƣờng hợp thực sự là
CSDL phân tán và những trƣờng hợp không phải là những CSDL phân tán.
Để có một khái niệm rõ ràng hơn, ta xét một số ví dụ sau:
Ví dụ 1.1: Xét một ngân hàng có ba chi nhánh ở các vị trí địa lý khác nhau đƣợc
mô tả trong hình 1.3.
3
Tập bài giảng Cơ sở dữ liệu phân tán
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ý
Tại mỗi chi nhánh có máy tính kiểm soát các máy rút tiền của chi nhánh, và một
CSDL tài khoản (account database) của chi nhánh. Mỗi máy tính với CSDL tài khoản
cục bộ ở một chi nhánh tạo thành một nơi (site) của CSDL phân tán; các máy tính
đƣợc nối với nhau thông qua mạng máy tính truyền thông (communication network).
Khi hoạt động bình thƣờng, các ứng dụng đƣợc chạy tại các thiết bị đầu cuối của chi
nhánh chỉ cần truy nhập CSDL ở chi nhánh đó. Những ứng dụng này đƣợc thực hiện
hoàn tất bởi máy tính của chi nhánh, nơi mà chúng đƣợc chạy, và đƣợc gọi là các ứng
dụng cục bộ (local application). Một ví dụ của ứng dụng cục bộ là ứng dụng “ghi nợ”
hoặc “ghi có” trên một tài khoản đƣợc lƣu trữ trong cùng một chi nhánh mà tại đây
chạy ứng dụng này.
Nếu chúng ta thử áp dụng định nghĩa của CSDL phân tán cho trƣờng hợp này, thì
chúng ta nhận thấy rằng khó nói là có tính tƣơng quan logic hay không.
Có phải các chi nhánh chỉ chứa thông tin về các tài khoản của cùng một ngân hàng
là đủ?
Có nên xem điều này là một ví dụ của một CSDL phân tán hoặc một tập hợp CSDL
cục bộ?
Để trả lời cho câu hỏi này, chúng ta tập chung vào cái gì làm cho một tập hợp các
CSDL cục bộ khác với một CSDL phân tán có cùng dữ liệu. Về quan điểm công nghệ
(technological viewpoint), có một khía cạnh thực sự quan trọng là sự tồn tại của một
4
Tập bài giảng Cơ sở dữ liệu phân tán
vài ứng dụng truy xuất dữ liệu tại hai chi nhánh trở lên. Các ứng dụng này đƣợc gọi là
ứng dụng toàn cục (global application) hoặc ứng dụng phân tán (distributed
application). Sự tồn tại của các ứng dụng toàn cục là đặc điểm phân biệt của các CSDL
phân tán so với một tập hợp các CSDL cục bộ.
Một ứng dụng toàn cục tiêu biểu là một sự chuyển quĩ của một tài khoản trong một
chi nhánh này vào tài khoản trong một chi nhánh khác. Ứng dụng này cập nhật dữ liệu
tại hai chi nhánh khác nhau. Lƣu ý ứng dụng này thực hiện hai cập nhật cục bộ tại hai
chi nhánh riêng biệt (ghi nợ và ghi có), bởi vì cũng cần phải đảm bảo cả hai cập nhật
này đƣợc thực hiện hoặc đều không đƣợc thực hiện. Do đó, việc đảm bảo yêu cầu này
của các ứng dụng toàn cục là một công việc khó khăn.
Trong ví dụ 1.1, các máy tính đƣợc đặt tại các vị trí địa lý khác nhau. Tuy nhiên,
các CSDL phân tán cũng có thể đƣợc xây dựng trên các mạng cục bộ.
Ví dụ 1.2: Xét cùng một ngân hàng của ví dụ 1.1, với cùng các ứng dụng. Tuy
nhiên hệ thống có một cấu hình đƣợc chỉ ra trong hình 1.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ộ
Cùng các bộ xử lý các CSDL của chúng đã đƣợc di chuyển từ các chi nhánh về một
toà nhà chung và bây giờ đƣợc kết nối với nhau bởi một mạng cục bộ băng thông cao
(high-bandwidth local network).
Các máy rút tiền của các chi nhánh đƣợc kết nối với các máy tính tƣơng ứng bởi
các tuyến điện thoại. Mỗi bộ xử lý và CSDL của nó tạo thành một nơi của mạng máy
tính cục bộ.
Chúng ta thấy rằng cấu trúc vật lý của các kết nối đã đƣợc thay đổi so với ví dụ 1.1;
tuy nhiên các khía cạnh đặc trƣng của kiến trúc vẫn không thay đổi. Đặc biệt cùng các
máy tính thực hiện cùng các ứng dụng truy xuất trên cùng các CSDL. Một ứng dụng là
cục bộ trong ví dụ 1.1 thì vẫn là cục bộ, miễn là tính cục bộ (locality) không đƣợc định
5
Tập bài giảng Cơ sở dữ liệu phân tán
nghĩa đối với sự phân tán địa lý của các máy tính thực hiện ứng dụng này, nhƣng chỉ
đối với một máy tính và CSDL riêng của nó.
Nếu có các ứng dụng toàn cục thì ví dụ này đƣợc xem là CSDL phân tán, vì hầu hết
các điểm đặc trƣng của ví dụ trƣớc vẫn còn hợp lệ. Tuy nhiên, CSDL phân tán đƣợc
thực hiện trên một mạng cục bộ (LAN) thay vì trên một mạng diện rộng (WAN), với
độ tin cậy (reliability) và thông lƣợng (throughput) của nó cao hơn, trong một số
trƣờng hợp sẽ thay đổi các giải pháp cho trƣớc đối với một số vấn đề. Chúng ta xét
một ví dụ của một hệ thống mà chúng ta không xem là một CSDL phân tán.
Ví dụ 1.3: Xét cùng một ngân hàng của ví dụ 1.1, nhƣng với cấu hình của hệ thống
đƣợc chỉ ra trong hình 1.5.
Hình 1.5. Một hệ thống đa xử lý (multiprossor system)
Dữ liệu của các chi nhánh khác nhau đƣợc phân tán trên ba máy tính phía sau
(backend conputer), mà chúng thực hiện các chức năng quản trị cơ sở dữ liệu. Chƣơng
trình ứng dụng đƣợc thực hiện bởi một máy tính khác, mà máy tính này yêu cầu các
dịch vụ truy xuất CSDL tại các máy tính phía sau khi cần thiết.
Lý do mà hệ thống máy tính này không đƣợc xem là một CSDL phân tán, bởi vì
mặc dù dữ liệu đƣợc phân tán về mặt vật lý trên các bộ xử lý khác nhau, nhƣng sự
phân tán của chúng là không thích hợp trên quan điểm ứng dụng. Điều mà chúng ta
không có ở đây chính là sự tồn tại của các ứng dụng cục bộ, bởi vì không có một máy
tính nào mà chính nó có khả năng thực hiện một ứng dụng.
Từ các ví dụ trên, ta có một phát biểu về cơ sở dữ liệu phân tán nhƣ sau:
6
Tập bài giảng Cơ sở dữ liệu phân tán
Một CSDL phân tán, là sự tập hợp dữ liệu đƣợc phân tán trên các máy tính khác
nhau của một mạng máy tính. Mỗi nơi của mạng máy tính có khả năng xử lý tự trị
(autonomous processing capability) và có thể thực hiện các ứng dụng cục bộ. Mỗi nơi
cũng tham gia vào sự thực hiện của ít nhất một ứng dụng toàn cục, mà nơi này yêu cầu
truy xuất dữ liệu ở nhiều nơi bằng cách dùng hệ thống truyền thông con
(communication subsystem).
Định nghĩa này nhấn mạnh ba khía cạnh quan trọng của một CSDL phân tán, đó là:
- Sự phân tán dữ liệu: Dữ liệu phải đƣợc phân tán ở nhiều nơi.
- Ứng dụng cục bộ: Mỗi nơi phải thực hiện ít nhất một ứng dụng cục bộ.
- Ứng dụng toàn cục: Mỗi nơi phải tham gia vào sự thực hiện của ít nhất một ứng
dụng toàn cục .
Ví dụ 1.5: Xét hệ thống quản lý dự án trong một công ty phát triển phần mềm. Để
quản lý, công ty có một CSDL với lƣợc đồ toàn cục nhƣ sau:
- NV(MANV, TENNV, CV): Quan hệ này chứa thông tin về nhân viên của công
ty gồm: mã nhân viên, tên nhân viên, chức vụ của nhân viên.
- TL(CV, LUONG): Quan hệ này chứa thông tin về lƣơng trả theo chức vụ của
nhân viên.
- DA(MADA, TENDA, NS, VT): Quan hệ này chứa thông tin về các dự án mà
công ty đang thực hiện gồm: mã dự án, tên dự án, ngân sách dành cho dự án, nơi thực
hiện dự án.
- HS(MANV, MADA, NHIEMVU, THOIGIAN): Quan hệ này chứa thông tin về
việc phân công các nhân viên thực hiện các dự án gồm mã nhân viên, mã dự án, nhiệm
vụ trong dự án, thời gian thực hiện trong dự án.
Giả sử công ty có văn phòng ở Nam Định, Hà Nội, Đà Nẵng, Cần Thơ; mỗi nơi
đều thực hiện một số dự án.
Giả sử hệ thống có các ứng dụng sau:
- Ứng dụng 1: Truy xuất DA theo vị trí là “Hà Nội”
- Ứng dụng 2: Truy xuất các bộ của DA có ngân sách lớn hơn 20000
- Ứng dụng 3: Truy xuất các bộ của DA có ngân sách nhỏ hơn hoặc bằng 20000.
Do tính phân tán của các văn phòng nên tại mỗi văn phòng có lƣu trữ dữ liệu tác
nghiệp của chính văn phòng đó, các nhân viên tại và các dự án mà văn phòng đó đang
quản lý.
Với các yêu cầu nhƣ trên, sử dụng thiết kế và cài đặt CSDL phân tán là hợp lý.
Trong đó 3 khía cạnh quan trọng của một CSDL phân tán:
- Sự phân tán dữ liệu: Dữ liệu đƣợc phân tán tại 4 nơi: Nam Định, Hà Nội, Đà
Nẵng, Cần Thơ
7
Tập bài giảng Cơ sở dữ liệu phân tán
- Ứng dụng cục bộ: Với 3 ứng dụng trên thì mỗi nơi đều phải thực hiện ít nhất một
ứng dụng cục bộ.
- Ứng dụng toàn cục: Với 3 ứng dụng trên thì thì mỗi nơi đều tham gia vào sự thực
hiện của ít nhất một ứng dụng toàn cục .
Hình 1.6. Sơ đồ lưu trữ phân tán
1.2. Mục đích của việc sử dụng cơ sở dữ liệu phân tán
Trong những năm gần đây, công nghệ CSDL phân tán đã trở thành một lĩnh vực
quan trọng của công nghệ thông tin, tính cần thiết của nó ngày càng nâng cao. Có rất
nhiều nguyên nhân thúc đẩy sự phát triển của CSDL phân tán. Các động cơ thúc đẩy
chính là:
- Sự phát triển tổ chức (organizational) kinh tế (economic)
- Kết nối lẫn nhau (interconnection) của các CSDL hiện tại
- Sự lớn mạnh gia tăng (incremental growth)
- Giảm chi phí truyền thông (communication overhead)
- Hiệu quả công việc (performance consideration)
- Độ tin cậy (reliability) và tính sẵn sàng (availability)
1.2.1. Sự phát triển của các cơ cấu tổ chức kinh tế
Cùng với sự phát triển của xã hội, nhiều cơ quan, xí nghiệp có cơ cấu tổ chức
không đƣợc tập trung hoá, hoạt động phân tán trên phạm vi rộng. Vì vậy thiết kế và cài
đặt CSDL phân tán là phù hợp, đáp ứng mọi nhu cầu truy xuất và khai thác dữ liệu.
Với sự phát triển hiện nay của công nghệ máy tính, các động cơ giảm bớt chi phí để có
8
Tập bài giảng Cơ sở dữ liệu phân tán
các trung tâm máy tính tập trung lớn trở lên có vấn đề. Tuy nhiên, các động cơ thúc
đẩy về tổ chức và kinh tế có thể là lý do quan trọng nhất để phát để phát triển CSDL
phân tán.
1.2.2. Sự kết nối lẫn nhau của CSDL hiện tại
Các CSDL phân tán là giải pháp tự nhiên khi có nhiều CSDL đã tồn tại trong một
tổ chức và cần phải thực hiện nhiều ứng dụng toàn cục hơn. Trong trƣờng hợp này,
CSDL đƣợc tạo từ dƣới lên từ các CSDL cục bộ đã đƣợc tạo từ trƣớc. Tiến trình này
đòi hỏi cấu trúc lại các cơ sở dữ liệu cục bộ ở một mức nhất định. Tuy nhiên, việc tái
cấu trúc này sẽ cần sự nỗ lực ít hơn so với việc tái tạo mới hoàn toàn một CSDL tập
trung.
1.2.3. Sự lớn mạnh gia tăng
Khi một tổ chức lớn mạnh lên do có thêm các đơn vị tổ chức tƣơng đối độc lập (các
chi nhánh mới, các kho mới,…), thì cách tiếp cận CSDL phân tán hỗ trợ sự lớn mạnh
tăng dần với một mức độ ảnh hƣởng tối thiểu đến các đơn vị đã tồn tại. Với cách tiếp
cận tập trung, quy mô ban đầu của hệ thống cần phải thận trọng để mở rộng trong
tƣơng lai, mà điều này cũng khó nhìn thấy trƣớc và tốn kém nhiều cho việc thực hiện,
hoặc sự lớn mạnh sẽ ảnh hƣởng nhiều đến các ứng dụng mới và các ứng dụng đang tồn
tại.
1.2.4. Giảm chi phí truyền thông
Trong thực tế, sử dụng một số ứng dụng mang tính cục bộ sẽ làm giảm chi phí
truyền thông. Trong một CSDL phân tán về mặt địa lý, chẳng hạn nhƣ CSDL của ví dụ
1.1, rõ ràng nhiều ứng dụng cục bộ làm giảm đi chi phí truyền thông so với CSDL tập
trung. Do đó, việc tối ƣu hóa hoá tính cục bộ của các ứng dụng là một trong các mục
tiêu chính trong thiết kế CSDL phân tán.
1.2.5. Hiệu quả công việc
Vì có nhiều bộ xử lý độc lập, do đó hiệu xuất đƣợc nâng cao thông qua một cơ chế
song song hóa mức độ cao. Nghiên cứu này có thể áp dụng cho bất kỳ hệ thống đa xử
lý (multiprocesor system), chứ không chỉ áp dụng cho các CSDL phân tán. Chẳng hạn,
cấu hình của ví dụ 1.3 cũng cho phép song song hoá, nhƣng nó không đƣợc xem là
một CSDL phân tán.
Tuy nhiên, các CSDL phân tán có ƣu điểm trong trƣờng hợp sự phân rã dữ liệu
phản ánh các tiêu chí phụ thuộc ứng dụng, mà các tiêu chí này làm cực đại hoá tính
cục bộ của ứng dụng . Bằng cách này, các bộ xử lý sẽ ít liên lạc với nhau hơn. Tải
đƣợc dùng chung giữa các bộ xử lý khác nhau, và các hiện tƣợng thắt cổ chai nguy
kịch, chẳng hạn nhƣ mạng truyền thông hoặc các dịch vụ chung của toàn bộ hệ thống,
sẽ đƣợc tránh khỏi. Hiệu quả này là kết quả của khả năng xử lý tự trị đối với các ứng
dụng cục bộ mà đã đƣợc nói đến trong định nghĩa của CSDL phân tán.
9
Tập bài giảng Cơ sở dữ liệu phân tán
1.2.6. Độ tin cậy và tính sẵn sàng
Cách tiếp cận CSDL phân tán, nhất là đối với dữ liệu dƣ thừa, có thể đƣợc sử dụng
để có tính sẵn sàng và độ tin cậy cao. Tuy nhiên, để có đƣợc mục tiêu này là điều
không phải dễ dàng, và cần phải sử dụng các kỹ thuật mà hoàn toàn vẫn còn chƣa đƣợc
thoả thuận với nhau. Khả năng tự trị của các nơi khác nhau tuy không thể đảm bảo
toàn bộ độ tin cậy cao của hệ thống, nhƣng nó đảm bảo đặc tính suy biến (degradation
property). Nói cách khác, các hƣ hỏng trong CSDL phân tán có thể xảy ra nhiều hơn
so với trong CSDL tập trung, bởi vì số thành phần nhiều hơn, nhƣng ảnh hƣởng của
mỗi hƣ hỏng bị hạn chế đối với các ứng dụng sử dụng dữ liệu của nơi hƣ hỏng và rất
hiếm khi hệ thống bị ngƣng hoàn toàn.
Các động cơ thúc đẩy ở trên đối với CSDL phân tán không phải là mới. Tại sao sự
phát triển của các hệ thống CSDL chỉ mới bắt đầu? Có hai lý do chính:
Thứ nhất, sự phát triển hiện nay của máy tính nhỏ, cung cấp nhiều khả năng có
mức chi phí thấp so với các máy tính lớn trƣớc đây, sẽ hỗ trợ các phần cứng cần thiết
để phát triển các hệ thống thông tin phân tán.
Thứ hai, công nghệ CSDL phân tán dựa trên hai công nghệ khác nhau đã đƣợc phát
triển thành một nền tảng đủ vững chắc trong những thập niên 1970 là: công nghệ mạng
máy tính, và công nghệ CSDL. Đó là một công việc phức tạp để xây dựng một CSDL
phân tán ở trên một mạng máy tính, và một tập hợp các hệ quản trị CSDL cục bộ tại
mỗi nơi; nó sẽ không khả thi nếu không có các khối xây dựng sẵn này.
1.3. Các đặc điểm chính của cơ sở dữ liệu phân tán
Các CSDL phân tán không đơn giản là sự thực hiện phân tán của các CSDL tập
trung, bởi vì chúng cho phép thiết kế các hệ thống biểu thị các đặc điểm khác so với
các hệ thống tập trung truyền thống. Do đó, chúng ta sẽ xét các đặc điểm tiêu biểu của
các CSDL truyền thống, và so sánh chúng với các đặc điểm tƣơng ứng của các CSDL
phân tán. Các đặc điểm đặc trƣng cho cách tiếp cận CSDL truyền thống là:
- Điều khiển tập trung (centralized control).
- Độc lập dữ liệu (data independence).
- Giảm dƣ thừa (reduction of redundancy).
- Các cấu trúc vật lý phức tạp dùng để truy xuất hiệu quả.
- Tính toàn vẹn (integrity).
- Phục hồi (recovery).
- Điều khiển đồng thời (concurrency control).
- Tính riêng biệt (privacy) và tính bảo mật (security).
1.3.1. Điều khiển tập trung
Khả năng cung cấp điều khiển tập trung trên các tài nguyên thông tin (information
resourecs) của toàn bộ xí nghiệp (hoặc một tổ chức) đƣợc xem nhƣ là một trong những
10
Tập bài giảng Cơ sở dữ liệu phân tán
động cơ thúc đẩy tốt nhất cho việc giới thiệu các CSDL; chúng đƣợc phát triển nhƣ là
một cuộc cách mạng của các hệ thống thông tin mà trong đó mỗi ứng dụng có các tệp
tin riêng biệt của nó. Chức năng cơ bản của ngƣời quản trị CSDL (DBA-Database
Administrator) là đảm bảo sự an toàn dữ liệu; bản thân dữ liệu đã đƣợc công nhận là
sự đầu tƣ quan trọng của xí nghiệp mà dữ liệu cần phải đƣợc tập trung.
Trong các CSDL phân tán, ý tƣởng điều khiển tập trung không nhấn mạnh. Điều
này còn tuỳ thuộc vào kiến trúc, nhƣ chúng ta có thể thấy trong các ví vụ 1.1 và 1.2. Ví
dụ 1.2 thích hợp với điều khiển tập trung hơn so với ví dụ 1.1.
Nói chung, trong các CSDL phân tán chúng ta có thể nhận biết một cấu trúc điều
khiển phân cấp (hierarchical control structure) gồm có ngƣời quản trị CSDL cục bộ
(global database administrator), mà ngƣời này có trách nhiệm về CSDL cục bộ của họ.
Tuy nhiên, cần phải nhấn mạnh là những ngƣời quản trị CSDL cục bộ có thể có
một mức độ tự trị cao, cao đến mức mà hoàn toàn không cần có ngƣời quản trị CSDL
toàn cục, và sự phối hợp giữa các nơi (intersite coordination) đƣợc thực hiện bởi chính
những ngƣời quản trị cục bộ. Đặc tính này thƣờng đƣợc gọi là tính tự trị vị trí (site
autonomy).
Các CSDL phân tán có thể khác nhau rất nhiều về mức độ tự trị vị trí: từ tính tự vị
trí hoàn toàn (complete site autonony) không có ngƣời quản trị CSDL tập trung, đến
điều khiển tập trung hầu nhƣ hoàn toàn.
1.3.2. Độc lập dữ liệu
Độc lập dữ liệu cũng đƣợc xem nhƣ là một trong những động cơ thúc đẩy chính
cho việc giới thiệu cách tiếp cận CSDL. Về cơ bản, độc lập dữ liệu có nghĩa là tổ chức
hiện tại của dữ liệu là trong suốt đối với ngƣời lập trình ứng dụng. Các chƣơng trình
đƣợc viết dựa trên một khung nhìn khái niệm (conceptual view) về dữ liệu, đƣợc gọi là
lƣợc đồ khái niệm (conceptual schema).
Ƣu điểm chính của độc lập dữ liệu, là các chƣơng trình không bị ảnh hƣởng bởi
những thay đổi về tổ chức vật lý của dữ liệu.
Trong các CSDL phân tán, độc lập dữ liệu có cùng tầm quan trọng nhƣ trong các
CSDL truyền thống. Tuy nhiên, một khía cạnh mới đƣợc đƣa vào trong khái niệm
thông thƣờng của độc lập dữ liệu, đƣợc gọi là tính trong suốt phân tán (distributation
transparency). Nhờ tính trong suốt phân tán mà các chƣơng trình có thể đƣợc viết
giống nhƣ khi CSDL không đƣợc phân tán. Do đó, tính đúng đắn của các chƣơng trình
không bị ảnh hƣởng bởi việc di chuyển dữ liệu từ một nơi này đến một nơi khác,
nhƣng tốc độ thực hiện thì có bị ảnh hƣởng.
Độc lập dữ liệu đã đƣợc cung cấp cho các CSDL truyền thống thông qua nhiều
mức (multilevel architecture), có các mô tả khác nhau về dữ liệu và ánh xạ giữa chúng;
các khái niệm của lƣợc đồ khái niệm, lƣợc đồ lƣu trữ (storage schema) đã đƣợc phát
11
Tập bài giảng Cơ sở dữ liệu phân tán
triển nhằm mục đích này. Một cách tƣơng tự, tính trong suốt phân tán có đƣợc trong
CSDL phân tán bằng cách nêu ra các mức độ và những lƣợc đồ mới.
1.3.3. Giảm dƣ thừa
Trong các CSDL truyền thống, dƣ thừa dữ liệu đƣợc giảm càng nhiều càng tốt với
hai lý do:
Thứ nhất, những sự không nhất quán (inconsistency) giữa các bản sao của cùng dữ
liệu sẽ tự động đƣợc tránh khỏi bằng cách chỉ có một bản sao.
Thứ hai, vùng nhớ lƣu trữ đƣợc tiết kiệm bằng cách loại bỏ dƣ thừa.
Giảm dƣ thừa có đƣợc bằng cách dùng chung dữ liệu (data sharing), nghĩa là cho
phép nhiều ứng dụng truy xuất đến cùng các tập tin và các mẩu tin.
Tuy nhiên, trong các CSDL phân tán, có nhiều lý do để xem dƣ thừa dữ liệu là một
đặc điểm cần thiết:
Thứ nhất, tính cục bộ (locality) của các ứng dụng có thể đƣợc gia tăng nếu dữ liệu
đƣợc nhân bản tại tất cả các nơi mà ứng dụng cần dữ liệu này;
Thứ hai, tính sẵn sàng (availability) của hệ thống có thể đƣợc gia tăng, bởi vì một
nơi bị hỏng sẽ không làm ngƣng thực hiện của các ứng dụng tại các nơi khác nếu dữ
liệu không đƣợc nhân bản.
Nói chung, các lý do về sự dƣ thừa này đối với môi trƣờng truyền thống vẫn còn có
giá trị, mà do đó muốn đánh giá mức độ dƣ thừa tối ƣu thì cần phải đánh giá về sự thoả
hiệp phức tạp hơn. Lợi ích của việc nhân bản một mục dữ liệu sẽ tăng theo tỉ số giữa
các lần truy xuất lấy dữ liệu (retrieval access), với các lần truy xuất cập nhật dữ liệu
(update access), đƣợc thực thực hiện bởi các ứng dụng truy xuất đến mục dữ liệu này.
Lợi ích của nhân bản dữ liệu đƣợc gia tăng, bởi vì nếu chúng ta có nhiều bản sao của
một mục dữ liệu thì việc lấy dữ liệu sẽ đƣợc thực hiện trên bất kỳ bản sao nào, trong
khi việc cập nhật dữ liệu sẽ đƣợc thực hiện một cách nhất quán trên tất cả các bản sao.
Do đó nhân bản dữ liệu cần phải xem xét kỹ lƣỡng dựa vào hai loại ứng dụng cơ bản,
đó là ứng dụng chỉ đọc và ứng dụng cập nhật. Nhân bản dữ liệu giúp cho các ứng dụng
chỉ đọc đƣợc thực hiện nhanh hơn, nhƣng nó làm cho các ứng dụng cập nhật bị thực
hiện lâu hơn vì phải cập nhật dữ liệu tại các nơi đƣợc nhân bản.
Nhƣ vậy, nhân bản dữ liệu sẽ là một ƣu điểm nếu hệ thống có rất nhiều ứng dụng
chỉ đọc và có rất ít ứng dụng cập nhật. Trong trƣờng hợp ngƣợc lại thì sự nhân bản dữ
liệu là một nhƣợc điểm.
1.3.4. Các cấu trúc vật lý phức tạp dùng để truy xuất hiệu quả
Các cấu trúc truy xuất phức tạp, chẳng hạn nhƣ các chỉ mục thứ cấp (secondary
index), các chuỗi kết nối giữa các tệp tin (interfile chain),…, là một khía cạnh chính
của các CSDL truyền thống. Sự hỗ trợ cho các cấu trúc này là một phần quan trọng
12
Tải về để xem bản đầy đủ
182 trang
18480
Free
Bạn đang xem 20 trang mẫu của tài liệu "Tập bài giảng Cơ sơ dữ liệu phân tán (Phần 1)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- tap_bai_giang_co_so_du_lieu_phan_tan_phan_1.pdf
