Tài liệu Các kỹ thuật phân tán dữ liệu trong cơ sở dữ liệu phân tán

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ------  ------ LUẬN VĂN THẠC SĨ KHOA HỌC NGÀNH : CÔNG NGHỆ THÔNG TIN CÁC KỸ THUẬT PHÂN TÁN DỮ LIỆU TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN KOEU SOKMEAK GV HƯỚNG DẪN KHOA HỌC: GS.TS NGUYỄN THÚC HẢI HÀ NỘI-2008 KOEU SOKMEAK CÔNG NGHỆ THÔNG TIN 2006-2008 Hà nội 2008 LỜI NÓI ĐẦU Lịch sử của hệ phân tán bắt nguồn từ sự phát triển của máy tính đa người dùng. Sự ra đời của hệ thống mạng LAN tốc độ cao vào những thế kỷ 70s đã tác động đến sự phát triển của hệ phân tán. Các trạm làm việc cũng như các hệ thống máy chủ đã quyết định sự ra đời của hệ phân tán. Xu hướng này đã và còn được thúc đẩy nhờ việc phát triển phần mềm hệ điều hành và các ứng dụng phân tán. Hệ cơ sở dữ liệu phân tán có phạm vi rất rộng, từ cung cấp các tiện ích tính toán dùng cho mục đích chung của nhiều nhóm người sử dụng đến các hệ thống truyền thông đa phương tiện. Hệ cơ sở dữ liệu phân tán được xây dựng dựa trên 2 công nghệ cơ bản: (1) cơ sở dữ liệu, và (2) mạng máy tính. Hệ cơ sở dữ liệu phân tán được mô tả như là tập hợp nhiều cơ sở dữ liệu có liên quan logic đến nhau và được phân bố trên mạng máy tính. Cơ sở dữ liệu phân tán giảm được chi phí truyền thông, thời gian đáp ứng nhanh, đảm bảo tính độc lập dữ liệu , tránh dư thừa dữ liệu và chia sẻ tài nguyên. Trong Khuôn khổ luận văn này, em đã đề cập đến các cơ sở lý thuyết cũng như các phương pháp, thuật toán sử dụng trong quá trình phân tán dữ liệu. Luận văn được hoàn thành nhờ vào sự hướng dẫn tận tình của GS.TS Nguyễn Thúc Hải, Khoa CNTT, Trường ĐHBKHN. Em xin trân trọng cảm ơn Thầy GS.TS Nguyễn Thúc Hải đã hướng dẫn chỉ bảo và luôn tạo điều kiện thuận lợi cho em hoàn hành luận văn này. Một lần nữa em xin cảm ơn các thầy cô trong Khoa CNTT, TTSĐH, Trường ĐHBKHN đã giảng dạy trong suốt thời gian qua, đặc biệt xin cảm ơn Chính phủ Cộng hòa Xã hội Chủ nghĩa Việt Nam đã tạo điều kiện và cơ hội tốt cho em hoành thành học tập của mình. Hà Nội :Tháng 11 Năm 2008. Học viên: Koeu Sokmeak. MỤC LỤC Trang LỜI NÓI ĐẦU ............................................................................................... 1 TÓM TẮT LUẬN VĂN ................................................................................ 2 MỤC LỤC ...................................................................................................... 3 BẢNG VÀ HÌNH VẼ .................................................................................... 5 BẢNG CÁC TỪ VIẾT TẮT& TỪ KHÓA ................................................. 6 PHẦN 1: GIỚI THIỆU CSDL PHÂN TÁN VÀ SỰ PHÂN TÁN DỮ LIỆU ............................................................................................................... 8 CHƯƠNG 1: TỔNG QUAN VỀ HỆ CSDL PHÂN TÁN .................... 8 1. ĐỊNH NGHĨA: ............................................................................. 8 2. CÁC ĐẶC ĐIỂM CSDL PHÂN TÁN SO VỚI CSDL TẬP TRUNG: ................................................................................................ 8 3. PHÂN LOẠI CSDL PHÂN TÁN: .............................................. 13 4. XU THẾ PHÁT TRIỂN CSDL PHÂN TÁN: ............................ 18 CHƯƠNG 2 : CÁC KHÁI NIỆM PHÂN TÁN DỮ LIỆU ..................... 20 1. LÝ DO PHÂN ĐOẠN :................................................................ 20 2. CÁC KIỂU PHÂN ĐOẠN: ......................................................... 21 3. MỨC ĐỘ PHÂN ĐOẠN: ............................................................ 22 4. CÁC QUY TẮC PHÂN ĐOẠN ĐÚNG ĐẮN:........................... 22 5. CÁC KIỂU CẤP PHÁT: ............................................................. 23 PHẦN II: CÁC KỸ THUẬT PHÂN TÁN DỮ LIỆU ................................ 25 CHƯƠNG 3: KỸ THUẬT PHÂN ĐOẠN: .............................................. 26 3.1. PHÂN ĐOẠN NGANG: ............................................................ 26 3.1.1. YẾU CẦU THÔNG TIN VỀ PHÂN ĐOẠN NGANG : ....................................................................................................... 26 3.1.1.1: THÔNG TIN VỀ CƠ SỞ DỮ LIỆU : .................... 26 3.1.1.2. THÔNG TIN ỨNG DỤNG: ..................................... 29 3.1.2. PHÂN LOẠI PHÂN ĐOẠN NGANG:.................................. 32 3.1.2.1. PHÂN ĐOẠN NGANG NGUYÊN THỦY: ............... 32 3.1.2.1.1. THUẬT TOÁN COM-MIN: ........................... 36 3.1.2.1.2. THUẬT TOÁN PHORIZONTAL: ................ 38 3.1.2.2. PHÂN ĐOẠN NGANG DẪN XUẤT: ........................ 42 3.1.3. KIỂM ĐỊNH TÍNH ĐÚNG ĐẮN CỦA PHÂN ĐOẠN NGANG 48 3.2. PHƯƠNG PHÁP PHÂN ĐOẠN DỌC AVP[13] ............................ 50 3.2.1. CÁC LÝ DO CHỌN AVP ........................................................ 50 3.2.2. CÁC YÊU CẦU VỀ THÔNG TIN .......................................... 52 3.2.3. MÔ HÌNH CHI PHÍ ................................................................. 53 3.2.4. THUẬT TOÁN PHÂN ĐOẠN DỌC AVP ............................. 54 3.2.4.1. GIAI ĐOẠN XÂY DỰNG CÂY PT ................................ 55 3.2.4.2. GIAI ĐOẠN TRÍCH KẾT QUẢ CÁC ĐOẠN DỮ LIỆU:.............................................................................................................. 61 3.2.5. TÓM TẮT ................................................................................... 65 CHƯƠNG 4: KỸ THUẬT PHÂN BỐ DỮ LIỆU ................................... 66 4.1. MỞ ĐẦU : ....................................................................................... 66 4.2. MÔ HÌNH VÀ MỘT SỐ VẤN ĐỀ CƠ BẢN LIÊN QUAN ĐẾN PHÂN BỐ DỮ LIỆU ........................................................................... 67 4.2.1. ĐẶT RA BÀI TOÁN .............................................................. 67 4.2.2. YÊU CẦU THÔNG TIN ........................................................ 69 4.2.2.1. THÔNG TIN VỀ CSDL .................................................. 69 4.2.2.2. THÔNG TIN VỀ ỨNG DỤNG ....................................... 69 4.2.2.3. THÔNG TIN VỀ CÁC TRẠM: ...................................... 70 4.2.2.4. THÔNG TIN VỀ MẠNG: ............................................... 70 4.2.3. MÔ HÌNH PHÂN BỐ DỮ LIỆU ............................................. 70 4.3. PHƯƠNG PHÁP HEURISTIC ĐỐI VỚI PHÂN BỐ DỮ LIỆU ĐỘNG[11] ...................................................................................................... 73 4.3.1. THUẬT TOÁN PHÂN BỐ TỐI ƯU(BRUNSTORM) ............ 73 4.3.1.1. ƯU ĐIỂM CỦA THUẬT TOÁN: ...................................... 76 4.3.1.2. NHƯỢC ĐIỂM CỦA THUẬT TOÁN:............................. 76 4.3.2. THUẬT TOÁN NGƯỠNG(TRESHOLD)................................. 77 4.4. TÓM TẮT:........................................................................................... 83 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................... 84 1. KẾT LUẬN :......................................................................................... 84 2. HƯỚNG PHÁT TRIỂN : .................................................................... 84 CÁC TÀI LIỆU THAM KHẢO .................................................................. 85 BẢNG VÀ HÌNH VẼ Trang Hình 1. Mô hình hệ CSDL phân tán thuần nhất đơn giản 9 Hình 2: Kiến trúc hệ CSDL phân tán thuần nhất 10 Hình 3: Phân đoạn quan hệ tổng thể R 11 Hình 4: Phân loại các hệ CSDL phân tán theo kiến trúc 12 Hình 5 : So sánh các lựa chọn nhân bản 19 Hình 6: CSDL mẫu 23 Hình 7 : Biểu diễn mối liên hệ giữa các quan hệ nhờ các đường nối. 23 Hình 8: Mô tả BVP 46 Hình 9 : Cây phân đoạn PT 51 Bảng 1 : Tần xuất để truy xuất các đoạn của các truy vấn. 52 Hình 10: Xây dựng cây PT. 53 Bảng 2: Các lợi nhuận trong bước 0 của cây PT hình 9. 54 Hình 11: Lược đồ Venn 54 Hình 12: Đoạn i trong thuật toán tối ưu 69 Bảng 3: Liệt kê xác suất truy cập ít nhất một lần 72 Hình 13: Biểu diễn đoạn i với bộ đếm 72 Hình 14 : Os hàm của xs trong hệ thống có 5 trạm 75 Hình 15 : Đồ thị đường cong khi thay đổi ngưỡng 76 BẢNG CÁC TỪ VIẾT TẮT& TỪ KHÓA Simple Predicate Minterm Predicate Miniterm selectivity Sel Access Frequency Relation Minterm Fragement Completeness Minimality Nonrelevant Attribute Usage Value aff(A,B) Physical Site Virtual Site Assign Assign set Query Processing Cost QPC Site Tranmission Cost STC Data Allocation Problem DAP File Allocation Problem FAP Processing Cost PC Tranmission Cost TC Access Cost AC Integrity Enforcement Cost IE Concurrency Control Cost CC Attribute Affinity Matrix Partition Vị từ đơn giản Vị từ hội sơ cấp Số lượng các bộ được truy xuất bởi một câu truy vấn Độ tuyển của hội sơ cấp Tần số truy xuất Quan hệ Đoạn hội sơ cấp Tính đầy đủ của vị từ đơn giản Tính tiểu cực của vị từ đơn giản Liên đới Giá trị sử dụng của các thuộc tính Số đo ái lực Trạm vật lý Trạm ảo Chỉ định Tập các chỉ định Chi phí để xử lý câu hỏi Chi phí để lưu trữ đoạn tại trạm Vấn đề định vị CSDL Vấn đề định vị tệp Chi phí xử lý Chi phí truyền dữ liệu Chi phí truy nhập Chi phí đảm bảo tính toàn vẹn Chi phí điều khiển tương tranh Ma trận ái lực thuộc tính Phân hoạch Partition Algorithm Fragement Bond Energy Algorithm BEA Derived Horizontal Fragmentation Primary Horizontal Fragmentation Couter Ma trix Adaptive Vertical Partitioning AVP Partition Tree Binary Vertical Partitioning BVP Thuật toán phân hoạch Phân đoạn hoặc phân mảnh Thuật toán năng lượng nối Phân đoạn ngang dẫn xuất Phân đoạn ngang nguyên thủy Ma trận đếm Phân đoạn dọc thích nghi Cây phân đoạn Phân đoạn dọc nhị phân Học viên: Koeu Sokmeak -1- Kỹ thuật Phân tán dữ liệu PHẦN 1: GIỚI THIỆU CSDL PHÂN TÁN VÀ SỰ PHÂN TÁN DỮ LIỆU CHƯƠNG 1: TỔNG QUAN VỀ HỆ CSDL PHÂN TÁN 1. ĐỊNH NGHĨA: Cơ sở dữ liệu phân tán (CSDL phân tán) có thể được định nghĩa như sau: CSDL phân tán là một tập các CSDL 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ị 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à trông suốt đối với người sử dụng [1]. Định nghĩa này nhấn mạnh hai khía cạnh quan trọng của CSDL phân tán: 1- Tính phân tán, thực tế dữ liệu không cư trú ở cùng một trạm, vì vậy chúng ta có thể phân biệt mỗi CSDL phân tán với CSDL tập trung. 2- Sự tương quan lôgic, các dữ liệu có một số tính chất ràng buộc lẫn nhau và như vậy có thể phân biệt CSDL phân tán với tập các CSDL địa phương hoặc với các tệp cư trú ở các trạm khác nhau trên mạng. 2. CÁC ĐẶC ĐIỂM CSDL PHÂN TÁN SO VỚI CSDL TẬP TRUNG: Để dễ xem xét đặc điểm của hệ CSDL phân tán ta xét chúng thông qua các đặc điểm của hệ CSDL tập trung: • Điều khiển tập trung: Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak -2- Kỹ thuật Phân tán dữ liệu Điều khiển tập trung các nguồn tài nguyên thông tin của một hãng hoặc một tổ chức được xem như động cơ thúc đẩy mạnh mẽ nhất của việc đưa vào sử dụng CSDL. Chúng phát triển như sự tiến hoá của các hệ thông tin, trong đó mỗi ứng dụng có các tệp riêng của nó. Chức năng cơ sở của người quản trị cơ sở dữ liệu là đạt được sự an toàn dữ liệu. Trong CSDL phân tán ý tưởng điều khiển tập trung phần nào đó ít được nhấn mạnh so với CSDL tập trung, điều này phụ thuộc vào kiến trúc của hệ thống. Nói chung, trong địa phương xác định một cấu trúc điều khiển phân cấp trên cơ sở người quản trị cơ sở dữ liệu tổng thể có trách nhiệm trung tâm của toàn bộ CSDL, những người quản trị cơ sở dữ liệu địa phương có trách nhiệm với các CSDL địa phương của họ.Tuy nhiên, nhấn mạnh rằng người quản trị cơ sở dữ liệu địa phương có thể có một sự tự trị cao hơn tới mức là phối hợp giữa các trạm được thực hiện bởi chính người quản trị địa phương mà không cần tới người quản trị CSDL tổng thể. Đặc điểm này được gọi là sự tự trị của các trạm. Các CSDL phân tán có thể không giống nhau về mức độ tự trị: từ tự trị hoàn toàn không có người quản trị cơ sở dữ liệu tập trung nào, đến hầu như hoàn toàn điều khiển tập trung. • Tính độc lập dữ liệu Độc lập dữ liệu có nghĩa là một tổ chức dữ liệu thực sự là trông suốt với người lập trình ứng dụng. Các chương trình được viết có cách nhìn quan niệm về dữ liệu gọi là sơ đồ quan niệm.Thuận lợi chính của sự độc lập dữ liệu là các chương trình không ảnh hưởng khi có thay đổi trong tổ chức vật lý của dữ liệu. Trong CSDL phân tán sự độc lập dữ liệu có tầm quan trọng như trong CSDL truyền thống và bổ xung một hướng mới vào khái niệm độc lập dữ liệu là sự trông suốt trong phân tán. Tính trong suốt (transparency) của một hệ CSDL phân tán biểu thị sự tách biệt những ngữ nghĩa ở mức cao với những vấn đề thực hiện ở mức thấp. Nói một cách khác, một hệ thống trong suốt dấu đi nhưng chi tiết thể hiện với người dùng. Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak -3- Kỹ thuật Phân tán dữ liệu Thế lợi của một CSDL trong suốt hoàn toàn là mức hỗ trợ cao để phát triển những ứng dụng phức tạp. Hiển nhiên là chúng ta muốn tạo ra những CSDL trong suốt hoàn toàn. Sự trong suốt phân tán được hiểu: Các chương trình được viết như với CSDL không phân tán. Như vậy sự đúng đắn của các chương trình không thay đổi khi dữ liệu từ trạm này sang trạm khác, mặc dù tốc độ thực hiện có thể bị ảnh hưởng. Độc lập dữ liệu được đáp ứng trong các CSDL tập trung quá kiến trúc nhiều mức có các mô tả dữ liệu khác nhau và các bản sao của chúng. Xuất hiện các khái niệm: sơ đồ quan niệm, sơ đồ lưu trữ, sơ đồ ngoài. • Giảm sự dư thừa Trong CSDL tập trung việc giảm dư thừa đã được giải quyết vì hai lý do: Thứ nhất các mâu thuẫn giữa các bản sao của cùng một dữ liệu được ngăn ngừa tự động bằng cách chỉ có một bản sao.Thứ hai, giảm không gian lưu trữ. Giảm dư thừa đạt được bằng cách dùng chung dữ liệu, tức là cho phép một vài ứng dụng cùng truy nhập đến một số tệp và bản ghi. Mặc dù vậy, trong CSDL phân tán có một số lý do để quan tâm đến sự giảm dư thừa dữ liệu.Thứ nhất, tính địa phương của các ứng dụng có thể tăng lên nếu dữ liệu được sao lại ở tất các trạm mà ở đó các ứng dụng cần đến. Thứ hai, tính sẵn dùng của hệ thống có thể tăng lên vì sai ở một trạm không làm dừng việc thực hiện các ứng dụng tại các trạm nếu dữ liệu được sao lại Nhìn chung, những lý do hạ chế sự dư thừa vẫn có giá trị trong CSDL phân tán, do đó việc đánh giá mức dư thừa đòi hỏi sự cân nhắc phức tạp. Có thể nói rằng: sự thuận lợi của bản dữ liệu tăng theo tỷ số các truy nhập tìm kiếm trên các tuy nhập cập nhật được thực hiện bởi các ứng dụng tới nó. Sở dĩ có vấn đề trên là vì ta có nhiều bản sao của một cá thể dữ liệu thì việc tìm kiếm có thể thực hiện trên một bản sao bất kỳ trong khi việc cập nhật dữ liệu phải được thực hiện một cách nhất quán trên tất cả các bản sao. Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak -4- Kỹ thuật Phân tán dữ liệu • Cấu trúc vật lý phức tạp và sự truy nhập hiệu quả: Các cấu trúc truy nhập phức tạp, như các chỉ dẫn thứ cấp, các dây truyền giữa các tập là vấn đề quan trọng của CSDL truyền thống và thường do hệ quản trị CSDL đảm nhận. Việc cung cấp các cấu trúc truy nhập phức tạp này làm tăng hiệu quả truy nhập dữ liệu. Trong CSDL phân tán các cấu trúc truy nhập phức tạp này không phải là công cụ thích hợp cho sự truy nhập hiệu quả. Việc truy nhập hiệu quả các CSDL phân tán không thể được cung cấp bằng các cấu trúc vật lý bởi vì việc xây dựng và duy trì các cấu trúc như vậy đối với hệ phân tán là khó khăn và các ứng dụng thực hiện ở mức bản ghi trong CSDL phân tán là không phù hợp. Để truy nhập CSDL, có hai thủ tục cài đặt cho hệ phân tán:  Thủ tục cho phép truy nhập bản ghi từ xa, mỗi truy nhập tới một bản ghi thì không chỉ bản ghi đó được truyền đi mà cả nhiều thông báo khác cũng phải được trao đổi.  Một thủ tục hiệu qủa hơn cho phép nhóm càng nhiều càng tốt tất cả các truy nhập được thực hiện tại cùng một trạm. Thủ tục này gồm hai kiểu thao tác: thực hiện các chương trình cục bộ tại từng trạm và truyền các tệp giữa các trạm. Thủ tục như vậy gọi là phương án truy nhập phân tán (Distributed Access Plan). Phương án truy nhập phân tán có thể được viết bởi người lập trình hay được sản sinh tự động bởi một bộ tối ưu hoá. • Tính toàn vẹn, phục hồi và điều khiển tương tranh Trong các CSDL, các vấn đề về tính toàn vẹn, phục hồi và điều khiển tương tranh quan hệ rất chặt chẽ với nhau. Giải pháp của các vấn đề này bao hàm việc cung cấp các giao tác. Một giao tác là một đơn vị nguyên tố, nghĩa là một dãy các giao tác, hoặc được thực hiện hoàn toàn, hoặc không được thực hiện. Rõ ràng các Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak -5- Kỹ thuật Phân tán dữ liệu giao tác nguyên tố là các phương tiện để đạt được tính toàn vẹn CSDL bởi vì chúng đảm bảo hoặc tất cả các thao tác biến đổi CSDL từ một trạng thái toàn vẹn này sang một trạng thái toàn vẹn khác, hoặc trạng thái ban đầu được giữ nguyên như cũ. Hai tác động ảnh hưởng tới tính nguyên tố của giao tác đó là hỏng hóc và tương tranh. Hỏng hóc có thể làm hệ thống dừng giữa lúc thực hiện giao tác, do đó vi phạm sự đòi hỏi của tính nguyên tố. Sự tương tranh của nhiều thao tác có thể cho phép một giao tác quan sát một trạng thái chuyển tiếp không toàn vẹn tạo ra bởi một giao tác khác trong quá trình thực hiện nó. Sự phục hồi có liên quan tới vấn đề đảm bảo tính nguyên tố của giao tác khi có hỏng hóc. Trong CSDL phân tán đây là một khía cạnh quan trọng bởi vì một số trạm tham gia thực hiện giao tác có thể bị hỏng Điều khiển tương tranh liên quan đến sự đảm bảo tính nguyên tố của giao tác khi có sự tương tranh của các giao tác. Vấn đề này có thể xem như một vấn đề đồng bộ hoá điển hình. Đối với CSDL phân tán vấn đề này khó hơn so với CSDL tập trung. • Tính riêng tư và an toàn Trong CSDL tập trung do điều khiển tập trung nên có thể chắc chắn rằng mọi truy nhập dữ liệu đều được thực hiện. Điều này CSDL tập trung tự đạt được không cần đến các thủ tục điều khiển đặc biệt nào. Trong CSDL phân tán, những người quản trị địa phương cũng phải xử lý bài toán như những người quản trị dữ liệu trong CSDL tập trung. Mặc dù vậy, có hai đặc điểm đặc thù cho CSDL phân tán.  Thứ nhất trong CSDL phân tán với mức tự trị cao nhất, những người quản trị địa phương cảm thấy bảo vệ hơn, bởi vì nó có thể áp đặt các biện pháp bảo vệ của mình thay vì phụ thuộc vào người quản trị dữ liệu CSDL tập trung  Thứ hai, vấn đề bảo mật là vấn đề cố hữu với hệ phân tán, bởi vì vấn đề bảo mật và an toàn cho mạng truyền thông là rất khó thực hiện. Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak -6- Kỹ thuật Phân tán dữ liệu 3. PHÂN LOẠI CSDL PHÂN TÁN: Dựa vào kiến trúc, các hệ CSDL phân tán có thể phân làm hai loại[5]:  Các hệ CSDL phân tán thuần nhất  Các hệ CSDL phân tán không thuần nhất Tính thuần nhất và không thuần nhất ở đây được xem xét dưới góc độ các hệ CSDL cục bộ tại các trạm. Với hệ CSDL phân tán thuần nhất thì các hệ CSDL cục bộ tại các trạm đồng nhất còn với hệ CSDL phân tán không thuần nhất thì các hệ CSDL cục bộ tại các trạm có thể khác nhau. CSDL phân tán thuần nhất hơi giống với CSDL tập trung chỉ khác ở điểm dữ liệu được phân tán tại một số trạm trên mạng. Một CSDL phân tán thuần nhất đơn giản có thể được biểu diễn như trong [hình 1]. Hệ quản trị CSDL phân tán thuần nhất bao gồm nhiều bộ sưu tập dữ liệu.Tùy mức tự trị, hệ số này có thể phân thành các loại tự trị và không tự trị Trong mô hình này không có các người sử dụng cục bộ, các người sử dụng truy nhập các CSDL thông qua một giao diện tổng thể. Lược đồ tổng thể là hợp của tất cả các mô tả dữ liệu cục bộ và các khung nhìn của người sử dụng được định nghĩa trên lược đồ tổng thể. Trong hình 1 đã không xem xét đến các lược đồ cục bộ cho các CSDL cục bộ. Nếu ta muốn đưa ra lược đồ quan niệm chuẩn cho CSDL phân tán theo kiểu ANSI – SPARC thì thêm vào các hệ CSDL cục bộ và các lược đồ cục bộ. Thực tế hầu hết các hệ thuần nhất không có các lược đồ cục bộ và chỉ có một phần mềm quản trị dữ liệu hạn chế ở mức cục bộ. Kiến trúc 3 tầng ANSI – SPARC của các hệ quản trị CSDL tập trung thực hiện đang được dùng trong phần lớn các hệ quản trị CSDL thương mại Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak -7- Kỹ thuật Phân tán dữ liệu Mô hình CSDL tập trung ANSI – SPARC có thể phát triển cho mô hình CSDL phân tán thuần nhất như trong [hình 1]. Người dùng tổng thể Người dùng tổng thể Hệ CSDL phân tán Phần mềm quản trị dữ liệu Phần mềm quản trị dữ liệu CSDL 1 CSDL 1 Phần mềm quản trị dữ liệu CSDL 1 Hình 1. Mô hình hệ CSDL phân tán thuần nhất đơn giản Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak -8- View tổng thể 1 cho USER Kỹ thuật Phân tán dữ liệu View tổng thể n cho USER Lược đồ tổng thể Lược đồ phân đoạn Lược đồ sắp chỗ Lược đồ quan niệm cục bộ 1 Lược đồ quan niệm cục bộ n CSDL cục bộ 1 CSDL cục bộ n Hình 2: Kiến trúc hệ CSDL phân tán thuần nhất Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak Kỹ thuật Phân tán dữ liệu -9- Lược đồ phân đoạn giải quyết vấn đề phân chia các quan hệ tổng thể thành các đoạn như thế nào để thực hiện các thao tác với CSDL được tốt nhất. [Hình 3] cho một ví dụ phân đoạn quan hệ R. Quan hệ này được chia thành 5 đoạn tách biệt và được lưu trữ tại các trạm khác nhau. R a b D C E Hình 3: Phân đoạn quan hệ tổng thể R Quan hệ R có thể được tái thiết lại từ các đoạn như sau: R = (A join B) union (C join D) union E Trong đó join và union là các phép toán qua hệ thống thường. Tất nhiên để có được biểu thức trên thì trong quá trình phân đoạn cần phải tuân theo một số quy tắc nhất định. Chẳng hạn, khi thực hiện phân đoạn dọc thì khoá chính của quan hệ R phải được đưa vào trong tất cả các đoạn. Các hệ CSDL phân tán không thuần nhất lại có thể phân ra làm hai lớp con chính tuỳ theo cách thức thích hợp các hệ CSDL cục bộ vào hệ thống:  Tích hợp hoàn toàn vào hệ thống.  Cung cấp những “hook” đơn giản thường được gọi là cổng nối (Gateway) để thực hiện liên kết với các hệ thống bên ngoài. Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak - 10 - Kỹ thuật Phân tán dữ liệu Các Hệ CSDL Phân tán Không thuần nhất Thuần nhất Tích hợp theo hệ Tích hợp theo cổng thống nối Hình 4: Phân loại các hệ CSDL phân tán theo kiến trúc Ta lại có thể tiếp tục chia các lớp con tuỳ theo kiến trúc hệ thống của chúng. Hầu hết các nghiên cứu về CSDL phân tán cho đến nay hầu hết tập trung vào các hệ thuần nhất. Tuy vậy, trong tương lai các hệ không thuần nhất sẽ được quan tâm thuộc lớp này. Ở đây chúng ta sẽ tập trung chủ yếu vào các hệ CSDL phân tán thuần nhất. Sự phát triển của công nghệ CSDL, công nghệ máy tính và công nghệ truyền thông cho phép khắc phục các nhược điểm của các ứng dụng xử lý CSDL tập trung bằng việc xây dựng các hệ CSDL phân tán. Mặc dù công nghệ phân tán mới chỉ phát triển trong khoảng 15 năm trở lại đây, nhưng những sản phẩm thế hệ đầu của hệ phân tán đã xuất hiện trên thị trường và từng bước chứng minh tính ưu việt của nó so với hệ tập trung truyền thống. Theo dự đoán của Tamer Ozsu và Patrik Valduriez là chuyên gia trong lĩnh vực CSDL phân tán thì trong một tương lai không xa, CSDL phân tán sẽ thay thế CSDL tập trung. Vấn đề thiết kế CSDL phân tán là công việc đầu tiên và rất quan trọng trong quá trình xây dựng một CSDL phân tán. Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải Học viên: Koeu Sokmeak - 11 - Kỹ thuật Phân tán dữ liệu 4. XU THẾ PHÁT TRIỂN CSDL PHÂN TÁN: Trong những năm gần đây, CSDL phân tán đã trở thành một lĩnh vực quan trọng của công nghệ thông tin, tầm quan trọng của nó ngày một nâng cao theo sự phát triển của công nghệ thông tin. Có nhiều nguyên nhân dẫn đến sự phát triển của các hệ CSDL phân tán. Chúng ta có thể kể sau đây một số động cơ thúc đẩy sự phát triển: • Vấn đề cơ cấu tổ chức và kinh tế Nhiều tổ chức có cơ cấu tổ chức không tập trung. Đối với các tổ chức này thì việc xây dựng một CSDL phân tán là phù hợp một cách tự nhiên với cấu trúc của tổ chức đó. Cùng với sự phát triển của công nghệ máy tính, động cơ thúc đẩy về 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 đặc biệt quan tâm. • Xây dựng mối quan hệ giữa các CSDL đã tồn tại Các CSDL phân tán là giải pháp tự nhiên khi một số các CSDL đã tồn tại trong tổ chức và xuất hiện sự cần thiết thực hiện các ứng dụng tổng thể. Trong trường hợp các CSDL phân tán được xây dựng từ dưới lên từ các CSDL địa phương hiện có. Quá trình này có thể đòi hỏi phải xây dựng lại cấu trúc địa phương. Chi phí cho việc xây dựng lại cấu trúc này sẽ nhỏ hơn nhiều so với chi phí để tạo sinh ra một CSDL tập trung mới hoàn toàn • Sự tăng trưởng Trong qúa trình phát triển của mình, một tổ chức có thể thêm một số thành viên mới, khi đó CSDL phân tán cho phép ảnh hưởng tới mức thấp nhất đến sự va chạm liên quan đến các thành viên đã tồn tại. Với CSDL tập trung điều này gây mở rộng hệ thống là việc khó dự đoán trước và chi phí cao hoặc gia tăng sự va chạm không chỉ với các ứng dụng mới mà cả với các ứng dụng đã tồn tại. Viện Sau Đại Học, Khoa CNTT, Trường Đại Học Bách Khoa Hà nội GV Hướng Dẫn Khoa Học: GS.TS Nguyễn Thúc Hải