Tài liệu Tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ LOAN TỐI ƯU HOÁ TRUY VẤN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN LUẬN VĂN THẠC SĨ KHOA H ỌC M ÁY T ÍNH Thái nguyên, 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ LOAN TỐI ƯU HOÁ TRUY VẤN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH Mà SỐ: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC M ÁY T ÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS ĐOÀN VĂN BAN Thái nguyên, 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Thái nguyên, 2011 http://www.lrc-tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan, kết quả của luận văn hoàn toàn là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu. Các tài liệu tham khảo đƣợc trích dẫn và chú thích đầy đủ. Tác giả NGUYỄN THỊ LOAN Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CẢM ƠN Lời đầu tiên tôi xin gửi lời cảm ơn chân thành nhất đến thầy PGS.TS Đoàn Văn Ban đã định hƣớng và nhiệt tình hƣớng dẫn, giúp đỡ tôi rất nhiều về mặt chuyên môn trong quá trình làm luận văn. Tôi xin gửi lời biết ơn sâu sắc đến các thầy, các cô đã dạy dỗ và truyền đạt những kinh nghiệm quý báu cho chúng tôi trong suốt hai năm cao học ở trƣờng Đại học Công nghệ thông tin và truyền thông. Cuối cùng tôi xin dành tình cảm thân thiết nhất cho bạn bè, đồng nghiệp, cha mẹ và gia đình, những ngƣời luôn gần gũi để động viên, chia sẻ cùng tôi trong suốt thời gian qua. Thái Nguyên, tháng 9 năm 2011 Nguyễn Thị Loan Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỤC LỤC Trang phụ bìa Trang Lời cam đoan i Lời cảm ơn ii Mục lục iii Danh mục các hình vẽ, đồ thị vi PHẦN MỞ ĐẦU ………………………………………………………………1 1. Đặt vấn đề…………………………………………………………….1 2. Đối tƣợng và phạm vi nghiên cứu……………………………………. 1 3. Hƣớng nghiên cứu của đề tài…………………………………………. 1 4. Phƣơng pháp nghiên cứu………………………………………………2 5. Ý nghĩa khoa học của đề tài……………………………………………2 6. Các kết quả dự kiến…………………………………………………….2 Chƣơng 1. CƠ SỞ DỮ LIỆU PHÂN TÁN…………………………………… .3 1.1. Khái niệm về hệ cơ sở dữ liệu phân tán…………………………… 3 1.1.1. Khái niệm………………………………………………………...3 1.1.2. Các đặc điểm chính của cơ sở dữ liệu phân tán…………………4 1.1.3. Mục đích của việc sử dụng cơ sở dữ liệu phân tán……………...8 1.2. Các đặc trƣng trong suốt của cơ sở dữ liệu phân tán………………...9 1.2.1.Trong suốt phân tán………………………………………………9 1.2.2. Trong suốt giao dịch…………………………………………….10 1.2.3.Trong suốt các sự cố……………………………………………..10 1.2.4. Trong suốt thao tác……………………………………………...10 1.2.5.Trong suốt về tính không thuần nhất…………………………… 10 1.3.Kiến trúc cơ bản của cơ sở dữ liệu phân tán…………………………10 1.3.1.Sơ đồ tổng thể……………………………………………………11 1.3.2. Sơ đồ phân đoạn……………………………………………… 11 1.3.3. Sơ đồ định vị…………………………………………………….12 1.3.4. Sơ đồ ánh xạ địa phương……………………………………….12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.3.5. Chia sẻ tài nguyên……………………………………………… 14 1.4. Các kỹ thuật xây dựng cơ sở dữ liệu phân tán……………………......14 1.4.1.Phân tán……………………………………………………………14 1.4.1.1. Phân đoạn ngang………………………………………… …14 1.4.1.2. Phân đoạn ngang dẫn tiếp……………………………….......15 1.4.1.3. Phân đoạn dọc……………………………………………….16 1.4.1.4. Phân đoạn hỗn hợp…………………………………………..17 1.4.2.Nhân bản dữ liệu………………………………………………..18 1.4.3. Định vị dữ liệu………………………………………………….19 1.4.4. Hệ quản trị CSDL phân tán…………………………………….19. 1.5. Kết luận……………………………………………………………….20 Chƣơng 2. TỐI ƢU HÓA TRUY VẤN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN 2.1. Các chiến lƣợc tối ƣu hóa cơ bản……………………………………..21 2.2. Các phép biến đổi đại số………………………………………………22 2.2.1. Các yêu cầu của phép biến đổi tối ưu hóa câu truy vấn………….22 2.2.2. Biểu thức tương đương……………………………………………23 2.2.3. Các qui tắc liên quan đến phép kết nối và tích Decartes………....23 2.2.4. Các qui tắc liên quan đến phép chọn và phép chiếu……………..24 2.2.5. Thuật toán cải tiến cây biểu diễn biểu thức quan hệ…………......25 2.3. Phân rã câu truy vấn thành những câu truy vấn con………………….30 2.3.1. Đồ thị nối các quan hệ……………………………………………30 2.3.2. Tách câu truy vấn thành các câu truy vấn con…………………..31 2.3.3. Dùng phép nửa kết nối để giảm kích thước quan hệ…………….32 2.3.4. Phương pháp thay thế n –bộ………………………………….....32 2.4. Các kỹ thuật tối ƣu hóa tập trung…………………………………….33 2.4.1. Thuật toán INGRES…………………………………………...…33 2.4.2. Thuật toán System R……………………………………………..37 2.5. Phân rã cây truy vấn……………………………………………….....40 2.5.1. Chuẩn hóa……………………………………………………….40 2.5.2.Phân tích………………………………………………………....42 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2.5.3. Loại bỏ dư thừa…………………………………………………44 2.5.4. Viết lại…………………………………………………………...45 2.6. Định vị dữ liệu phân tán…………………………………………......48 2.6.1. Rút gọn phân đoạn ngnang nguyên thủy………………………48 2.6.2. Rút gọn phân đoạn dọc………………………………………..51 2.6.3. Rút gọn phân đoạn gián tiếp…………………………………..52 2.6.4. Rút gọn phân đoạn hỗn hợp…………………………………...54 2.7. Khái quát về xử lý câu truy vấn…………………………………....55 2.7.1. Vấn đề xử lý truy vấn………………………………………….56 2.7.2. Các mục tiêu của xử lý câu truy vấn…………………………..56 2.7.3. Các giai đoạn xử lý câu truy vấn………………………………57 2.7.4. Tối ưu hóa các truy vấn phân tán……………………………..57 2.7.4.1. Đầu vào bộ tối ưu hóa câu truy vấn………………………58 2.7.4.2. Thứ tự kết nối trên các câu truy vấn đoạn………………..63 2.7.4.3.Thứ tự kết nối……………………………………………...63 2.7.4.4. Các thuật toán dựa trên phép nửa kết nối………………...65 2.8. Các thuật toán tối ƣu hóa truy vấn phân tán……………………….69 2.8.1. Thuật toán INGRES phân tán…………………………………70 2.8.2. Thuật toán R*………………………………………………….72 2.8.3. Thuật toán SDD -1…………………………………………….76 2.8.4. Các thuật toán AHY ( Apers – Hevner – Yao)…………………80 2.9. Kết luận…………………………………………………………….86 Chƣơng 3. CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN…………………89 3.1. Xác định thuật toán………………………………………………...89 3.2. Cài đặt thử nghiệm thuật toán……………………………………...89 3.2.1. Cấu trúc cơ sở dữ liệu………………………………………….89 3.2.2. Xây dựng ứng dụng……………………………………………90 3.2.3. Thử nghiệm 1………………………………………………….92 3.2.4. Thử nghiệm 2………………………………………………….94 3.3. Kết luận. …………………………………………………………..95 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI……………………96 TÀI LIỆU THAM KHẢO……………………………………………………97 CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1. Trong suốt phân đoạn……………………………………………6 Hình 1.2. Sự trong suốt về vị trí……………………………………………7 Hình 1.3. Sự trong suốt ánh xạ cục bộ……………………………………..8 Hình 1.4 Kiến trúc cơ sở dữ liệu phân tán…………………………………11 Hình 1.5. Các đoạn và hình ảnh vật lý của một quan hệ tổng thể…………12 Hình 1.6. Cây phân tán của quan hệ……………………………………….18 Hình 2.1. Cây biểu diễn biểu thức hỏi……………………………………..27 Hình 2.2. Cây với tổ hợp phép chọn………………………………………29 Hình 2.3. Cây kết quả với sự phân nhóm các phép toán…………………..30 Hình 2.4. Đồ thị nối quan hệ………………………………………………31 Hình 2.5. Đồ thị nối các quan hệ…………………………………………..32 Hình 2.6. Đồ thị các quan hệ có chu trình…………………………………33 Hình 2.7. Gỡ bỏ chu trình bằng cách thay thế n- bộ………………………33 Hình 2.8. Đồ thị kết nối của cây truy vấn…………………………………39 Hình 2.9. Các đồ thị quan hệ……………………………………………....43 Hình 2.10. Đồ thị cây truy vấn không liên thông………………………….44 Hình 2.11. Cây đại số quan hệ…………………………………………….46 Hình 2.12. Cây đại số quan hệ tƣơng đƣơng……………………………....47 Hình 2.13. Cây đại số quan hệ viết lại……………………………………..48 Hình 2.14. Rút gọn cho phân đoạn ngnang với phép chọn………………..49 Hình 2.15. Rút gọn phân đoạn ngang cho phép kết nối……………………50 Hình 2.16. Rút gọn đối với việc phân đoạn dọc…………………………...52 Hình 2.17. Rút gọn phân đoạn gián tiếp.…………………………………..54 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hình 2.18. Rút gọn phân đoạn hỗn hợp…………………………………...55 Hình 2.19. Sơ đồ phân lớp cho việc xử lý truy vấn phân tán……………..57 Hình 2.20. Truyền các toán hạng trong phép toán hai ngôi……………….64 Hình 2.21. Đồ thị kết nối của câu truy vấn phân tán……………………...64 Hình 2.22. Biến đổi của câu truy vấn chu trình…………………………...68 Hình 2.23. Câu truy vấn ví dụ và các thống kê…………………………...79 Hình 2.24. Ví dụ một câu truy vấn đơn và các thống kê………………….82 Hình 2.25. Schedule tối ƣu………………………………………………..83 Hình 2.26. Các giai đoạn của việc đánh giá một câu truy vấn phân tán….87 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -1- PHẦN MỞ ĐẦU 1. Đặt vấn đề. Ngày nay lĩnh vực thương mại ngày càng mở rộng và phát triển . Để kinh doanh được thuận lợi và có hiệu quả cần phải nắm bắt thông tin nhanh nhất khi các địa điểm kinh doanh ở xa nhau. Do đó xây dựng 1 hệ thống làm việc dựa trên cơ sở dữ liệu phân tán là phù hợp với xu hướng hiện nay. Cơ sở dữ liệu phân tán đã, đang được nghiên cứu và ứng dụng vào thực tế. Việc cần làm là nghiên cứu và làm sáng tỏ thêm khả năng ứng dụng thực tiễn của cơ sở dữ liệu phân tán. Lợi ích cơ bản nhất của cơ sở dữ liệu phân tán là dữ liệu của các cơ sở dữ liệu vật lý riêng biệt được tích hợp logic với nhau làm cho nhiều người sử dụng trên mạng có thể truy nhập được. Cơ sở dữ liệu phân tán với cấp độ tự trị cao ở mỗi điểm. Trong hệ phân tán các câu truy vấn có thể sử dụng kỹ thuật tối ưu hoá làm giảm thời gian tính toán, khối lượng truyền thông tin giữa các trạm và giảm không gian bộ nhớ, tránh được các công việc dư thừa, loại bỏ những phần vô ích. Khi khối lượng thông tin phải xử lý ngày càng lớn, phong phú và đa dạng thì vấn đề đặt ra là xử lý thông tin như thế nào để giảm chi phí đến mức tối thiểu. Một trong các giải pháp có tính khả thi là phải tối ưu hoá các câu lệnh khi truy vấn dữ liệu nên tôi chọn nghiên cứu “Tối ưu hoá truy vấn trong cơ sở dữ liệu phân tán” làm đề tài luận văn tốt nghiệp của mình. 2. Đối tƣợng và phạm vi nghiên cứu. - Đối tượng nghiên cứu là cơ sở dữ liệu phân tán. - Phạm vi nghiên cứu là một số các kỹ thuật tối ưu hoá truy vấn trong cơ sở dữ liệu. 3. Hƣớng nghiên cứu của đề tài. - Nghiên cứu tối ưu hoá truy vấn trong cơ sở dữ liệu phân tán, các nguyên lý chung, các kỹ thuật, các thuật toán liên quan đến vấn đề tối ưu hoá truy vấn và nghiên cứu cải tiến về tối ưu hoá truy vấn lồng trong cơ sở dữ liệu phân tán. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -2- - Cài đặt thử nghiệm thuật toán tối ưu hoá truy vấn lồng trong cơ sở dữ liệu phân tán. 4. Phƣơng pháp nghiên cứu. - Nghiên cứu lý thuyết: Tìm hi ểu nghiên cứu các tài liệu liên quan trong sách, tạp chí, các bài báo trên mạng Internet… Tổng hợp, so sánh các kết quả viết lại thành luận văn. - Nghiên cứu thực nghiệm: Cài đặt thử nghiệm. 5. Ý nghĩa khoa học của đề tài. - Giảm thiểu thời gian xử lý - Giảm vùng nhớ trung gian - Giảm chi phí truyền thông giữa các trạm. 6. Các kết quả dự kiến đạt đƣợc - Giới thiệu tổng quan về CSDL phân tán. - Trình bày các phương pháp, thuật toán tối ưu hóa truy vấn phân tán. - Cài đặt thử nghiệm một thuật toán tối ưu truy vấn phân tán. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -3- Chƣơng 1. CƠ SỞ DỮ LIỆU PHÂN TÁN 1.1. Khái niệm về hệ cơ sở dữ liệu phân tán 1.1.1. Khái niệm Cơ sở dữ liệu phân tán [3] là một tập hợp các dữ liệu phụ thuộc lôgic lẫn nhau của cùng một hệ thống và được lưu trữ trên các trạm của một mạng máy tính. Cơ sở dữ liệu phân tán làm tăng khả năng truy nhập tới cơ sở dữ liệu lớn trên mạng. Trong hệ thống đó mỗi máy tính quản lý một cơ sở dữ liệu thành phần được gọi là 1 node hoặc site. Hệ quản trị cơ sở dữ liệu phân tán (DBMS) là phần mềm quản trị cơ sở dữ liệu, đảm bảo trong suốt đối với người sử dụng và cho phép tính tự trị nghĩa là mỗi cơ sở dữ liệu thành phần vẫn được quản trị độc lập và riêng biệt. Một CSDL phân tán là một tập hợp nhiều CSDL có liên đới logic và được phân bố trên một mạng máy tính - Tính chất phân tán: Toàn bộ dữ liệu của CSDL phân tán không được cư trú ở một nơi mà cư trú trên 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 logic: Toàn bộ dữ liệu của CSDL phân tán có một số các 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 CSDL cục bộ hoặc các tệp cư trú tại các vị trí khác nhau trong một mạng máy tính. Ví dụ1.1: Một ngân hàng có ba chi nhánh đặt tại các vị trí khác nhau. Tại mỗi chi nhánh có một máy tính điều khiển một số máy kế toán cuối cùng (teller terminal) và cơ sở dữ liệu thống kê của chi nhánh đó. Mỗi máy tính với cơ sở dữ liệu thống kê địa phương của nó tại mỗi chi nhánh được đặt ở một vị trí của cơ sở dữ liệu phân tán. Các máy tính được nối với nhau bởi một mạng truyền thông. Các nút trong một mạng phân tán một mặt xử lý thông tin tại vị trí mà nó quản lý, mặt khác nó cũng tham gia vào việc xử lý các yêu cầu về thông tin cần truy cập qua nhiều địa điểm. Ví dụ như việc lên danh sách tất cả nhân viên của ngân hàng. Yêu cầu này đòi hỏi tất cả các máy tính ở các chi nhánh của công ty đều phải hoạt động để cung cấp thông tin. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -4- 1.1.2. Các đặc điểm chính của cơ sở dữ liệu phân tán 1. Chia sẻ tài nguyên Việc chia sẻ tài nguyên của hệ phân tán được thực hiện thông qua mạng truyền thông. Để chia sẻ tài nguyên một cách có hiệu quả thì mỗi tài nguyên cần được quản lý bởi một chương trình có giao diện truyền thông, các tài nguyên có thể được truy cập, cập nhật một cách tin cậy và nhất quán. Quản lý tài nguyên ở đây là lập kế hoạch dự phòng, đặt tên cho các lớp tài nguyên, cho phép tài nguyên được truy cập từ nơi này đến nơi khác, ánh xạ lên tài nguyên vào địa chỉ truyền thông, ... 2. Tính mở Tính mở của hệ thống phân tán là tính dễ dàng mở rộng phần cứng của nó. Một hệ thống được gọi là có tính mở thì phải có các điều kiện sau: - Hệ thống có thể tạo nên bởi nhiều loại phần cứng và phần mềm của nhiều nhà cung cấp khác nhau. - Có thể bổ sung vào các dịch vụ dùng chung tài nguyên mà không phá hỏng hay nhân đôi các dịch vụ đang tồn tại. - Tính mở được hoàn thiện bằng cách xác định hay phân định rõ các giao diện chính của một hệ và làm cho nó tương thích với các nhà phát triển phần mềm. - Tính mở của hệ phân tán dựa trên việc cung cấp cơ chế truyền thông giữa các tiến trình và công khai các giao diện dùng để truy nhập các tài nguyên chung. 3. Khả năng song song Hệ phân tán hoạt động trên một mạng truyền thông có nhiều máy tính, mỗi máy có thể có một hay nhiều CPU. Có thể thực hiện nhiều tiến trình trong cùng một thời điểm. Việc thực hiện tiến trình theo cơ chế phân chia thời gian (một CPU) hay (nhiều CPU). Khả năng làm việc song song trong hệ phân tán được thể hiện qua hai tình huống sau: - Nhiều người sử dụng đồng thời đưa ra các lệnh hay các tương tác với các chương trình ứng dụng. - Nhiều tiến trình Server chạy đồng thời, mỗi tiến trình phải đáp ứng yêu cầu từ các Clients. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -5- 4. Khả năng mở rộng Hệ phân tán có khả năng hoạt động tốt và hiệu quả ở nhiều mức khác nhau. Một hệ phân tán nhỏ nhất có thể hoạt động chỉ cần hai trạm làm việc và một File Server. Các hệ lớn hơn tới hàng nghìn máy tính. Khả năng mở rộng của một hệ phân tán được đặc trưng bởi tính không thay đổi phần mềm hệ thống và phần mềm ứng dụng khi hệ được mở rộng. Yêu cầu cho việc mở rộng không chỉ là mở rộng phần cứng, về 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ụ 1.2: 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 Server và phải đáp ứng các yêu cầu truy nhập các file đó. Người ta nhân bản các file trên một Server khác và hệ thống được thiết kế sao cho việc thêm Server được dễ dàng. Một số giải pháp khác là sử dụng Cache và các bảng sao dữ liệu. 5. Khả năng thứ lỗi Việc thiết kế khả năng thứ lỗi các hệ thống máy tính dựa trên hai giải pháp sau: - Dùng khả năng thay thế để đảm bảo sự hoạt động liên tục và hiệu quả. - Dùng các chương trình hồi phục dữ liệu khi xảy ra sự cố. 6. Tính trong suốt Tính trong suốt của một hệ phân tán được hiểu như là việc che khuất đi các thành phần riêng biệt của hệ đối với người sử dụng và những người lập trình ứng dụng. Các loại trong suốt trong hệ phân tán: Trong suốt phân đoạn (fragmentation transparency): Khi dữ liệu đã được phân đoạn thì việc truy cập vào CSDL được thực hiện bình thường như là chưa bị phân tán và không ảnh hưởng tới người sử dụng. Ví dụ 1.3: Xét quan hệ tổng thể NCC (Id, Tên, Tuổi) và các phân đoạn ngang được tách ra từ nó: NCC1 (Id, Tên, Tuổi) NCC2 (Id, Tên, Tuổi) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -6- NCC3 (Id, Tên, Tuổi) Giả sử DDBMS cung cấp tính trong suốt về phân đoạn, khi đó ta có thể thấy tính trong suốt này được thể hiện như sau: Khi muốn tìm một người có Id=”Id1“ thì chỉ cần tìm trên quan hệ tổng thể NCC mà không cần biết quan hệ NCC có phân tán hay không. SELECT * FROM NCC WHERE Id=”Id1” NCC1 Vị trí1 DDBMS NCC2 Vị trí2 NCC3 Vị trí3 Hình 1.1:Trong suốt phân đoạn Tính trong suốt về vị trí (location transparency): - Người sử dụng không cần biết về vị trí vật lý của dữ liệu mà có quyền truy cập đến cơ sở dữ liệu tại bất cứ vị trí nào. - Các thao tác để lấy hoặc cập nhật một dữ liệu từ xa được tự động thực hiện bởi hệ thống tại điểm đưa ra yêu cầu. - Tính trong suốt về vị trí rất hữu ích, nó cho phép người sử dụng bỏ qua các bản sao dữ liệu đã tồn tại ở mỗi vị trí. Do đó có thể di chuyển một bản sao dữ liệu từ một vị trí này đến một vị trí khác và cho phép tạo các bản sao mới mà không ảnh hưởng đến các ứng dụng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -7- Ví dụ 1.4 : Với quan hệ tổng thể R và các phân đoạn như đã nói ở trên nhưng giả sử rằng DDBMS cung cấp trong suốt về vị trí nhưng không cung cấp trong suốt về phân đoạn. Xét câu truy vấn tìm người có Id=”Id1”. SELECT * FROM NCC1 WHERE Id=”Id1” IF NOT #FOUND THEN • SELECT * FROM NCC2 WHERE Id=”Id1” Đầu tiên hệ thống sẽ thực hiện tìm kiếm ở phân đoạn NCC1 và nếu DBMS trả về biến điều khiển #FOUND thì một câu lệnh truy vấn tương tự được thực hiện trên phân đoạn NCC2 ,... • Ở đây quan hệ NCC2 được sao làm hai bản trên hai vị trí 2 và vị trí 3, ta chỉ cần tìm thông tin trên quan hệ NCC2 mà không cần quan tâm nó ở vị trí nào. DBMS NCC1 NCC2 NCC2 Vị trí 1 Vị trí 2 Vị trí 3 Hình 1.2:Sự trong suốt về vị trí Trong suốt ánh xạ cục bộ (local mapping transparency): - Là một đặc tính quan trọng trong một hệ thống DBMS không đồng nhất -Ứng dụng tham chiếu đến các đối tượng có các tên độc lập từ các hệ thống cục bộ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -8- -Ứng dụng được cài đặt trên một hệ thống không đồng nhất nhưng được sử dụng như một hệ thống đồng nhất. DBMS NCC1 Vị trí 1 NCC2 Vị trí 2 Hình 1.3:Sự trong suốt ánh xạ cục bộ Tính trong suốt của sự trùng lặp: Nếu dữ liệu trùng lặp để giảm chi phí truyền thông với cơ sở dữ liệu hoặc nâng cao độ tin cậy, người sử dụng không cần biết đến điều đó. 7. Đảm bảo tin cậy và nhất quán Hệ thống yêu cầu độ tin cậy như: - Bí mật của dữ liệu - Các chức năng khôi phục hư hỏng phải đảm bảo - Ngoài ra các yêu cầu của hệ thống về tính nhất quán cũng thể hiện ở chổ: không có mâu thuẩn trong nội dung cơ sở dữ liệu 1.1.3. Mục đích của việc sử dụng cơ sở dữ liệu phân tán Xuất phát từ yêu cầu thực tế về tổ chức và kinh tế: Trong thực tế nhiều tổ chức là không tập trung, dữ liệu ngày càng lớn và phục vụ cho đa người dùng nằm phân tán, vì vậy cơ sở dữ liệu phân tán là con đường thích hợp với cấu trúc tự nhiên của các tổ chức đó. Đây là một trong những yếu tố quan trọng thức đẩy việc phát triển cơ sở dữ liệu phân tán. Sự liên kết các cơ sở dữ liệu địa phương đang tồn tại: cơ sở dữ liệu phân tán là giải pháp tự nhiên khi có các cơ sở dữ liệu đang tồn tại và sự cần thiết xây dựng một ứng dụng toàn cục. Trong trường hợp này cơ sở dữ liệu phân tán được tạo từ dưới lên dựa trên nền tảng cơ sở dữ liệu đang tồn tại. Tiến trình này đòi hỏi cấu trúc lại các cơ sở dữ liệu cục bộ ở một mức nhất định. Dù sao, những sửa đổi này vẫn là nhỏ hơn rất nhiều so với việc tạo lập một cở sở dữ liệu tập trung hoàn toàn mới. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -9- Làm giảm tổng chi phí tìm kiếm: Việc phân tán dữ liệu cho phép các nhóm làm việc cục bộ có thể kiểm soát được toàn bộ dữ liệu của họ. Tuy vậy, tại cùng thời điểm người sử dụng có thể truy cập đến dữ liệu ở xa nếu cần thiết. Tại các vị trí cục bộ, thiết bị phần cứng có thể chọn sao cho phù hợp với công việc xử lý dữ liệu cục bộ tại điểm đó. Sự phát triển mở rộng: Các tổ chức có thể phát triển mở rộng bằng cách thêm các đơn vị mới, vừa có tính tự trị, vừa có quan hệ tương đối với các đơn vị tổ chức khác. Khi đó giải pháp cơ sở dữ liệu phân tán hỗ trợ một sự mở rộng uyển chuyển với một mức độ ảnh hưởng tối thiểu tới các đơn vị đang tồn tại Trả lời truy vấn nhanh: Hầu hết các yêu cầu truy vấn dữ liệu từ người sử dụng tại bất kỳ vị trí cục bộ nào đều thoả mãn dữ liệu ngay tại thời điểm đó. Độ tin cậy và khả năng sử dụng nâng cao: nếu có một thành phần nào đó của hệ thống bị hỏng, hệ thống vẫn có thể duy trì hoạt động. Khả năng phục hồi nhanh chóng: Việc truy nhập dữ liệu không phụ thuộc vào một máy hay một đường nối trên mạng. Nếu có bất kỳ một lỗi nào hệ thống có thể tự động chọn đường lại qua các đường nối khác. 1.2. Các đặc trƣng trong suốt của cơ sở dữ liệu phân tán 1.2.1 Trong suốt phân tán - Cho phép xử lý dữ liệu trên hệ cơ sở dữ liệu phân tán giống như đối với cơ sở dữ liệu tập trung. - Người sử dụng không cần biết: Dữ liệu đã được phân đoạn như thế nào, các bản sao dữ liệu để ở đâu, vị trí vật lý lưu trữ dữ liệu ở đâu. - Trong suốt phân tán thể hiện: + Trong suốt địa điểm: User không cần biết lưu trữ vật lý của dữ liệu ở đâu, trong truy vấn chỉ cần chỉ ra tên đoạn mà không cần chỉ ra vị trí. + Trong suốt tên: Khi một đối tượng đã được đặt tên thì có thể truy nhập chính xác không cần đặc tả thêm. + Trong suốt bản sao: Sự nhân bản là quá trình sao chép và duy trì dữ liệu trong hệ cơ sở dữ liệu phân tán. Cùng một dữ liệu (được lưu trữ vật lý tại một vị trí) có thể sử dụng được trên nhiều vị trí khác nhau. Các bản sao có thể được lưu trữ trên nhiều trạm làm tăng hiệu suất, độ tin cậy và tính sẵn sàng của hệ thống. Các ứng dụng có thể truy nhập dữ liệu tại các trạm mà không cần phải truy cập từ xa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -10- giảm truyền tải trên mạng lớn. Hệ thống cho phép tiếp tục thực hiện nếu như các trạm từ xa có sự cố. Trong suốt bản sao đảm bảo user không biết đó là các bản sao vì dữ liệu luôn được cập nhật và đồng bộ với dữ liệu gốc. + Trong suốt phân đoạn: Một quan hệ trong cơ sở dữ liệu phân tán có thể phân đoạn ngang hoặc phân đoạn dọc nghĩa là được tách thành các bộ dữ liệu hoặc các quan hệ con và lưu trữ trên nhiều trạm khác nhau. Trong suốt phân đoạn cho phép người sử dụng không cần biết có sự phân đoạn, các truy vấn dữ liệu vẫn được viết như cơ sở dữ liệu tập trung. 1.2.2 Trong suốt giao dịch Cơ sở dữ liệu phân tán cho phép một giao dịch có thể cập nhật, sửa đổi dữ liệu trên các trạm khác nhau. Để đảm bảo dữ liệu nhất quán trên toàn hệ thống, các trạm trong giao dịch chỉ ủy thác khi tất cả các trạm đã ủy thác thành công hoặc roll back khi một trạm bị thất bại. 1.2.3 Trong suốt các sự cố Đảm bảo tại một trạm của hệ thống bị hỏng thì hệ thống vẫn làm việc bình thường (do cơ chế tạo bản sao hoặc làm việc trên các trạm không bị sự cố). Nếu mạng hoặc hệ thống có sự cố trong khi ủy thác của giao dịch cơ sở dữ liệu phân tán thì giao dịch đó được giải quyết tự động và trong suốt theo nghĩa khi mạng hoặc hệ thống khôi phục thì tất các các trạm này hoặc là ủy thác hoặc là roll back lại giao tác đó. 1.2.4 Trong suốt thao tác Cho phép các câu lệnh thao các dữ liệu đơn giản để truy nhập được các cơ sở dữ liệu tại trạm cục bộ hoặc trạm từ xa. Các thao tác xử lý dữ liệu từ xa không phức tạp và vẫn đảm bảo vẫn giống như khi thao tác dữ liệu trên hệ cơ sở dữ liệu không phân tán. 1.2.5 Trong suốt về tính không thuần nhất Cho phép hỗn hợp nhiều hệ quản trị cơ sở dữ liệu khác nhau với các khả năng trao đổi dữ liệu, xử lý cập nhật dữ liệu, xử lý giao tác phân tán trên toàn hệ thống. 1.3 Kiến trúc cơ bản của CSDL phân tán Đây không là kiến trúc tường minh cho tất cả các CSDL phân tán. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -11Sơ ®å tổng thể (Global Schema) Các sơ đồ độc lập vị trí Sơ ®å ph©n m¶nh (Fragmentation Schema) Sơ ®å ®Þnh vÞ (Allocation Schema) Sơ ®å ¸nh x¹ ®Þa ph-¬ng 1 (Local mapping Schema 1) HÖ qu¶n trÞ CSDL t¹i vÞ trÝ 1 (DBMS 1) Sơ ®å ¸nh x¹ ®Þa ph-¬ng n (Local mapping Schema n) HÖ qu¶n trÞ CSDL t¹i vÞ trÝ n (DBMS n) CSDL địa phương 2 (Local Database 2) CSDL địa phƣơng 1 (Local Database 1) Hình 1.4. Kiến trúc CSDL phân tán 1.3.1. Sơ đồ tổng thể (Global Schema): - Xác định tất cả các dữ liệu sẽ được lưu trữ trong cơ sở dữ liệu phân tán cũng như các dữ liệu không được phân tán ở các trạm trong hệ thống. - Sơ đồ tổng thể được định nghĩa theo cách như trong CSDL tập trung. - Trong mô hình quan hệ, sơ đồ tổng thể bao gồm định nghĩa của tập các quan hệ tổng thể (Globle relation) . 1.3.2. Sơ đồ phân đoạn (fragment schema): - Mỗi quan hệ tổng thể có thể chia thành một vài phần không giao nhau gọi là phân đoạn (fragment). - Có nhiều cách khác nhau để thực hiện việc phân chia này - Sơ đồ phân đoạn mô tả các ánh xạ giữa các quan hệ tổng thể và các đoạn được Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn