Giáo trình Cơ sở dữ liệu phân tán (Dùng cho sinh viên hệ đào tạo đại học từ xa)

Nội dung text: Giáo trình Cơ sở dữ liệu phân tán (Dùng cho sinh viên hệ đào tạo đại học từ xa)

1. HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG CƠ SỞ DỮ LIỆU PHÂN TÁN (Dùng cho sinh viên hệ đào tạo đại học từ xa) Lưu hành nội bộ HÀ NỘI - 2009
2. HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG CƠ SỞ DỮ LIỆU PHÂN TÁN Biên soạn : TS. PHẠM THẾ QUẾ
3. LỜI NÓI ĐẦU Tài liệu “Cơ sở dữ liệu phân tán” là sách hướng dẫn học tập dùng cho sinh viên hệ đào tạo từ xa ngành công nghệ thông tin và ngành kỹ thuật điện tử, viễn thông. Nội dung của tài liệu bao gồm: - Chương I giới thiệu khái niệm cơ bản về cơ sở dữ liệu phân tán, xử lý phân tán vàhệ thống xử lý phân tán. Sự cần thiết của hệ cơ sở dữ liệu phân tán và các đặc điểm của cơ sở dữ liệu phân tán. Cấu trúc logic của cơ sở dữ liệu phân tán và các lợi íchphân tán dữ liệu trên mạng. - Chương II giới thiệu tổng quát về hệ quản trị cơ sở dữ liệu phân tán.Ưu điểm cách tiếp cận mô hình cơ sở dữ liệu quan hệ và hệquản trị cơ sở dữ liệu quan hệ. Vấn đề quy tắc toàn vẹn dữ liệu. Mô hình kiến trúc hệ quản trị cơ sở dữ liệu phân tán và kiến trúc tổng quan của một hệ quản trị phức hệ CSDL phân tán - Chương III trình bày những vấn đề thiết kế cơ sở dữ liệu phân tán,là các vấn đề phân mảnh dữ liệu. Sự cần thiết phải phân mảnh, các kiểu phân mảnh, mức độ phân mảnh, các quy tắc phân mảnh và bài toán cấp phát dữ liệu. Nội dung của chương trình bày tổng quát kỹ thuật phân mảnh ngang cơ sở và phân mảnh ngang dẫn xuất. Thông tin cần thiết của phân mảnh ngang. Phương pháp phân mảnh dọc, thông tin cần thiết của phân mảnh dọc và các thuật toán tụ nhóm và phân mảnh. Có nhiều bài toán cần thiết phải sử dụng lai ghép phân mảnh ngang và phân mảnh dọc. Bài toán cấp phát dữ liệu, thông tin cần thiết cho bài toán cấp phát và mô hình cấp phát. - Chương IV giới thiệu kiểm soát dữ liệu ngữ nghĩa, là quá trình kiểm soát khung nhìn trong các hệ quản trịcơ sử dữ liệu tập trung và khung nhìn trong các hệ quản trị cơ sở dữ liệu phân tán. Nội dung kiểm soát dữ liệu ngữ nghĩa cũng bao hàm vấn đề an toàn dữ liệu. Kiểm soát cấp quyền tập trung và kiểm soát cấp quyền phân tán.Kiểm soát toàn vẹn ngữ nghĩa tập trung và kiểm soát toàn vẹn ngữ nghĩa phân tán. - Chương V đề cập đến các vấn đề xử lý truy vấn trong các hệ cơ sở dữ liệu phân tán. Khái niệm xử lý truy vấn,mục đích của việc xử lý truy vấn và giới thiệu các tầng của quá trình xử lý truy vấn. Tài liệu”Cơ sở dữ liệu phân tán” không chỉ đề cập đến những vấn đề cơ sở lý thuyết mà còn trình bày 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 cụ thể. Hy vọng sẽ có ích cho sinh viên và những người muốn xây dựng các hệ thống tin học ứng dụng. Tài liệu có thể còn nhiều thiếu sót trong biên soạn, tôi vẫn mạnh dạn giới thiệu tài liệu này và mong nhận được sự góp ý của bạn đọc. Tác giả
4. CHƯƠNG 1: KHÁI NIỆM CƠ BẢN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN Trong chương này trình bày những khái niệm cơ bản về nguyên lý các hệ cơ sở dữ liệu phân tán, bao gồm các nội dung sau • Xử lý dữ liệu phân tán. • Hệ cơ sở dữ liệu phân tán là gì. • Khả năng của các hệ cơ sở dữ liệu phân tán. • Các mô hình xử lý dữ liệu phân tán • Tổng quan về hệ quản trị cơ sở dữ liệu quan hệ. 1.1 MỞ ĐẦU 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 bgà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.2 XỬ LÝ PHÂN TÁN VÀ HỆ THỐNG XỬ LÝ PHÂN TÁN 1.2.1 Khái niệm 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 3
5. loại thiết bị khác nhau chẳng hạn như: hệ đa bộ 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.2.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.3 HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN LÀ GÌ. Công nghệ các hệ cơ sở dữ liệu phát triển từ mô hình xử lý 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ó (hình 1.1), sang mô hình định nghĩa và quản lý dữ liệu tập trung. 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. Ứng dụng 1 TẬP TIN 1 Ứng dụng 2 DỮ TẬP TIN 2 Mô tả dữ liệu LIỆU THỪA Ứng dụng 3 TẬP TIN 3 Mô tả dữ liệu Hình 1.1: Xử lý dữ liệu truyền thống 4
6. Ứng dụng 1 Mô tả dữ liệu Ứng dụng 3 Thao tác dữ liệu CƠ SỞ DỮ LIỆU Ứng dụng 3 Hình 1.2: Xử lý cơ sở dữ liệu 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ệ cơ sở dữ liệu phân tán ở đây bao gồm cả khái niệm cơ sở dữ liệu phân tán và hệ quản trị cơ sở dữ liệu phân tán. Cơ sở dữ liệu phân tán là một tập các cơ sở dữ liệu có quan hệ với nhau về mặt logic và được phân bố trên một mạng máy tính. Hệ quản trị cơ sở dữ liệu phân tán là hệ thống phần mềm cho phép quản trị cơ sở dữ liệu phân tán và làm cho sự phân tán đó là trong suốt đối với người sử dụng. Trong mô hình cơ sở dữ liệu phân tán bản thân cơ sở dữ liệu có ở trên nhiều máy tính khác nhau. Như vậy, đặc trưng của cơ sở dữ liệu phân tán là các CSDL được phân bố trên mạng máy tính và có quan hệ với nhau về mặt logic. Hệ CSDL phân tán không đơn thuần bao gồm nhiều file dữ liệu được tổ chức lưu trữ riêng lẻ trên các thiết bị nhớ của mạng máy tính. Để tạo một hệ CSDL phân tán, các file không chỉ có quan hệ với nhau về mặt logic mà còn cần có một cấu trúc giao diện chung giữa chúng để các file có thể truy nhập lẫn nhau. Có rất nhiều ứng dụng yêu cầu các hệ quản trị CSDL thao tác trên dữ liệu bán cấu trúc hoặc không cấu trúc, như các file Web trên mạng Internet. 1.4 SỰ CẦN THIẾT CỦA HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN Trong những năm gần đây, công nghệ cơ sở dữ liệu 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 được nâng cao. Có nhiều nguyên nhân thúc đẩy sự phát triển của các hệ CSDLPT: 1.4.1 Sự phát triển của các cơ cấu tổ chức Cùng với sự phát triển cuả xã hội, nhiều cơ quan, xí nghiệp có cơ cấu tổ chức không tập trung, hoạt động phân tán trên phạm vi rộng. Vì vậy thiết kế và cài đặt cơ sở dữ liệu 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 Cùng với sự phát triển của công nghệ viễn thông, tin học, động cơ thúc đẩy kinh tế, việc tổ chức các trung tâm máy tính lớn và tập trung trở thành vấn đề cần nghiên cứu. Cơ cấu tổ chức và vấn đề kinh tế là một trong những nguyên nhân quan trọng nhất của sự phát triển cơ sở dữ liệu phân tán. 5
7. 1.4.2 Giảm chi phí truyền thông Trong thực tế, sử dụng một số ứng dụng mang tính địa phương sẽ làm giảm chi phí truyền thông. Bởi vậy, việc tối ưu hoá tính địa phương của các ứng dụng là một trong những mục tiêu chính của việc thiết kế và cài đặt một CSDLPT. 1.4.3 Hiệu quả công việc Sự tồn tại một số hệ thống xử lý điạ phương đạt được thông quan việc xử lý song song. Vấn đề này có thể thích hợp với mọi hệ đa xử lý. CSDLPT có thuận lợi trong phân tích dữ liệu phản ánh điều kiện phụ thuộc của các ứng dụng, cực đại hoá tính địa phương của ứng dụng. Theo cách này tác động qua lại giữa các bộ xử lý được làm cức tiểu. Công việc được phân chia giữa các bộ xử lý khác nhau và tránh được các tắc nghẽn thông tin trên mạng truyền thông hoặc các dịch vụ chung của toàn hệ thống. Sự phân tán dữ liệu phản ánh hiệu quả làm tăng tính địa phương của các ứng dụng. 1.4.4 Độ tin cậy và tính sẵn sàng Cách tiếp cận CSDLPT, cho phép truy nhập độ tin cậy và tính sẵn sàng cao hơn. Tuy nhiên, để đạt được mục đích đó là vấn đề không đơn giản đòi hỏi kỹ thuật phức tạp. Những lỗi xuất hiện trong một CSDLPT có thể xảy ra nhiều hơn vì số các thành phần cấu thành lớn hơn, nhưng ảnh hưởng của lỗi chỉ ảnh hưởng tới các ứng dụng sử dụng các site lỗi. Sự hỏng hóc của toàn hệ thống hiếm khi xảy ra. CSDLPT là sự tập hợp các dữ liệu thuộc cùng một hệ thống về mặt logic nhưng phân bố trên các site của mạng máy tính. Công nghệ CSDLPT là sự kết hợp giữa hai vấn đề phân tán và hợp nhất: • Phân tán : phân tán dữ liệu trên các site của mạng • Hợp nhất : hợp nhất về mặt logic các dữ liệu phân tán sao cho chúng xuất hiện với người sử dụng giống như với CSDL đơn lẻ duy nhất. Công nghệ CSDL phân tán mới thực sự phát triển trong những năm gần đây nhờ sự phát triển của kỹ thuật tính toán, kỹ thuật truyền thông và mạng máy tính. Những ứng dụng được xây dựng trên CSDL 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ó so với CSDL tập trung. 1.5 CÁC ĐẶC ĐIỂM CỦA CƠ SỞ DỮ LIỆU PHÂN TÁN Cơ sở dữ liệu phn tán không đơn giản là sự phân bố của các cơ sở dữ liệu, bởi vì cơ sở dữ liệu phân tán có nhiều đặc điểm khác biệt so với cơ sở dữ liệu tập trung truyền thống. Phần này so sánh cơ sở dữ liệu phân tán với cơ sở dữ liệu tập trung ở một số đặc điểm: điều khiển tập trung, sự độc lập dữ liệu, sự giảm dư thừa dữ liệu, các cấu trúc vật lý phức tạp để truy xuất hiệu quả. 1.5.1 Điểu khiển tập trung Điều khiển tập trung (Centralized Control) là một đặc điểm của cơ sở dữ liệu tập trung, toàn bộ dữ liệu được tập trung lại nhằm để tránh sự dư thừa dữ liệu, đảm bảo được tính độc 6
8. lập của dữ liệu. Dữ liệu được quản lý tập trung bởi người quản trị cơ sở dữ liệu. Chức năng cơ bản của người quản trị cơ sở dữ liệu (DBA - Database Administrator) là bảo đảm sự an toàn của dữ liệu. Trong các cơ sở dữ liệu phân tán vấn đề điều khiển tập trung không được nhấn mạnh. Nói chung, trong các cơ sở dữ liệu phân tán , sự điều khiển được thực hiện theo một cấu trúc điều khiển phân cấp bao gồm hai loại người quản trị cơ sở dữ liệu: • Người quản trị cơ sở dữ liệu toàn cục (Global Database Administrator) là người có trách nhiệm chính về toàn bộ cơ sở dữ liệu phân tán • Người quản trị cơ sở dữ liệu cục bộ (Local Database Administrator) là người có trách nhiệm về cơ sở dữ liệu cục bộ của họ. Tuy nhiên, những người quản trị cơ sở dữ liệu cục bộ cần phải có những quyền độc lập riêng về cơ sở dữ liệu cục bộ của mình mà người quản trị cơ sở dữ liệu toàn cục hoàn toàn không có những quyền này và sự phối hợp giữa các vị trí được thực hiện bởi chính những người quản trị cục bộ. Đặc điểm này được gọi là sự độc lập vị trí. Các cơ sở dữ liệu phân tán có thể khác nhau rất nhiều về mức độ độc lập vị trí. Từ sự độc lập vị trí hoàn toàn (không có người quản trị cơ sở dữ liệu tập trung) đến sự điều khiển tập trung hoàn toàn. 1.5.2 Độc lập dữ liệu Độc lập dữ liệu (Data Independence) là một đặc điểm của cơ sở dữ liệu. Độc lập dữ liệu có nghĩa là tổ chức lưu trữ dữ liệu là trong suốt đối với người lập trình ứng dụng. Ưu điểm 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 lưu trữ vật lý của dữ liệu. Trong các hệ cơ sở dữ liệu phân tán, độc lập dữ liệu cũng quan trọng như trong các cơ sở dữ liệu tập trung. Tuy nhiên, một đặc điểm mới được đưa vào trong khái niệm thông thường của độc lập dữ liệu là sự trong suốt phân tán (Distribution Transparency). Nhờ sự trong suốt phân tán mà các chương trình ứng dụng có thể được viết giống như trong cơ sở dữ liệu không được phân tán. Vì vậy, tính đúng đắn của các chương trình ứng dụng không bị ảnh hưởng bởi sự di chuyển dữ liệu từ một vị trí này đến một vị trí khác. Tuy nhiên, tốc độ thực hiện của các chương trình ứng dụng thì bị ảnh hưởng. Độc lập dữ liệu trong cơ sở dữ liệu tập trung được thể hiện thông qua một kiến trúc nhiều mức, các mức này có những mô tả khác nhau về dữ liệu và những ánh xạ biến đổi giữa các mức. Sự trong suốt phân tán trong cơ sở dữ liệu phân tán được thê hiện bằng cách bổ sung thêm các mức trong suốt vào kiến trúc nhiều mức của cơ sở dữ liệu tập trung. 1.5.3 Giảm dư thừa dữ liệu Trong các cơ sở dữ liệu tập trung, sự dư thừa dữ liệu được giảm thiểu, vì tránh sự không nhất quán giữa nhiều bản sao bằng cách chỉ có một bản sao và tiết kiệm vùng nhớ lưu trữ. Các ứng dụng chia sẻ chung, truy xuất đến các tập tin dữ liệu. Tuy nhiên, trong các cơ sở dữ liệu phân tán, sự dư thừa dữ liệu là một đặc điểm cần thiết, vì các lý do sau: 7
9. • Làm tăng tính cục bộ của các ứng dụng nếu dữ liệu được nhân bản tại tất cả các vị trí mà ứng dụng cần dữ liệu này. Khi đó, các ứng dụng cục bộ được thực hiện nhanh hơn vì không cần phải truy xuất dữ liệu từ xa. • Làm tăng tính sẵn sàng của hệ thống ứng dụng, vì một vị trí có sự cố sẽ không làm ngưng sự thực hiện của các ứng dụng ở những vị trí khác nếu dữ liệu tại vị trí bị hỏng được nhân bản tại các vị trí khác. Tuy nhiên, sự 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. Sự 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 bị thực hiện lâu hơn vì phải cập nhật dữ liệu tại các vị trí được nhân bản. Như vậy, sự 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ại là một nhược điểm. 1.5.4 Độ tin cậy qua các giao dịch phân tán Hệ quản trị CSDL phân tán cải thiện độ tin cậy qua các giao dịch phân tán, vì các thành phần được nhân bản hạn chế được các vị trí lỗi riêng lẻ. Lỗi của trạm riêng, hoặc lỗi của truyền thông làm cho một hoặc nhiều trạm mất liên lạc, không đủ để phá vỡ toàn bộ hệ thống. Trong trường hợp CSDL phân tán, điều này nghĩa là một số dữ liệu không thể truy nhập được, nhưng nếu biết cách hỗ trợ cho các giao dịch phân tán và các giao thức ứng dụng, thì người sử dụng vẫn có thể truy nhập được tới phần khác trong CSDL phân tán. Giao dịch là một đơn vị tính toán cơ bản, nhất quán và tin cậy, bao gồm một chuỗi các thao tác CSDL được thực hiện chuyển từ trạng thái CSDL nhất quán này sang trạng thái CSDL nhất quán khác ngay cả khi có một số giao dịch được thực hiện đồng thời và thậm chí cả khi xảy ra lỗi. Vì vậy, hệ quản trị CSDL phải hỗ trợ đầy đủ cho giao dịch đảm bảo rằng việc thực thi đồng thời các giao dịch của người sử dụng sẽ không vi phạm tính nhất quán của CSDL trong khi hệ thống có lỗi, với điều kiện là giao dịch được thực hiện chính xác, nghĩa là tuân theo các qui tắc toàn vẹn của CSDL. 1.5.5 Cải tiến hiệu năng Hiệu năng của CSDL phân tán được cải tiến dựa vào hai điểm: a) Hệ quản trị CSDL phân tán có khả năng phân mảnh CSDL khái niệm và cho phép cục bộ hoá dữ liệu. Có hai ưu điểm nổi bật: • Vì mỗi trạm chỉ xử lý một phần CSDL, sự tranh chấp về CPU và các dịch vụ vào/ra không nghiêm trọng như trong các hệ CSDL tập trung. • Tính cục bộ làm giảm trễ truy nhập từ xa thường gặp trên các mạng diện rộng. Hầu hết các hệ CSDL phân tán được cấu trúc nhằm tận dụng tối đa những ưu điểm của tính cục bộ dữ liệu. Lợi ích đầy đủ của việc giảm tranh chấp và giảm chi phí truyền chỉ có thể có được bằng cách phân mảnh và phân tán dữ liệu hợp lý. 8
10. b) Tính song song của các hệ thống phân tán có thể được khai thác để thực hiện song song liên truy vấn và truy vấn nội bộ. Liên truy vấn song song là khả năng thực hiện nhiều truy vấn tại cùng thời điểm, còn nội truy vấn song song là phương pháp tách một truy vấn đơn thành các truy vấn con và mỗi truy vấn con được thực hiện tại các trạm khác nhau, truy nhập các phần khác nhau của CSDL phân tán. 1.5.6 Dễ dàng mở rộng hệ thống Trong môi trường phân tán, dễ dàng tăng kích thước dữ liệu. và hiếm khi cần sửa đổi trong các hệ thống lớn. Việc mở rộng thường có thể được thực hiện bằng cách tăng khả năng lưu trữ và xử lý của mạng. Rõ ràng là không thể có được sự gia tăng “khả năng” một cách tuyến tính, vì điều này phụ thuộc vào chi phí phân tán. Tuy nhiên, vẫn có thể có những cải tiến có ý nghĩa. Khả năng mở rộng hệ thống dễ dàng mang tính kinh tế, chi phí giảm. 1.6 CÁC MÔ HÌNH CƠ SỞ DỮ LIỆU CLIENT/SERVER Nhìn chung mọi ứng dụng cơ sở dữ liệu bao gồm các phần: • Thành phần xử lý ứng dụng (Application Processing Components) • Thành phần phần mềm cơ sở dữ liệu (Database Software Componets) • Bản thân cơ sở dữ liệu (The Database Ifself) Có 5 mô hình kiến trúc vật lý về truy nhập dữ liệu • Mô hình cơ sở dữ liệu tập trung (Centralized database model) • Mô hình cơ sở dữ liệu theo kiểu file - server (File - server database model) • Mô hình xử lý từng phần cơ sở dữ liệu (Database extract processing model) • Mô hình cơ sở dữ liệu Client/Server (Client/Server database model) • Mô hình cơ sở dữ liệu phân tán (Distributed database model) 1.6.1 Mô hình cơ sở dữ liệu tập trung: Trong mô hình này, các ứng dụng, hệ quản trị cơ sở dữ liệu và cơ sở dữ liệu được cài đặt trên cùng một bộ xử lý. Ví dụ trên máy tính cá nhân có thể chạy các chương trình ứng dụng có sử dụng phần mềm cơ sở dữ liệu Oracle để truy nhập tới cơ sở dữ liệu trên đĩa cứng của máy tính cá nhân đó. Mô hình xử lý tập trung phù hợp với hầu hết công việc của nhiều tổ chức, doanh nghiệp Ví dụ một bộ xử lý mainframe chạy phần mềm cơ sở dữ liệu IMS hoặc DB2 của IBM có thể cung cấp cho các trạm làm việc ở các vị trí phân tán truy nhập nhanh chóng tới cơ sở dữ liệu trung tâm. Tuy nhiên trong rất nhiều hệ thống, cả 3 thành phần của ứng dụng cơ sở dữ liệu đều thực hiện trên cùng một máy mainframe do vậy cấu hình này cũng thích hợp với mô hình tập trung 1.6.2 Mô hình cơ sở dữ liệu theo kiểu File Server: Trong mô hình cơ sở dữ liệu theo kiểu File Server, các thành phần ứng dụng và phần mềm cơ sở dữ liệu ở trên một hệ thống máy tính và các File dữ liệu vật lý cơ sở dữ liệu cài đặt trên hệ thống máy tính khác. Một cấu hình như vậy thường được dùng trong môi trường cục bộ, 9
11. trong đó một hoặc nhiều hệ thống máy tính đóng vai trò của Server lưu trữ các file dữ liệu. Mô hình File Server giống với mô hình tập trung, cơ sở dữ liệu và các thành phần ứng dụng, phần mềm cơ sở dữ liệu cài đặt trên các máy tính khác nhau. Tuy nhiên các thành phần ứng dụng và phần mềm cơ sở dữ liệu có thể có cùng thiết kế để vận hành một môi trường tập trung. Hệ điều hành mạng có thể thực hiện cơ chế đồng thời cho phép nhiều người sử dụng cuối có thể truy nhập vào cùng cơ sở dữ liệu. 1.6.3 Mô hình xử lý từng phần cơ sở dữ liệu Mô hình trong đó một cơ sở dữ liệu ở xa có thể được truy nhập bởi phần mềm cơ sở dữ liệu, được gọi là xử lý dữ liệu từng phần. Với mô hình này, người sử dụng có thể tại một máy tính cá nhân kết nối truy nhập, khai thác cơ sở dữ liệu ở xa. Với cách tiếp cận này, người sử dụng phải biết chắc chắn là dữ liệu nằm ở đâu và làm như thế nào để truy nhập dữ liệu. Phần mềm ứng dụng cần phải có trên cả hai hệ thống máy tính để kiểm soát sự truy nhập dữ liệu và chuyển dữ liệu giữa hai hệ thống. Tuy nhiên, phần mềm cơ sở dữ liệu chạy trên hai hệ thống không cần biết rằng việc xử lý cơ sở dữ liệu từ xa đang diễn ra vì người sử dụng tác động tới chúng một cách độc lập. 1.6.4 Mô hình cơ sở dữ liệu Client/Server Trong mô hình cơ sở dữ liệu Client/Server, cơ sở dữ liệu được cài đặt trên Server, các ứng dụng trên các máy Client và phần mềm cơ sở dữ liệu được cài đặt trên cả Client lẫn Server. Trong mô hình này, các thành phần xử lý ứng dụng trên hệ thống Client đưa ra yêu cầu cho phần mềm cơ sở dữ liệu trên máy client, phần mềm này sẽ kết nối với phần mềm cơ sở dữ liệu chạy trên Server. Phần mềm cơ sở dữ liệu trên Server sẽ truy nhập vào cơ sở dữ liệu xử lý theo yêu cầu và gửi trả kết quả cho máy Client. Mới nhìn, mô hình cơ sở dữ liệu Client/Server có vẻ giống như mô hình File Server, tuy nhiên mô hình Client/Server có rất nhiều thuận lợi hơn mô hình File Server. Với mô hình File Server, một giao tác cần truy nhập dữ liệu nhiều lần có thể gây ra tắc nghẽn lưu lượng truyền trên mạng. Giả sử người sử dụng tạo ra một vấn tin để lấy dữ liệu tổng số từ 1000 bản ghi, với cách tiếp cận File Server, nội dung của 1000 bản ghi phải được lưu chuyển trên mạng, vì phần mềm cơ sở dữ liệu chạy trên máy của người sử dụng phải truy nhập từng bản ghi để thoả mãn yêu cầu của người sử dụng. Với cách tiếp cận cơ sở dữ liệu Client/Server, chỉ có lời vấn tin khởi động ban đầu và kết quả cuối cùng cần đưa lên mạng, phần mềm cơ sở dữ liệu chạy trên máy lưu giữ cơ sở dữ liệu sẽ truy nhập các bản ghi cần thiết, xử lý chúng và gọi các thủ tục cần thiết để đưa ra kết quả cuối cùng. Trong mô hình cơ sở dữ liệu Client/Server, thường nói đến các phần mềm Front End Software và Back End Software. Front End Software được chạy trên thiết bị truy nhập đầu cuối hoặc trên các Workstation, nhằm đáp ứng các yêu cầu xử lý đơn lẻ riêng biệt. Nó đóng vai trò của Client trong ứng dụng cơ sở dữ liệu Client/Server và thực hiện các chức năng hướng tới nhu cầu của người sử dụng. Front End Software chia thành các loại sau: • End User Database Software: Phần mềm cơ sở dữ liệu này có thể được người sử dụng thực hiện trên thiết bị đầu cuối, truy nhập vào các cơ sở dữ liệu cục bộ, kết nối với các cơ sở dữ liệu trên Server. 10
12. • Simple Query and Reporting Software là phần mềm được thiết kế để cung cấp các công cụ xử lý dữ liệu từ cơ sở dữ liệu và tạo các báo cáo đơn giản từ dữ liệu đã có. • Data Analysis Software cung cấp các hàm về tìm kiếm, khôi phục và cung cấp các phân tích phức tạp cho người sử dụng. • Application Development Tools là phần mềm cung cấp các khả năng phát triển các ứng dụng cơ sở dữ liệu Bao gồm các công cụ về thông dịch, biên dịch đơn đến các công cụ CASE (Computer Aided Software Engineering). Chúng tự động tất cả các bước trong quá trình phát triển ứng dụng và sinh ra chương trình cho các ứng dụng. • Database Administration Tools: Các công cụ cho phép người quản trị cơ sở dữ liệu thực hiện việc quản trị cơ sở dữ liệu như định nghĩa, lưu trữ hay phục hồi. CSDL Back End Software được cài đặt trên Server cơ sở dữ liệu,. bao gồm phần mềm cơ sở dữ liệu Client/Server và phần mềm mạng Application Network Tow er System Application Database Application Hình 1.3 Mô hình Client-Server 1.6.5 Distributed database model (Mô hình cơ sở dữ liệu phân tán) Cả hai mô hình File Server và Client/Server đều giả định là dữ liệu nằm trên một bộ xử lý và chương trình ứng dụng truy nhập dữ liệu nằm trên một bộ xử lý khác, còn mô hình cơ sở dữ liệu phân tán lại giả định bản thân cơ sở dữ liệu có ở trên nhiều máy khác nhau. 1.7 MÔ HÌNH THAM CHIẾU CƠ SỞ DỮ LIỆU PHÂN TÁN Mô hình kiến trúc cơ sở dữ liệu phân tán tại các site gồm lược đồ tổng thể, lược đồ phân mảnh và lược đồ cấp phát. 1.7.1 Lược đồ toàn cục Lược đồ toàn cục định nghĩa tất cả dữ liệu được chứa trong cơ sở dữ liệu phân tán như trong cở sở dữ liệu tập trung. Vì vậy, lược đồ toàn cục được định nghĩa chính xác như định nghĩa lược đồ cở sở dữ liệu tập trung. Tuy nhiên, mô hình dữ liệu lược đồ toàn cục cần phải tương thích với việc định nghĩa các ánh xạ tới các mức của cở sở dữ liệu phân tán. Vì vậy mô 11
13. hình dữ liêu quan hệ sẽ được sử dụng.trong kiến trúc mô hình tham chiếu cơ sở dữ liệu phân tán, định nghĩa một tập các quan hệ toàn cục. Global Schema Fragmentation Schema Allocation Schema Local mapping Local mapping Schema 1 Schema 1 DBMS of site 1 DBMS of site 2 Local databese Local databese At site 1 At site 2 Hình 1.4: Mô hình tham chiếu của cơ sở dữ liệu phân tán 1.7.2 Lược đồ phân mảnh Mỗi quan hệ toàn cục có thể chia thành nhiều phần không chồng lặp lên nhau được gọi là phân mảnh. Ánh xạ giữa các quan hệ toàn cục và phân mảnh được định nghĩa là lược đồ phân mảnh. Ánh xạ này là mối quan hệ một-nhiều. Ví dụ, nhiều phân mảnh tương ứng với một quan hệ toàn cục, nhưng chỉ một quan hệ toàn cục tương ứng với một phân mảnh. Các phân mảnh được chỉ ra bằng tên của quan hệ toàn cục với một chỉ số (chỉ số phân mảnh), ví dụ, Ri chỉ đến phân mảnh thứ i trong quan hệ toàn cục R Các kiểu phân mảnh dữ liệu bao gồm phân mảnh ngang và phân mảnh dọc và một kiểu phân mảnh phức tạp hơn là sự hết hợp của 2 loại trên. Trong tất cả các kiểu phân mảnh, một phân mảnh có thể được định nghĩa bằng một biểu thức ngôn ngữ quan hệ cho các quan hệ toàn cục như là các toán hạng và kết quả đầu ra là các phân mảnh. 1.7.3 Lược đồ cấp phát Các phân mảnh là những phần logic của các quan hệ toàn cục được chứa ở một hay nhiều site trong mạng. Lược đồ cấp phát xác định các phân mảnh được chứa ở những site nào. Tất cả các phân mảnh tương ứng với cùng một quan hệ R và được lưu ở dùng một site j tạo thành một mô hình vật lý của quan hệ toàn cục lên site j. Do đó, có một ánh xạ một-một giữa một 12
14. mô hình vật lý và một cặp là một quan hệ toàn cục được định danh và một chỉ số site tương ứng với một mô hình vật lý. Ký hiệu Rji tương ứng với mô hình vật lý mảnh thứ i của quan hệ R trên site j. Một ví dụ của quan hệ giứa các kiểu đối tượng được định nghĩa như trên được biểu diễn trong hình sau. Một quan hệ toàn cục R chia thành 4 phân mảnh R1, R2, R3, R4. Bốn phân mảnh này được cấp phát dư tại 3 site của mạng máy tính, vì thế tạo nên ba mô hình vật lý R1 site 1, R2 site 2 và R3.site 3 Hình 1.5: Các phân mảnh và mô hình vật lý cho một quan hệ toàn cục Có thể định nghĩa một bản sao của một phân mảnh tại một site cho trước và kí hiệu bằng tên quan hệ toàn cục R và hai chỉ số. Ví dụ R32 để chỉ bản sao của phân mảnh R2 được chứa ở site 3. Hai mô hình vật lý có thể giống nhau, ví là bản sao của nhau Lược đồ các site phụ thuộc: gồm lược đồ ánh xạ cục bộ, DBMS của các site cục bộ, cơ sở dữ liệu ở site đó. 1.7.4 Lược đồ ánh xạ cục bộ Do ba mức đầu các site độc lập, do đó chúng không phụ thuộc vào mô hình dữ liệu của DBMS cục bộ. Ở mức thấp hơn, nó cần phải ánh xạ mô hình vật lý thành các đối tượng được thao tác bởi các DBMS cục bộ. Ánh xạ này được gọi là lược đồ ánh xạ cục bộ và phụ thuộc vào kiểu của DBMS cục bộ. Trong hệ thống không đồng nhất có các kiểu khác nhau của ánh xạ cục bộ tại các site khác nhau. Yếu tố quan trong nhất để thiết kế kiến trúc này là: • Phân mảnh và phân phát dữ liệu • Quản lí dư thừa dữ liệu • Sự độc lập của các DBMS cục bộ 13
15. 1.7.5 DBMS ở các site cục bộ dộc lập Tính năng trong suốt trong ánh xạ cục bộ cho phép xây dựng một hệ thống cơ sở dữ liệu phân tán đồng nhất hoặc không đồng nhất. Trong hệ thống đồng nhất, các lược đồ độc lập của một site được định nghĩa sử dụng cùng một mô hình như DBMS cục bộ nhưng trong hệ thống không đồng nhất thì các lược đồ ánh xạ cục bộ dùng để phối hợp các kiểu khác nhau của DBMS 1.8 CẤU TRÚC LOGIC CỦA CƠ SỞ DỮ LIỆU PHÂN TÁN Có 3 kiểu thiết kế cơ sở dữ liệu phân tán trên mạng máy tính. a) Các bản sao: Cơ sở dữ liệu được sao chép thành nhiều bản và được lưu trữ trên các site phân tán khác nhau của mạng máy tính. b) Phân mảnh: Cơ sở dữ liệu được phân thành nhiều mảnh nhỏ theo kỹ thuật phân mảnh dọc hoặc phân mảnh ngang, các mảnh được lưu trữ trên các site khác nhau. c) Mô hình kết hợp các bản sao và phân mảnh. Trên một số site chứa cấc bản sao, một số site khác chứa các mảnh 1.9 LỢI ÍCH PHÂN TÁN DỮ LIỆU TRÊN MẠNG 1. Việc phân tán dữ liệu tạo cho cơ sở dữ liệu có tính tự trị địa phương. Tại một site, dữ liệu được chia sẻ bởi một nhóm người sử dụng tại nơi họ làm việc và như vậy dữ liệu được kiểm soát cục bộ, phù hợp đối với những tổ chức phân bố tập trung. Cho phép thiết lập và bắt buộc sách lược địa phương đối với việc sử dụng cơ sở dữ liệu. Database Tow er System Application Application Server Network Network Tow er System Application Tow er System Middleware Server Database Server Application Tow er System Application Server Hình 1.6 Mô hình Client-Server nhiều lớp 2. Tính song song trong các hệ cơ sở dữ liệu phân tán có thể nâng cao được hiệu quả truy nhập. Tính chất này có thể lợi dụng để xử lý song song các câu hỏi. Có hai dạng : • Câu hỏi đồng thời phát sinh tại các trạm khác nhau. 14
16. • Câu hỏi có thể được phân rã thành những câu hỏi thành phần được thực hiện song song tại các trạm khác nhau. 3. Trong tổ chức phân tán, tương tranh dịch vụ, CPU, vào/ra ít hơn so với tổ chức tập trung. Độ trễ trong truy nhập từ xa có thể giảm do việc thực hiện địa phương hoá dữ liệu một cách hợp lý. 4. Độ tin cậy và tính sẵn sàng được nâng cao trong tổ chức phân tán, là một trong những mục tiêu cơ bản của tổ chức dữ liệu phân tán. Việc tổ chức lặp dữ liệu cũng có thể đảm bảo cho việc truy nhập cơ sở dữ liệu không bị ảnh hưởng khi có sự cố xảy ra đối với trạm hoặc kênh truyền, không thể làm sụp đổ cả hệ thống. 5. Tổ chức dữ liệu phân tán kinh tế hơn so với tổ chức tập trung. Giá cho một hệ máy tính nhỏ rẻ hơn nhiều so với giá của một máy tính lớn khi triển khai cùng một mục đích ứng dụng. Giá chi phí truyền thông cũng ít hơn do việc địa phương hoá dữ liệu. 6. Khả năng mở rộng hệ thống và phân chia tài nguyên. Việc mở rộng khả năng cho một hệ xử lý phân tán là dễ dàng hơn và cho phép thực hiện tốt hơn. 1.10 HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU QUAN HỆ 1.10.1 Kiến trúc tổng quát Hệ quản trị cơ sở dữ liệu quan hệ DBMS là một hệ thống phần mềm hỗ trợ mô hình quan hệ và ngôn ngữ quan hệ. DBMS khi thực hiện các giao dịch cần phải giao tiếp với 2 thành phần khác, đó là thành phần các hệ thống con truyền thông (Communication subsystem) và hệ điều hành (Operating system). Các hệ thống con truyền thông cho phép DBMS giao tiếp với các hệ thống truyền thông khác thông qua các ứng dụng. Hệ điều hành cung cấp giao diện giữa DBMS với các tài nguyên của máy. Kiến trúc tổng quát của hệ quản trị cơ sở dữ liệu quan hệ được mô tả trong hình 2.9 dưới đây. Ứng dụng 1 Ứng dụng 2 Ứng dụng n Hệ thống con truyền thông Hệ qủn trị cơ sở dữ liệu Hệ điều hành Cơ sở dữ liệu Hình 1.7: Kiến trúc tổng quát của mô hình hệ quản trị cơ sở dữ liệu quan hệ 15
17. 1.10.2 Chức năng của hệ quản trị cơ sở dữ liệu quan hệ Chức năng của hệ quản trị cơ sở dữ liệu quan hệ được phân thành nhiều tầng. Bao gồm các tầng giao diện, điều khiển, biên dịch, thực thi, tầng truy xuất dữ liệu và tầng duy trì nhất quán dữ liệu. Tầng giao diện (Interface Layer): có chức năng quản lý giao diện với các các ứng dụng như giao diện trong SQL và các ứng dụng CSDL thực hiện trên các khung nhìn dữ liệu. Khung nhìn sẽ mô tả cách nhìn dữ liệu của các ứng dụng, là một quan hệ ảo dẫn xuất từ quan hệ cơ sở bằng cách áp dụng các phép đại số quan hệ. Việc quản lý khung nhìn bao gồm việc biên dịch câu vấn tin của người sử dụng thành dữ liệu khái niệm. Các ứng dụng Giao diện người sử dụng Tầng giao diện QuCácản lýứng khung dụng nhìn Phép tính quan hệ Kiểm soát toàn vẹn dữ liệu Tầng điều khiển Kiểm soát cấp quyền Các k Phép tính quan hệ ế t qu Phân rã và tối ưu hoá vấn tin ả Tầng xử lý vấn tin Quản lý hoạch định truy xuất Đại số quan hệ Điều khiển thực thi hoạch định truy xuất Tầng thực thi Thực thi phép toán đại số Truy xuất/cập nhật Quản lý vùng đệm Tầng truy xuất dữ liệu Các phương pháp truy xuất Truy xuất/cập nhật Điều khiển đồng thời Tầng duy trì nhất quán Nhật ký CSDL Hình 1.8: Các tầng chức năng của một hệ quản trị cơ sở dữ liệu quan hệ 16
18. Tầng điều khiển (Control Layer): Có chức năng điều khiển câu vấn tin bằng cách thêm các vị từ toàn vẹn dữ liệu và các vị từ cấp quyền truy nhập. Toàn vẹn dữ liệu và cấp quyền truy nhập đặc tả bằng các phép tính quan hệ. Kết quả của tầng này là câu vấn tin được biểu diễn bằng phép tính quan hệ. Tầng xử lý vấn tin (Query Proccessing layer): Có chức năng ánh xạ câu vấn tin thành biểu thức đại số quan hệ - các chuỗi thao tác được tối ưu hoá. Tầng này có liên quan đến hiệu năng CSDL. Phân rã câu vấn tin thành một cây đại số, gồm các các phép toán đại số quan hệ. Kết quả sẽ được lưu trong một hoạch định truy xuất. Kết xuúat của tầng này là câu vấn tin được biểu diễn bằng đại số quan hệ. Tầng thực thi (Execution Layer): Chịu trách nhiệm hướng dẫn việc thực hiện các hoạch định truy xuất, bao gồm các việc quản lý giao dịch và đồng bộ hoá các phép toán đại số quan hệ. Biên dịch các phép toán đại số quan hệ bằng cách gọi tầng truy xuất dữ liệu qua các yêu cầu truy xuất và cập nhật. Tầng truy xuất dữ liệu (Data Access Layer): Tầng này thực hiện việc quản lý cấu trúc dữ liệu cài đặt các quan hệ. Quản lý các vùng đệm bằng cách lưu trữ tạm các dữ liệu thường được truy xuất nhiều nhất. Sử dụng tầng truy xuất dữ liệu làm giảm thiểu việc truy xuất dữ liệu trên đĩa từ. Tầng duy trì nhất quán (Consistency Layer): Chức năng của tầng này là điều khiển các hoạt động đồng thời và ghi nhật ký các yêu cầu cập nhật. Cho phép khôi phục lại các giao dịch, hệ thống và thiết bị sau khi bị sự cố. 1.11 TỔNG QUAN VỀ HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU PHÂN TÁN (Database Distributed Managment System) 1.11.1 Mở đầu Một cách trực quan, một CSDL phân tán là một bộ sưu tập các loại dữ liệu có liên kết logic với nhau và được phân bố vật lý trên nhiều máy chủ của mạng máy tính. Khái niệm hệ CSDLPT bao gồm cả khái niệm CSDL và hệ quản trị CSDLPT. Định nghĩa này nhấn mạnh hai khía cạnh quan trọng của CSDLPT: • Tính phân tán: thực tế dữ liệu không cư trú trên cùng một site, vì vậy có thể phân biệt một CSDLPT với cơ sở dữ liệu tập trung (CSDLTT). • Sự tương quan logic: các loại dữ liệu có một số tính chất ràng buộc lẫn nhau, như vậy có thể phân biệt CSDLPT với tập các CSDL địa phương hoặc với các tệp lưu trữ trên các site khác nhau. Hệ quản trị CSDL phân tán là hệ thống phần mềm cho phép quản trị CSDL phân tán và làm cho sự phân tán đó là trong suốt đối với người sử dụng. Nói cách khác CSDL phân tán là CSDL được phân tán một cách vật lý nhưng được thống nhất tổ chức như là một CSDL duy nhất. Như vậy sự phân tán dữ liệu là trong suốt đối với người sử dụng. Việc quản lý các dữ liệu phân tán đòi hỏi mỗi trạm (site) cài đặt các thành phần hệ thống sau: 17
19. • Thành phần quản trị CSDL (Database Management DM) • Thành phần truyền dữ liệu (Data Communication DC) • Từ điển dữ liệu (Data Dictionary DD): thông tin về sự phân tán dữ liệu trên mạng • Thành phần CSDLPT (Distributed Database DDB) Các dịch vụ của hệ thống trên bao gồm: • Các ứng dụng truy nhập CSDL từ xa . • Cung cấp các mức trong suốt phân tán. • Hỗ trợ quản trị và điều khiển CSDL, bao gồm các bộ công cụ, thu thập thông tin từ các trình tiện ích, cung cấp cách nhìn tổng quan về các file dữ liệu trên mạng. • Khả năng mở rộng với các hệ thống khác nhau • Cung cấp khả năng điều khiển đồng thời và phục hồi các giao tác phân tán. Trình quản lý các ứng dụng Trình quản lý các ứng dụng Trình quản lý Trình quản lý Trình quản lý Trình quản lý dữ liệu phân tán truyền thông Network dữ liệu phân tán truyền thông Hệ quản trị CSDL phân tán Hệ quản trị CSDL phân tán Databas Database Hình 1.9 Hệ quản trị CSDL phân tán Các hệ QTCSDL phân tán thường hỗ trợ về điều khiển tương tranh và khôi phục các tiến trình phân tán. Khả năng truy cập từ xa có thể thực hiện được bằng 2 cách. Cách thứ nhất (hình 1.10a) trình ứng dụng yêu cầu truy cập từ xa. Yêu cầu này được định tuyến tự động bởi DDBMS tới máy chủ chứa dữ liệu. Được thực hiện tại máy chủ chứa cơ sở dữ liệu và gửi lại kết quả. về trạm yêu cầu. Cách tiếp cận này được sử dụng cho truy cập từ xa, trong suốt phân tán có thể thực hiện được bằng việc cung cấp các file chung (global) và các truy nhập trước đó có thể địa chỉ hoá một cách tự động tới các trạm ở xa. Hình 1.10 b chỉ ra một cách tiếp cận khác, chương trình phụ thực hiện tại các trạm ở xa (người lập trình phải tự lập), các kết quả trả lại cho chương trình ứng dụng. 18
20. Hệ quản trị CSDL phân tán hỗ trợ cả hai cách tiếp cận trên. Mỗi một cách tiếp cận đều có những thuận lợi và khó khăn riêng. Giải pháp thứ nhất cung cấp khả năng trong suốt phân tán cao hơn, trong khi giải pháp thứ hai có thể hiệu quả hơn nếu như có rất nhiều chương trìnắtngs dụng cùng yêu cầu truy nhâp, bởi vì các chương trình phụ có thể thực hiện các yêu cầu từ các trạm ở xa và trả lại kết quả. Yêu cầu truy nhập 1 Chương trình Hệ quản trị Site 1 ứng dụng CSDL 1 6 Trả kết quả 5 2 3 Hệ quản trị Site 2 CSDL CSDL 2 4 Hình 1.10a Truy nhập CSDL từ xa Chương trình Hệ quản trị ứng dụng CSDL 1 Site 1 Chương trình Hệ quản trị ứng dụng CSDL 2 CSDL Site 2 Hình 1.10b Truy nhập từ xa bằng chương trình phụ 1.11.2 Hệ quản trị CSDL phân tán thuần nhất CSDLPT có được bằng cách chia một CSDL thành một tập các CSDL cục bộ (Local) và được quản lý bởi cùng một hệ QTCSDL, trong hình 2.13 CSDLPT có thuần nhất hay không được phụ thuộc bởi các yêu tố phần cứng, hệ điều hành và các hệ quản trị CSDL cục bộ. Tuy nhiên, hạn chế quan trọng tại hệ QTCSDL cục bộ, bởi vì nó phụ thuộc vào sự quản lý hệ điều hành mạng truyền thông 1.11.3 Hệ quản trị CSDL phân tán không thuần nhất CSDLPT không thuần nhất được tích hợp bởi một tập các CSDL cục bộ được quản lý bởi các hệ QTCSDL khác nhau. Hệ QTCSDLPT không thuần nhất thêm việc chuyển đổi các mô hình dữ liệu của các hệ QTCSDL khác nhau để thống nhất việc quản lý. Hình 14 19
21. Hệ quản trị CSDL phân tán Hệ QTCSDL Hệ QTCSDL Hệ QTCSDL Databa Databa Databa Hình 1,11 Kiến trúc mô hình hệ QTCSDLPT thuần nhất Hệ quản trị CSDL1 Hệ quản trị CSDL2 Hệ quản trị CSDL3 Database Database Database Hình 1.12 Kiến trúc mô hình hệ QTCSDLPT không thuần nhất Nếu việc phát triển CSDL phân tán theo mô hình Top-down, không phụ thuộc vào hệ thống trước đó (hệ thống các CSDL cục bộ), thì việc phát triển một hệ thuần nhất là tốt nhất. Tuy nhiên, trong một số trường hợp cần xây dựng CSDL phân tán từ các CSDL đã có thì đòi hỏi phải phát triển một hệ không thuần nhất. Phương pháp tốt nhất là tiếp cận từ dưới lên (Bottum-up). Trình quản lý dữ liệu phân tán phải cung cấp các giao diện trao đổi giữa các hệ QTCSDL . Vấn đề quản trị CSDL phân tán không thuần nhất rất khó khăn. 1.12 MÔ HÌNH KIẾN TRÚC HỆ QUẢN TRỊ CSDL PHÂN TÁN Có ba kiểu kiến trúc tham chiếu cho hệ quản trị CSDL phân tán , đó là hệ Client Server, hệ quản trị CSDL phân tán kiểu ngang hàng (Peer-to-Peer) và hệ đa CSDL. 20
22. Các lựa chọn cài đặt một hệ quản trị CSDLđược tổ chức hệ thống theo các đặc tính: (1) tính tự trị, (2) tính phân tán, (3) tính hỗn hợp (không thuần nhất) của hệ thống. 1.12.1 Tính tự vận hành Tính tự vận hành hay còn gọi là tính tự trị, được hiểu là sự phân tán quyền điều khiển. Là mức độ hoạt động độc lập của từng hệ quản trị CSDL riêng lẻ. Tính tự vận hành được biểu hiện qua chức năng của một số yếu tố, như sự trao đổi thông tin giữa các hệ thống thành viên với nhau, thực hiện giao dịch độc lập/ không đôck lập và có được phép sửa đổi chúng hay không. Yêu cầu của hệ thống tự vận hành được xác định theo nhiều cách. Ví dụ, • Các thao tác cục bộ của hệ quản trị CSDL riêng lẻ không bị ảnh hưỏng khi tham gia hoạt động trong hệ đa CSDL (Multi Database System). • Các hệ quản trị CSDL xử lý và tối ưu truy vấn cũng không bị ảnh hưởng bởi thực thi truy vấn toàn cục truy nhập nhiều hệ CSDL. • Tính nhất quán của hệ thống hoặc thao tác không bị ảnh hưởng khi các hệ quản trị CSDL riêng lẻ kết nối hoặc tách rời khỏi tập các CSDL. Ph©n t¸n d÷ liÖu (A0, D2, H0) (A2, D2, H1) TÝnh tù trÞ TÝnh hçn hîp Hình 1.13. Lựa chọn cài đặt hệ quản trị CSDL Mặt khác, xác định chiều của tính tự trị như sau: 1. Tự trị thiết kế: Mỗi hệ quản trị CSDL riêng lẻ có thể sử dụng mô hình dữ liệu và kỹ thuật quản lý giao dịch theo ý muốn. 2. Tự trị truyền thông: Mỗi hệ quản trị CSDL riêng lẻ tuỳ ý đưa ra quyết định của nó về loại thông tin mà nó cần cung cấp cho các hệ quản trị CSDL khác hoặc phần mềm điều khiển thực thi toàn cục của nó. 3. Tự trị thực thi: Mỗi hệ quản trị CSDL có thể thực thi các giao dịch được gửi tới nó theo bất kỳ cách nào mà nó muốn. 21
23. Ba lựa chọn xem xét ở trên cho các hệ thống tự trị không phải là những khả năng duy nhất, mà là ba lựa chọn phổ biến nhất. 1.12.2 Tính phân tán dữ liệu Tính phân tán dữ liệu: Tính tự vận hành đề cập đến việc phân tán quyền điều khiển, thì tính phân tán dữ liệu đề cập đến dữ liệu. Hiển nhiên, sự phân tán vật lý của dữ liệu trên nhiều vị trí khác nhau. Người sử dụng nhìn dữ liệu bằng khung nhìn dữ liệu. Có hai cách phân tán dữ liệu: phân tán kiểu Client/Server và phân tán kiểu ngang hàng. Kết hợp với các tùy chọn không phân tán, trục kiến trúc cho ba loại kiến trúc khác nhau. • Phân tán kiểu Client/Server ngày càng phổ biến. Quản trị dữ liệu tại Server, Client cung cấp môi trường ứng dụng và giao diện người sử dụng. Nhiệm vụ truyền thông được chia sẻ giữa các Client và Server. Hệ quản trị CSDL kiểu Client/Server là hệ phân tán chức năng. Có nhiều cáchễuây dựng, mỗi cách cung cấp một mức độ phân tán khác nhau. • Trong kiểu ngang hàng không có sự khác biệt giữa chức năng Client và Server. Mỗi máy đều có đầy đủ chức năng của hệ quản trị CSDL và có thể trao đổi thông tin với các máy khác để thực hiện các truy vấn và giao dịch. Các hệ thống này cũng được gọi là phân tán đầy đủ, 1.12.3 Tính hỗn hợp Tính hỗn hợp: Từ khác biệt về phần cứng và các giao thức mạng đến khác biệt trong cách quản lý dữ liệu, có một số dạng hỗn hợp trong các hệ phân tán. Sự khác biệt lớn nhất liên quan đến các mô hình dữ liệu, ngôn ngữ truy vấn và giao thức quản lý giao dịch. Biểu diễn dữ liệu bằng nhiều mô hình khác nhau tạo ra tính hỗn hợp. Tính hỗn hợp trong ngôn ngữ truy vấn không chỉ bao gồm việc sử dụng các dạng truy nhập dữ liệu khác nhau trong các mô hình dữ liệu khác nhau , mà còn bao gồm những khác biệt trong các ngôn ngữ ngay cả khi sử dụng cùng một mô hình dữ liệu. Ngôn ngữ truy vấn khác nhau sử dụng cùng một mô hình dữ liệu thường chọn các phương pháp khác nhau để diễn tả các yêu cầu giống nhau, ví dụ, DB2 sử dụng SQL, trong khi INGRES sử dụng QUEL. 1.12.4 Các kiểu kiến trúc Xem xét các kiến trúc trong hình 2.15, bắt đầu từ gốc và di chuyển theo trục tự trị. Ký hiệu A là tự trị, D là phân tán và H là hỗn hợp. Các kiểu trên trục tự trị được định nghĩa, A0 là biểu diễn tích hợp chặt chẽ,A1 biểu diễn hệ bán tự trị và A2 biểu diễn hệ cô lập. Trên trục phân tán, D0 nghĩa là không phân tán, D1 là hệ Client/Server, và D2 là phân tán ngang hàng. Trên trục hỗn hợp, H0 xác định các hệ thống thuần nhất, H1 là các hệ hỗn hợp. Trong hình 2.15 định nghĩa hai loại kiến trúc: (A0, D2, H0) là hệ quản trị CSDL thuần nhất phân tán (ngang hàng) và (A2, D2, H1) là phức hệ CSDLhỗn hợp, phân tán ngang hàng. • Loại kiến trúc (A0, D0, H0): Được gọi là hệ thống phức hợp (Composite System). Nếu không phân tán dữ liệu và hỗn hợp, thì hệ thống chỉ là một tập gồm nhiều hệ quản trị CSDL được tích hợp về mặt lôgic. Phù hợp với các hệ thống đa xử lý và tài nguyên đều dùng chung. Kiểu này không xuất hiện nhiều trong thực tế 22
24. • Loại kiến trúc (A0, D0, H1): Nếu hỗn hợp thì phải có nhiều bộ quản lý dữ liệu hỗn hợp có thể cung cấp một khung nhìn tích hợp cho người sử dụng. Trước đây được thiết kế truy nhập tích hợp CSDL mạng, phân cấp và quan hệ trên cùng một máy đơn. • (A0, D1, H0):Trường hợp CSDL phân tán khi có một khung nhìn tích hợp về dữ liệu cung cấp cho người sử dụng. Hệ thống loại này thích hợp cho phân tán Client/Server. • (A0, D2, H0): Biểu diễn môi trường phân tán hoàn toàn trong suốt cung cấp cho người sử dụng. Không phân biệt giữa Client và Server, cung cấp đầy đủ các chức năng. • (A1, D0, H0): Là dạng các hệ thống bán tự trị. Các hệ thống thành viên có quyền tự trị nhất định trong các hoạt động của chúng. Kiến trúc này sử dụng thiết lập bộ khung cho hai dạng kiến trúc kế tiếp. Trong thực tế rất ít sử dụng • (A1, D0, H1): Là hệ thống hỗn hợp và tự trị., rất phổ biến hiện nay. Một ví dụ hệ thống loại này bao gồm một hệ quản trị CSDL quan hệ quản lý dữ liệu có cấu trúc, một hệ quản trị CSDL xử lý hình ảnh tĩnh và một Server cung cấp video. Để cung cấp hình ảnh tích hợp cho người sử dụng, cần phải che dấu tính tự động và tính hỗn hợp của các hệ thống thành viên và thiết lập một giao diện chung. • (A1, D1, H1): Trong các hệ thống loại này, các hệ thống thành viên được cài đặt trên các máy khác nhau. Được gọi là các hệ quản trị CSDL hỗn hợp phân tán. Đặc điểm phân tán ít quan trọng hơn so với tính tự trị và hỗn hợp. Các hệ quản trị CSDL kiểu (A0, D1, H0) và (A0, D2, H0) có thể giải quyết những vấn đề khó khăn khi phân tán dữ liệu • (A2, D0, H0): Đặc điểm của các hệ thống loại này là các thành viên không có khái niệm thỏa hiệp và không biết cách liên lạc với nhau. Nếu không có tính hỗn hợp hoặc tính phân tán thì một phức hệ CSDL chỉ là một tập các CSDL tự trị được kết nối với nhau. Hệ quản trị phức hệ CSDL cho phép quản lý tập hợp các CSDL tự trị và cho phép truy nhập trong suốt đến nó. Dạng hệ thống này ít thực tế. • (A2, D0, H1): Hệ thống loại này có tính thực tế cao, hơn cả (A1, D0, H1).Có khả năng xây dựng các ứng dụng truy nhập dữ liệu từ nhiều hệ thống lưu trữ khác nhau với các đặc tính khác nhau. Có thể là những hệ thống lưu trữ không phải là hệ quản trị CSDL và không được thiết kế phát triển có thể tương tác với các phần mềm khác. Cũng như trong hệ (A1, D0, H1), giả thiết các hệ thống thành viên không tham gia vào toàn bộ hệ thống. • (A2, D1, H1) và (A2, D2, H1): Hai trường hợp này đều biểu diễn cho trường hợp các CSDL thành viên tạo ra phức hệ CSDLđược phân tán trên mọt số vị trí – gọi là các phức hệ CSDL phân tán. Cả hai trường hợp các giải pháp phân tán và xử lý tương tác tương tự nhau. Trong trường hợp phân tán Client/Server (A2, D1, H1), các vấn đề tương tác được trao cho hệ thống trung gian (Middleware System), tạo ra kiến trúc ba tầng. Tổ chức của một phức hệ CSDL phân tán và việc quản lý nó hoàn toàn khác với các hệ quản trị CSDL phân tán. Sự khác biệt cơ bản của chúng là ở mức độ tự trị của các chương trình quản lý dữ liệu cục bộ. Các phức hệ CSDL phân tán hoặc tập trung đều có thể thuần nhất hoặc hỗn hợp, không thuần nhất 23
25. Sự phân tán, tính hỗn hợp và tính tự trị của CSDL là các vấn đề liên quan đến nhau. Mục tiêu của tài liệu là các hệ phân tán nên chú ý nhiều hơn tính hỗn hợp và tính tự trị. 1.13 KIẾN TRÚC HỆ QUẢN TRỊ CSDL PHÂN TÁN Phần này sẽ xem xét chi tiết ba kiến trúc hệ thống trong số các kiến trúc đã được trình bày ở trên. Ba loại kiến trúc là: • Hệ Client/Server, bỏ qua các vấn đề hỗn hợp và tự trị có dạng (Ax, D1, Hy). • Các CSDL phân tán, ứng với (A0, D2, H0). • Hệ đa CSDL, ứng với (A2, Dx, Hy). 1.13.1 Các hệ Client/Server Các hệ quản trị CSDL Client/Server cung cấp kiến trúc hai lớp chức năng Server và chức năng Client, nhằm tạo ra sự dễ dàng trong việc quản lý tính phức tạp của các hệ quản trị CSDL hiện đại và tính phức tạp của việc phân tán dữ liệu Server thực hiện hầu hết các công việc quản lý dữ liệu. Nghĩa là tất cả mọi xử lý và tối ưu hoá truy vấn, quản lý giao dịch và quản lý lưu trữ đều được thực hiện trên Srver. Client, ngoài ứng dụng và giao diện người sử dụng, có một module hệ quản trị CSDL Client trách nhiệm quản lý dữ liệu và khóa giao dịch được gửi đến Client. Client và Server trao đổi với nhau bởi các câu lệnh SQL. Cụ thể hơn, Client chuyển truy vấn SQL đến Server, Server sẽ thực hiện và trả lại kết quả cho Client. Loại kiến trúc Client/Server đơn giản chỉ có một Server được truy nhập bởi nhiều Client, gọi là đa Client-một Server. Việc quản lý dữ liệu không khác so với CSDL tập trung. CSDL được lưu chỉ trên Server và có phần mềm quản lý nó. Tuy nhiên, sự khác biệt quan trọng so với các hệ thống tập trung là cách thực thi giao dịch và quản lý bộ nhớ Cache. Loại kiến trúc có nhiều Server trong hệ thống, được gọi là đa Client-đa Server. Có hai chiến lược quản lý: hoặc Client quản lý kết nối của nó tới Server hoặc Client chỉ biết Server chủ của nó và liên lạc với các Server khác qua Server chủ khi có yêu cầu. Chiến lược thứ nhất làm đơn giản cho các Server, nhưng lại gắn thêm nhiều trách nhiệm cho các máy Client. Điều này dẫn đến một hệ thống được gọi là hệ máy khách tự phục vụ. Mặt khác, với chiến lược thứ hai, tập trung vào chức năng quản lý dữ liệu tại Server. Vì vậy, tính trong suốt của truy nhập dữ liệu được cung cấp tại giao diện Server. Mô hình CSDLlogic Client/Server là duy nhất. Mô hình mức vật lý của nó có thể phân tán. Vì vậy phân biệt giữa Client/Server và ngang hàng không phải ở mức độ trong suốt được cung cấp cho người sử dụng và cho ứng dụng mà ở mô hình kiến trúc được dùng để nhận ra mức độ trong suốt 24
26. Operating Giao diện Chương trình Systemh người sử dụng ứng dụng Hệ quản trị CSDL Client Phần mềm truyền thông Kếtquả SQL truy vấn truy vấn Phần mềm truyền thông Bộ điều khiển dữ liệu ngữ nghĩa Operating Bộ tối ưu hoá truy vấn Bộ quản lý giao dịch Bộ quản lý khôi phục Bộ xử lý hỗ trợ thời gian thực hiện Hệ thống CSDL Hình 1.14 Kiến trúc tham chiếu Client/Server 1.13.2 Các hệ phân tán ngang hàng( Peer to Peer) Trước tiên khảo sát về tổ chức dữ liệu vật lý trong các hệ mgamg hàng. Tổ chức lưu trữ trên các máy khác nhau có thể khác mhau. Điều này có nghĩa là cần phải có một định nghĩa nội tại riêng cho mỗi vị trí, được gọi là lược đồ nội tại cục bộ LIS (Local Internal Schema). Lược đồ khái niệm toàn cục mô tả cấu trúc logic của dữ liệu ở mọi vị trí. Dữ liệu trong một CSDL phân tán thường được phân mành và nhân bản trên các vị trí khác nhau. Vì vậy cần phải mô tả tổ chức lưu trữ dữ liệu vật trên mọi vị trí. Cần bổ sung thêm tầng thứ trong kiến trúc cơ sở dữ liệu 3 mức, đó là lược đồ khái niệm cục bộ LCS (Local Conceptual Schema). Vì vậy lược đồ khái niệm toàn cục GCS (Global Conceptual Schema) là hợp của các lược đồ khái niệm cục bộ. Mức trên cùng là khung nhìn dữ liệu của người sử dụng, lược đồ ngoài ES (External Schema). Người sử dụng khác nhau có cách nhìn dữ liệu cũng khác nhau. Như vậy kiến trúc của hệ cơ sở dữ liệu phân tán có 3 mức: Có nhiều khung nhìn dữ liệu khác nhau trong mức lược đồ ngoài, nhưng chỉ có duy nhất một mô hình khái niệm toàn cục và có nhiều mô hình khái niệm cục bộ, ứng với lược đồ trong cục bộ trên mỗi vị trí. 25
27. ES1 ES2 ESn GCS LCS1 LCS2 LCSn LIS1 LIS2 LISn Hình 1.15 Kiến trúc tham chiếu CSDL phân tán. Mô hình trong hình 1.15 được mở rộng từ mô hình ANSI/SPARC. Nó phản ảnh tính trong suốt và tính độc lập dữ liệu .Trong suốt định vị và trong suốt nhân bản được hỗ trợ bằng các lược đồ khái niệm cục bộ và toàn cục và ánh xạ giữa chúng. Mặt khác, trong suốt mạng được hỗ trợ bằng lược đồ khái niệm toàn cục. Người sử dụng truy vấn dữ liệu không cần biết đến vị trí hay các thành phần CSDLcục bộ. Hệ quản trị CSDL phân tán dịch truy vấn toàn cục thành các nhóm truy vấn cục bộ và được thực hiện bởi các thành phần quản trị CSDL phân tán tại các trạm khác nhau và giữa các trạm giao tiếp với nhau. Mô hình đang xét là mô hình ANSI/SPARC được mở rộng bằng cách thêm vào từ điển/thư mục toàn cục GD/D (Glocal Directory/Directionary) cho phép ánh xạ yêu cầu toàn cục. Ánh xạ cục bộ được thực hiện bởi từ điển/thư mục cục bộ LD/D (Local Directory/Directionary). Vì vậy, các thành phần quản lý CSDL cục bộ được tích hợp thành các chức năng của hệ quản trị CSDL toàn cục . Trong hình 1.16 lược đồ khái niệm cục bộ ánh xạ đến lược đồ trong tại mỗi vị trí. Lược đồ khái nhiệm toàn cục ánh xạ vào lược đồ khái niệm cục bộ. Tất cả các định nghĩa khung nhìn của mô hình ngoài đều có phạm vi toàn cục. Các ánh xạ nó đảm bảo cho tính trong suốt của cơ sở dữ liệu phân tán và tính độc lập của cơ sở phân tán. 26
28. Quản trị Xí nghiệp Bộ Bộ quản lý quản lý Bộ xử lý lược đồ hệ thống toàn cục khái niệm toàn cục ứng dụng Bộ xử lý lược đồ GD/D CSDL ngoài Quản lý CSDL cục bộ Qu ản lý CSDL cục bộ Bộ xử lý Bộ quản lý Bộ xử lý Bộ quản lý lược đồ khái CSDL lược đồ khái CSDL niệm CSDL1 toàn cục niệm CSDL1 toàn cục Bộ xử lý Bộ xử lý lược đồ khái lược đồ khái LD/D niệm CSDL1 LD/D niệm CSDL1 Bộ xử lý Bộ xử lý lược đồ khái lược đồ khái niệm trong niệm trong Hình 1.16 sơ đồ chức năng của hệ qu ản trị CSDL phân tán tích hợp 27
29. Ng−êi dïng §¸p øng cña Yªu cÇu cña hÖ thèng ng−êi dïng Bé Xö Lý NG¦êi dïng Bé xö lý giao diÖn ng−êi dïng L−îc ®å ngoµi Bé ®iÒu khiÓn d÷ liÖu ng÷ nghÜa L−îc ®å kh¸i niÖm toµn côc Bé tèi −u hãa truy vÊn toµn côc Bé gi¸m s¸t GD/D thùc thi toµn côc Bé Xö Lý d÷ liÖu L−îc ®å Bé xö lý kh¸i niÖm côc bé truy vÊn côc bé Bé qu¶n lý NhËt ký kh«i phôc côc bé hÖ thèng Bé xö lý hç trî L−îc ®å trong thêi gian thùc thi côc bé Hình 1.17 Các thành phần của một hệ quản trị CSDL phân tán. Một hệ DBMS phân tán gồm 2 phần như trong hình 2.19. Bộ xử lý phía người sử dụng (User Procesor), xử ly tất cả tương tác với người sử dụng và bộ phận thứ 2 của DBMS phân tán là bộ phận xử lý dữ liệu (Data Processor). Bộ xử lý phía người sử dụng bao gồm: 1. Bộ xử lý giao diện người sử dụng: Có trách nhiệm dịch các lệnh của người sử dụng khi họ gửi đến và định dạng dữ liệu kết quả để gửi nó lại cho người sử dụng . 28
30. 2. Bộ kiểm soát dữ liệu ngữ nghĩa: sử dụng ràng buộc toàn vẹn và xác thực, được định nghĩa như là một phần của lược đồ khái niệm cục bộ, để kiểm tra xem truy vấn của người sử dụng có được xử lý hay không. Thành phần này cũng có trách nhiệm xác thực và một số chức năng khác. 3. Bộ phân rã và bộ tối ưu hoá truy vấn toàn cục xác định chiến lược thực thi để giảm thiểu chức năng chi phí, và dịch các truy vấn toàn cục ra thành các truy vấn cục bộ bằng cách sử dụng các lược đồ khái niệm cục bộ, toàn cục và thư mục toàn cục. Bộ tối ưu hoá truy vấn có trách nhiệm tạo ra chiến lược thực thi các hoạt động kết nối phân tán. 4. Bộ giám sát thực thi phân tán phối hợp thực thi phân tán yêu cầu của người sử dụng .Bộ giám sát thực thi cũng được gọi là bộ quản lý giao dịch phân tán. Việc thực thi truy vấn trong hệ phân tán, bộ giám sát thực thi tại một số trạm có thể, và thường, liên lạc với một bộ giám sát thực thi khác. Phần thứ hai của hệ quản trị CSDL phân tán là bộ xử lý dữ liệu gồm ba thành phần: 1. Bộ tối ưu hoá truy vấn cục bộ hoạt động như là bộ chọn đường dẫn truy nhập. Chọn đường truy nhập tốt nhất vào bất kỳ mục dữ liệu nào. 2. Bộ quản lý khôi phục cục bộ có trách nhiệm đảm bảo duy trì tính nhất quán trong CSDL cục bộ ngay cả khi có lỗi xảy ra. 3. Bộ hỗ trợ thời gian thực thi truy nhập vào CSDL tùy vào các lệnh trong lịch biểu được tạo ra bởi bộ tối ưu hóa truy vấn. Bộ xử lý hỗ trợ thời gian thực thi là giao diện với hệ điều hành và chứa bộ quản lý vùng đệm CSDL (buffer hoặc cache), có trách nhiệm quản lý vùng đệm của bộ nhớ chính và quản lý việc truy nhập dữ liệu. 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) 1.14.1 Mô hình kiến truc tổng quan của một phức hệ Một phức hệ phân tán bao gồm nhiều phức hệ quản trị được cài đặt tại nhiều vị trí (site) khác nhau. Mỗi phức hệ tại mỗi vị trí bao gồm hai thành phần chính đó là • Hệ quản trị dữ liệu DBMS (Database Management System) là các hệ quản trị cơ sơ dữ liệu ở mức thấp nhất của hệ thống. Nó có chức năng tổ chức lưu trữ và thực hiện các thao tác vấn tin được chuyển cho nó và trả về kết quả cho hệ thống • Các phức hệ quản trị ( Multi-DataBase Management System) tại mỗi site, các phức hệ này có chức năng quản lý các DBMS thành phần trong hệ thống và các mối tương tác qua lại giưa chúng. Đồng thời nhận và và xử lý các câu vấn tin trước khi chuyển giao cho các DBMS thành phần. Hình 1.18 mô tả mô hình kiến trúc của một phức hệ. 29
31. 1.14.2 Phân loại các phức hệ dựa vào cấu trúc Hệ quản trị phức hệ CSDL phân tán khác với hệ quản trị CSDL phân tán được phản ánh trong định nghĩa lược đồ khái niệm toàn cục. Trong các hệ quản trị CSDL phân tán tích hợp logic, lược đồ khái niệm toàn cục là hợp của các CSDL cục bộ, trong khi đó ở hệ quản trị phức hệ CSDL phân tán chỉ định nghĩa một tập con gồm một số CSDL cục bộ mà các hệ quản trị CSDL cục bộ chia sẻ. Vì vậy định nghĩa CSDL toàn cục đa CSDL có khác với định nghĩa CSDL toàn cục trong hệ quản trị CSDL phân tán. user user Request Repond Request Repond Multi Database Multi Database Management System Management System Database Database Database Database Management Management Management Management System System System System Site 1 Site n Hình 1.18 Mô hình kiến truc tổng quan của một phức hệ phân tán a) Các mô hình sử dụng lược đồ khái niệm toàn cục: Trong một hệ đa CSDL, lược đồ khái niệm toàn cục GCS được định nghĩa bằng cách tích hợp các lược đồ ngoài của các CSDL tự vận hành cục bộ hoặc các thành phần của lược đồ khái niệm cục bộ của chúng. Mặt khác, Vì hệ thống là tự trị, người sử dụng của một DBMS cục bộ sẽ định nghĩa khung nhìn riêng của họ trên CSDL cục bộ và không cần phải thay đổi các ứng dụng khi truy xuất vào các CSDL cục bộ khác. Việc thiết kế lược đồ khái niệm toàn cục GCS trong phức hệ CSDL thường được thực hiện từ dưới lên (Bottom-Up), ánh xạ đi từ lược đồ khái niệm cục bộ đến lược đồ toàn cục (trong khi quản trị CSDL phân tán, việc thiết kế lược đồ khái niệm toàn cục GCS thường được thiết kế từ trên xuống (Top-Down), ánh xạ lại theo hướng ngược lại). Khung nhìn của người sử dụng trên lược đồ quan hệ toàn cục được định nghĩa theo yêu cầu truy nhập toàn cục. Các lược đồ ngoài toàn cục GES (Global External Schema) và lược đồ khái niện toàn cục 30
32. GCS không nhất thiết phải sử dụng theo cùng một mô hình và ngôn ngữ dữ liệu, không cần xác định hệ thống là thuần nhất hay hỗn hợp. Nếu hệ thống là hỗn hợp, thì có hai lựa chọn cài đặt: đơn ngữ (Unilingual) và đa ngữ (Multilingual). • Hệ quản trị phức hệ CSDL đơn ngữ cho phép sử dụng các mô hình và ngôn ngữ dữ liệu khác nhau khi truy xuất CSDL cục bộ và CSDL toàn cục. Bất kỳ ứng dụng nào truy xuất dữ liệu từ các phức hệ CSDL đều phải thực hiện qua một khung nhìn đã được định nghĩa trong lược đồ khái niệm toàn cục, nghĩa là truy xuất CSDL toàn cục khác với truy xuất CSDL cục bộ. Vì vậy, phải định nghĩa lược đồ ngoài cục bộ LES (Local External Schema) trên lược đồ khái niệm cục bộ và lược đồ ngoài toàn cục GES trên lược đồ khái niệm toàn cục. Khung nhìn ngoài khác nhau cũng có thể sử dụng các ngôn ngữ truy nhập khác nhau. Hình 2.21 mô tả mô hình logic của hệ CSDL đơn ngữ tích hợp với lược đồ khái niệm cục bộ trong lược đồ khái niệm toàn cục. • Kiến trúc đa ngữ (Multilingual) cho phép người sử dụng truy nhập tới CSDL toàn cục bằng lược đồ ngoài được định nghĩa bởi ngôn ngữ của hệ quản trị CSDL cục bộ. Định nghĩa GCS trong kiến trúc đơn ngữ và đa ngữ giống nhau. Tuy nhiên định nghĩa các lược đồ ngoàì trong kiến trúc đa ngữ được mô tả bằng ngôn ngữ của lược đồ ngoài của CSDL cục bộ. Truy vấn được xử lý một cách chính xác như truy vấn trong các hệ quản trị CSDL tập trung. Truy vấn CSDL toàn cục được sử dụng ngôn ngữ của hệ quản trị CSDL.Người sử dụng truy vấn CSDL dễ dàng hơn với cách tiếp cận đa ngữ . GES1 GES2 GES3 LES11 LES12 LES13 GCS LESn1 LESn2 LESn3 GES1 GESn LISn LIS1 Hình 1.19 kiến trúc phức hệ CSDL với một lược đồ khái niệm toàn cục. 1.14.3 Các mô hình không sử dụng lược đồ khái niệm toàn cục Một hệ thống có nhiều CSDL nhưng không có lược đồ toàn cục có nhiều ưu điểm hơn, so với hệ thống có lược đồ khái niệm toàn cục. Hình 2.22. mô tả kiến trúc của một mô hình gồm hai tầng: tầng hệ thống cục bộ và tầng phức hệ CSDL. Tầng hệ thống cục bộ gồm một số hệ quản trị CSDL với chức năng là trình bày cho tầng phức hệ CSDL các phần của CSDL cục bộ dùng chung bởi nhiều người sử dụng các CSDL khác. Dữ liệu dùng chung được trình bày bởi 31
33. lược đồ khái niệm cục bộ hoặc qua một định nghĩa lược đồ ngoài cục bộ. Tầng này được trình bày bằng một tập các lược đồ khái niệm cục bộ LCS. Nếu hỗn hợp, mỗi lược đồ LCS có thể sử dụng mỗi mô hình dữ liệu khác nhau. Trên tầng hệ thống cục bộ là tầng hệ đa CSDL, bao gồm các khung nhìn được định nghĩa trên một hay nhiều lược đồ khái niệm cục bộ. Vì vậy có thể cấp quyền truy xuất vào nhiều CSDL bởi ánh xạ giữa khung nhìn và lược đồ khái niệm cục bộ ES1 ES2 ESn Multidatabase Layer Local System Layer LCS1 LCS2 LCSn LIS1 LIS2 LISn Hình 1.20 Kiến trúc phức hệ CSDL không sử dụng GCS Mô hình kiến trúc dựa trên các thành phần của hệ đa CSDL khác biệt nhiều so với một hệ quản trị CSDL phân tán. Khác biệt cơ bản là sự tồn tại của các DBMS hoàn chỉnh quản lý từng CSDL khác nhau. Đa CSDL cung cấp một tầng phần mềm chạy trên những DBMS riêng biệt này và cung cấp cho người dùng những tiện ích để truy xuất nhiều CSDL khác nhau. Tuỳ thuộc vào vấn đề có lược đồ khái niệm toàn cục hoặc là có vấn đề đa chủng hay không, nội dung của tầng phần mềm sẽ thay đổi. hinh 4.10 trình bày một hệ quản trị đa CSDL phi phân tán. nếu là hệ phân tán, chúng ta cần phải sao chép tầng đa CSDL hco mỗi vị trí có hệ quản trị CSDL cục bộ tham gia vào hệ thống. cũng cần chú ý rằng nếu xem xét từng DBMS riêng biệt, tầng phức hệ CSDL chỉ đơn giản là một ứng dụng có nhiệm vụ “đệ trình” các yêu cầu và nhận kết quả trả lời. 32
34. Hình 1.21 Các thành phần của một phức hệ CSDL CÂU HỎI TRẮC NGHIỆM 1. Cơ sở dữ liệu phân tán là sự: A. Hợp nhất lý thuyết cơ sở dữ liệu và công nghệ mạng máy tính. B. Hợp nhất công nghệ viễn thông và tin học. C. Tích hợp công nghệ tin học và cơ sở dữ liệu. 2. Khái niệm hệ cơ sở dữ liệu phân tán bao gồm khái niệm về: A. Cơ sở dữ liệu phân tán và công nghệ mạng máy tính. B. Cơ sở dữ liệu tập trung và tối ưu hoá câu hỏi C. Cơ sở dữ liệu phân tán và hệ quản trị cơ sở dữ liệu phân tán. 3. Cơ sở dữ liệu phân tán là: 33
35. A. Một tập các cơ sở dữ liệu có quan hệ với nhau về mặt logic và được phân tán trên một mạng máy tính. B. Một tập các cơ sở dữ liệu được phân tán trên một mạng máy tính. C. Một tập các cơ sở dữ liệu được cài đặt lưu trữ trên các máy chủ. 4. Hệ quản trị cơ sở dữ liệu phân tán là: A. Hệ thống phần mềm quản trị cơ sở dữ liệu phân tán và làm cho sự phân tán đó là trong suốt đối với người sử dụng. B. Hệ thống phần mềm điều khiển truy nhập cơ sở dữ liệu phân tán . C. Hệ thống phần mềm thực hiện các phép lưu trữ và tìm kiếm dữ liệu trên mạng máy tính. 5. Đặc trưng của cơ sở dữ liệu phân tán là: A. Dữ liệu được phân tán trên mạng máy tính và có quan hệ logic. với nhau B. Tập các file dữ liệu được lưu trữ trên các thiết bị nhớ của mạng máy tính. C. Tập các file dữ liệu có quan hệ với nhau về mặt logic 6. Độc lập dữ liệu được hiểu là: A. Tổ chức lưu trữ dữ liệu là trong suốt đối với người sử dụng dụng. B. Các chương trình ứng dụng không phụ thuộc vào tổ chức lưu trữ dữ liệu. C. Tổ chức lưu trữ dữ liệu trên các máy chủ của mạng 7. Đặc trưng về độc lập dữ liệu trong các hệ cơ sở dữ liệu phân tán là: A. Sự trong suốt phân tán B. Các ứng dụng được phân tán. C. Cơ sở dữ liệu tổ chức lưu trữ tập trung 8. Mô hình cơ sở dữ liệu tập trung: A. Ứng dụng, hệ quản trị CSDL và CSDL được cài đặt trên cùng một bộ xử lý. B. Ứng dụng, hệ quản trị CSDL cài đặt khác hệ thống máy tính với CSDL C. Ứng dụng, hệ quản trị CSDL và CSDL được cài đặt trên các vị trí khác nhau 9. Mô hình cơ sở dữ liệu Client/Server A. CSDL được cài đặt trên Server, các ứng dụng trên các máy Client và phần mềm cơ sở dữ liệu được cài đặt trên cả Client lẫn Server. B. CSDL được cài đặt trên Server, các ứng dụng trên các máy Client C. CSDL, các ứng dụng và hệ quản trị CSDL được cài đặt trên Server 10. Mô hình kiến trúc cơ sở dữ liệu phân tán tại các site gồm: 34
36. A. Lược đồ tổng thể, lược đồ phân mảnh và lược đồ cấp phát. B. Lược đồ khái niệm, lược đồ quan hệ và lược đồ cấp phát. C. Lược đồ tổng thể, lược đồ cục bộ và các chiến lược truy nhập. 11. Lược đồ toàn cục trong cơ sở dữ liệu phân tán được định nghĩa như: A. Lược đồ cơ sở dữ liệu quan hệ B. Lược đồ khái niệm. C. Lược đồ cục bộ 12. Khái niệm phân mảnh cơ sở dữ liệu được hiểu là: A. Quan hệ toàn cục có thể chia thành nhiều mảnh không chồng lặp B. Các quan hệ được cài đặt trên các site khác nhau. C. Các quan hệ được sao chép và cài đặt trên các site khác nhau. 13. Khái niệm cấp phát trong cơ sở dữ liệu phân tán được hiểu là: A. Phương pháp cài đặt các bản sao, phân mảnh trên mạng máy tính B. Phương pháp phân mảnh dữ liệu C. Phương pháp cài đặt cơ sở dữ liệu trên mạng máy tính 14. Các kiểu thiết kế cơ sở dữ liệu phân tán trên mạng máy tính. D. Bản sao, phân mảnh và kết hợp bản sao và phân mảnh. E. Bản sao và phân mảnh F. Phân mảnh 15. Tính tự trị địa phương, nghĩa là A. Dữ liệu được chia sẻ bởi một nhóm người sử dụng, kiểm soát cục bộ. B. Dữ liệu được phân tán trên nhiều vị trí, kiểm soát toàn cục. C. Dữ liệu lưu trữ tập trung. 16. Tính song song trong các hệ cơ sở dữ liệu phân tán nghĩa là: A. Các câu hỏi truyền về vị trí chính và xử lý. B. Xử lý đồng thời các câu hỏi tại các vị trí khác nhau. C. Câu hỏi phân rã thành các câu hỏi thành phần, thực hiện song song tại các vị trí khác nhau. 17. Một trong những ưu điểm cơ bản của tổ chức dữ liệu phân tán là: A. Độ tin cậy và tính sẵn sàng được nâng cao. B. Đảm bảo an toàn cho việc truy nhập cơ sở dữ liệu khi có sự cố xảy, không thể làm sụp đổ cả hệ thống. 35
37. C. Nâng cao hiệu quả 18. Tổ chức dữ liệu phân tán kinh tế hơn so với tổ chức tập trung, vì: A. Giá cho một hệ máy tính nhỏ rẻ hơn B. Hiệu quả hơn khi triển khai cùng một mục đích ứng dụng. C. Giá chi phí truyền thông thấp hơn. 19. Ưu điểm cách tiếp cận mô hình cơ sở dữ liệu quan hệ A. Tính đơn giản, tính độc lập dữ liệu, đối xứng, cơ sở lý thuyết vững chắc. B. Tính đơn giản, tính độc lập dữ liệu và toàn vẹn dữ liệu. C. Tính độc lập dữ liệu và toàn vẹn dữ liệu. 20. Quy tắc toàn vẹn dữ liệu (Integrity Rule) là các quy tắc: A. Ràng buộc các trạng thái nhất quán của dữ liệu. B. Ràng buộc cấu trúc và các ràng buộc về hành vi. C. Các mối quan hệ, ràng buộc lẫn nhau trong cơ sở dữ liệu 21. Kiến trúc tổng quát của một hệ quản trị cơ sở dữ liệu quan hệ là: A. Một hệ thống phần mềm B. Các hệ thống truyền thông và hệ điều hành C. Các hệ thống các ứng dụng. 22. Các tầng chức năng kiến trúc của một hệ QTCSDL quan hệ gồm: A. Tầng giao diện, điều khiển, xử lý vấn tin, thực thi, truy xuất dữ liệu và tầng duy trì nhất quán. B. Tầng ứng dụng, trình bày, giao vận, mạng, liên kết dữ liệu và tầng vật lý. C. Tầng điều khiển, xử lý vấn tin, và tầng truy xuất dữ liệu. 23. Hệ quản trị CSDL phân tán thuần nhất, nghĩa là A. CSDL phân mảnh thành các CSDL cục bộ (Local) và được quản lý bởi cùng một hệ QTCSDL. B. CSDL toàn cục bộ được quản lý bởi một hệ QTCSDL. C. CSDL phân tán trên các vị trí khác nhau được quản lý bởi nhiều hệ QTCSDL.khác nhau 24. Hệ quản trị CSDL phân tán không thuần nhất: A. CSDL cục bộ được quản lý bởi các hệ QTCSDL khác nhau. B. CSDL toàn cục bộ được quản lý bởi một hệ QTCSDL. C. CSDL phân mảnh thành các CSDL cục bộ (Local) 36
38. 25. Đặc tính hệ quản trị cơ sở dữ liệu phân tán A. Client Server, ngang hàng và hệ đa CSDL. B. Tự trị, phân tán, hỗn hợp. C. Đơn quan hệ và đa CSDL. 37
39. CHƯƠNG II: THIẾT KẾ CÁC HỆ CSDL PHÂN TÁN Trong chương này sẽ trình bày những khái niệm cơ bản về các phương pháp phân mảnh dữ liệu và bài toán cấp phát dữ liệu trên các vị trí của mạng máy tính. Nội dung của chương bao gồm các phần: • Các vấn đề về phân mảnh dữ liệu • Phương pháp phân mảnh ngang • Phân mảnh ngang dẫn xuất • Phân mảnh dọc • Phương pháp phân mảnh hỗn hợp( Hybrid Fragmentation) • Cấp phát và mô hình cấp phát 2.1 CÁC VẤN ĐỀ VỀ PHÂN MẢNH DỮ LIỆU Phần lớn các hệ cơ sở dữ liệu phân tán được thiết kế theo hướng từ trên xuống (Top- Down). Thiết kế phân mảnh dữ liệu là công việc đầu tiên phải thực hiện. Mục đích của việc phân mảnh dữ liệu là tạo ra các đơn vị cấp phát logic, sao cho chi phí để thực hiện truy vấn thông tin là thấp nhất. Các bộ hoặc các thuộc tính của quan hệ không thể được xem như một đơn vị cấp phát, vì sẽ làm cho việc cấp phát trở lên phức tạp hơn. Thiết kế phân mảnh bằng cách nhóm một số bộ trong trường hợp phân mảnh ngang hay nhóm các thuộc tính trong trường hợp phân mảnh dọc có cùng đặc tính theo quan điểm cấp phát. Các mảnh hình thành bằng các phương pháp phân mảnh tạo ra các đơn vị cấp phát dữ liệu khác nhau. 2.1.1 Lý do phân mảnh Trong thiết kế CSDL phân tán , cần thiết phải thực hiện phân mảnh dữ liệu vì những lý do sau đây: • Trong các hệ quản trị CSDL, các quan hệ được lưu trữ dưới dạng các bảng 2 chiều. Các thao tác đối với CSDL được thực hiện trên các bảng. Tuy nhiên trong thực tế, các ứng dụng chỉ yêu cầu thao tác trên các tập con của các quan hệ, là khung nhìn dữ liệu của người sử dụng. Vì vậy việc xem tập con của quan hệ là đơn vị truy xuất thông tin để phân tán dữ liệu là hợp lý. • Việc phân rã một quan hệ thành nhiều mảnh, mỗi mảnh được xử lý như một đơn vị dữ liệu, sẽ cho phép thực hiện nhiều giao dịch đồng thời. Đồng thời việc phân mảnh các quan hệ cũng cho phép thực hiện song song một câu vấn tin bằng cách chia nó thành một tập các câu vấn tin con hoạt tác trên các mảnh. Vì thế việc phân mảnh sẽ làm tăng mức độ hoạt động đồng thời và tăng lưu lượng hoạt động của hệ thống. Tuy nhiên không phải việc phân mảnh chỉ có ưu điểm hoàn toàn, mà nó cũng thể hiện những hạn chế nhất định như: • Nếu ứng dụng có những yêu cầu “xung đột” ngăn cản phân rã thành các mảnh được sử dụng độc quyền. 38
40. • Những ứng dụng có các khung nhìn được định nghĩa trên nhiều mảnh khác nhau sẽ làm giảm hiệu suất hoạt động của hệ thống, làm tăng chi phí truy xuất dữ liệu đến các mảnh và tăng chi phí kết nối các mảnh • Việc kiểm soát ngữ nghĩa, đặc biệt là vấn đề kiểm tra tính toàn vẹn sẽ khó khăn hơn 2.1.2 Các kiểu phân mảnh Các quan hệ cơ sở dữ liệu thường được biểu diễn dưới dạng bảng. Việc phân mảnh một quan hệ thành nhiều quan hệ con khác nhau theo các cách khác nhau, sẽ có các cách phân mảnh tương ứng. Có hai kiểu phân mảnh tương ứng với việc chia quan hệ theo chiều dọc và chia quan hệ theo chiều ngang . Phân mảnh theo chiều dọc: Các quan hệ được chia theo chiều dọc. Nghĩa là thiết lập một quan hệ mới chỉ có một số thuộc tính từ quan hệ gốc. Thực chất đây là phép chiếu trên tập con các thuộc tính của quan hệ. Ví dụ 2.1 Tách dọc quan hệ PROJ thành 2 quan hệ PROJ1 và PROJ2 như sau: π PNO,BUDGET (PROJ) và π PNO,PNAME,LOG (PROJ) và PROJ PROJ PNO BUDGET PNO PNAME LOG P1 150000 P1 Instrumentation Montreal P2 135000 P2 Database Develop New York P3 250000 P3 CAD/CAM New York P4 310000 P4 Maintenance Paris Hình 2.1. Phân mảnh dọc Phân mảnh ngang: Quan hệ được chia theo chiều ngang. Thực chất đây là phép chọn trong quan hệ. Chọn những bộ của quan hệ thỏa mãn một biểu thức điều kiên cho trước. Ví dụ 2.2 Tách ngang quan hệ PROJ thành 2 quan hệ PROJ1 và PROJ2 thoả theo điều kiện: BUDGET ≤ 200000 và BUDGET > 200000 như sau: σ BUDGET ≤ 200000 (PROJ) σ BUDGET > 200000 (PROJ) PROJ1 PNO PNAME BUDGET P1 Instrumentation 150000 P2 Database Develop 135000 PROJ2 PNO PNAME BUDGET P3 CAD/CAM 250000 P4 Maintenance 310000 Hình 2.2. Phân mả nh ngang 39
41. 2.1.3 Mức độ phân mảnh Phân mảnh cơ sở dữ liệu đến mức độ nào là đủ, không làm ảnh hưởng đến hiệu năng của việc thực hiện truy vấn. Mức độ phân mảnh có thể là phân mảnh một quan hệ chưa được phân mảnh, có thể phân mản các quan hệ đã được phân mảnh. Có thể phân mảnh theo chiều dọc (theo từng thuộc tính) hoặc theo chiều ngang (theo từng bộ trong quan hệ). Một mức độ ứng phân mảnh thích hợp sao cho tránh được các hạn chế khi phân mảnh chỉ được định nghĩa ứng với các ứng dụng sẽ chạy trên cơ sở dữ liệu. 2.1.4 Các quy tắc phân mảnh Các nguyên tắc để đảm bảo cơ sở dữ liệu khi phân mảnh sẽ đảm bảo tính không thay đổi về ngữ nghĩa. Dưới đây là ba qui tắc phải tuân thủ khi phân mảnh cơ sở dữ liệu quan hệ. 1. Tính đầy đủ: Quan hệ R được phân rã thành các mảnh R1, R2 Rn, thì mỗi mục dữ liệu có trong quan hệ R sẽ được chứa trong ít nhất một mảnh Ri (i=1, ,n). Quy tắc này đảm bảo cho các mục dữ liệu trong R được ánh xạ hoàn toàn vào các mảnh và không bị mất. Mục dữ liệu có thể hiểu là bộ trong phân mảnh ngang và thuộc tính trong phân mảnh dọc. 2. Tính phục hồi: Nếu một quan hệ R được phân rã thành các mảnh R1, R2, ,Rn khi đó: R =∇ Ri, ∀ Ri∈FR . Toán tử ∇ thay đổi tùy theo từng loại phân mảnh Khả năng phục hồi quan hệ từ các mảnh sẽ đảm bảo bảo toàn các phụ thuộc. 3. Tính tách biệt: Nếu quan hệ R được phân rã ngang thành các mảnh Ri, i=1, n và mục dữ liệu di nằm trong một mảnh Ri thì nó sẽ không nằm trong mảnh Rk , (k≠j). Quy tắc này đảm bảo các mảnh phân rã rời nhau. Trong trường hợp phân mảnh dọc, khóa chính của quan hệ phải được lập lại trong tất cả các mảnh. Vì vậy tính tách biệt trong phân mảnh dọc được hiểu không liên quan gì đến khóa chính của quan hệ. 2.1.5 Các kiểu cấp phát Giả sử CSDL đã được phân mảnh, thích hợp và thoả các yêu cầu phải cấp phát cho các vị trí trên mạng. Khi dữ liệu được cấp phát, có thể không nhân bản hoặc có thể được nhân bản. Không nhân bản, thường được gọi là CSDL phân hoạch, các mảnh chỉ được cấp phát trên các trạm và không có bản sao nào trên mạng. Trong trường hợp nhân bản, hoặc toàn bộ CSDL đều có ở trên tất cả các từng trạm (CSDL được nhân bản đầy đủ), hoặc các mảnh của CSDL được phân tán tới các trạm bằng cách các mảnh sao được đặt trên nhiều trạm (CSDL được nhân bản từng phần). Một số các bản sao của mảnh có thể là đầu vào cho thuật toán cấp phát hoặc quyết định giá trị của biến được xác bởi thuật toán. Nhân bản làm tăng độ tin cậy và tăng hiệu quả của các câu vấn tin chỉ đọc (Read-only Query) Đặc biệt có thể truy xuất CSDL khi gặp sự cố. Hơn nữa các câu truy vấn đọc truy xuất đến cùng một mục dữ liệu có thể cho thực hiện song song vì các bản sao có mặt tại nhiều vị trí. Hình 2.3 so sánh ba cách nhân bản theo một số chức năng của hệ quản trị CSDL phân tán. Việc cấp phát dữ liệu phải được thực hiện sao cho thỏa mãn hai yêu cầu sau: • Chi phí nhỏ nhất • Hiệu năng lớn nhất: Giảm thiểu thời gian đáp ứng và tăng tối đa lưu lượng hệ thống tại mỗi vị trí. 40
42. Nhân bản hoàn toàn Nhân bản một phần Phân hoạch Xử lý Dễ Cùng mức độ khó khăn truy vấn Quản lý Dễ hoặc không tồn tại Cùng mức độ khó khăn thư mục Điều khiển Vừa phải Khó Dễ đồng thời Độ tin cậy Rất cao Cao Thấp Có thể áp Tính thực tế Có thể áp dụng Thực tế dụng Hình 2.3 So sánh các phương pháp nhân bản 2.1.6 Các yêu cầu thông tin Công việc thiết kế cơ sở dữ liệu phân tán phụ thuộc rất nhiều vào các yếu tố có là ảnh hưởng đến một thiết kế tối ưu, tổ chức logic cơ sở dữ liệu, vị trí các ứng dụng, đặc tính truy xuất của các ứng dụng đến cơ sở dữ liệu và các đặc tính của hệ thống máy tính tại mỗi vị trí. Điều này làm cho việc diễn đạt bài toán phân tán trở nên hết sức phức tạp. Các thông tin cần thiết cho thiết kế phân tán bao gồm: • Thông tin cơ sở dữ liệu • Thông tin ứng dụng • Thông tin về mạng • Thông tin về hệ thống máy tính Yêu cầu thông tin về mạng và thông tin về hệ thống máy tính chỉ được sử dụng trong các mô hình cấp phát, không sử dụng trong các thuật toán phân mảnh dữ liệu 2.2 PHƯƠNG PHÁP PHÂN MẢNH NGANG 2.2.1 Giới thiệu Phân mảnh ngang chính là việc chia quan hệ thành nhiều các nhóm bộ. Kết quả của quá trình phân mảnh ngang là các quan hệ con, số lượng quan hệ con phụ thuộc vào điều kiện ràng buộc của các thuộc tính. Và các bộ trong các quan hệ con là tách biệt nhau. Phân mảnh ngang thực chất là phép chọn quan hệ thỏa mãn một biểu thức điều kiên cho trước. Có hai loại phương pháp phân mảnh ngang là: • Phân mảnh ngang nguyên thủy: Là phân mảnh ngang được thực hiện trên các vị từ của chính quan hệ đó. • Phân mảnh ngang dẫn xuất: Là phân rã một quan hệ dựa trên các vị từ của quan hệ khác. 2.2.2 Thông tin cần thiết của phân mảnh ngang a) Thông tin về CSDL có liên quan tới lược đồ khái niệm toàn cục. Trong mô hình quan hệ, các mối quan hệ giữa các thực thể được mô tả như là những quan hệ. Trong mô hình quan 41
43. hệ thực thể (ER), các mối liên hệ giữa các đối tượng CSDL được mô tả rõ ràng. Nhìn chung mối quan hệ giữa các đối tượng trong CSDL thường mô tả bằng các mối quan hệ một - một, một - nhiều và mối quan hệ nhiều - nhiều. Với mục đích cho thiết kế ,đường nối (Link) có hướng giữa các quan hệ được sử dụng cho việc biểu diễn bởi thao tác nối bằng (Equijoin). Ví dụ 2.3: Trong hình 2.4, mỗi một chức vụ (Title) có nhiều nhiều nhân viên (Employee) giữ chức vụ đó. Đây là mối quan hệ môt - nhiều được biểu diễn bằng một đường nối có hướng L1 trỏ từ quan hệ PAY đến EMP. Mối quan hệ nhiều - nhiều được trỏ từ các quan hệ EMP và PROJ đến quan hệ ASG.được biểu diễn bằng hai đuờng nối L2 và L2. PAY TITLE, SAL L1 EMP PROJ ENO, ENAME, TITLE PNO, PNAME, BUDGET, LOC L2 L3 ASG ENO, PNO, RESP, DUR Hình 2.4 Mô tả mối quan hệ giữa các quan hệ bởi các đường nối Quan hệ tại điểm cuối của đường nối được gọi là quan hệ chủ (quan hệ đích ) và các quan hệ tại điểm đầu được gọi là các quan hệ thành viên (quan hệ nguồn). Ánh xạ Owner và Member từ tập đường nối tới tập quan hệ. Khi cho trước một đường nối, hàm sẽ trả về quan hệ đích hay quan hệ nguồn của đường nối. Ví dụ trong hình 2.4: owner(L1) = PAY và member(L1) = EMP Ký hiệu lực lượng (cardinality) của mỗi quan hệ R là Card(R). b) Thông tin về ứng dụng: Để thực hiện phân mảnh, cần phải có thông tin định tính và thông tin định lượng. Thông tin định tính hướng dẫn cho hoạt động phân mảnh, thông tin định lượng chủ yếu sử dụng trong các mô hình cấp phát. Thông tin định tính cơ bản gồm các vị từ dùng trong câu truy vấn. Sau đây là các định nghĩa về vị từ đơn giản (Simple Predicate) và vị từ hội sơ cấp (Minterm Predicate) như sau: • Cho quan hệ R(A1, A2, ,An), trong đó Ai là thuộc tính được định nghĩa trên một miền biến thiên Di , một vị từ đơn giản Pj được định nghĩa trên R có dạng: Pj: Ai θ Value 42
44. Trong đó θ thuộc {=, , ≥} và Value được chọn từ miền Ai (Value thuộc Di). Chúng ta sử dụng Pri để biểu thị tập tất cả các vị từ đơn giản được định nghĩa trên quan hệ Ri. Các phần tử của Pri được ký hiệu là pij. Ví dụ 2.5. Cho quan hệ PROJ PNAME = “Maintenance” BUDGET ≤ 200000 là các vị từ đơn giản. • Trong thực tế các câu truy vấn là tổ hợp của rất nhiều vị từ đơn giản. Mỗi tổ hợp được gọi là một vị từ hội sơ cấp. Cho tập Pri = {pi1, pi2, , pim} là các vị từ đơn giản trên quan hệ Ri, tập các vị từ hội sơ cấp Mi = {mi1, mi2, , miz} được định nghĩa như sau: Cho tập Pri = {pi1, pi2, , pim} là các vị từ đơn giản trên quan hệ Ri, tập các vị từ hội sơ cấp Mi = {mi1, mi2, , miz} được định nghĩa như sau: ⎧ * ⎫ M i = ⎨mij mij = ∧ pik ⎬ , 1 ≤ k ≤ m , 1 ≤ j ≤ z . ⎩ pik ∈pri ⎭ * * Trong đó, pik = pik hoặc pik = ¬pik . Vì thế mỗi vị từ đơn giản có thể xuất hiện trong vị từ hội sơ cấp dưới dạng tự nhiên hoặc dạng phủ định của nó. Phủ định của một vị từ sẽ có thể: Attribute = Value không có phủ định. Attribute ≤ Value, phủ định là Attribute > Value Cận_dưới ≤ Attribute_1, phủ định là ¬(Cận_dưới ≤ Attribute_1) Attribute_1 ≤ Cận_trên, phủ định là ¬(Attribute_1 ≤ Cận_trên) Cận_dưới ≤ Attribute_1 ≤ Cận_trên, phủ định là ¬(Cận_dưới ≤ Attribute_1 ≤ Cận_trên) Ví dụ 2.4: Xét một số vị từ đơn giản có thể định nghĩa được trên quan hệ PAY. p1: TITLE = “Elect.Eng” p2: TITLE = “Syst. Anal” p3: TITLE = “Mech. Eng” p4: TITLE = “Programmer” p5: SAL ≤ 30000 p6: SAL > 30000 Các vị từ hội sơ cấp được định nghĩa dựa trên các vị từ đơn giản: m1: TITLE = “Elect.Eng” ^ SAL ≤ 30000 m2: TITLE = “Elect.Eng” ^ SAL > 30000 m3: ¬(TITLE = “Elect.Eng”) ^ SAL ≤ 30000 m4: ¬(TITLE = “Elect.Eng”) ^ SAL > 30000 m5: TITLE = “Programmer” ^ SAL ≤ 30000 m6: TITLE = “Programmer” ^ SAL > 30000 43
45. PAY TITLE SAL Elect.Eng 40000 Mech.Eng 27000 Programmer 24000 Syst.Anal 34000 Thông tin số lượng về ứng dụng cần phải có hai tập dữ liệu: 1. Độ tuyển hội sơ cấp (Minterm Selectivity): số các bộ của quan hệ sẽ được chọn theo vị từ hội sơ cấp cho trước, ký hiệu chọn của hội sơ cấp m là sel(m).Ví dụ, không có bộ nào được chọn trong PAY thoả mãn vị từ hội sơ cấp m1. Có 1 bộ thoả m2. 2. Tần số ứng dụng người dùng truy nhập dữ liệu. Nếu Q = {q1, q2, , qq} là tập truy vấn, ký hiệu acc(qi) là tần số truy nhập của truy vấn qi trong một khoảng thời gian đã cho. 3. Tần số truy nhập hội sơ cấp là tần số truy nhập của hội sơ cấp m, ký hiệu là acc(m). 2.2.3 Phân mảnh ngang cơ sở Phân mảnh ngang cơ sở được định nghĩa bằng phép chọn trên quan hệ đích của lược đồ CSDL. Cho quan hệ R, các mảnh ngang , R = σ (R) , i-1 n i Fi Trong đó Fi là biểu thức đại số quan hệ. Nếu Fi có dạng chuẩn hội, thì nó là vị từ hội sơ cấp (mi). Thực tế, thuật toán sẽ thảo luận khẳng định Fi là vị từ hội sơ cấp. Ví dụ 2.5: Xết quan hệ PROJ F1:= {BUDGET≤200000} và F2:= {BUDGET >200000} Khi đó quan hệ PROJ được phân rã thành các mảnh ngang PROJ1 và PROJ2 như sau: PROJ1 = σBUDGET≤200000(PROJ) PROJ2 = σBUDGET>200000(PROJ) Giả sử tập các biểu thức đại số quan hệ: F1:= {BUDGET≤200000} F2:= { 200000 < BUDGET ≤ 400000} F3:= { 400000 < BUDGET ≤ 600000} F4:= { 600000 < BUDGET} Khi đó quan hệ PROJ được phân rã thành các mảnh ngang như sau: PROJ1 = σ BUDGET≤200000(PROJ) PROJ2 = σ 200000 < BUDGET ≤ 400000 (PROJ) PROJ3 = σ 400000 < BUDGET ≤ 600000 (PROJ) PROJ4 = σ 600000 < BUDGET (PROJ) Ví dụ 2.6: Xét quan hệ PROJ, các mảnh ngang sau đây được định nghĩa dựa vào vị trí các dự án. Các mảnh như sau: PROJ1 = σLOC=”Montreal” (PROJ); PROJ2 = σLOC=”New York”(PROJ); PROJ3 = σLOC=”Paris”(PROJ) 44
46. PROJ1 PNO PNAME BUDGET LOC P1 Instrumentation 150000 Montreal PROJ 2 PNO PNAME BUDGET LOC P2 Database Develop 135000 New York P3 CAD/CAM 250000 New York PROJ3 PNO PNAME BUDGET LOC P4 Maintenance 310000 Paris Hình 2.5. Phân mảnh ngang cơ sở quan hệ PROJ Phân mảnh ngang Ri của quan hệ R gồm tất cả các bộ của R thoả một vị từ hội sơ cấp mi. Vì vậy, cho một tập M các vị từ hội sơ cấp, số lượng phân mảnh ngang của quan hệ R bằng số lượng các vị từ hội sơ cấp. Tập các mảnh ngang được gọi là tập các mảnh hội sơ cấp (Minterm Fragment). Định nghĩa phân mảnh ngang phụ thuộc vào vị từ hội sơ cấp, vì vậy, cần phải xác định các vị từ đơn giản rạo ra vị từ hội sơ cấp. 2.2.4 Tính đầy đủ và tính cực tiểu của vị từ đơn giản Vị từ đơn giản có tính đầy đủ (Completeness) và tính cực tiểu (Minimality). Tập các vị từ đơn giản Pr là đầy đủ khi và chỉ khi xác suất truy nhập bởi mỗi ứng dụng tới bộ bất kỳ của một mảnh hội sơ cấp bất kỳ được định nghĩa theo Pr là như nhau. Vị từ đầy đủ sẽ đảm bảo cho các mảnh thoả mãn các vị từ sơ cấp, nhất quán về mặt logic. Đồng nhất về mặt thống kê theo cách ứng dụng truy nhập. Vì vậy, sử dụng một tập vị từ đầy đủ làm cơ sở cho việc phân mảnh ngang cơ sở. Ví dụ 2.8: Trong ví dụ 2.7, các ứng dụng truy nhập PROJ theo vị trí, thì tập vị từ tương ứng là đầy đủ, vì mỗi bộ của các mảnh PROJi , i=1,2,3, đều có xác xuất được truy nhập bằng nhau. Tuy nhiên, nếu thêm ứng dụng dự án có ngân sách trên 200.000$ vào tập Pr, thì Pr sẽ là không đầy đủ, vì một số bộ trong các mảnh PROJi có xác suất được truy nhập lớn hơn. Để tập vị từ này là đầy đủ thì cần phải thêm các vị từ (BUDGET≤200000, BUDGET>200000) vào Pr : Pr = {LOC= “Montreal”, LOC=”New York”, LOC=”Paris”, BUDGET≤200000, BUDGET > 200000} Đặc tính thứ hai của tập các vị từ có tính cực tiểu. Nếu một vị từ f phân mảnh thành các mảnh nhỏ hơn f1 và f2, thì phải có ít nhất một ứng dụng truy nhập đến f1 và f2 theo các cánh khác nhau. Khi đó nói rằng vị từ đơn giản f có tính liên đới (Relevant), ảnh hưởng đến việc xác định một phân mảnh. Nếu tất cả các vị từ của tập Pr đều có liên đới thì tập Pr được gọi là cực tiểu. 45
47. Tính liên đới của vị từ đơn giản được định nghĩa hình thức lnhư sau: Gọi mi và mj là hai vị từ hội sơ cấp. Vị từ hội sơ cấp mi chứa vị từ đơn giản pi, vị từ hội sơ cápp mj chứa pj dạng phủ định ¬pi. Gọi fi và fj là hai mảnh tương ứng được định nghĩa theo mi và mj. Khi đó pi là có liên đới khi và chỉ khi: acc(m ) acc(m ) i ≠ j card( f i ) card( f j ) Ví dụ 2.9: Tập Pr = {LOC= “Montreal”, LOC=”New York”, LOC=”Paris”, BUDGET≤200000, BUDGET > 200000} là tập vị từ đầy đủ và cực tiểu. Nếu thêm vị từ PNAME = “”Instrumentation” và tập Pr, khi đó sẽ không đảm bảo tính cực tiểu, vì vị từ thêm vào không có tính liên đới ứng với Pr. Không một ứng dụng nào truy xuất khác nhau đến các mảnh được tạo ra. 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 Thuật toán COM_MIN tạo ra ra một tập đầy đủ và cực tiểu các vị từ Pr’ từ một tập các vị từ đơn giản Pr cho trước theo quy tắc: một quan hệ hoặc một mảnh “được phân hoạch thành ít nhất hai phần và chúng được truy nhập khác nhau bởi ít nhất bởi một ứng dụng” Mảnh fi được định nghĩa theo một vị từ hội sơ cấp trên Pr’, qui ước là fi của Pr’ Thuật toán 2.1. COM_MIN Input: R là quan hệ cần phân mảnh ngang cơ sở. Pr là tập các vị từ đơn giản Output: Pr’ là tập các vị từ đơn giản. Khai báo: F là tập các mảnh hội sơ cấp. Begin Tìm một vị từ pi ∈ Pr sao cho pi phân hoạch R theo qui tắc Pr’ ← pi Pr ← Pr – pi F ← fi {fi là mảnh hội sơ cấp theo pi } do begin Tìm một pj∈Pr sao cho pj phân hoạch một mảnh fk của Pr’ theo qui tắc Pr’ ← Pr’ ∪ pj Pr ← Pr - pj F ← F ∪ fi If ∃pk ∈ Pr’, một vị từ không có liên đới then begin Pr’ ← Pr’ - pk F ← F - pk end-if end-begin until Pr đầy đủ End. { COM_MIN} Thuật toán thực hiện như sau: • Bắt đầu bằng cách tìm một vị từ có liên đới và phân hoạch quan hệ đã cho. Vòng lặp do-until thêm các vị từ vào tập Pr’, đảm bảo Pr’ là cực tiểu và đầy đủ. 46
48. • Bước thứ hai: Trong quá trình phân mảnh ngang cơ sở suy dẫn ra tập các vị từ hội sơ cấp có thể được định nghĩa trên các vị từ trong tập Pr’. Các vị từ hội sơ cấp này xác định các mảnh cấp phát. • Bước thứ ba: Các vị từ hội sơ cấp có thể rất lớn, tỷ lệ hàm mũ theo số lượng các vị từ đơn giản Vì vậy cần phải loại bỏ những mảnh không có ý nghĩa, bằng cách xác định những vị từ mâu thuẫn với tập các phép kéo theo (Implication). 2.2.6 Thuật toán phân mảnh ngang nguyên thuỷ Thuật toán 2.2. PHORIZONTAL Input: R là quan hệ cần phân mảnh ngang cơ sở. Pr là tập các vị từ đơn giản Output: M là tập các vị từ hội sơ cấp Begin Pr’ ← COM_MIT(R, Pr) Xác định tập M các vị từ hội sơ cấp Xác định tập I các phép kéo theo giữa các pi ∈ Pr’ For mỗi mi ∈ M do If mi mâu thuẫn với I then M ← M - mi End_if End_for End. {PHORIZONTAL} Ví dụ 2.10. Giả sử chỉ có một ứng dụng kiểm tra thông tin lương và xác định số lương sẽ tăng trên quan hệ PAY. Giả sử có hai vị trí, một vị trí xử lý các bộ có lương thấp hơn hoặc bằng 30000$ và vị trí còn lại xử lý các bộ có lương cao hơn 30000$. Câu truy vấn sẽ thực hiện trên cả hai vị trí. Tập vị từ đơn giản sử dụng để phân hoạch quan hệ PAY là: p1: SAL ≤ 30000 p2: SAL > 30000 Tập vị từ đơn giản khởi đầu là Pr = {p1, p2}. Áp dụng thuật toán COM_MIN với i=1 làm giá trị khởi đầu tạo ra Pr’={p1} là tập đầy đủ và cực tiểu vì p2 không phân hoạch f1 (là mảnh hội sơ cấp được tạo ra ứng với p1) theo quy tắc. Như vậy, các vị từ hội sơ cấp sau đây là các phần tử của M: m1: (SAL ≤ 30000) m1: ¬(SAL ≤ 30000) = SAL > 30000 Khi đó, hai mảnh Fs = {PAY1, PAY2} theo M là: PAY1 PAY2 TITLE SAL TITLE SAL Mech. Eng. 27000 Elect. Eng. 40000 Programmer 24000 Syst. Anal. 34000 Hình 2.6. Phân mảnh ngang cho quan hệ PAY Giả sử có hai ứng dụng trên quan hệ PROJ. Ứng dụng thứ nhất xác định tên các dự án và ngân sách của chúng trên ba vị trí. 47
49. SELECT PNAME, BUDGET FROM PROJ WHERE LOC = Value Ứng dụng này, các vị từ đơn giản có thể được sử dụng là: p1: LOC = “Montreal” p2: LOC = “New York” p3: LOC = “Paris” Ứng dụng thứ hai liên quan đến các dự án có ngân sách nhỏ hơn hoặc bằng 200000$ được quản lý tại một vị trí và các dự án có ngân sách lớn hơn 200000 được quản lý tại vị trí thứ hai. Vì vậy, các vị từ đơn giản được sử dụng để phân mảnh ứng dụng thứ hai là: p4: BUDGET ≤ 200000 p5: BUDGET > 200000 Sử dụng thuật toán COM_MIN kiểm tra tập Pr’ = {p1, p2, p3, p4, p5} là đầy đủ và cực tiểu. Có thể định nghĩa sáu vị từ hội sơ cấp tạo ra M dựa trên Pr’ như sau:: m1: (LOC=“Montreal”) ∧ (BUDGET≤20000) m2: (LOC=“Montreal”) ∧ (BUDGET>20000) m3: (LOC=“New York”) ∧ (BUDGET≤20000) m4: (LOC=“New York”) ∧ (BUDGET>20000) m5: (LOC=“Paris”) ∧ (BUDGET≤20000) m6: (LOC=“Paris”) ∧ (BUDGET>20000) Kết quả phân mảnh ngang cơ sở PROJ tạo ra sáu mảnh FPROJ = {PROJ1, PROJ2, PROJ3, PROJ4, PROJ5, PROJ6} theo các vị từ hội sơ cấp M. Các mảnh PROJ2, PROJ5 rỗng. PROJ1 PNO PNAME BUDGET LOC P1 Instrumentation 150000 Montreal PROJ3 PNO PNAME BUDGET LOC Database P2 135000 New York Dl PROJ4 PNO PNAME BUDGET LOC P3 CAD/CAM 250000 New York PROJ6 PNO PNAME BUDGET LOC P4 Maintenance 31000 Paris Hình 2.7 . Phân hoạch ngang quan hệ PROJ 2.3 PHÂN MẢNH NGANG DẪN XUẤT Phân mảnh ngang dẫn xuất dựa trên các quan hệ thành viên của một đường nối theo phép toán chọn trên quan hệ chủ. Mục tiêu của phân mảnh ngang dẫn xuất là phân chia các quan 48
50. hệ thành viên thành các mảnh của quan hệ chủ được định nghĩa trên các thuộc tính của quan hệ thành viên. Vì vậy liên kết giữa quan hệ chủ và quan hệ thành viên được định nghĩa như là một nối bằng (Equijoin) và kết nối bằng có thể được cài đặt nối nửa (Semijoin). Cho một đường nối L trong đó, Owner(L) = S và Member(L) = R. Phân mảnh ngang dẫn xuất của R được định nghĩa như sau: Ri = R α Si 1 ≤ i ≤ k, trong đó, k là số mảnh Si = σ Fi (S), Fi là biểu thức định nghĩa mảnh ngang nguyên thuỷ Si . Ví dụ 2.11. Cho Owner(L) = PAY và Member(L) = EMP. Nhóm các kỹ sư (Engineer) thành hai nhóm theo lương SAL≤30000 và SAL>30000. PAY1 = σ SAL≤30000(PAY) PAY2 = σSAL>30000(PAY) Hai mảnh EMP1 và EMP2 được định nghĩa như sau: EMP1 = EMP ∝ PAY1 EMP2 = EMP ∝ PAY2 EMP1 EMP2 ENO ENAME TITLE ENO ENAME TITLE E3 A. Lee Mech. Eng. E1 J. Doe Elect. Eng. E4 J. Miller Programmer E2 M. Smith Syst. Anal. E7 R. David Mech. Eng. E5 B. Casey Syst. Anal. E6 L. Chu Elect. Eng. E8 J. Jones Syst. Anal. Hình 2.8. Phân mảnh ngang dẫn xuất quan hệ EMP Trong một số trường hợp, như thí dụ 2.11 ở trên, mỗi một mảnh chỉ có một đường liên kết đến hoặc đi. Đồ thị có cấu trúc như vậy, được gọi là đồ thị đơn giản. Ưu điểm của thiết kế loại này là mối liên kết giữa các mảnh đơn giản. Quan hệ thành viên và quan hệ chủ nhân của đường kết nối có thể cấp phát cho một vị trí và các nối giữa các cặp mảnh khác nhau có thể tiến hành độc lập và song song với nhau. Ngoài việc thực hiện được nhiều câu vấn tin tại nhiều vị trí khác nhau, còn có thể thực hiện song song một câu vấn tin với thời gian đáp ứng và lưu lượng của hệ thống tối ưu hơn. Ví dụ giữa các mảnh EMP và PAY. Trong những trường hợp này, thuật toán phân mảnh hoà toàn tầm thường. Trong một số trường hợp khác, có nhiều hơn hai liên kết đến một quan hệ R. Khi đó người ta thường chọn một thiết kế tạo ra một đồ thị nối phân hoạch (Partioned Join Graph). Một đồ thị phân hoạch có thể chứa hai hoặc nhiều đồ thị con và không có đường kết nối giữa chúng. Các đồ thị như vậy thường có thể cấp phát, nhưng rất khó phân tán để thực hiện song song. Trong hình 2.4 có hai đường nối đến quan hệ ASG. Như vậy sẽ có nhiều cách phân mảnh ngang dẫn xuất quan hệ R. Việc quyết định chọn phân mảnh nào tối ưu hơn cần dựa trên hai tiêu chuẩn sau: 1. Phân mảnh có đặc tính kết nối tốt hơn 49
51. 2. Phân mảnh được sử dụng cho nhiều ứng dụng hơn PAY PAY 1 2 TITLE SAL TITLE SAL EMP1 EMP2 ENO ENAME TITLE ENO ENAME TITLE Hình 2.9. Đồ thị đơn giản nối giữa các mảnh Ví dụ 2.12 Trong hình 2.4 ta có Owner(L1) = PROJ và Member(L1) = ASG. Owner(L2) = EMP và Member(L2) = ASG. Thực hiện phân mảnh dẫn xuất của ASG ứng PROJ và EMP như sau: Xét quan hệ ASG có hai ứng dụng trên nó: ASG1 ASG3 ENO PNO RESP DUR ENO PNO RESP DUR E1 P1 Manager 12 E3 P3 Consultant 10 E2 P2 Analyst 24 E6 P3 Engineer 36 E7 P3 Manager 40 ASG2 ASG4 ENO PNO RESP DUR ENO PNO RESP DUR E2 P2 Analyst 6 E3 P4 Engineer 48 E4 P2 Programmer 18 E6 P4 Manager 48 E5 P2 Manager 24 Hình 2.10 Phân mảnh dẫn xuất của ASG ứng với PROJ • Ứng dụng 1: Danh sách các kỹ sư làm việc tại một vị trí nào đó. Ứng dụng này thực hiện trên ba trạm và truy xuất thông tin về các kỹ sư làm việc trong các dự án tại chỗ với xác suất cao hơn các kỹ sư làm việc trong các dự án trên các vị trí khác. Phân mảnh ASG theo các mảnh PROJ1, PROJ2, PROJ4 và ,PROJ4, như sau: PROJ1 = σLOC=“Montreal” ∧ BUDGET≤20000(PROJ) PROJ3 = σLOC=“New York” ∧ BUDGET≤20000(PROJ) PROJ4 = σLOC=“New York” ∧ BUDGET>20000(PROJ) PROJ6 = σLOC=“Paris” ∧ BUDGET>20000(PROJ) Phân mảnh dẫn xuất của ASG theo {PROJ1, PROJ3, PROJ4, PROJ6} có thể được định nghĩa như sau: ASG1 = ASG ∝ PROJ1 50
52. ASG2 = ASG ∝ PROJ3 ASG3 = ASG ∝ PROJ4 ASG4 = ASG ∝ PROJ6 • Ứng dụng thứ 2: Tại các trạm quản lý nhân viên, ứng dụng sẽ truy xuất thông tin về thời gian thực hiện các dự án của các nhân viên. Câu vấn tin có thể viết: SELECT RESP, DUR FROM ASG, EMPi WHERE ASG ENO = EMPi ENO Trong đó i=1 hoặc i=2 tùy thuộc vào vị trí đưa ra truy vấn. Phân mảnh dẫn xuất của ASG theo phân mảnh của EMP được định nghĩa nhw sau: ASG1 = ASG ∝ EMP1 ASG2 = ASG ∝ EMP2 ASG1 ASG2 ENO PNO RESP DUR ENO PNO RESP DUR E3 P3 Consultant 02 E1 P1 Manager 12 E3 P4 Engineer 48 E2 P1 Analyst 24 E4 P2 Programmer 18 E3 P2 Analyst 6 E7 P3 Engineer 36 E4 P2 Manager 24 E5 P4 Manager 48 E6 P3 Manager 40 Hình 2.11. Phân mảnh dẫn xuất của ASG ứng với EMP Nhận xét 1. Phân mảnh dẫn xuất có thể xảy ra dây chuyền, trong đó một quan hệ được phân mảnh như là hệ quả của một phân mảnh cho một quan hệ khác, và đến lượt nó lại làm cho các quan hệ khác phải phân mảnh (như dây chuyền PAY-EMP-ASG). 2. Một quan hệ có thể có nhiều cách phân mảnh. Chọn lựa một lược đồ phân mảnh nào cho tối ưu phụ thuộc vào ứng dụng và cấp phát. 2.4 PHÂN MẢNH DỌC 2.4.1 Khái niệm phân mảnh dọc Phân mảnh dọc quan hệ R sinh ra các mảnh R1, R2, , Rr, sao cho mỗi mảnh chứa một tập con các thuộc tính của quan hệ R và khoá của nó. Mục đích của phân mảnh dọc là phân chia quan hệ R thành tập các quan hệ nhỏ hơn để có nhiều ứng dụng có thể chỉ cần thực hiện trên một mảnh. Mảnh tối ưu là mảnh sinh ra một lược đồ phân mảnh cho phép giảm tối thiểu thời gian thực hiện của ứng dụng trên mảnh đó. Kỹ thuật phân mảnh dọc phức tạp hơn so với kỹ thuật phân mảnh ngang, vì số lựa chọn phân hoạch rất lớn. Trong phân mảnh ngang, nếu số vị từ đơn giản trong Pr là n, khi đó sẽ có 2n vị từ hội sơ cấp có thể thể được định nghĩa trên đó. Mặt khác, một số vị từ hội sơ cấp có 51
53. thể mâu thuẫn với các phép kéo theo. Vì vậy sẽ làm giảm số lượng các mảnh dự tuyển cần được xem xét. Trong trường hợp phân mảnh dọc, nếu quan hệ có m thuộc tính không phải là khoá chính, thì số mảnh có thể có là mm . Để có được các lời giải tối ưu cho bài toán phân mảnh dọc rất không hiệu quả, phải sử dụng hai phương pháp Heuristic cho phân mảnh dọc các quan hệ toàn cục: 1. Nhóm thuộc tính: bắt đầu gán mỗi thuộc tính cho một mảnh và trong mỗi bước, nối một số mảnh lại với nhau cho đến khi thỏa điều kiện. 2. Tách mảnh bắt đầu bằng một quan hệ và quyết định cách phân chia dựa trên hành vi truy nhập của các ứng dụng trên các thuộc tính. Kỹ thuật tách mảnh thích hợp với phương pháp thiết kế từ trên xuống. Các mảnh không gối chồng lấn lên nhau (không phải là khoá chính). Ngược lại, với phương pháp nhóm thuộc tính thường tạo ra các mảnh gối chồng lên nhau. Trong các hệ CSDL phân tán, các mảnh không gối chồng lên nhau được quan tâm, nghiên cứu. Việc nhân bản các thuộc tính khóa tại mỗi trạm sẽ bảo đảm tính toàn vẹn ngữ nghĩa và làm giảm đi quá trình trao đổi dữ liệu. 2.4.2 Thông tin cần thiết của phân mảnh dọc a) Ma trận giá trị sử dụng thuộc tính: Gọi Q={q1, q2, , qq} là tập các câu vấn tin của người dùng hay còn gọi là các ứng dụng của người sử dụng., sẽ thực hiện trên quan hệ R(A1, A2, , An). Khi đó ma trận giá trị sử dụng thuộc tính có q hàng và n cột. Các phần tử được ký hiệu là giá trị câu vấn tin qi i=1 q sử dụng thuộc tính Aj , j=1 n, ký hiệu là use(qi, Aj) được định nghĩa như sau: 1 Nếu thuộc tính Aj được vấn tin qi tham chiếu Use(qi,Aj)= i=1 q và 0 Ngược lại j=1 n Ví dụ 2.13: Xét quan hệ PROJ . PNO PNAME LOG P1 Instrumentation Montreal P2 Database Develop New York P3 CAD/CAM New York P4 Maintenance Paris Giả sử có các ứng dụng sau ssược sử dụng trên quan hệ PROJ: q1: Cho biết ngân sách của một dự án cụ thể SELECT BUDGET FORM PROJ WHERE PNO=Value q2: Tên và ngân sách của tất cả dự án. SELECT BUDGET, PNAME FORM PROJ 52
54. q3: Tên của các dự án được thực hiện tại một thành phố biết trước SELECT PNAME FORM PROJ WHERE PNO=Value q4: Tổng ngân sách dự án cho mỗi thành phố SELECT SUM(BUDGET) FORM PROJ WHERE LOC=Value Ký hiệu A1 là thuộc tính PNO, A2 là thuộc tính PNAME, A3 l à thuộc tính BUDGET và A4 là thuộc tính LOC. Khi đó ma trận biểu diễn giá trị sử dụng các thuộc tính được biểu diễn như sau: A1 A2 A3 A4 q1 1 0 1 0 q2 0 1 1 0 q3 0 1 0 1 q4 0 0 1 1 Hình 2.12 .Một ví dụ về ma trận giá trị sử dụng thuộc tính b) Ma trận hấp dẫn (Affinity) của thuộc tính: Hầu hết các thông tin cho phân mảnh dọc có mối quan hệ mật thiết với các ứng dụng. Các thuộc tính thường được truy nhập chung với nhau, cần phải định nghĩa một giá trị để chỉ ra mức độ liên hệ giữa các thuộc tính, được gọi là sự hấp dẫn (Affinity) của thuộc tính. Số đo hấp dẫn giữa hai thuộc tính Ai, Aj của quan hệ R(A1,A2, ,An) ứng với tập ứng dụng Q={q1,q2, ,qq} được định nghĩa như sau: aff ( A i , A j ) = ∑ ∑ ref l ( q k ) acc l ( q k ) k [( use ( q k , A i ) ∧ use ( q k , A j ) l ∀ S l Trong đó refl (qk) là số truy suất các thuộc tính (Ai,Aj) cho qk tại vị trí Sl và accl (qk) là số đo tần số truy suất ứng dụng qk tại vị trí Sl . Kết quả tính toán là một ma trận vuông cấp n x n, phần tử (i, j) là số đo sự hấp dẫn của các thuộc tính Ai, Aj. Ví dụ 2.14 Giả sử refl(qk)=1 cho tất cả qk và Sl. Nếu tần số ứng dụng là: acc1(q1)=15 acc2(q2)=20 acc3(q1)=10 acc1(q2)=5 acc2(q2)=0 acc3(q2)=0 acc1(q3)=25 acc2(q3)=25 acc3(q3)=25 acc1(q4)=3 acc2(q4)=0 acc3(q4)=0 Khi đó số đo sự hấp dẫn giữa thuộc tính A1 và A3 có thể đo bằng: l 3 aff ( A1 , A3 ) = ∑∑acc 1 (q k ) = acc 1 (q1 ) +acc 2 (q1 ) + acc 3 (q1 ) = 45 kl==1 1 Vì ứng dụng duy nhất truy xuất đến cả hai thuộc tính này là q1. Ma trận hấp dẫn thuộc tính đầy đủ được trình bày trong hình 2.13 Chú ý rằng để cho đầy đủ ,các giá trị ở đường chéo cũng được tính dù rằng chúng hoàn toàn vô nghĩa 53
55. A1 A2 A3 A4 A1 45 0 45 0 A2 0 80 5 75 Â3 45 5 53 3 A4 0 75 3 78 Hình 2.13 Ma trận ái lực thuộc tính 2.4.3 Thuật toán tụ nhóm Thuật toán năng lượng nối BEA (Bond Energy Algorithm) nhóm các thuộc tính của một quan hệ dựa trên các giá trị hấp dẫn thuộc tính trong ma trận AA. Thuật toán hoán hoán vị các hàng và các cột của ma trận hấp dẫn thuộc tính AA, sao cho số đo hấp dẫn chung AM là lớn nhất (Global Affinity Measure). Kết quả sẽ là một ma trận gọi là ma trận hấp dẫn tụ CA (Cluster Affinity). Thuật toán gồm 3 bước : Bước 1: Đặt cố định một cột của AA vào trong CA. Thuật toán chọn cột 1. Bước 2: Giả sử có i cột đã được thực hiện và đặt vào CA. Lấy lần lượt một trong (n-i) cột còn lại và thử đặt vào (i+1) vị trí còn lại trong ma trận CA .Ssao cho số đo hấp dẫn chung AM (Global Affinity Measure) tại vị trí đó là lớn nhất. Thuật toán tiếp tục cho đến khi không còn cột nào để đặt. Bước 3: Cuối cùng là sắp thứ tự hàng. Khi thứ tự cột đã đựợc xác định thì các hàng cũng cần phải sắp xếp vị trí phù hợp với các vị trí tương đối của các cột. Thuật toán BEA (Thuật toán năng lượng nối) Input: AA:ma trận hấp dẫn thuộc tính Output: CA : Ma trận hấp dẫn tụ nhóm Begin {Khởi tạo , nhớ rằng AA là ma trận n x n} CA(.,1)←AA(.,1) CA(.,2)←AA(.,2) index ← 3 While index <= n do { chọn vị trí tốt nhất cho thuộc tính AAindex} Begin For i From 1 to index-1 by 1 do Tính cont(Ai-1,Aindex,Ai ) End-for Tính cont(Aindex-1,Aindex,Aindex+1) {Ddieeuf kiện biên} loc←vị trí được đặt bởi giá trị cont lớn nhất For j From index To loc By -1 Do CA(.,j) ←AA(.,j-1) End-for CA(.,loc) ←AA(.,index) index←index+1 End-While End {BEA} Ma trận hấp dẫn thuộc tính AA có tính đối xứng, số đo hấp dẫn chung AM được định nghĩa như sau: 54