Tài liệu Tối ưu hóa truy vấn trong các 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&TRUYỀN THÔNG LƢƠNG KIM CƢƠNG TỐI ƢU HÓA TRUY VẤN TRONG CÁC 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 - 2019 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG LƢƠNG KIM CƢƠNG TỐI ƢU HÓA TRUY VẤN TRONG CÁC CƠ SỞ DỮ LIỆU PHÂN TÁN Chuyên ngành: Khoa học máy tính Mã số: 8480101 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 - 2019 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 và nghiên cứu thông qua tham khảo các tài liệu và đƣợc thực hiện dƣới sự hƣớng dẫn của PGS.TS Đoàn Văn Ban . Các tài liệu tham khảo đƣợc trích dẫn và chú thích đầy đủ. Tác giả Lƣơng Kim Cƣơng LỜI CẢM ƠN Lời đầu tiên, tôi xin chân thành cảm ơn PGS.TS Đoàn Văn Ban, ngƣời đã trực tiếp giảng dạy tôi trong thời gian học tập và cũng là ngƣời đã trực tiếp hƣớng dẫn, giúp đỡ và tạo mọi điều kiện thuận lợi cho tôi từ lúc nhận đề tài đến khi hoàn thành luận văn. Tôi xin gửi lời cảm ơn sâu sắc đến tất cả các Thầy cô đã tham gia giảng dạy và truyền đạt kiến thức, kinh nghiệm quý báu cho chúng tôi trong hai năm học cao học tại trƣờng Đại học Công Nghệ Thông Tin và Truyền Thông – Đại học Thái Nguyên. Những kiến thức này đã giúp tôi rất nhiều trong quá trình làm luận văn của mình. Cuối cùng, tôi xin cảm ơn tất cả ngƣời thân, bạn bè và đồng nghiệp đã khích lệ, động viên, đóng góp ý kiến và giúp đỡ tôi hoàn thành luận văn này. Thái Nguyên, ngày…..tháng….năm 2019 Lƣơng Kim Cƣơng i DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT STT Ký hiệu Diễn giải 1 CSDL Cơ sở dữ liệu 2 CPU Bộ xử lý trung tâm 3 I/O Cổng vào/ ra 4 DP Quy hoạch động 5 ACO Tối ƣu đàn kiến ii DANH MỤC CÁC HÌNH VẼ Hình 1.1: Kiến trúc tham chiếu của cơ sở dữ liệu phân tán [3] ................................ 9 Hình 1.2: Cây phân tách của quan hệ ...................................................................... 13 Hình 2.1: Giải pháp A ............................................................................................. 18 Hình 2.2: Giải pháp B ............................................................................................. 18 Hình 2.3: Sơ đồ quy trình xử lý truy vấn [4]........................................................... 21 Hình 2.4: Đồ thị truy vấn và Đồ thị nối .................................................................. 25 Hình 2.5: Đồ thị truy vấn và Đồ thị nối với câu truy vấn sai ngữ nghĩa................. 25 Hình 2.6: Cây đại số quan hệ .................................................................................. 28 Hình 2.7: Cây đại số quan hệ sau khi tái cấu trúc .................................................. 30 Hình 2.8: Câu truy vấn gốc ..................................................................................... 32 Hình 2.9: Câu truy vấn đã rút gọn .......................................................................... 32 Hình 2.10: Rút gọn phân mảnh ngang .................................................................... 33 Hình 2.11: Rút gọn phân mảnh dọc ....................................................................... 35 Hình 2.12: Rút gọn cho phân mảnh ngang dẫn xuất .............................................. 36 Hình 2.13: Rút gọn phân mảnh hỗn hợp ................................................................. 37 Hình 2.14: Bộ tối ƣu truy vấn ................................................................................. 38 Hình 2.15: Các cây nối ............................................................................................ 39 Hình 2.16: Hình dáng của một số cây nối ............................................................... 40 Hình 2.17: Đồ thị minh họa tổng chi phí và thời gian trả lời ......................... 42 Hình 2.18: Đồ thị nối của truy vấn q1 ..................................................................... 58 Hình 2.19: Các thứ tự kết nối .................................................................................. 59 Hình 2.20: Quá trình quyết định đƣờng đi của đàn kiến ......................................... 64 MỤC LỤC GIỚI THIỆU.......................................................................................................... 1 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. Hệ quản trị cơ sở dữ liệu phân tán ...................................................... 3 1.1.3. Những ƣu điểm của cơ sở dữ liệu phân tán ........................................ 4 1.1.4. Những nhƣợc điểm của cơ sở dữ liệu phân tán [3] ............................. 5 1.2. Các đặc trƣng trong suốt của cơ sở dữ liệu phân tán .................................. 6 1.2.1. Trong suốt phân tán ............................................................................. 6 1.2.2. Trong suốt giao dịch ............................................................................ 7 1.2.3. Trong suốt thất bại............................................................................... 7 1.2.4. Trong suốt thao tác ............................................................................. 7 1.2.5. Trong suốt về tính không thuần nhất .................................................. 8 1.3. Kiến trúc tham chiếu của cơ sở dữ liệu phân tán ........................................ 8 1.4. Các kỹ thuật xây dựng cơ sở dữ liệu phân tán ........................................... 9 1.4.1. Phân mảnh ........................................................................................... 9 1.4.1.1. Phân mảnh ngang ....................................................................... 10 1.4.1.2. Phân mảnh ngang dẫn tiếp ......................................................... 11 1.4.1.3. Phân mảnh dọc ........................................................................... 12 1.4.1.4. Phân mảnh hỗn hợp .................................................................... 13 1.4.2 Nhân bản dữ liệu ................................................................................... 14 1.4.3 Định vị dữ liệu ....................................................................................... 14 1.5. Kết luận chƣơng ...................................................................................... 15 CHƢƠNG 2. TỐI ƢU HÓA TRUY VẤN CƠ SỞ DỮ LIỆU PHÂN TÁN ...... 16 2.1. Vấn đề tối ƣu hóa xử lý truy vấn................................................................. 16 2.2. Quá trình xử lý truy vấn .............................................................................. 20 2.2.1. Phân rã truy vấn ................................................................................ 21 2.2.2. Cục bộ hóa dữ liệu phân tán ............................................................ 30 2.2.2.1. Rút gọn cho phân mảnh ngang nguyên thủy ............................ 31 2.2.2.2. Rút gọn cho phân mảnh dọc. ..................................................... 34 2.2.2.3. Rút gọn cho phân mảnh ngang dẫn xuất ................................... 35 2.2.2.4. Rút gọn cho phân mảnh hỗn hợp ............................................... 37 2.2.3. Tối ƣu hóa toàn cục .......................................................................... 38 2.2.3.1. Không gian tìm kiếm ................................................................. 39 2.2.3.2. Mô hình chi phí ......................................................................... 41 2.2.4. Tối ƣu hóa cục bộ ............................................................................. 47 2.3. Tối ƣu hóa truy vấn dựa vào phƣơng pháp tối ƣu đàn kiến ........................ 47 2.4. Một số thuật toán tối ƣu hóa truy vấn phân tán .......................................... 48 2.4.1. Thuật toán D-INGRES .................................................................... 49 2.4.2. Thuật toán R* ................................................................................... 54 2.4.3. Thuật toán SDD-1 ............................................................................ 59 2.4.4. Thuật toán Hybrids đàn kiến tối ƣu truy vấn phân tán ..................... 63 2.5. Kết luận chƣơng .......................................................................................... 68 CHƢƠNG 3. ........................................................................................................ 70 CÀI ĐẶT THUẬT TOÁN TỐI ƢU HÓA TRUY VẤN PHÂN TÁN ............... 70 3.1. Xác định bài toán......................................................................................... 70 3.2. Mô hình phân tán CSDL, công cụ, ngôn ngữ lập trình ............................... 73 3.3. Thuật toán áp dụng ...................................................................................... 76 3.4. Kết quả thử nghiệm ..................................................................................... 76 3.5. Kết luận thực nghiệm .................................................................................. 81 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .......................................................... 82 TÀI LIỆU THAM KHẢO ................................................................................... 83 1 GIỚI THIỆU 1. Lý do chọn đề tài Cơ sở dữ liệu phân tán đã đáp ứng một phần lớn các nhu cầu trong thực tế về dữ liệu phục vụ công tác quản lý ngày càng lớn và đa dạng. Đặc biệt, các hệ quản trị cơ sở dữ liệu phân tán đã giải quyết đƣợc vấn đề lƣu trữ dữ liệu và phục vụ cho nhiều ngƣời dùng ở phân tán khắp mọi nơi. Khi khối lƣợng thông tin phải xử lý ngày càng lớn, đa dạng và phong phú, dữ liệu đƣợc phân bố nhiều nơi 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 hóa các câu lệnh khi truy vấn dữ liệu. Nghiên cứu về tối ƣu hóa truy vấn trong cơ sở dữ liệu phân tán là cần thiết để khai thác có hiệu quả dữ liệu phân tán. Do đó, tôi chọn nghiên cứu đề tài “Tối ƣu hóa truy vấn trong các cơ sở dữ liệu phân tán” làm luận văn tốt nghiệp của mình. 2. Mục đích nghiên cứu Đề tài phân tích, trình bày một cách có hệ thống các nghiên cứu về cơ sở dữ liệu quan hệ, nghiên cứu các phƣơng pháp thiết kế cơ sở dữ liệu phân tán, các kỹ thuật tối ƣu hóa câu truy vấn trong cơ sở dữ liệu phân tán, cài đặt thử nghiệm một số thuật toán tối ƣu hóa câu truy vấn trong cơ sở dữ liệu phân tán, từ đó đƣa ra lựa chọn phù hợp với từng bài toán trên thực tế. 3. Đối tƣợng và phạm vi nghiên cứu Đối tƣợng và phạm vi nghiên cứu của luận văn là cơ sở dữ liệu phân tán, các câu truy vấn phân tán, một số thuật toán tối ƣu hóa truy vấn phân tán và cài đặt một thuật toán tối ƣu hóa truy vấn. 4. Phƣơng pháp nghiên cứu Nghiên cứu lý thuyết: Tìm hiểu các nghiên cứu từ các tài liệu, tạp chí và các bài viết trên mạng internet… sau đó tổng hợp so sánh để viết thành luận văn. Nghiên cứu thực nghiệm: Cài đặt thử nghiệm thuật toán R* 2 5. Bố cục luận văn Với những yêu cầu trên, nội dung của bản luận văn này trình bày khái quát chung về cơ sở dữ liệu phân tán, các kỹ thuật xây dựng cơ sở dữ liệu phân tán, tối ƣu hóa truy vấn trong quá trình xử lý truy vấn, trình bày một số thuật toán tối ƣu hóa truy vấn phân tán, cài đặt thuật toán R* để tối ƣu hóa truy vấn. Luận văn đƣợc chia làm 3 chƣơng: Chƣơng 1: Khái quát về cơ sở dữ liệu phân tán. Trong chƣơng này trình bày khái quát về cơ sở dữ liệu phân tán: Khái niệm về cơ sở dữ liệu phân tán, ƣu nhƣợc điểm của cơ sở dữ liệu phân tán, các mức trong suốt phân tán, kiến trúc tham chiếu của cơ sở dữ liệu phân tán, các kỹ thuật xây dựng cơ sở dữ liệu phân tán. Chƣơng 2: Trình bày tối ƣu hóa truy vấn trong cơ sở dữ liệu phân tán: Quá trình xử lý truy vấn, tối ƣu hóa truy vấn dựa vào phƣơng pháp tối ƣu đàn kiến, trình bày một số thuật toán tối ƣu hóa truy vấn Chƣơng 3: Cài đặt thuật toán tối ƣu hóa truy vấn phân tán: Xác định bài toán, mô hình phân tán cơ sở dữ liệu, sử dụng thuật toán R* để áp dụng, trình bày kết quả thử nghiệm và kết luận thực nghiệm. 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 là một tập hợp các dữ liệu phụ thuộc logic 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 và nhấn mạnh hai khía cạnh quan trọng của cơ sở dữ liệu phân tán [4]. - Tính chất phân tán: Thực tế dữ liệu không nằm ở cùng một trạm mà nằm trên nhiều trạm thuộc một mạng máy tính. - Quan hệ logic: Trong CSDL phân tán dữ liệu có một số đặc tính liên kết, ràng buộc với nhau nhƣ tính kết nối, mối quan hệ, đ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 nằm tại các vị trí khác nhau trong một mạng máy tính. 1.1.2. Hệ quản trị cơ sở dữ liệu phân tán Các hệ quản trị cơ sở dữ liệu phân tán có chức năng hỗ trợ việc tạo và bảo trì cơ sở dữ liệu phân tán, chúng có các thành phần tƣơng tự nhƣ một hệ quản trị cơ sở dữ liệu tập trung thành các thành phần hỗ trợ trong việc chuyển tải dữ liệu đến các trạm và ngƣợc lại. Các thành phần sau đây đòi hỏi một hệ quản trị cơ sở dữ liệu phân tán thƣơng mại phải có: - Quản trị dữ liệu (Database management): DB - Truyền thông dữ liệu (Data Communication): DC - Từ điển dữ liệu (Data Dictionary): DD dùng để mô tả thông tin về sự phân tán của dữ liệu mạng - Cơ sở dữ liệu phân tán (Distributed Database): DDB Hệ quản trị cơ sở dữ liệu phân tán đƣợc phân làm 2 loại: 4 - Cơ sở dữ liệu phân tán thuần nhất: Là hệ cơ sở dữ liệu mà tất cả các nút sử dụng cùng một loại hệ quản trị cơ sở dữ liệu, công nghệ cơ sở dữ liệu là nhƣ nhau, dữ liệu tại các vị trí khác nhau có các định nghĩa và khuôn dạng chung (các hệ quản trị cơ sở dữ liệu ở các nút có sự tƣơng thích cao) - Cơ sở dữ liệu phân tán không thuần nhất: Là hệ cơ sở dữ liệu mà có ít nhất một nút không cùng một loại hệ quản trị cơ sở dữ liệu với hệ cơ sở dữ liệu ở các nút còn lại, có nghĩa là dữ liệu trên các vị trí thƣờng không tƣơng thích. Các mâu thuẫn điển hình bao gồm sự khác biệt về cú pháp và các khác biệt về ngữ nghĩa. 1.1.3. Những ƣu điểm 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 [11]. a) Cho phép quản lý dữ liệu với nhiều mức trong suốt Hệ quản trị cơ sở dữ liệu phải đƣợc trong suốt phân tán theo nghĩa làm cho ngƣời sử dụng không cần biết vị trí của dữ liệu và không cần biết sự phức tạp truy cập qua mạng. b) Tăng độ tin cậy và khả năng sẵn sàng Độ tin cậy là khả năng hệ thống đang làm việc (không bị ngừng) tại một thời điểm nào đó, tính sẵn sàng là khả năng hệ thống tiếp tục làm việc trong một khoảng thời gian nào đó. Khi dữ liệu và cơ sở dữ liệu phân tán trên một vài trạm, một trạm có thể có sự cố trong khi các trạm khác vẫn có thể hoạt động hoặc sử dụng các thành phần khác của cơ sở dữ liệu. Chỉ trên trạm bị sự cố, dữ liệu và ứng dụng không thể truy cập đƣợc. Để nâng cao độ tin cậy và tính sẵn sàng, có thể áp dụng cơ chế tạo bản sao trên nhiều trạm [1]. c) Cải thiện hiệu năng Một hệ quản trị cơ sở dữ liệu phân tán, phân đoạn cơ sở dữ liệu có thể làm 5 cho dữ liệu sẽ đƣợc lƣu giữ tại gần nơi sử dụng nhất. Dữ liệu đƣợc lƣu giữ cục bộ làm giảm cạnh tranh CPU (bộ xử lý trung tâm), giảm các phục vụ I/O (các thiết bị nhâp, xuất) và giảm tƣơng tranh truy nhập trên mạng. Dữ liệu đƣợc phân tán tại các trạm nên dung lƣợng dữ liệu cục bộ sẽ nhỏ hơn, các xử lý giao tác và truy vấn cục bộ sẽ đƣợc thực hiện tốt hơn. Hơn nữa trên mỗi trạm có ít các giao tác hơn số các giao tác trên cơ sở dữ liệu tập trung vì vậy cũng tăng hiệu suất hệ thống. d) Dễ dàng mở rộng Việc thêm cơ sở dữ liệu mới, tăng kích cỡ cơ sở dữ liệu hoặc thêm bộ xử lý trong môi trƣờng phân tán là dễ hơn vì cũng chỉ nhƣ là thêm các cơ sở dữ liệu thành phần. 1.1.4. Những nhƣợc điểm của cơ sở dữ liệu phân tán [3] Tuy có những ƣu điểm vƣợt trội so với CSDL tập trung, CSDL phân tán có những điểm yếu nhất định có thể tóm gọn lại trong 4 vấn đề sau:  Độ phức tạp thiết kế và cài đặt hệ thống tăng: Hệ quản trị cơ sở dữ liệu phân tán phải bổ sung thêm các chức năng nhƣ:  Theo dõi dấu vết dữ liệu  Xử lý các truy vấn phân tán  Quản lý giao dịch phân tán  Phục hồi cơ sở dữ liệu phân tán  Quản lý các bản sao  Quản lý thƣ mục - catalog phân tán  Khó điều khiển tính nhất quán về dữ liệu  Các phần mềm hệ thống đảm bảo quản trị, duy trì kết nối, trao đổi dữ liệu trên mạng.  Bảo mật khó khăn: Trong cơ sở dữ liệu phân tán các máy đƣợc kết nối qua mạng máy tính, việc đảm bảo an ninh trong môi trƣờng mạng ra phức tạp hơn. 6 Ở mức vật lý, những nhân tố chính sau là để phân biệt một hệ cơ sở dữ liệu phân tán với hệ cơ sở dữ liệu tập trung:  Có nhiều máy tính đƣợc gọi là các trạm hay các nút.  Các trạm này phải đƣợc kết nối bởi một kiểu mạng truyền thông để truyền dữ liệu. Trong mô hình dữ liệu tập trung, tài nguyên tập trung tại một máy tính. Trong hệ thống cơ sở dữ liệu phân tán, cơ sở dữ liệu đƣợc chứa trong nhiều máy tính, các máy tính này đƣợc nối với nhau qua các hệ thống truyền thông, chúng không chia sẻ bộ nhớ chung cũng nhƣ không dùng chung đồng hồ. Các bộ xử lý trong hệ thống phân tán có kích cỡ và chức năng khác nhau (chẳng hạn có thể bao gồm các bộ vi xử lý, trạm làm việc, máy tính mini, hay các máy lớn vạn năng). Trong hệ thống cơ sở dữ liệu phân tán gồm nhiều trạm thì mỗi trạm có thể truy nhập dữ liệu ở các trạm 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: Ngƣời dùng không cần biết cũng nhƣ không cần quan tâm tới vị trí của các tài nguyên trên hệ thống vì vị trí của chúng không ảnh hƣởng đến cách thức truy xuất.  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. 7 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 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 ngƣời dùng 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 rollback (lùi cơ sở dữ liệu về một trạng thái cũ) khi một trạm bị thất bại. 1.2.3. Trong suốt thất bại Đả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à rollback 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 8 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 tham chiếu của cơ sở dữ liệu phân tán Kiến trúc tham chiếu không đƣợc cài đặt rõ ràng trên tất cả cơ sở dữ liệu phân tán, tuy nhiên các mức của nó đƣợc khái quát chính xác, thích hợp để mô tả tổ chức chung cho mọi hệ cơ sở dữ liệu phân tán.  Lƣợc đồ tổng thể: Mô tả tổng thể và thống nhất chung nhất của tất cả dữ liệu của cơ sở dữ liệu phân tán độc lập với môi trƣờng phân tán.  Phân đoạn: Mối quan hệ tổng thể có thể đƣợc chia thành vài phần không giao nhau đƣợc gọi là các đoạn. Lƣợc đồ phân đoạn định nghĩa ánh xạ giữa các quan hệ tổng thể và các phân đoạn. Ánh xạ này là một nhiều, một số đoạn tƣơng ứng với một quan hệ tổng thể, nhƣng chỉ một quan hệ tổng thể tƣơng ứng với một đoạn. Ký hiệu Ri là đoạn thứ i của quan hệ tổng thể R.  Lƣợc đồ định vị: Định nghĩa ánh xạ từ các phân đoạn vào những trạm chứa những phân đoạn đó. Tất cả các đoạn tƣơng ứng với cùng quan hệ tổng thể R và đƣợc đặt tại cùng trạm j tạo thành hình ảnh vật lý của quan hệ tổng thể R tại trạm j.  Lƣợc đồ ánh xạ địa phƣơng: Ánh xạ các hình ảnh vật lý tới các đối tƣợng đƣợc thao tác bởi các hệ quản trị cơ sở dữ liệu địa phƣơng. Trong hệ không thuần nhất ta có các kiểu ánh xạ địa phƣơng khác nhau tại các trạm khác nhau. 9 Lƣợc đồ tổng thể Lƣợc đồ phân đoạn Lƣợc đồ độc lập trạm Lƣợc đồ định Lƣợc đồ ánh xạ địa phƣơng 1 Lƣợc đồ ánh xạ địa phƣơng 2 Hệ quản trị cơ sở dữ liệu của trạm 1 Hệ quản trị cơ sở dữ liệu của trạm 2 Cơ sở dữ liệu địa phƣơng của trạm 1 Cơ sở dữ liệu địa phƣơng của trạm 2 Các trạm khác Hình 1.1: Kiến trúc tham chiếu của cơ sở dữ liệu phân tán [3] 1.4. Các kỹ thuật xây dựng cơ sở dữ liệu phân tán - Kỹ thuật phân tách dữ liệu từ một cơ sở dữ liệu để lƣu trữ trên các trạm khác nhau đƣợc gọi là phân mảnh. - Sử dụng bản sao cho phép cùng một dữ liệu có thể đƣợc lƣu trữ trên nhiều hơn một trạm. - Quá trình định vị các phân mảnh dữ liệu hoặc định vị các bản sao phân mảnh lƣu trữ dữ liệu trên các trạm khác nhau. 1.4.1. Phân mảnh Sự phân mảnh là chia dữ liệu trong các bảng dữ liệu thành các bộ hoặc các bảng dữ liệu con. Có ba kiểu phân mảnh một quan hệ tổng thể: Phân mảnh ngang, phân mảnh dọc và phân mảnh hỗn hợp. 10 Một sự phân mảnh là đúng đắn nếu thoả mãn ba điều kiện sau: - Điều kiện không mất thông tin: Tất cả dữ liệu của quan hệ tổng thể phải đựơc ánh xạ tới các mảnh, có nghĩa mỗi phần tử dữ liệu thuộc quan hệ tổng thể phải thuộc một hay nhiều mảnh của nó. - Điều kiện xây dựng lại: Luôn có thể xây dựng lại đƣợc quan hệ tổng thể từ các mảnh đã có. - Điều kiện rời nhau (chỉ áp dụng cho phân mảnh ngang): Để tối thiểu hoá sự lặp lại của dữ liệu. 1.4.1.1. Phân mảnh ngang Phân mảnh ngang là sự phân chia một quan hệ thành các tập con các bộ, mỗi tập con đƣợc xác định bởi phép chọn với tân từ p trên quan hệ tổng thể R: Ri = pi, với pi là tân từ của Ri. Để có thể khôi phục đƣợc R ta dùng phép hợp các quan hệ R = R1  R2 ... Rn. Ví dụ 1.1: Xét quan hệ tổng thể DAILY (SHDL, DCDL,THPHO) Trong đó có các thuộc tính: SHDL: Số hiệu đại lý DCDL: Địa chỉ đại lý THPHO: Thành phố Ta tách quan hệ DAILY thành hai quan hệ DAILY1 và DAILY2 thuộc hai chi nhánh „HN‟ và „HCM‟. Ta có phân đoạn ngang: DAILY1 = THPHO=”HN” DAILY DAILY2 = THPHO=”HCM” DAILY Thoả mãn: - Điều kiện xây dựng lại: DAILY = DAILY1  DAILY2 - Điều kiện rời nhau thoả mãn vì: DAILY1  DAILY2 =  Tổng quát: - Điều kiện không mất thông tin nếu tập các tân từ của tất cả các đoạn phải 11 đầy đủ. - Điều kiện xây dựng lại luôn luôn thoả mãn với phép hợp. - Điều kiện rời nhau đòi hỏi các tân từ phải loại trừ nhau. 1.4.1.2. Phân mảnh ngang dẫn tiếp Phân mảnh ngang dẫn tiếp là sự phân chia một quan hệ ban đầu thành các quan hệ thứ hai khác mà các quan hệ đó liên hệ với quan hệ ban đầu bằng một khoá ngoài. Điều này nhƣ là liên hệ dữ liệu giữa quan hệ ban đầu và quan hệ thứ hai đƣợc phân đoạn trong cùng một cách. Ví dụ 1.2: Xét quan hệ tổng thể CUNGCAP(SHDL, SHSP, SHCHINHANH, SOLUONG) Trong đó có các thuộc tính: SHDL: Số hiệu đại lý SHSP: Số hiệu sản phẩm SHCHINHANH: Số hiệu chi nhánh SOLUONG: Số lƣợng Phân đoạn ngang dẫn tiếp của quan hệ CUNGCAP đƣợc thực hiện nhƣ sau: CUNGCAP1 = CUNGCAP ⋉SHDL= SHDL DAILY1 CUNGCAP2 = CUNGCAP ⋉ SHDL = SHDL DAILY2 Việc bố trí trên cùng một trạm của mỗi cặp đoạn (DAILY1, CUNGCAP1) và (DAILY2, CUNGCAP2) cho phép cải tiến hiệu năng của phép kết nối các quan hệ NHACUNGCAP và CUNGCAP vì có thể thực hiện song song bởi hai phép kết nối (DAILY1⋈ CUNGCAP1) và (DAILY2⋈ CUNGCAP2). - Điều kiện không mất thông tin của phân đoạn trên đòi hỏi không có SHDL nào trong quan hệ CUNGCAP mà lại không chứa trong quan hệ DAILY. Ở đây có ràng buộc toàn vẹn tham chiếu. s  CUNGCAP => phải  pDAILY mà p.SHDL= s. SHDL p.SHDL  DAILY1 qua ⋉ => s  CUNGCAP1 hoặc p.SHNCC  DAILY2 qua ⋉ => s  CUNGCAP2 12 => Thoả mãn điều kiện không mất thông tin - Điều kiện xây dựng lại: CUNGCAP = CUNGCAP1  CUNGCAP2 - Điều kiện rời nhau: Ta chứng minh: CUNGCAP1  CUNGCAP2 =  Giả sử: p  CUNGCAP1 & CUNGCAP2 => p1  NCC1 p.SHDL = p1.SHDL => p2  NCC2 p.SHDL = p2.SHDL Mâu thuẫn vì SHDL là khoá của DAILY 1.4.1.3. Phân mảnh dọc Phân mảnh dọc là sự chia một quan hệ thành tập con các bộ, mỗi tập đƣợc xác định bởi một phép chiếu đƣợc áp dụng cho quan hệ: R i = ПATTRi R, trong đó ATTRi là tập con các thuộc tính của R. Tiêu chuẩn cho sự phân mảnh dọc là đúng đắn: - Điều kiện đầy đủ: Nếu một thuộc tính xuất hiện trong một quan hệ tổng thể thì nó cũng phải xuất hiện trong một mảnh dọc nào đó. - Điều kiện xây dựng lại: Cần phải thêm vào mỗi mảnh khoá chính, do đó việc xây dựng lại đƣợc nhờ vào phép kết nối các mảnh dọc theo các thuộc tính chung. - Điều kiện rời nhau: Ít nhất khoá phải đƣợc lặp lại trên tất cả các mảnh để cho phép xây dựng lại, nên ở đây không thể xem là rời nhau hoàn toàn đƣợc. Ví dụ 1.3: Xét quan hệ tổng thể NHANVIEN(SHNV, TEN, LUONG, THUE, SHQL, SHPHONG) Trong đó có các thuộc tính: SHNV: Số hiệu nhân viên TEN: Tên nhân viên LUONG: Mức lƣơng THUE: Thuế SHQL: Số hiệu quản lý