Tài liệu Nghiên cứu tối ưu truy vấn trong cơ sở dữ liệu phân tán

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ ĐIỆU NGHIÊN CỨU TỐI ƯU TRUY VẤN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN LUẬN VĂN THẠC SĨ KỸ THUẬT PHẦN MỀM Hà Nội – 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ ĐIỆU NGHIÊN CỨU TỐI ƯU TRUY VẤN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN Ngành : Công nghệ thông tin Chuyên ngành : Kỹ thuật Phần mềm Mã số : 60480103 LUẬN VĂN THẠC SĨ KỸ THUẬT PHẦN MỀM NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN TUỆ Hà Nội – 2014 2 LỜI CẢM ƠN Trước hết, tôi xin gửi lời biết ơn sâu sắc đến người thầy TS. Nguyễn Tuệ, thầy đã dành rất nhiều thời gian, tâm huyết hướng dẫn nghiên cứu và giúp tôi hoàn thành tốt luận văn tốt nghiệp này. Thầy đã có những hướng mở rất hay và những định hướng nghiên cứu thiết thực, bổ ích, đồng thời tạo điều kiện thuận lợi nhất cho tôi nghiên cứu. Tôi cũng xin được bày tỏ lòng biết ơn tới các thầy cô trường Đại học Công nghệ, ĐH Quốc gia Hà Nội đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tập thể học viên trong khóa nói chung và cá nhân tôi nói riêng. Tôi xin cảm ơn tới các thầy và các anh chị đã thường xuyên giúp đỡ, trao đổi, góp ý về những vấn đề khoa học liên quan tới luận văn. Trên tất cả, tôi xin gửi lời biết ơn tới bố mẹ, gia đình người thân. Bố mẹ đã phải làm việc vất vả tạo cơ hội và điều kiện thuận nhất giúp tôi toàn tâm toàn ý thực hiện luận văn và chọn con đường đi của mình. Một lần nữa, tôi xin chân thành cảm ơn! Nội, tháng 11 năm 2014 Học viên Nguyễn Thị Điệu 3 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Học viên thực hiện Luận văn NGUYỄN THỊ ĐIỆU 4 MỤC LỤC TRANG BÌA PHỤ............................................................................................ 1 LỜI CẢM ƠN................................................................................................... 2 LỜI CAM ĐOAN ............................................................................................. 4 MỤC LỤC ........................................................................................................ 5 Danh mục các ký hiệu và chữ viết tắt.............................................................. 7 Danh mục các bảng .......................................................................................... 8 Danh mục các hình vẽ, đồ thị........................................................................... 9 MỞ ĐẦU......................................................................................................... 11 CHƯƠNG 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN ................ 14 1.1 Cơ sở dữ liệu phân tán ......................................................................... 14 1.2 Kiến trúc của cơ sở dữ liệu phân tán .................................................... 14 1.3 Hệ cơ sở dữ liệu phân tán..................................................................... 15 1.4 Lợi ích của cơ sở dữ liệu phân tán........................................................ 16 1.5 Cơ sở dữ liệu phân tán đồng nhất và không đồng nhất ......................... 17 1.6 Lưu trữ dữ liệu phân tán....................................................................... 18 1.6.1 Nhân bản .......................................................................................... 18 1.6.2 Phân mảnh ........................................................................................ 20 1.7 Các bước thiết kế cơ sở dữ liệu phân tán.............................................. 20 1.7.1 Thiết kế quan niệm ........................................................................... 21 1.7.2 Thiết kế lôgic.................................................................................... 21 1.7.3 Thiết kế phân mảnh .......................................................................... 21 1.7.3.1 Phân mảnh ngang (Horizontal Fragmentation)............................ 22 1.7.3.2 Phân mảnh dọc (Vertical Fragmentation) ................................... 26 1.7.3.3 Phân mảnh hỗn hợp (Hybrid Fragmentation).............................. 27 1.7.4 Thiết kế định vị................................................................................. 28 1.8 Tính trong suốt của cơ sở dữ liệu phân tán........................................... 28 1.9 Vấn đề xử lý truy vấn trong CSDL phân tán ........................................ 30 CHƯƠNG 2. PHÂN TÍCH VÀ XÂY DỰNG CƠ SỞ DỮ LIỆU PHÂN TÁN ..... 34 2.1 Phân tích bài toán................................................................................. 34 2.2 Lược đồ quan niệm của cơ sở dữ liệu................................................... 35 2.3 Lược đồ cơ sở dữ liệu toàn cục ............................................................ 36 5 2.4 Thiết kế phân tán cơ sở dữ liệu cho hệ thống ....................................... 41 2.4.1 Thực trạng ........................................................................................ 41 2.4.2 Giải pháp .......................................................................................... 41 2.4.3 Phân mảnh cơ sở dữ liệu ................................................................... 42 2.5 Xử lý các nghiệp vụ của hệ thống ........................................................ 44 CHƯƠNG 3. TỐI ƯU HÓA TRUY VẤN ..................................................... 46 3.1 Mô hình xử lý truy vấn......................................................................... 46 3.1.1 Phân rã truy vấn................................................................................ 47 3.1.2 Cục bộ hóa dữ liệu............................................................................ 47 3.1.3 Tối ưu truy vấn toàn cục ................................................................... 47 3.1.4 Thực thi truy vấn phân tán ................................................................ 48 3.2 Mục đích và quy trình tối ưu truy vấn .................................................. 48 3.2.1. Không gian tìm kiếm ....................................................................... 49 3.2.2 Chiến lược tìm kiếm ......................................................................... 51 3.2.3 Mô hình chi phí phân tán .................................................................. 52 3.2.3.1 Hàm chi phí ................................................................................ 52 3.2.3.2 Các thống kê cơ sở dữ liệu.......................................................... 53 3.3 Các thuật toán tối ưu truy vấn .............................................................. 54 3.3.1 Thuật toán tối ưu truy vấn cục bộ...................................................... 55 3.3.1.1 Thuật toán INGRES....................................................................... 55 3.3.1.2 Thuật toán SYSTEM R.................................................................. 57 3.3.2 Thuật toán tối ưu toàn cục................................................................. 59 3.3.2.1 Thuật toán phân tán INGRES (D- INGRES).................................. 60 3.3.2.2 Thuật toán phân tán SYSTEM R*.................................................. 61 CHƯƠNG 4. CÀI ĐẶT THỰC NGHIỆM.................................................... 64 4.1 Hệ thống mạng của cơ sở dữ liệu ......................................................... 64 4.2 Các truy vấn đã thực hiện..................................................................... 65 4.3 Đánh giá............................................................................................... 67 KẾT LUẬN..................................................................................................... 68 TÀI LIỆU THAM KHẢO.............................................................................. 70 6 Danh mục các ký hiệu và chữ viết tắt STT Từ viết tắt Ý nghĩa 1 DBMS Database Management System 2 SQL Structured Query Language 3 OS Operating System 4 DDBS Distributed Database System 5 DDB Distributed Database 6 DDBMS Distributed Database Management System 7 CSDL Cơ sở dữ liệu 8 CPU Central Processing Unit 9 I/O Input/Output 10 SD Service Directory 11 QEP Query Execution Plan 12 UK United Kingdom 13 QOA Query Optimization Algorithm 14 ORQ Mono - Relation Query 7 Danh mục các bảng Bảng 1.1 Chi phí của chiến lược 1.................................................................... 32 Bảng 1.2 Chi phí của chiến lược 2.................................................................... 32 Bảng 2.1 Danh sách các Actor của hệ thống..................................................... 35 Bảng 2.2 Danh sách các Use case của hệ thống................................................ 35 Bảng 2.3 Bảng loại hình kinh doanh................................................................. 36 Bảng 2.4 Bảng Quận/Huyện............................................................................. 36 Bảng 2.5 Bảng tổ chức ..................................................................................... 36 Bảng 2.6 Bảng thông tin server của mỗi tổ chức .............................................. 37 Bảng 2.7 Bảng phòng ban ................................................................................ 37 Bảng 2.8 Bảng nhóm........................................................................................ 37 Bảng 2.9 Bảng người phụ trách ........................................................................ 37 Bảng 2.10 Bảng loại contact............................................................................. 38 Bảng 2.11 Bảng loại dịch vụ ............................................................................ 38 Bảng 2.12 Bảng đơn vị giá ............................................................................... 38 Bảng 2.13 Bảng dịch vụ ................................................................................... 39 Bảng 2.14 Bảng ghi nhận dịch vụ đã cung cấp cho khách hàng........................ 39 Bảng 2.15 Bảng phân mảnh ngang tổ chức....................................................... 43 Bảng 3.1 So sánh các thuật toán ....................................................................... 63 8 Danh mục các hình vẽ, đồ thị Hình 1.1 Tổng quan về cơ sở dữ liệu phân tán.................................................. 14 Hình 1.2 Lược đồ định vị cơ sở dữ liệu ............................................................ 15 Hình 1.3 Kiến trúc cơ sở dữ liệu phân tán ........................................................ 15 Hình 1.4 Xử lý tập tin truyền thống.................................................................. 16 Hình 1.5 Xử lý cơ sở dữ liệu ............................................................................ 16 Hình 1.6 Cơ sở dữ liệu phân tán đồng nhất....................................................... 18 Hình 1.7 Cơ sở dữ liệu phân tán không đồng nhất............................................ 18 Hình 1.8 Khởi tạo bảng Subscriber không đồng nhất trong cơ chế nhân bản .... 20 Hình 1.9 Các bước thiết kế CSDL phân tán...................................................... 21 Hình 1.10 Các quan hệ trong cơ sở dữ liệu Ngân hàng(CSDL Banking) .......... 23 Hình 1.11 Phân mảnh ngang quan hệ TAIKHOAN.......................................... 25 Hình 1.12 Đồ thị nối giữa các mảnh ................................................................. 26 Hình 1.13 Phân mảnh dọc quan hệ TAIKHOAN.............................................. 27 Hình 1.14 Phân mảnh hỗn hợp ......................................................................... 28 Hình 1.15 Khôi phục phân mảnh hỗn hợp ........................................................ 28 Hình 1.16 Trong suốt phân mảnh ..................................................................... 29 Hình 1.17 Sự trong suốt về vị trí ...................................................................... 30 Hình 1.18 Chiến lược thứ nhất ......................................................................... 32 Hình 1.19 Chiến lược thứ hai ........................................................................... 32 Hình 2.1 Sơ đồ Use case tổng quan của hệ thống ............................................. 35 Hình 2.2 Lược đồ thực thể liên kết ................................................................... 35 Hình 2.3 Lược đồ cơ sở dữ liệu quan hệ toàn cục (gọi là CSDL SD)................ 40 Hình 2.4 Mô hình cơ sở dữ liệu tập trung ......................................................... 41 Hình 2.5 Mô hình CSDL phân tán cho ứng dụng.............................................. 42 Hình 2.6 Lược đồ cục bộ cơ sở dữ liệu thứ nhất ............................................... 44 Hình 2.7 Lược đồ cục bộ cơ sở dữ liệu thứ hai quản lý chung .......................... 44 Hình 3.1 Mô hình xử lý truy vấn phân tán........................................................ 46 Hình 3.2 Quy trình tối ưu truy vấn ................................................................... 49 Hình 3.3 Biểu diễn truy vấn bằng cây nối......................................................... 50 Hình 3.4 Hai loại cây nối chính ........................................................................ 51 Hình 3.5 Các hoạt động tối ưu trong chiến lược đơn định ................................ 51 9 Hình 3.6 Hoạt động tối ưu trong chiến lược ngẫu nhiên hóa............................. 52 Hình 3.7 Ví dụ về truyền tải dữ liệu cho truy vấn ............................................. 53 Hình 3.8 Đồ thị nối của truy vấn ...................................................................... 58 Hình 3.9 Lựa chọn thứ tự nối ........................................................................... 59 Hình 4.1 Các cơ sơ sở dữ liệu được phân tán.................................................... 65 Hình 4.2 Các linked server cho kết nối từ xa .................................................... 65 Hình 4.3 Màn hình đăng nhập hệ thống............................................................ 66 Hình 4.4 Màn hình thống kê tất cả các dịch vụ đã cung cấp ............................. 66 Hình 4.5 Màn hình thống kê dịch vụ đã tất toán theo ngày............................... 66 Hình 4.6 Màn hình thống kê nhân viên............................................................. 67 Hình 4.7 Biểu đồ so sánh thời gian thực thi truy vấn (dựa vào chức năng thống kê dịch vụ đã cung cấp).................................................................................... 67 Hình 4.8 Biểu đồ so sánh thời gian thực thi truy vấn (dựa vào chức năng thống kê dịch vụ đã tất toán) ...................................................................................... 68 10 MỞ ĐẦU 1. Lý do chọn đề tài Cơ sở dữ liệu phân tán là thích hợp với môi trường quản lý phân tán của các công ty, doanh nghiệp. Ngày nay, khi mà các công ty phát triển ngày càng mạnh mẽ, không đơn thuần chỉ hoạt động kinh doanh trên một địa bàn, một khu vực địa lý mà phát triển phân tán ở nhiều nơi khác nhau, trên nhiều vùng miền (Quận/Huyện hoặc Tỉnh/Thành). Các công ty này đều có một hoặc nhiều chi nhánh nhằm quản lý các hoạt động kinh doanh của họ. Khi có nhiều chi nhánh con cùng hoạt động, việc lưu trữ dữ liệu tập trung không phải là hiệu quả trong trường hợp này bởi nhiều lý do như dữ liệu truyền tải quá mạng với kích thước lớn sẽ ảnh hưởng đến tốc độ, chi phí và bảo mật, lượng người dùng truy xuất đến máy chủ cơ sở dữ liệu nhiều sẽ dẫn đến quá tải. Giải pháp hiệu quả cho bài toán này là lưu trữ phân tán dữ liệu, tức là dữ liệu của mỗi chi nhánh sẽ được lưu trữ và quản lý cục bộ tại mỗi vị trí của chi nhánh đó, đảm bảo tính trong suốt đối với người sử dụng. Bài toán trên lại gặp một vấn đề đó là khi trụ sở chính công ty muốn tổng hợp dữ liệu từ các chi nhánh hoặc giữa các chi nhánh có trao đổi dữ liệu. Với người dùng, dữ liệu là trong suốt, tuy nhiên thực tế thì dữ liệu sẽ phải được tổng hợp lại từ rất nhiều vị trí khác nhau qua môi trường mạng. Khi dữ liệu truy vấn nhỏ thì thì không gặp vấn đề gì, nhưng đến thời điểm dữ liệu truy vấn có thể là vài chục nghìn hoặc hàng triệu bản ghi thì thời gian trả lời truy vấn và là một vấn đề lớn và cần có phải pháp cho từng bài toán cụ thể. Việc tối ưu truy vấn phân tán làm giảm các chi phí thực hiện truy vấn, làm tăng hiệu suất của hệ thống. Vì vậy, luận văn chọn hướng nghiên cứu tối ưu truy vấn phân tán làm đề tài. 2. Mục tiêu và nhiệm vụ nghiên cứu Luận văn nghiên cứu thuật toán tối ưu truy vấn trong cơ sở dữ liệu phân tán chú trọng tới Thuật toán phân tán INGRES (D-INGRES), ngoài ra Luận văn cũng trình bày về Thuật toán phân tán SYSTEM R (SYSTEM R *), với nghiên cứu này luận văn nhằm tìm ra giải pháp hiệu quả cho thực thi các phép vấn tin từ xa, từ đó thực hiện cài đặt thực nghiệm và đánh giá kết quả. 3. Đối tượng và phạm vi nghiên cứu a. Đối tượng nghiên cứu - Nghiên cứu lý thuyết về cơ sở dữ liệu phân tán. - Nghiên cứu xây dựng cơ sở dữ liệu phân tán cho bài toán cụ thể. - Cài đặt cơ sở dữ liệu phân tán sử dụng SQL Server 2008 R2. - Nghiên cứu thuật toán tối ưu truy vấn. 11 b. Phạm vi nghiên cứu Có 3 cách tiếp cận lưu trữ dữ liệu trong cơ sỡ dữ liệu phân tán:  Nhân bản: hệ thống duy trì nhiều bản sao (copies) giống hệt nhau của quan hệ và lưu mỗi bản sao tại các trạm khác nhau.  Phân mảnh: hệ thống phân chia các quan hệ thành nhiều mảnh và lưu trữ mỗi mảnh tại các trạm khác nhau.  Kết hợp: một quan hệ có thể được chia thanh nhiều mảnh và thực hiện nhân bản cho mỗi mảnh. Một cơ sở dữ liệu có thể được phân tán đồng nhất hoặc không đồng nhất. Hệ cơ sở dữ liệu phân tán đồng nhất (homogeneous distributed database system) nghĩa tất cả các trạm chạy cùng phần mềm hệ quản trị cơ sở dữ liệu (DBMS) nhưng hệ điều hành (OS) có thể khác nhau ở các trạm này. Với cơ sở dữ liệu phân tán không đồng nhất (heterogeneous distributed database) thì các trạm chạy phần mềm hệ quản trị cơ sở dữ liệu khác nhau hoặc hệ thống cơ sở dữ liệu khác nhau. Luận văn tiếp cận Cơ sở dữ liệu phân tán đồng nhất và lưu trữ phân mảnh ngang. Thực nghiệm trên cơ sở dữ liệu này và đánh giá hiệu quả tối ưu của truy vấn. 4. Phương pháp nghiên cứu a. Phương pháp lý thuyết Luận văn nghiên cứu và tham khảo tài liệu, các công trình khoa học về cơ sở dữ liệu phân tán, nguyên lý các hệ phân tán. Hệ thống lại các vấn đề và rút ra kết luận so sánh giữa thời gian trả lời truy vấn chưa tối ưu và thời gian trả lời vấn tin đã tối ưu. b. Phương pháp thực nghiệm Luận văn cài đặt cơ sở dữ liệu phân tán cho một bài toán cụ thể trên môi trường mạng LAN, cài đặt các phép truy vấn từ xa, thực hiện tối ưu các phép truy vấn và đưa ra đánh giá cụ thể. 5. Kết quả dự kiến Nghiên cứu và lựa chọn thuật toán phù hợp cho bài toán, cài đặt các nghiệp vụ phía trung tâm áp dụng thuật toán phân tán Ingres để so sánh thời gian trả lời truy vấn phân tán khi chưa tối ưu và khi đã tối ưu. Đưa ra biểu đồ đánh giá với nhiều phép vấn tin khác nhau. 6. Ý nghĩa khoa học và thực tiễn của đề tài Luận văn phục vụ cho lĩnh vực phát triển phần mềm nhằm cải thiện thời gian trả lời vấn tin với kích thước lớn nhằm tiết kiệm chi phí. 12 7. Đặt tên đề tài “NGHIÊN CỨU TỐI ƯU TRUY VẤN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN” 8. Bố cục luận văn Luận văn được thiết kế bao gồm 4 chương: Chương 1: Tổng quan về cơ sở dữ liệu phân tán Chương này giới thiệu tổng quan về cơ sở dữ liệu phân tán, hệ cơ sở dữ liệu phân tán, những lợi ích khi sử dụng cơ sở dữ liệu phân tán. Thế nào là đồng nhất và không đồng nhất cơ sở dữ liệu phân tán, lưu trữ cơ sở dữ liệu phân tán. Chương 2. Phân tích và xây dựng cơ sở dữ liệu phân tán Chương này nhằm giới thiệu tổng quan về bài toán thực nghiệm, thực hiện phân tích và thiết kế cơ sở dữ liệu phân tán cho bài toán sử dụng hệ quản trị SQL Server 2008. Chương 3. Tối ưu hóa truy vấn Chương này sẽ giới thiệu chung về về xử lý truy vấn phân tán. Các thuật toán giúp tối ưu truy vấn trong cơ sở dữ liệu phân tán áp dụng cho bài toán thực nghiệm. Chương 4. Cài đặt thực nghiệm Chương này sẽ thực hiện cài đặt chương trình trên môi trường thực tế. Đưa ra kết luận và đánh giá về đề tài. 13 CHƯƠNG 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN 1.1 Cơ sở dữ liệu phân tán Cơ sở dữ liệu phân tán (DDB) là một tập các cơ sở dữ liệu có quan hệ với nhau về mặt lôgic và được phân bố tại các trạm (site) trên một mạng máy tính [2, 3]. Các cơ sở dữ liệu trong trong cơ sở dữ liệu phân tán không chỉ được phân tán trong mạng cục bộ bên trong một công ty mà còn trên nhiều công ty thông qua mạng diện rộng [16]. Việc thực hiện phân tán có thể là đồng nhất hoặc không đồng nhất cơ sở dữ liệu. Hình 1.1 Tổng quan về cơ sở dữ liệu phân tán - Tính chất phân tán: Toàn bộ dữ liệu của cơ sở dữ liệu (CSDL) phân tán không được lưu trữ tại một vị trí mà lưu trữ tại nhiều trạm thuộc mạng máy tính, điều này giúp chúng ta phân biệt CSDL phân tán với CSDL tập trung đơn lẻ. - Tương quan lôgic: Toàn bộ dữ liệu của CSDL phân tán có một số thuộc tính ràng buộc chúng với nhau điều này giúp chúng ta có thể phân biệt một CSDL phân tán với một tập hợp các CSDL cục bộ [7 ]. 1.2 Kiến trúc của 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 gồm lược đồ toàn cục, lược đồ phân mảnh, lược đồ định vị và lược đồ ánh xạ cục bộ [1, 4, 6]: - Lược đồ toàn cục: Xác định toàn bộ dữ liệu được lưu trữ trong CSDL phân tán như trong CSDL tập trung. Trong mô hình quan hệ, lược đồ toàn cục là các quan hệ và mối liên kết giữa chúng. - Lược đồ phân mảnh: Mỗi quan hệ tổng thể có thể được chia thành các phần không giao nhau gọi là phân mảnh. Có nhiều cách khác nhau để phân mảnh như phân mảnh dọc, phân mảnh ngang, phân mảnh hỗn hợp. Các mảnh được mô tả bằng tên của quan hệ tổng thể cùng với chỉ mục đoạn. Ví dụ ri là đoạn thứ i của quan hệ toàn cục r. - Lược đồ định vị: Xác định mảnh dữ liệu nào được định vị tại trạm nào trên mạng. Ký hiệu rij : Cho biết mảnh thứ i của quan hệ tổng thể r được định vị trên trạm j. 14 Ví dụ 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 trạm của mạng máy tính, vì thế tạo nên ba mô hình vật lý r1 trạm 1, r2 trạm 2 và r3 trạm 3 (xem Hình 1.2). r11 r1 r r12 r2 1 r2 r3 r2 2 r4 r3 1 r3 2 r1 trạm 1 r2 trạm 2 r3 trạm 2 r3 3 Quan hệ toàn cục Phân mảnh Định vị Hình 1.2 Lược đồ định vị cơ sở dữ liệu Lược đồ toàn cục Lược đồ phân mảnh Lược đồ định vị Lược đồ ánh xạ cục bộ 1 CSDL1 Lược đồ ánh xạ cục bộ 2 CSDL2 Lược đồ ánh xạ cục bộ n CSDLn Hình 1.3 Kiến trúc cơ sở dữ liệu phân tán - Lược đồ ánh xạ cục bộ: Thực hiện ánh xạ các ảnh vật lý lên các đối tượng được thực hiện bởi hệ quản trị cơ sở dữ liệu địa phương. Tất cả các đoạn của một quan hệ tổng thể trên cùng một trạm tạo ra một ảnh vật lý. 1.3 Hệ cơ sở dữ liệu phân tán Hệ cơ cở dữ liệu phân tán (DDBS) là sự kết hợp của hai khái niệm là hệ cơ sở dữ liệu và các công nghệ mạng máy tính [15]. Hệ cơ sở dữ liệu đã đưa chúng ta từ một mô hình xử lý dữ liệu trong đó mỗi ứng dụng xác định và duy 15 trì dữ liệu riêng của mình (xem Hình 1.4) tới một mô hình trong đó dữ liệu được xác định và quản lý tập trung (xem Hình 1.5). Định hướng mới này dẫn đến độc lập dữ liệu, nhờ đó mà các chương trình ứng dụng không bị ảnh hưởng bởi những thay đổi lôgic và vật lý trong tổ chức dữ liệu và ngược lại. Chương trình 1o Dữ liệu Mô tả Tệp tin 1 Chương trình 2 Dữ liệu Mô tả Tệp tin 2 Dữ liệu dư thừ a Chương trình 3o Tệp tin 3 Dữ liệu Mô tả Hình 1.4 Xử lý tập tin truyền thống Chương trình 1 Chương trình 2 Mô tả dữ liệu Thao tác dữ liệu CSDL …. Chương trình 3 Hình 1.5 Xử lý cơ sở dữ liệu 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 (Distributed Database Management System - DDBMS). Trong ngữ cảnh xử lý phân tán thì DDBMS 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. Hệ cơ sở dữ liệu phân tán không đơn thuần bao gồm nhiều file dữ liệu được tổ chức riêng lẻ trên thiết bị nhớ của mạng máy tính. Để tạo một hệ CSDL phân tán, các tệp tin không chỉ có quan hệ với nhau về mặt lôgic mà còn cần có một cấu trúc giao diện chung giữa chúng để các tập tin có thể truy cập lẫn nhau [4]. 1.4 Lợi ích của cơ sở dữ liệu phân tán So với các cơ sở dữ liệu tập trung truyền thống, cơ sở dữ liệu phân tán có những ưu điểm sau [15, 16]:  Tính tự trị cục bộ (Local Autonomy): tất cả dữ liệu trong cơ sở dữ liệu phân tán được làm chủ và quản lý tại mỗi trạm, các trạm không bị phụ thuộc vào cơ sở dữ liệu tập trung mà chỉ cần cài đặt và thao tác với mỗi cơ 16 sở dữ liệu riêng để đáp ứng nhu cầu công việc. Tính tự trị liên quan dến tính phân tán của kiểm soát chứ không phải dữ liệu. Nó chỉ ra mức độ mà các hệ quản trị CSDL có thể thao tác một cách độc lập.  Nâng cao hiệu suất hệ thống (Improved Performance): do việc định vị dữ liệu làm giảm sự tương tranh giữa CPU và các dịch vụ vào/ra (I/O) và dẫn đến việc trễ trong các mạng diện rộng.  Tăng tính tin cậy (Reliability): là xác suất hệ thống chạy (không dừng) tại thời điểm xác định.  Tính sẵn sàng (Availability): là xác suất hệ thống có khả năng vận hành liên tục trong suốt một khoảng thời gian.  Tính dễ mở rộng (Easier System Expansion): khả năng vận hành của các cơ sở dữ liệu phân tán có thể được cải thiện một cách dễ dàng bằng cách bổ sung thêm các máy tính vào mạng. Việc mở rộng này thường là không ảnh hưởng đến hệ thống đang chạy và chi phí thấp. Trong môi trường phân tán, hệ thống có thể kết hợp các máy nhỏ để đạt được sức mạnh tương đương với sức mạnh của một siêu máy tính. Các máy tính nhỏ là rẻ hơn nhiều so với siêu máy tính, và không đòi hỏi phải có cơ sở hạ tầng đắt tiền cho việc cài đặt và bảo vệ. Yêu cầu cho việc mở rộng không chỉ là mở rộng phần cứng trên mạng mà nó trải trên các khía cạnh khi thiết kế hệ phân tán. Ví dụ: tần suất sử dụng trên mạng đột ngột, để tránh tình trạng tắc nghẽn xảy ra khi chỉ có một máy chủ CSDL và phải đáp ứng các yêu cầu truy xuất thì thực hiện nhân bản các dữ liệu trên một máy chủ khác và hệ thống được thiết kế sao cho việc thêm máy chủ CSDL được dễ dàng [9]. 1.5 Cơ sở dữ liệu phân tán đồng nhất và không đồng nhất Trong một hệ cơ sở dữ liệu phân tán đồng nhất (homogeneous distributed database system), tất cả các trạm chạy cùng phần mềm hệ quản trị cơ sở dữ liệu (DBMS) nhưng hệ điều hành (OS) có thể khác nhau ở các trạm này [10]. Trao đổi dữ liệu giữa các trạm khác nhau được xử lý dễ dàng (xem Hình 1.6). 17 Hình 1.6 Cơ sở dữ liệu phân tán đồng nhất Trong cơ sở dữ liệu phân tán không đồng nhất (heterogeneous distributed database), các trạm chạy phần mềm hệ quản trị cơ sở dữ liệu khác nhau hoặc hệ thống cơ sở dữ liệu khác nhau [10]. Trong trường hợp này, cần một phần mềm để hỗ trợ việc trao đổi dữ liệu giữa các trạm (xem Hình 1.7). Hình 1.7 Cơ sở dữ liệu phân tán không đồng nhất Sự khác nhau trong các lược đồ (Schema) thường là một vấn đề lớn cho việc xử lý truy vấn, trong khi sự khác nhau trong phần mềm trở thành chướng ngại cho việc xử lý giao dịch để truy xuất đến nhiều trạm khác nhau. Luận văn tập trung vào cơ sở dữ liệu phân tán đồng nhất. 1.6 Lưu trữ dữ liệu phân tán Xem xét một quan hệ r được lưu trữ trong cơ sở dữ liệu. Có hai cách tiếp cận lưu trữ quan hệ này trong cơ sở dữ liệu phân tán là Nhân bản và Phân mảnh. 1.6.1 Nhân bản Nhân bản (Replication) có nghĩa là hệ thống duy trì nhiều bản sao (copies) giống hệt nhau của quan hệ và lưu mỗi bản sao tại các trạm khác nhau [10]. Nếu quan hệ r được nhân bản, một bản sao của quan hệ r được lưu trữ tại 18 hai hay nhiều trạm. Trong trường hợp xấu nhất, chúng ta có bản sao đầy đủ của quan hệ, trong đó một bản sao được lưu trữ tại mội trạm trong hệ thống. Có một vài lợi ích và bất lợi của việc nhân bản:  Tính sẵn có (Availability): Nếu một trong số những trạm chứa quan hệ bị hỏng (fail), thì quan hệ r có thể được phục hồi từ trạm khác. Ví thế, hệ thống có thể tiếp tục xử lý truy vấn liên quan đến r bất chập việc có một trạm bị hỏng.  Tăng khả năng xử lý đồng thời (Increased parallelism): Trong phần lớn các trường hợp, việc truy xuất đến quan hệ r là chỉ đọc, do đó một vài trạm có thể xử lý truy vấn đồng thời tới r đáp ứng tốt hơn nhu cầu truy xuất dữ liệu. Do đó, sao chép dữ liệu giúp giảm thiểu sự di chuyển của dữ liệu giữa các trạm.  Chi phí cập nhật tăng (Increased overhead on update): Hệ thống phải đảm bảo rằng tất cả các bản sao của quan hệ r phải nhất quán, nếu không có thể dẫn đến tính toán sai. Vì vậy, bất cứ khi nào r được cập nhật, bản cập nhật phải được phổ biến đến tất cả các trạm có chứa bản sao. Điều này dẫn đến việc tăng chi phí cập nhật. Có thể lấy ví dụ như sau, trong một hệ thống ngân hàng, thông tin về tài khoản (account information) được nhân bản tại nhiều trạm khác nhau, điều này là cần thiết để đảm bảo rằng số dư tài khoản (balance) thống nhất tại tất cả các trạm. Nhưng khi thông tin tài khoản được cập nhật, thì tất cả các bản sao tại các trạm đều phải được cập nhật, tức là chi phí cập nhật tăng. Nhìn chung, nhân bản giúp tăng hiệu suất của các hoạt động đọc và tăng sự sẵn có của dữ liệu trong giao dịch chỉ đọc. Tuy nhiên, các giao dịch cập nhật phải chịu chi phí cao hơn. Việc kiểm soát cập nhật đồng thời từ một số giao dịch tới bản sao dữ liệu trong hệ thống phân tán là phức tạp hơn trong các hệ thống tập trung. Chúng ta có thể đơn giản hóa việc quản lý các bản sao của quan hệ r bằng cách chọn một trong số chúng là bản sao chính của r. Ví dụ, trong một hệ thống ngân hàng, một tài khoản có thể liên kết với trạm mà trong đó tài khoản đã được mở. Ví dụ 1.1: Dữ liệu kinh hoanh của công ty có thể được nhân bản tại các trạm tại SaiGon (dữ liệu mua bán quần áo), tại Huế (dữ liệu mua bán xe hơi), tại UK (dữ liệu đối tác) 19 Hình 1.8 Khởi tạo bảng Subscriber không đồng nhất trong cơ chế nhân bản 1.6.2 Phân mảnh Phân mảnh (Fragmentation) tức là hệ thống phân chia các quan hệ thành nhiều mảnh và lưu trữ mỗi mảnh tại các trạm khác nhau. Phân mảnh và nhân bản có thể thực hiện kết hợp: một quan hệ có thể được chia thành nhiều mảnh và thực hiện nhân bản cho mỗi mảnh [10]. Có ba quy tắc đảm bảo rằng cơ sở dữ liệu không bị thay đổi ngữ nghĩa trong quá trình phân mảnh đó là [14]:  Tính đầy đủ (Completeness): Quan hệ r được phân rã thành các mảnh Fr = {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.  Tính phục hồi (Reconstruction): Nếu một quan hệ r được phân rã thành các mảnh Fr = {r1, r2,...,rn} khi đó: r = ∇ ri, ∀ ri ∈ Fr . Toán tử ∇ thay đổi tùy theo từng loại phân mảnh, có thể là phép ∪ (phép hợp) đối với phân mảnh ngang hoặc ⊳⊲ (phép nối) đối với phân mảnh dọc. Khả năng phục hồi quan hệ từ các mảnh sẽ bảo toàn các phụ thuộc.  Tính tách biệt (Disjointness): Nếu quan hệ r được phân rã ngang thành các mảnh Fr = {r1, r2,...,rn} 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 ≠ i). 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ệ. 1.7 Các bước thiết kế cơ sở dữ liệu phân tán 20