Đề tài Nghiên cứu một số vấn đề về truy vấn và tối ưu hóa truy vấn cơ sở dữ liệu phân tán trong hệ thống thông tin

......................................................... 5 CHƯƠNG 1. TỔNG QUAN NGHIÊN CỨU ĐỀ TÀI ................................................... 6 1. Tính cấp thiết nghiên cứu của đề tài...................................................................... 6 2. Tổng quan về đề tài nghiên cứu ............................................................................ 6 3. Mục tiêu nghiên cứu .............................................................................................. 8 4. Đối tượng và phạm vi nghiên cứu ......................................................................... 9 5. Phương pháp nghiên cứu ....................................................................................... 9 6. Kết cấu báo cáo nghiên cứu .................................................................................. 9 CHƯƠNG 2: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN ................................ 11 1. Khái niệm về hệ cơ sở dữ liệu phân tán .............................................................. 11 1.1. Cơ sở dữ liệu phân tán ................................................................................. 11 1.2. Hệ quản trị cơ sở dữ liệu phân tán ............................................................... 12 2. Các đặc trưng của cơ sở dữ liệu phân tán ............................................................ 13 2.1. Điều khiển tập trung ..................................................................................... 13 2.2. Độc lập dữ liệu ............................................................................................. 14 2.3. Giảm dư thừa dữ liệu .................................................................................... 14 2.4. Độ tin cậy qua các giao dịch phân tán ......................................................... 14 2.5. Cải tiến hiệu năng ......................................................................................... 14 2.6. Dễ dàng mở rộng hệ thống ........................................................................... 15 3. Kiến trúc cơ bản của cơ sở dữ liệu phân tán ....................................................... 15 3.1. Sơ đồ tổng thể ............................................................................................... 15 3.2. Sơ đồ phân đoạn ........................................................................................... 16 3.3. Sơ đồ định vị ................................................................................................. 16 3.4. Sơ đồ ánh xạ địa phương .............................................................................. 18 4. Các mô hình xử lý phân tán................................................................................. 18 4.1. Mô hình xử lý Master - Slave........................................................................ 18 4.2. Các hệ phân tán ngang hàng ........................................................................ 19 4.3. Môi trường đa tầng ....................................................................................... 20 CHƯƠNG 3: CÁC NGUYÊN LÝ CHUNG CỦA TỐI ƯU HÓA TRUY VẤN CƠ SỞ DỮ LIỆU PHÂN TÁN .................................................................................................. 22 1. Mục tiêu chung của bài toán toán truy vấn trong CSDLPT ................................ 22 2. Giới thiệu về xử lý truy vấn ................................................................................ 22 3. Các giai đoạn trong xử lý truy vấn CSDLPT ...................................................... 24 4. Các đặc trưng về xử lý truy vấn trong CSDLPT: ................................................ 27 4.1. Ngôn ngữ (language) .................................................................................... 27 4.2. Các dạng tối ưu hóa (types of optimization) ................................................ 27 4.3. Thời gian tối ưu hóa (optimization timing) .................................................. 27 2 4.4. Thống kê (statistics) ...................................................................................... 28 4.5. Tối ưu hóa tập trung & tối ưu hóa phân tán (Decision sites) ...................... 28 4.6. Sử dụng kiến trúc mạng (Exploitation of the network topology) ................. 28 4.7. Sử dụng bản sao phân đoạn (Exploitation of Replicated Fragments) ......... 29 4.8. Sử dụng toán tử bán kết nối (Use of Semijoins) ........................................... 29 5. Các kỹ thuật tối ưu hóa tập trung ........................................................................ 30 5.1. Thuật toán INGRES ...................................................................................... 30 5.2. Thuật toán SYSTEM R .................................................................................. 30 CHƯƠNG 4: TỐI ƯU HÓA TRUY VẤN PHÂN TÁN ............................................... 22 1. Phân rã câu truy vấn ............................................................................................ 32 1.1. Chuẩn hóa ..................................................................................................... 32 1.2. Phân tích ....................................................................................................... 33 1.3. Loại bỏ dư thừa ............................................................................................ 35 1.4. Viết lại ........................................................................................................... 36 2. Định vị dữ liệu phân tán ...................................................................................... 37 2.1 Rút gọn phân mảnh ngang nguyên thủy ........................................................... 38 2.2 Rút gọn phân mảnh dọc ................................................................................... 40 2.3 Rút gọn phân mảnh dẫn xuất ........................................................................... 42 2.4 Rút gọn phân mảnh hỗn hợp ............................................................................ 43 3. Tối ưu hóa các truy vấn phân tán ........................................................................ 44 3.1 Đầu vào bộ tối ưu hóa câu truy vấn ................................................................ 45 3.2 Thứ tự kết nối trên các truy vấn đoạn .............................................................. 47 4. Tối ưu hóa các truy vấn phân tán ........................................................................ 48 4.1 Thuật toán tối ưu hóa truy vấn phân tán SDD-1 ............................................. 48 4.2 Thuật toán System R* ....................................................................................... 50 4.3 Thuật toán INGRES phân tán .......................................................................... 52 5. Kết luận và hướng phát triển của đề tài ............................................................... 54 5.1 Kết luận ............................................................................................................ 54 5.2 Hướng phát triển của đề tài ............................................................................. 54 TÀI LIỆU THAM KHẢO ............................................................................................. 56 3 DANH MỤC HÌNH VẼ Hình 1: Sơ đồ tổng thể ................................................................................................... 16 Hình 2: Sơ đồ định vị .................................................................................................... 18 Hình 3: Kiến trúc khách/chủ .......................................................................................... 19 Hình 4: Các hệ phân tán ngang hàng ............................................................................. 20 Hình 5: Môi trường đa tầng ........................................................................................... 20 Hình 6: Mô tả bộ xử lý truy vấn .................................................................................... 23 Hình 7: Mô tả các giai đoạn trong xử lý truy vấn ......................................................... 24 Hình 8: Mô hình tối ưu hóa truy vấn ............................................................................. 25 Hình 9: Đồ thị kết nối tương ứng .................................................................................. 34 Hình 10: Đồ thị truy vấn không liên thông ................................................................... 35 Hình 11: Ví dụ về cây đại số quan hệ ............................................................................ 37 Hình 12: Rút gọn phân mảnh ngang với phép chọn ...................................................... 39 Hình 13: Cây đại số quan hệ truy vấn gốc..................................................................... 40 Hình 14: Rút gọn phân mảnh ngang với phép kết nối ................................................... 40 Hình 15: Rút gọn phân mảnh dọc .................................................................................. 41 Hình 16: Rút gọn phân mảnh dẫn xuất .......................................................................... 43 Hình 17: Rút gọn phân mảnh hỗn hợp .......................................................................... 44 Hình 18: Truyền các toán hạng trong phép toán hai ngôi ............................................. 47 4 DANH MỤC TỪ VIẾT TẮT 1. DANH MỤC TỪ VIẾT TẮT TIẾNG VIỆT STT Từ viết tắt Cụm từ đầy đủ 1 CSDL Cơ sở dữ liệu 2 CSDLPT Cơ sở dữ liệu phân tán 3 CSDLTT Cơ sở dữ liệu tập trung 4 HQT CSDLPT Hệ quản trị cơ sở dữ liệu phân tán 5 HQTCSDL Hệ quản trị cơ sở dữ liệu 6 HTTT Hệ thống thông tin 7 XLTV Xử lý truy vấn 2. DANH MỤC TỪ VIẾT TẮT TIẾNG ANH STT Từ viết tắt Cụm từ đầy đủ Nghĩa Tiếng Việt 1 DBM Database management Quản trị cơ sở dữ liệu 2 DC Data communication Truyền thông dữ liệu 3 DD Data dictionary Từ điển dữ liệu 4 DDB Distributed database Cơ sở dữ liệu phân tán 5 ES External Schema Lược đồ ngoài 6 GCS Global Conceptual Schema Lược đồ khái niệm toàn cục 7 LCS Local Conceptual Schema Lược đồ khái niệm cục bộ 5 CHƯƠNG 1. TỔNG QUAN NGHIÊN CỨU ĐỀ TÀI 1. Tính cấp thiết nghiên cứu của đề tài Xã hội ngày càng phát triển kèm theo yêu cầu khối lượng thông tin cần xử lý, lưu trữ trong các hệ thống thông tin (HTTT) tăng lên nhanh chóng. Dữ liệu lớn, cực lớn lên tới hàng triệu bản ghi lại phải cập nhật chỉnh lý thường xuyên nên với mô hình cơ sở dữ liệu tập trung (CSDLTT) sẽ gặp rất nhiều khó khăn về vấn đề tốc độ xử lý tại máy chủ, băng thông đường truyền, ảnh hưởng đến tính sẵn sàng của hệ thống. Bên cạnh đó, trên thực tế, các doanh nghiệp, các đơn vị và các tổ chức phải phân bố trên một vùng rộng lớn về mặt địa lý, có thể dàn trải trên phạm vi nhiều thành phố, toàn bộ quốc gia hay một vài quốc gia, thậm chí trên toàn cầu, nên việc lưu trữ, xử lý dữ liệu tập trung không khả thi. Dữ liệu không thể lưu trữ tập trung ở một địa điểm nhất định mà rải khắp các địa điểm mà cơ quan, tổ chức hay doanh nghiệp đó hoạt động. Khi dữ liệu không còn lưu trữ tập trung thì vấn đề làm thế nào để quản lý truy xuất, tốc độ truy xuất dữ liệu phục vụ cho công tác chuyên môn không bị ảnh hưởng, không bị gián đoạn là một vấn đề quan trọng được đặt ra. Đây chính là tiền đề để cơ sở dữ liệu phân tán (CSDLPT) ra đời. Trong các hệ thống sử dụng CSDLPT dữ liệu thực sự được lưu trữ trên nhiều trạm riêng biệt, tuy nhiên, việc quản lý khai thác lại được xây dựng sao cho người sử dụng có thể truy vấn dữ liệu như một CSDLTT. 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à cần 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. Tối ưu hóa câu lệnh truy vấn trên CSDLPT đòi hỏi nhiều kỹ thuật phức tạp hơn khi tối ưu hóa truy vấn trên CSDL thông thường, do cơ sở dữ liệu được lưu trữ rời rạc. Từ tình hình thực tế và nhu cầu đó, việc nghiên cứu về truy vấn và tối ưu hóa truy vấn trong CSDLPT là một điều vô cùng cần thiết, có tính ứng dụng cao trong các doanh nghiệp. Vì vậy tôi chọn đề tài “Nghiên cứu một số vấn đề về truy vấn và tối ưu hóa truy vấn cơ sở dữ liệu phân tán trong hệ thống thông tin” để nghiên cứu. Đề tài hướng đến việc hệ thống hóa các vấn đề trong xây dựng câu truy vấn và tối ưu hóa các câu truy vấn trong môi trường đặc trưng của CSDLPT. 2. Tổng quan về đề tài nghiên cứu Hiện nay, quản lý, xử lý và khai thác thông tin, dữ liệu là một lĩnh vực thu hút sự quan tâm, đầu tư nghiên cứu và triển khai mạnh mẽ ở các nước tiên tiến về CNTT, nhất là khi ngành công nghiệp nội dung số đang nổi lên như một lĩnh vực kinh doanh có lợi nhuận cao. Các công nghệ liên quan đến công nghệ dữ liệu (data engineering), tìm kiếm thông tin (information retrieval), xử lý dữ liệu (data procesing), CSDL lưới (Grid Database) được nghiên cứu rộng rãi tại các chuyên ngành liên quan đến CNTT tại các trường đại học lớn trên thế giới. Các chương trình này đã và đang được hỗ trợ bởi một ngành công nghiệp khổng lồ để đưa các thành tựu mới về công nghệ trong các lĩnh vực này vào ứng dụng một cách nhanh chóng. Các chính phủ của các 6 nước tiên tiến coi việc phát triển, nắm bắt và ứng dụng các thành tựu mới trong các ngành công nghệ này là công tác sống còn trong việc phát triển các hạ tầng thông tin và phục vụ lợi ích quốc gia và phát triển kinh tế. Do đó, một số hiệp hội của các nhà nghiên cứu và phát triển các công nghệ, ứng dụng quản lý thông tin và dữ liệu đã ra đời và có ảnh hưởng lớn trên thế giới. Nổi tiếng nhất là SIGMOD thuộc ACM và Data Engineering của IEEE, cả hai đều thuộc Mỹ nhưng được công nhận rộng rãi trên toàn thế giới. Tại một số nước tiên tiến khác cũng tổ chức các phân hội địa phương của các hiệp hội này. Ðiều này chứng tỏ tầm ảnh hưởng của các tổ chức này trong ngành xử lý dữ liệu trên thế giới. Ngoài ra các nước cũng có các tổ chức quốc gia riêng về công nghệ xử lý dữ liệu. Ví dụ, tại Nhật Bản có SIGMOD-Japan và Tổ chức xử lý thông tin Japan (Japan InformationProcessing Society). Các tổ chức này hiện nay đều hỗ trợ mạnh các công nghệ xử lý dữ liệu lớn (big data) trong đó có vấn đề nghiên cứu về CSDLPT. Theo [1], trong hệ thống cơ sở dữ liệu phân tán, sự lưu trữ và dư thừa dữ liệu phân tán có tiện ích là để phục hồi lỗi, nhưng cũng vì thế nó làm cho quá trình xử lý truy vấn phân tán phức tạp hơn tại cùng một thời điểm. Vì vậy, trong các nhánh nghiên cứu về CSDLPT, nghiên cứu về tối ưu hóa và xử lý truy vấn là một trong những công nghệ quan trọng nhất. Trong nghiên cứu này, tác giả sử dụng toán tử bán kết hợp nhằm cải thiện hiệu suất của các truy vấn và giảm thời gian tìm kiếm. Tác giả Lin Zhou đã mô tả ngắn gọn các khái niệm tương ứng và đặc điểm của hệ thống cơ sở dữ liệu phân tán, tóm tắt những mục tiêu tối ưu hóa truy vấn cơ sở dữ liệu phân tán và phân tích các quá trình tối ưu hóa truy vấn dựa trên toán tử bán kết hợp với các ứng dụng thực tế cùng với thuật toán cổ điển SDD-1 nhằm thực hiện tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán. Theo Pawandeep Kaur [2] thì tối ưu hóa truy vấn là quá trình sử dụng phương án tốt nhất cho truy vấn để cải thiện hiệu suất của các truy vấn. Tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán khó khăn hơn rất nhiều so với cơ sở dữ liệu tập trung. Truy vấn trong cơ sở dữ liệu phân tán bị ảnh hưởng bởi các yếu tố như phương pháp chèn dữ liệu vào máy chủ từ xa và cách thời gian phản hồi giữa các máy chủ. Thời gian trả lời của các truy vấn phụ thuộc vào thời gian truyền và tốc độ xử lý của các máy cục bộ. Trong đó, vai trò của việc xây dựng một mô hình ước lượng chi phí của truy vấn phù hợp là rất quan trọng. Mô hình phù hợp sẽ tạo nên tảng để ước lượng chi phí cho các phương thức tối ưu hóa truy vấn khác nhau và lựa chọn phương án tốt nhất. Trong [3], Shyam Padia đã chứng minh tường minh răng vấn đề tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán quy mô lớn là bài toán NP - khó trong tự nhiên và rất khó để giải quyết. Các bài toán thuộc lớp NP-khó, ví dụ như bài toán tối ưu hó truy vấn, sự phức tạp của bộ tối ưu hóa tăng phi tuyến khi số lượng các quan hệ và số lượng các mối ràng buộc trong một truy vấn tăng lên. Nghiên cứu đã tìm hiểu và giới thiệu một số các các chiến lược tối ưu hóa khác nhau và các nghiên cứu cho thấy rằng hiệu suất tối ưu hóa truy vấn phân tán được cải thiện khi sử dụng thuât toán đàn kiến được tích hợp trong các thuật toán tối ưu hóa. 7 Tại Việt nam, trong một thời gian dài, tầm quan trọng của các HTTT có mức tự động hóa cao không được đánh giá đúng mức trong quản lý nhà nước và phát triển kinh tế, kinh doanh. Việc nghiên cứu về CSDL trong một thời gian dài tập trung vào lý thuyết CSDL như nghiên cứu về mô hình CSDL dùng các công cụ toán học. Trong lĩnh vực ứng dụng, mặc dù có không ít các dự án xây dựng các CSDL nhưng lĩnh vực này chưa được nghiên cứu đánh giá một cách tổng thể, sử dụng còn ở mức chưa khai thác hết tất cả các tính năng của các công nghệ CSDL hiện đại. Giữa lý thuyết và ứng dụng là một khoảng cách lớn. Theo Đào Ngọc Sơn [4], hệ thống phân tán là một hệ thống cơ sở dữ liệu phức tạp, đòi hỏi việc tổ chức cơ sở hạ tầng vật lý và mô hình kết nối mạng phức tạp. Việc tìm hiểu và tối ưu hóa truy vấn trong CSDLPT có ý nghĩa quan trọng quyết định đến hiệu năng hệ thống, làm hệ thống cơ sở dữ liệu phân tán mang những lợi ích giống như cơ sở dữ liệu tập trung và phát huy những ưu thế cơ sở dữ liệu phân tán mang lại. Công trình đã trình bày các nguyên lý chung để tối ưu hóa bao gồm: Các chiến lược tối ưu tổng quát, các kỹ thuật tối ưu hóa cơ bản, các biến đổi đại số, và giới thiệu các thuật toán tối ưu hóa trong cơ sở dữ liệu phân tán, dựa vào mô hình chi phí hoặc thời gian đáp ứng hệ thống, các thuật toán INGRES phân tán, Thuật toán System R*, thuật toán SDD-1 và thuật toán AHY. Bên cạnh đó tác giả cũng đã cài đặt thử nghiệm thuật toán System R* phân tán trong một hệ thống CSDLPT mô phỏng. Đề tài nghiên cứu của Phạm Thị Thu Huyền [5] đã trình bày các vấn đề cơ bản của cơ sở dữ liệu phân tán, cơ sở dữ liệu tập trung, các kỹ thuật tối ưu hóa truy vấn tập trung và phân tán. Qua đó cài đặt thử nghiệm một thuật toán SDD-1 để tối ưu truy vấn phân tán trong một hệ thống CSDLPT đơn giản. Qua các nghiên cứu trên thế giới và tại Việt nam, chúng ta có thể nhận thấy việc nghiên cứu về CSDLPT và tối ưu hóa truy vấn trên cơ sở dữ liệu này là rất quan trọng. Các nghiên cứu trên thế giới đã đi sâu vào các khía cạnh kỹ thuật đơn giản cũng như phức tạp trong việc phân tích câu truy vấn và tối ưu hóa xử lý câu truy vấn. Các nghiên cứu ở Việt nam cũng đã từng bước thực hiện việc cài đặt và thử nghiệm các thuật toán ứng dụng trong tối ưu hóa các truy vấn một cách rời rạc. Do đó, trong nghiên cứu này, tác giả thực hiện việc trình bày một cách có hệ thống các vấn đề liên quan đến CSDLPT và tổng hợp các thuật toán phổ biến đại diện cho các cách tiếp cận khác nhau trong việc tối ưu hóa câu truy vấn dành cho CSDLPT. 3. Mục tiêu nghiên cứu Tối ưu hóa truy vấn trong CSDLPT là một lĩnh vực rất rộng, trong phạm vi của đề tài này, tác giả sử dụng một cách tiếp cận có tính ứng dụng cao. Trong đó mục tiêu chính trong nghiên cứu bao gồm: - Hệ thống hóa các nghiên cứu, và lý thuyết về các vấn đề cơ bản của cơ sở dữ liệu phân tán, các nguyên lý chung, các kỹ thuật và các thuật toán liên quan đến truy vấn và tối ưu hóa truy vấn trong hệ thống thông tin. - Giới thiệu chi tiết các thuật toán chính được sử dụng trong tối ưu hóa CSDLPT. 8 - Báo cáo đề tài có thể làm tài liệu tham khảo cho việc viết giáo trình các môn: Cơ sở dữ liệu 2; Phân tích thiết kế hệ thống thông tin và là tài liệu tham khảo các học phần: Phân tích thiết kế hệ thống thông tin; Hệ thống thông tin quản lý. 4. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu: Các vấn đề về 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 cơ sở dữ liệu phân tán trong hệ thống thông tin. Phạm vi nghiên cứu: Đề tài tập trung nghiên cứu về truy vấn và một số các kỹ thuật tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán. 5. Phương pháp nghiên cứu Đề tài đã sử dụng phương pháp nghiên cứu tài liệu về lý thuyết cơ sở dữ liệu phân tán, các kỹ thuật truy vấn trong các sách chuyên ngành, bài báo đã công bố tại các tạp chí chuyên ngành uy tín, nhằm đưa ra một số các kiến thức tổng quan xử lý truy vấn cơ sở dữ liệu phân tán. Phương pháp thu thập dữ liệu: sử dụng phương pháp thống kê, so sánh nhằm nêu ra được những sự khác biệt giữa vấn đề xử lý truy vấn trong cơ sở dữ liệu tập trung và cơ sở dữ liệu phân tán. Mặt khác, đề tài cũng kết hợp nghiên cứu giữa lý thuyết và thực nghiệm để có thể phân tích một số các ví dụ minh họa giữa các thao tác khi xử lý tối ưu hóa truy vấn cơ sở dữ liệu phân tán trong hệ thống thông tin. 6. Kết cấu báo cáo nghiên cứu Về nội dung và bố cục, ngoài các phần như: mục lục, danh mục hình vẽ, danh mục từ viết tắt và tài liệu tham khảo, phụ lục, báo cáo được trình bày gồm 5 chương: Chương 1: Tổng quan nghiên cứu đề tài Chương này sẽ trình bày sơ lược về tổng quan đề tài nghiên cứu: tính cấp thiết, tình hình nghiên cứu về đề tài ở trong và ngoài nước, mục tiêu nghiên cứu, đối tượng, phạm vi nghiên cứu, và các phương pháp nghiên cứu khi tìm hiểu về vấn đề truy vấn và tối ưu hóa truy vấn cơ sở dữ liệu phân tán trong hệ thống thông tin. Chương 2: Tổng quan về cơ sở dữ liệu phân tán Nội dung chương này sẽ trình bày một cách tổng quan nhất về CSDL phân tán, bao gồm các khái niệm, đặc trưng và kiến trúc của cơ sở dữ liệu phân tán đồng thời nội dung của chương này cũng giới thiệu thêm một số các mô hình xử lý phân tán trong hệ thống thông tin. Chương 3: Các nguyên lý chung của tối ưu hóa truy vấn cơ sở dữ liệu phân tán Trong chương này sẽ giới thiệu về nguyên lý xử lý truy vấn, các chiến lược tối ưu hóa truy vấn cơ bản, một số các phép biến đổi đại số và các kỹ thuật tối ưu hóa tập trung làm nền tảng cho tối ưu hóa trong CSDLPT. 9 Chương 4: Tối ưu hóa truy vấn phân tán Nội dung chương này sẽ đề cập đến vấn đề tối ưu hóa truy vấn như cách phân rã câu truy vấn, phương pháp định vị dữ liệu phân tán và các chiến lược và các thuật toán để tối ưu hóa truy vấn phân tán. Đồng thời trong chương này cũng đưa ra nững hạn chế còn tồn tại trong nghiên cứu và đặt ra các hướng phát triển nghiên cứu trong tương lai. 10 CHƯƠNG 2: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN 1. Khái niệm về hệ cơ sở dữ liệu phân tán 1.1. Cơ sở dữ liệu phân tán Trong các Hệ thống thông tin (HTTT) xử lý tập trung, hệ cơ sở dữ liệu phát triển từ mô hình xử lý dữ liệu mà trong đó mỗi hệ thống ứng dụng định nghĩa một hay nhiều tệp dữ liệu riêng, các dữ liệu được ánh xạ sang mô hình định nghĩa và được quản lý tập trung. Mô hình này dẫn đến sự độc lập dữ liệu, nói cách khác, các ứng dụng có sự bất biến tương đối về cấu trúc lưu trữ và chiến lược truy cập dữ liệu. Tuy nhiên, trong các hệ xử lý phân tán, các thành phần của hệ xử lý phân tán nằm độc lập về mặt vật lý, có sự liên kết tương đối lỏng lẻo thông qua các hệ thống mạng kết nối, do đó “hệ dữ liệu phân tán” được coi như công cụ làm cho quá trình xử lý dữ liệu phân tán dễ dàng và hiệu quả hơn. Cơ sở dữ liệu phân tán được phát triển như là một tất yếu trong mô hình xử lý thông tin này. Cơ sở dữ liệu phân tán: Là một tập hợp nhiều cơ sở dữ liệu có liên đới logic và được phân bố rải rác trên nhiều máy trong một mạng máy tính. Trong mô hình cơ sở dữ liệu phân tán, bản thân cơ sở dữ liệu có ở trên nhiều máy tính khác nhau. Như vậy, đặc trưng nổi bật nhất của cơ sở dữ liệu phân tán là các CSDL được phân bố trên nhiều máy tính khác nhau trong một mạng máy tính và có liên đới về mặt logic. Tuy nhiên, việc làm rõ thế nào là một CSDLPT có liên đới logic và một tập hợp các CSDL rời rạc vẫn còn tương đối khó khăn. Hiện tại, vẫn chưa tồn tại một định nghĩa rõ ràng về các liên đới logic trong CSDLPT, nhưng một định nghĩa được chấp nhận phổ biến như sau: Liên đới logic: Toàn bộ dữ liệu của CSDLPT 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 tin lưu trữ tại các vị trí khác nhau trong một mạng máy tính. Hệ CSDL phân tán không đơn thuần là tập hợp các tệp dữ liệu đơn lẻ phân bố rời rạc trong mạng máy tính. Để hình thành một hệ CSDL phân tán, cần có một cấu trúc giao diện chung giữa các tệp dữ liệu này để có thể xây dựng một cơ chế truy cập lẫn nhau giữa các tệp dữ liệu. Ví dụ: CSDL quan hệ thường được tổ chức và biểu diễn dưới dạng các bảng. Việc phân mảnh một quan hệ thành nhiều quan hệ con khác nhau để lưu trữ trên nhiều máy trạm trong một mạng máy tính thường được thực hiện theo cách phân mảnh theo chiều dọc hoặc theo chiều ngang. Cụ thể: cho quan hệ PROJ = {PNO, BUDGET, PNAME, LOG}; quan hệ PROJ có thể tách thành hai quan hệ PROJ1 = {PNO, BUDGET} và quan hệ PROJ2 = {PNO, PNAME, LOG} và hai quan hệ này có thể được lưu trữ ở hai máy trạm khác nhau. 11 Giả sử quan hệ PROJ có dữ liệu như sau. PNO BUDGET PNAME LOG P1 150000 Instrumentation Montreal P2 350000 Database development New York P3 250000 CAD/CAM New York P4 139000 Maintenance Paris Khi đó: PROJ1 = 휋푃푁푂,퐵푈퐷퐺퐸푇(푃푅푂퐽) và có kết quả tương ứng là PNO BUDGET P1 150000 P2 350000 P3 250000 P4 139000 Đồng thời: PROJ2 = 휋푃푁푂,푃푁퐴푀퐸,퐿푂퐺(푃푅푂퐽) và có kết quả tương ứng là PNO PNAME LOG P1 Instrumentation Montreal P2 Database development New York P3 CAD/CAM New York P4 Maintenance Paris Vậy trong CSDLPT quan hệ PROJ sẽ được lưu trữ dưới dạng hai quan hệ PROJ1 và PROJ2. Cùng với sự phát triển của các cấu trúc tổ chức kinh tế xã hội, trong đó các cơ quan tổ chức thường hoạt động phân tán trong một phạm vi rộng, tầm quốc gia hoặc toàn cầu, các thiết kế và cài đặt hệ CSDL phân tán là phù hợp và đáp ứng mọi nhu cầu truy xuất dữ liệu. Sự phát triển mạnh của công nghệ phần cứng, mạng truyền thông cũng đảm bảo cho các hệ thống sử dụng hệ CSDL phân tán có tính tin cậy và tính sẵn sàng cao, giảm chi phí truyền thông và đảm bảo hiệu suất công việc. 1.2. Hệ quản trị cơ sở dữ liệu phân tán Hệ quản trị CSDL là một tập hợp các chương trình cho phép người dùng định nghĩa, tạo lập, bảo trì các CSDL và cung cấp các truy cập có điều khiển đến các CSDL này. Mục đích chính của một hệ CSDL là cung cấp cho người dùng một cách nhìn trừu tượng về dữ liệu. Điều đó có nghĩa là hệ thống che dấu những chi tiết phức tạp về cách thức dữ liệu được lưu trữ và bảo trì. Hệ CSDL phân tán cũng đòi hỏi một Hệ quản trị CSDL phân tán có những đặc điểm riêng biệt. Hệ quản trị cơ sở dữ liệu phân tán: Hệ quản trị CSDL phân tán cung cấp công cụ như tạo lập và quản lý CSDL phân tán. Hệ quản trị CSDL phân tán có chức năng hỗ trợ việc tạo và bảo trì CSDL phân tán, chúng có các thành phần tương tự như một hệ quản trị CSDL tập trung và 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. 12 Các thành phần sau đây đòi hỏi một Hệ quản trị CSDL phân tán thương mại phải có: - Quản trị dữ liệu (database management): DBM - 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 trên mạng. - Cơ sở dữ liệu phân tán (distributed database): DDB Hệ quản trị CSDL phân tán sử dụng nhiều kiến trúc lưu trữ phân tán khác nhau, có thể phân thành một số loại chính như sau: Cơ sở dữ liệu phân tán thuần nhất: Một CSDLPT được coi là thuần nhất nếu thỏa mãn tính chất sau: tất cả các nút (các máy tính trạm của một mạng máy tính dùng để lưu trữ toàn bộ CSDLPT) cùng sử dụng một loại hệ quản trị CSDL. CSDLPT thuần nhất thường được xây dựng bằng cách chia một CSDL thành một tập CSDL cục bộ. Phương phức xử lý trong CSDLPT thuần nhất thuận lợi cho việc tăng trưởng, mở rộng CSDL và cho phép nâng cao hiệu năng xử lý của toàn hệ thống. Cơ sở dữ liệu phân tán hỗn tạp: Ngược lại với CSDLPT thuần nhất, trong CSDLPT hỗn tạp, các nút có thể thực hiện trên các hệ quản trị CSDL khác nhau. CSDLPT hỗn tạp thường xảy ra khi CSDL mới được xây dựng từ tập hợp các nút mạng đã cài đặt CSDL riêng. Khi đó, thay vì xây dựng lại các CSDL cục bộ, hệ thống mới được xây dựng bằng cách tích hợp luôn các CSDL cục bộ đã có. 2. Các đặc trưng của cơ sở dữ liệu phân tán CSDL phân tán không đơn giản là sự thực hiện phân tán của các CSDL tập trung, bởi vì chúng cho phép thiết kế các đặc trưng khác với CSDL tập trung truyền thống. Các đặc điểm tiêu biểu của CSDL truyền thống gồm: Điều khiển tập trung, độc lập dữ liệu, giảm dư thừa dữ liệu, biệt lập và bảo mật dữ liệu. Những đặc điểm này trong CSDLPT có sự thay đổi đáng kể, tạo ra một hướng đi mới trong việc xây dựng các HTTT trên CSDLPT. 2.1. Điều khiển tập trung Trong CSDL tập trung: Khả năng điều khiển tập trung trên toàn nguồn tài nguyên thông tin của tổ chức, được xem là động cơ mạnh nhất cho việc ra đời CSDL. Chúng được phát triển như là sự tiến hoá của hệ thống thông tin mà trong đó mỗi ứng dụng có các tập tin riêng của nó. Trong CSDL phân tán: Ý niệm về điều khiển tập trung ít được nhấn mạnh hơn, điều này phụ thuộc vào kiến trúc của CSDL phân tán. Kiến trúc của CSDLPT được trình bay chi tiết hơn ở phần tiếp theo, tuy nhiên ở đây, chúng ta có thể nhận định các 13 CS...ọi là kết nối trộn, kết nối hai quan hệ đã sắp xếp trên thuộc tính kết nối. Nếu là kết nối bằng, chi phí của việc kết nối hai quan hệ được lưu trữ trên n1 và n2 bộ bản ghi là n1+ n2. Vì vậy, phương pháp này luôn được chọn khi có kết nối bằng, và khi các quan hệ được sắp xếp trước. Nếu chỉ một hoặc không có quan hệ nào được sắp xếp, chi phí của vòng lặp lồng nhau được so sánh với chi phí của phương pháp trộn + chi phí sắp xếp. Chi phí sắp xếp n bộ bản ghi là nlog2n. . 31 CHƯƠNG 4: KỸ THUẬT TỐI ƯU HÓA TRUY VẤN TRONG CSDLPT 1. Phân rã câu truy vấn 1.1. Chuẩn hóa Mức độ phức tạp của câu truy vấn đầu vào phụ thuộc vào ngôn ngữ cung cấp các phương tiện. Mục đích của việc chuẩn hóa là biến đổi một câu truy vấn sang một dạng chuẩn để xử lý tiếp. Với các ngôn ngữ quan hệ như SQL, việc chuyển đổi quan trọng nhất là lượng từ hóa truy vấn mệnh đề WHERE. Có 2 dạng chuẩn có thể cho việc dự đoán: một là đưa ra mức độ ưu tiên cho phép AND và cái còn lại cho phép OR. Dạng chuẩn hội: là hội của các tuyển như sau: (p11  p12 ... p1m ) ....  (pm1  pm2 ... pmn ) Ngược lại một lượng từ hóa ở dạng tuyển: (p11  p12 ...  p1m )  ....  (pm1  pm2 ...  pmn ) Biến đổi các vị từ phi lượng từ bằng cách sử dụng các quy tắc tương đương sau: 1. p1  p2  p2  p1 2. p1  p2  p2  p1 3. p1  (p2  p3 )  (p1  p2 )  p3 ) 4. p1  (p2  p3 )  (p1  p2 )  p3 ) 5. p1  (p2  p3 )  (p1  p2 )  (p1  p3 ) 6. p1  (p2  p3 )  (p1  p2 )  (p1  p3 ) 7. (p1  p2 )  (p1 )  (p2 ) 8. (p1  p2 )  (p1 )  (p2 ) 9. (p)  p Ví dụ: Tìm tên các nhân viên làm việc trong dự án P1 trong 12 hoặc 24 tháng: SELECT ENAME FROM EMP, ASG WHERE EMP.ENO=ASG.ENO AND ASG.PNO="P1" AND DUR=12 OR DUR=24 Lượng từ hóa dạng chuẩn hội là: EMP.ENO= ASG.ENO  ASG.PNO "P1"(DUR 12  DUR  24) 32 Lượng từ hóa dạng chuẩn tuyển là: (EMP.ENO= ASG.ENO  ASG.PNO "P1"DUR  12)  (EMP.ENO= ASG.ENO  ASG.PNO "P1"DUR  24) 1.2. Phân tích Bước phân tích câu truy vấn cho phép loại bỏ câu truy vấn đã được chuẩn hóa nhưng sai kiểu hoặc không đúng ngữ nghĩa. - Sai kiểu: Một câu truy vấn sai kiểu nếu có một thuộc tính trong quan hệ hay tên một quan hệ cha được khai báo trong lược đồ toàn cục hoặc các thao tác áp dụng cho các thuộc tính có kiểu không thích hợp. Tìm các truy vấn có kiểu không đúng tương tự như kiểm tra khai báo trong các ngôn ngữ lập trình. Ví dụ: SELECT E# FROM EMP WHERE ENAME >200 Truy vấn này sai kiểu vì thuộc tính E# không phải là thuộc tính của lược đồ quan hệ toàn cục, ENAME có kiểu chuổi, không thể so sánh với kiểu số 200. - Sai ngữ nghĩa: Một câu truy vấn được gọi là sau ngữ nghĩa nếu các thành phần của nó không tham gia vào việc tạo ra kết quả. Để có thể xác định tính đúng đắn ngữ nghĩa câu truy vấn tổng quát bằng các biểu diễn đồ thị truy vấn hay đồ thị kết nối gồm các phép chọn, phép chiếu và các phép kết nối, không chứa các phép tuyển và phép phủ định. Trong một đồ thị truy vấn, có một node biểu thị cho một quan hệ kết quả và các node khách biểu thị cho quann hệ toán hạng. Đường nối giữa 2 node không phải là quan hệ kết quả biểu thị cho phép kết nối, đường nối có node đích là quan hệ kết quả hiển thị cho phép chiếu. Các node quan hệ toán hạng có thể được gán nhãn là một vị từ chọn hoăc vị từ kết nối. Đồ thị kết nối là đồ thị con của đồ thị truy vấn, được sử dụng nhiều trong kỹ thuật tối ưu hóa truy vấn. Ví dụ: Tên và nhiệm vụ của các lập trình viên đã làm việc cho dự án CAD/CAM hơn 3 năm: SELECT ENAME, RESP FROM EMP, ASG, PROJ WHERE EMP.ENO=ASG.ENO AND ASG.PNO=PROJ.PNO AND PNAME="CAD/CAM" AND DUR>=36 AND TITLE ="Programmer" Đồ thị truy vấn như sau: 33 Hình: Ví dụ đồ thị truy vấn Hình 9: Đồ thị kết nối tương ứng Đồ thị truy vấn sử dụng nhằm mục đích xác định tính đúng đắn về mặt ngữ nghĩa của truy vấn hội đa biến không có phép phủ định. Một truy vấn không đúng về mặt ngữ nghĩa nếu đồ thị truy vấn của nó không liên thông. Nghĩa là có ít nhất một đồ thị con, tương ứng với câu truy vấn con tách ra khỏi đồ thị truy vấn có chứa quan hệ kết quả. Khi các vị từ kết nối bị thiếu,câu truy vấn đó cần được loại bỏ Ví dụ: Xét câu truy vấn: SELECT ENAME, RESP FROM EMP, ASG, PROJ WHERE EMP.ENO=ASG.ENO AND PNAME="CAD/CAM" AND DUR>=36 AND TITLE ="Programmer" 34 Đồ thị truy vấn như sau: Hình 10: Đồ thị truy vấn không liên thông Đồ thị truy vấn trên không liên thông, có 2 đồ thị tách biệt nên câu truy vấn này sai nghĩa. Có 3 giải pháp khắc phục là loại bỏ câu truy vấn, giải thiết 1 tích Đề các giữa quan hệ ASG và PROJ hoặc có thể đoán nhận vị từ kết nối bị thiếu ASG.PNO=PROJ.PNO 1.3. Loại bỏ dư thừa Trong một câu truy vấn, có thể loại bỏ các vị từ dư thừa và các thao tác dư thừa bằng cách giản ước các lượng từ hóa bằng các qui tắc lũy đẳng sau đây: Ví dụ: Xét câu truy vấn: SELECT TITLE FROM EMP WHERE (NOT (TITLE="Programmer") AND (TITLE="Programmer") OR TITLE="Elect.Eng") AND NOT (TITLE="Elect.Eng")) OR ENAME="J.Doe" 35 Đặt p1 là TITLE="Programmer", p2=TITLE="Elect.Eng" và p3=ENAME="J.Doe" Lượng từ hóa câu truy vấn trên ta được: Áp dụng quy tắc: p1  (p2  p3 )  (p1  p2 )  (p1  p3 ) và p1  (p2  p3 )  (p1  p2 )  p3 ), khi đó (p  ( p  p )  p )  ((p  p )  (p  p )  p )  p 1 1 2 2 1 1 1 2 2 3  ((p1  ( p2  p2 ))  p3  p1  false  p3  p3 Tức là: SELECT TITLE FROM EMP WHERE ENAME="J.Doe" 1.4. Viết lại Bước cuối cùng của việc phân rã truy vấn là viết lại truy vấn dưới dạng đại số quan hệ. Bước này bao gồm các giai đoạn sau: - Chuyển đổi truy vấn từ phép tính quan hệ sang đại số quan hệ. - Xây dựng lại truy vấn đại số quan hệ để cải thiện khả năng thực hiện Cách chuyển một truy vấn phép tính quan hệ thành một cây đại số quan hệ: - Các nút lá khác nhau được tạo cho mỗi biến bộ khác nhau (tương ứng một quan hệ). Trong SQL các nút lá chính là các quan hệ trong mệnh đề FROM. - Nút gốc được tạo ra bởi một phép chiếu lên các thuộc tính kết quả. Trong SQL nút gốc được xác định qua mệnh đề SELECT. - Điều kiện (mệnh đề WHERE trong SQL) được biến đổi thành dãy các phép toán đại số thích hợp (phép chọn, nối, phép hợp, v.v...) đi từ lá đến gốc, có thể thực hiện theo thứ tự xuất hiện của các vị từ và các phép toán.Định vị dữ liệu phân tán. Ví dụ: Xét câu truy vấn "Tìm tên các nhân viên trừ J.Doe đã làm cho dự án CAD/CAM trong 1 hoặc 2 năm". Câu lệnh SQL như sau: SELECT ENAME FROM EMP, ASG, PROJ WHERE EMP.ENO=ASG.ENO AND PROJ.PNO=ASG.PNO AND ENAME"J.Doe" 36 AND PROJ.NAME="CAD/CAM" AND (DUR=12 OR DUR =24) Cây đại số quan hệ như sau: Hình 11: Ví dụ về cây đại số quan hệ 2. Định vị dữ liệu phân tán Sau khi phân rã câu truy vấn, bước thứ hai của quá trình truy vấn là cục bộ hóa dữ liệu, hay nói cách xác là xác định các phân mảnh tương ứng từ lược đồ phân mảnh phục vụ cho câu truy vấn đã được phân rã. Giai đoạn này xác định các phân mảnh được sử dụng và chuyển đổi câu truy vấn phân tán thành một câu truy vấn trên mảnh cụ thể. Để xây dựng một câu truy vấn trên các phân mảnh cần thực hiện hai bước: Bước 1: Truy vấn phân tán được ánh xạ sang một truy vấn trên phân mảnh bằng việc thay thế mỗi quan hệ phân tán bằng chương trình xây dựng lại có chứa các phép toán đại số quan hệ thao tác trên mảnh, gọi là chương trình cục bộ hóa (localization program). Bước 2: Truy vấn trên mảnh được đơn giản hóa và xây dựng lại để tạo ra một câu truy vấn khác tốt hơn. Quá trình đơn giản hóa và xây dựng lại có thể được thực hiện dựa theo cùng một quy tắc được sử dụng trong lúc phân rã cách quan hệ tổng thể thành lược đồ phân mảnh. 37 Phân mảnh được định nghĩa bằng các quy tắc phân mảnh bao gồm phân mảnh ngang, phân mảnh dọc, và phân mảnh hỗn hợp, trong đó các mảnh được biểu diễn bởi các quan hệ. Do đó một quan hệ toàn cục có thể được xây dựng lại bằng cách áp dụng các quy tắc phân mảnh đảo và dẫn xuất một chương trình cục bộ hóa mà các toán hạng quan hệ là các mảnh. Để đơn giản, giả thiết không có các mảnh nhân bản, ta có các trường hợp rút gọn phân đoạn phổ biến như sau: - Rút gọn phân đoạn ngang nguyên thủy - Rút gọn phân đoạn dọc - Rút gọn phân đoạn dẫn xuất - Rút gọn phân đoạn hỗn hợp 2.1 Rút gọn phân mảnh ngang nguyên thủy Phân mảnh ngang phân tán một quan hệ dựa trên các vị từ chọn (Select Predicate). Ví dụ quan hệ EMP(ENO, ENAME, TITLE) có thể được phân mảnh ngang thành: EMP1 = σENO ≤E3" (EMP) EMP2 = σENO>"E3"∧3"∧<"E6" (EMP) EMP3 = σENO>"E6" (EMP) Khi đó chương trình cục bộ hóa cho quan hệ phân mảnh ngang là hợp các mảnh: EMP= EMP1  EMP2  EMP3 Vì vậy dạng truy vấn gốc được xác minh dựa trên EMP sẽ thu được bằng cách thay EMP bởi (EMP1  EMP2  EMP3). Như vậy để giảm các thao tác truy vấn trên quan hệ đã được phân mảnh theo chiều ngang, trước hết phải các định rõ cần thao tác trên mảnh nào và sau đó xây dựng lại cây con, xem xét loại bỏ các quan hệ rổng. Phân mảnh ngang sẽ được sử dụng để làm đơn giản hóa các phép chọn và phép kết nối. 2.1.1 Rút gọn phép chọn Phép chọn thực hiện trên các mảnh có lượng từ hóa mâu thuẩn với lượng từ hóa của quy tắc phân mảnh sinh ra các quan hệ rổng. Cho một quan hệ R được phân mảnh theo chiều ngang là R j = σpj(R), j =1..n , quy tắc này có thể được biểu diễn một cách hình thức như sau: Qui tắc 1: σ pj(R j )=Φ nếu ∀ x∈ R:¬(pi (x)∧ p j (x)) Trong đó pi, pj là các vị từ chọn, x là một bộ. Ví dụ vị từ ENO= “E1” mâu thuẩn với các vị từ của mảnh EMP2, EMP3 nghĩa là không có bộ nào thỏa vị từ ENO= “E1”. Ví dụ: Xét câu truy vấn sau: SELECT * FROM EMP 38 WHERE ENO=:E5” Áp dụng cách tiếp cận thô sơ để cục bộ hóa EMP từ EMP1 , EMP2 ,EMP3 cho câu truy vấn gốc ở hình a dưới đây bằng các hoán vị phép chọn và phép hợp. Dễ dàng nhận thấy vị từ chọn mâu thuẩn vơi EMP1, EMP3. Câu truy vấn đã rút gọn chỉ ứng dụng có một mảnh EMP2 như trong hình b: Hình 12: Rút gọn phân mảnh ngang với phép chọn 2.1.2 Rút gọn với phép kết nối Phép kết nối được thực hiện trên các phân mảnh ngang có thể đơn giản khi kết nối dựa theo các thuộc tính kết nối, bằng cách phân phối kết nối trên các hợp và sau đó loại bỏ các kết nối không tác dụng. Việc phân phổi các kết nối trên phép hợp được phát biểu như sau: (R ∪R ) S = (R S) ∪(R S) 1 2 1 2 Trong đó, Ri là các mảnh của R và S là một quan hệ. Bằng phép biến đổi này, các phép hợp có thể được di chuyển xuống dưới trong cây đại số quan hệ, nên tất cả các phép kết nối có thể của các mảnh đều được lộ ra. Các phép kết nối vô dụng được xác định khi lượng từ hóa các mảnh có mâu thuẫn. Giả sử các mảnh Ri và Rj được xác định theo cac vị từ chọn pi và pj trên cùng một quan hệ, quy tắc đơn giản hóa có thể được phát biểu như sau: Quy tắc 2: R i  R j =Φ nếu ∀x∈Ri ,∀y∈R j :¬(pi (x)∧p j (y)) Việc xác định các kết nối vô dụng có thể được thực hiện bằng cách chỉ xét các vị từ của các mảnh. Ví dụ: Giả sử xét quan hệ EMP(ENO, ENAME, TITLE) được phân mảnh ngang thành EMP1 , EMP2 ,EMP3: 39 EMP1 = σENO ≤"E3" (EMP) EMP2 = σENO>"E3"∧3"∧<"E6" (EMP) EMP3 = σENO>"E6" (EMP) Quan hệ ASG(ENO, PNO, RESP, DUR) được phân mảnh như sau: ASG1 = σENO ≤E3" (ASG) ASG2 = σENO>"E3" (ASG) EMP1 và ASG1 cùng định nghĩa bởi vị từ ENO≤“E3”. Vị từ định nghĩa trong ASG2 là hợp của các vị từ được định nghĩa trong EMP2 và EMP3: ENO > “E3”= ((“E3” “E6” ) Xét câu truy vấn sau: SELECT * FROM EMP, ASG WHERE EMP.ENO=ASG.ENO Câu truy vấn được rút gọn bằng cách phân phối các nối trên các hợp và áp dụng quy tắc 2 có thể cài đặt như hợp của ba nối từng phần được thực hiện song song: Hình 13: Cây đại số quan hệ truy vấn gốc Hình 14: Rút gọn phân mảnh ngang với phép kết nối 2.2 Rút gọn phân mảnh dọc Phân mảnh dọc phân tán một quan hệ dựa trên các thuộc tính chiếu. Vì vậy phép kết nối sẽ là phép toán tái xây dựng phân mảnh dọc. Chương trình cục bộ hóa cho quan hệ phân mảnh dọc bao gồm các kết nối của các mảnh trên các thuộc tính chung. 40 Ví dụ: Giả sử quan hệ EMP(ENO, ENAME, TITLE) được phân mảnh như sau: Phân mảnh ngang phân tán một quan hệ dựa trên các vị từ chọn (select Predicate). Ví dụ quan hệ EMP(ENO, ENAME, TITLE) có thể được phân mảnh ngang thành: EMP1= ENO, ENAME (EMP) EMP2= πENO,TITLE (EMP) Khi đó chương trình cục bộ hóa cho quan hệ phân mảnh dọc là: EMP= EMP1 ENO EMP2 Cũng như phân mảnh ngang, các câu truy vấn trên các phân mảnh dọc được rút gọn bằng cách xác định các quan hệ trung gian vô dụng và loại bỏ các cây con đã sinh ra chúng. Phép chiếu trên một phân mảnh dọc không có thuộc tính chung với các thuộc tính chiếu sinh ra các quan hệ vô dụng có thể không rỗng. Cho một quan hệ R định nghĩa trên các tập thuộc tính A={A1, A2, , An} và được phân thành Ri=πA’(R), i=1..k, A’A. Quy tắc được phát biểu một cách hình thức như sau: Quy tắc 3: πD,K(Ri) là vô dụng nếu tập các thuộc tính chiếu D không nằm trong A’. Ví dụ: Giả sử: EMP1= ENO, ENAME (EMP) EMP2= πENO,TITLE (EMP) Xét câu truy vấn SQL như sau: SELECT ENAME FROM EMP Bằng cách hoán vị phép chiếu và phép kết nối, ta nhận thấy rằng phép chiếu trên thuộc tính ENAME trên quan hệ EMP2 là vô dụng, vì ENAME không phải là thuộc tính của EMP2. Vì vậy phép chiếu chỉ cần thực hiện trên EMP1. Hình 15: Rút gọn phân mảnh dọc 41 2.3 Rút gọn phân mảnh dẫn xuất Phép kết nối thường xuyên xảy ra và có chi phí cao. Tối ưu hóa bằng phân mảnh ngang nguyên thủy khi các quan hệ nối được phân mảnh theo các thuộc tính nối. Trong trường hợp này nối của hai quan hệ được cài đặt như hợp của các nối từng phần. Tuy nhiên phương pháp này ngăn cản không cho một trong các quan hệ phân mảnh theo một phép chọn trên một thuộc tính khác. Phân mảnh ngang dẫn xuất phân phối hai quan hệ, cải thiện khả năng xử lý các điểm giao nhau giữa các phép chọn và phép kết nối. Nếu quan hệ R phân mảnh dẫn xuất theo quan hệ S, các mảnh của R và S có giá trị như nha ở thuộc tính kết nối sẽ nằm cùng vị trí. Quan hệ S có thể phân mảnh theo một vị từ được chọn. Vì các bộ của quan hệ R được đặt tùy chọn theo các bộ của S, để cho đơn giản, giả sử chỉ xét phân mảnh dẫn xuất chỉ được sử dụng cho mối liên hệ 1-n, trong đó một bộ của S tương ứng với n bộ của R và 1 bộ của R chỉ khớp đúng với 1 bộ của S. Ví dụ: Cho mối quan hệ 1-n EMP  ASG. Giả sử ASG được phân mảnh gián tiếp theo các qui tắc sau: ASG = ASG  EMP 1 ENO 1 ASG2 = ASG  ENO EMP2 Trong đó, EMP1 = σTITLE ="Programmer" (EMP)và EMP2= σTITLE≠"Programmer" (EMP) Chương trình cục bộ hóa cho quan hệ phân mảnh ngang là: ASG=ASG1  ASG2 Các câu truy vấn trên các mảnh dẫn xuất có thể được rút gọn bằng cách phân phối các nối trên các phép hợp và áp dụng quy tắc 2. Vì quy tắc phân mảnh chỉ rõ các bộ sẽ khớp với nhau, một số nối sinh ra quan hệ rỗng, các vị từ phân mảnh có mâu thuẫn. Ví dụ như các vị từ của ASG1 và EMP2 có mâu thuẫn vì vậy ASG1  EMP2 =  Xét câu truy vấn sau: SELECT ENAME FROM EMP, ASG WHERE EMP.ENO=ASG.ENO AND TITLE= “Mech, Eng” Câu truy vấn gốc được thao tác trên các mảnh EMP1, EMP2, ASG1, ASG2 như hình a bên dưới). Thực hiện phép chọn trên các mảnh EMP1, EMP2, vì vị từ chọn mâu thuẫn trên mảnh EMP1 nên kết quả câu truy vấn rút gọn thu được như hình b. Nhằm xác định các vị từ kết nối mâu thuẫn, cần phải phân phối các nối trên các hợp. Kết quả là cây hình c. Cây con bên trái nối 2 mảnh ASG1 và EMP2 với các lượng từ hóa mâu thuẫn bởi các vị từ chọn TITLE= “Programmar” trong ASG1 và TITLE≠ “Programmar” trong EMP2. Vì vậy có thể loại bỏ cây bên trái và thu được kết quả câu 42 truy vấn rút gọn được chỉ ra trong hình d. Ví dụn này minh họa giá trị phân mảnh trong việc cải thiện hiệu năng của các câu truy vấn phân tán. (a) Câu truy vấn gốc (b) Câu truy vấn sau khi đẩy phép chọn xuống (c) Truy vấn sau khi đẩy các phép hợp xuống (d) Câu truy vấn đã rút gọn sau khi loại cây con bên trái Hình 16: Rút gọn phân mảnh dẫn xuất 2.4 Rút gọn phân mảnh hỗn hợp Phân mảnh hỗn hợp bao gồm việc phân mảnh ngang và phân mảnh dọc. Mục đích của phân mảnh hỗn hợp là hỗ trợ một cách hiệu quả các câu truy vấn có chứa các phép chọn, phép chiếu và phép kết nối. Chương trình hóa cục bộ cho một quan hệ 43 phân mảnh hỗn hợp có sử dụng phép hợp và kết nối các mảnh. Để tối ưu hóa một phép toán hay tổ hợp các phép toán luôn luôn phải trả chi phí cao cho các phép toán khác. Ví dụ phân mảnh hỗn hợp dựa trên phép chiếu-chọn sẽ làm cho phép chiếu hoặc phép chọn kém hiệu quả hơn so với phân mảnh ngang hoặc phân mảnh dọc. Ví dụ: phân mảnh hỗn hợp của quan hệ EMP như sau: EMP1 = σENO ≤"E4" (π ENO, ENAME (EMP)) EMP2 = σENO>"E4" (π ENO, ENAME (EMP)) EMP3 = πENO, ENAME (EMP) Chương trình cục bộ hóa như sau: EMP= (EMP1 ∪EMP2 ) ENO EMP3 Các truy vấn trên những mảnh hỗn hợp có thể được rút gọn bằng cách kết hợp lần lượt các quy tắc trong phân mảnh ngang nguyên thủy, phân mảnh dọc và phân mảnh ngang dẫn xuất. Các quy tắc có thể tóm tắt như sau: 1. Loại bỏ các quan hệ rỗng được tạo ra do các phép chọn mâu thuẫn nhau trên các mảnh ngang. 2. Loại bỏ các kết nối vô dụng được tạo ra do các phép chiếu trên các phân mảnh dọc 3. Phân phối các kết nối cho các phép hợp nhằm cô lập và loại bỏ các kết nối vô dụng Ví dụ: Xét câu truy vấn sau: SELECT ENAME FROM EMP WHERE EMP = “E5”  Hình 17: Rút gọn phân mảnh hỗn hợp 3. Tối ưu hóa các truy vấn phân tán Một câu truy vấn trong phép tính quan hệ biểu diễn trên các quan hệ phân tán có thể được ánh xạ thành một câu truy vấn trên các đoạn quan hệ bằng cách phân rã và 44 định vị dữ liệu, ánh xạ này sử dụng lược đồ phân đoạn. Trong xử lý này, việc áp dụng các luật biến đổi cho phép đơn giản hoá câu truy vấn bằng cách tìm các biểu thức con chung và loại bỏ các biểu thức vô ích. Câu truy vấn thu được từ giai đoạn phân rã và định vị dữ liệu có thể được thực thi một cách đơn giản bằng việc thêm vào các thao tác truyền thông. Tuy nhiên, hoán vị thứ tự các phép toán trong câu truy vấn có thể cung cấp nhiều chiến lược tương đương để thực thi chúng. Tìm một thứ tự “tối ưu” của các phép toán cho một câu truy vấn đã cho là chức năng chính của bộ tối ưu hoá câu truy vấn. Sự lựa chọn thứ tự tối ưu đối với một câu truy vấn là bài toán khó thực hiện nên mục đích thực sự của bộ tối ưu là tìm một chiến lược gần tối ưu. Sau đây ta sẽ gọi chiến lược (hoặc thao tác sắp thứ tự) được đưa ra bởi bộ tối ưu là chiến lược tối ưu (hoặc sắp chiến lược tối ưu). Đầu ra của bộ tối ưu là một lịch trình được tối ưu bao gồm câu truy vấn đại số được xác định trên các trạm. 3.1 Đầu vào bộ tối ưu hóa câu truy vấn 2.1.1. Mô hình chi phí Chi phí của một chiến lược thực hiện phân tán có thể được biểu diễn hoặc theo tổng chi phí (total cost) hoặc theo thời gian trả lời. Tổng chi phí là tổng của tất cả các thành phần chi phí, còn thời gian trả lời tính từ lúc bắt đầu đến lúc kết thúc câu truy vấn. Công thức chung để tính tổng chi phí như sau: Total_cost = CCPU*#insts + CI/O*#I/Os + CMSG #msgs + CTR*#bytes Trong đó: - Total_cost - là tổng chi phí; - CCPU - chi phí của một lệnh CPU; - CI/O- chi phí của một truy xuất/nhập đĩa; - CMSG - chi phí cố định của việc khởi đầu và nhận một thông báo; - CTR - chi phí truyền một đơn vị dữ liệu từ trạm này tới trạm khác, CTR được coi như là hằng số; - #insts, #I/Os, #msgsm, #byte: Tương ứng là tổng trên các trạm của tất cả các số lệnh CPU, số lần truy xuất/ nhập đĩa, số thông báo, kích thước của tất cả các thông báo. Khi thời gian trả lời của câu truy vấn là hàm mục tiêu của bộ tối ưu các xử lý địa phương song song và truyền thông song song phải được xét. Chức tổng quát tính thời gian trả lời (response time) là: Response_time = CCPU*seq_#insts + CI/O*seq_#I/Os + CMSG *seq_#msgs + CTR*seq_#bytes Trong đó: seq_#x (x có thể là các lệnh CPU, I/O, các thông báo, các byte) là số lớn nhất của x phải được thực hiện tuần tự đối với sự thực thi của câu truy vấn. 45 2.1.2. Các thống kê cơ sở dữ liệu Yếu tố chính ảnh hưởng đến hiệu suất của một chiến lược thực thi là kích thước của các quan hệ trung gian sinh ra trong quá trình thực hiện. Khi gặp phép toán tiếp theo đặt tại một trạm khác, quan hệ trung gian phải được truyền lên mạng. Do vậy, để tối thiểu hoá khối lượng dữ liệu truyền, điểm quan tâm đầu tiên là đánh giá kích thước kết quả trung gian của các phép toán đại số quan hệ. Đánh giá này dựa trên các thông tin thống kê về các quan hệ cơ sở và các công thức ước tính lực lượng của kết quả của các phép toán quan hệ. Một số các kí hiệu: Quan hệ R xác định trên A = {A1, A2,...,An} được phân đoạn thành R1, R2,...,Rr. Khi đó dữ liệu thống kê điển hình bao gồm: - length(Ai): độ dài (byte) của thuộc tính Ai, với mỗi AiRj - card(Ai(Rj)): lực lượng của phép chiếu của đoạn Rj trên Ai - Miền xác định của Ai là tập số nguyên hoặc tập số thực, có max(Ai) và min(Ai). - card(dom[Ai]): Lực lượng của thuộc tính Ai, đó là số các giá trị duy nhất trên mỗi miền trị của thuộc tính Ai. - card(Rj): Số các bộ trong mỗi đoạn Rj Ngoài ra, dữ liệu thống kê cũng bao gồm hệ số chọn của phép kết nối (SFJ) đối với số cặp quan hệ; hệ số SFJ của quan hệ R và S là một số thực giữa 0 và 1: Hệ số SFJ nhỏ thì phép kết nối có tính chọn tốt, ngược lại có tính chọn tồi. Các thống kê này có lợi để đánh giá kích thước của các quan hệ trung gian. Kích thước của một quan hệ trung gian R như sau: Size(R)= card(R)*length(R). Trong đó: card(R) là số các bộ của R được tính theo các công thức ở phần sau. 2.1.3. Lực lượng của các kết quả trung gian Phần này sẽ đưa ra các công thức để ước tính lực lượng của kết quả của các phép toán cơ sở của đaị số quan hệ (phép chọn, phép chiếu, phép tích Decartes, kết nối, bán kết nối, phép hợp và phép trừ). Các toán hạng quan hệ được ký hiệu bởi R và S. Hệ số chọn của một phép toán (SFOP, OP biểu thị phép toán) là tỷ lệ giữa các bộ của một toán hạng quan hệ tham gia vào kết quả của phép toán. 46 Phép chiếu: card(A(R))=card(R) Tích Decartes: card(R x S)=card(R) * card(S) Phép kết nối: card(R  S)  SFj *card(R) *card(S) Bán kết nối: Hệ số chọn của phép bán kết nối (SFSJ) xấp xỉ là: card( (S) SF (R  S)   A SJ A card(dom[A]) card(R  A S)  SFSJ (S.A)*card(R) Phép hợp: Công thức tính cận trên bằng card(R)+card(S), cận dưới bằng max{card(R),card(S)} (giả sử R và S không chứa các bộ lặp) Phép trừ: cận trên của card(R-S) là card(S), cận dưới là 0 3.2 Thứ tự kết nối trên các truy vấn đoạn Thứ tự kết nối có vai trò quan trọng trong việc tối ưu hoá câu truy vấn tập trung. Thứ tự kết nối trong môi trường phân tán còn quan trọng hơn vì các phép kết nối giữa các đoạn có thể làm tăng chi phí truyền thông. Có hai cách tiếp cận cơ bản để sắp thứ tự các phép kết nối trong các câu truy vấn đoạn. - Cố gắng tối ưu thứ tự của các phép kết nối một cách trực tiếp - Thay các phép kết nối bởi kết hợp các phép bán kết nối để cực tiểu hóa các chi phí truyền thông Thứ tự kết nối: Một số thuật toán tối ưu hoá thứ tự của các phép kết nối một cách trực tiếp không sử dụng phép bán kết nối. Thuật toán INGRES phân tán và R* là đại diện cho lớp này. Một số các giả thiết: - Câu truy vấn được định vị và biểu diễn trên các đoạn, ta không cần phân biệt giữa các đoạn của cùng một quan hệ và các đoạn của các quan hệ khác. - Dùng thuật ngữ quan hệ để chỉ một đoạn lưu trữ tại một trạm cụ thể. - Bỏ qua chi phí xử lý địa phương. - Chỉ xét các câu truy vấn kết nối mà các toán hạng quan hệ được lưu tại các trạm khác nhau. - Bỏ qua chi phí truyền dữ liệu tại trạm kết quả. Vấn đề truyền toán hạng trong phép kết nối đơn, hiển nhiên là gửi quan hệ nhỏ hơn tới trạm của quan hệ lớn hơn, có hai khả năng như hình sau: Hình 18: Truyền các toán hạng trong phép toán hai ngôi 47 Trường hợp có hơn hai quan hệ kết nối, cũng như trường hợp một kết nối đơn, mục đích của thuật toán thứ tự kết nối là truyền các toán hạng nhỏ hơn. Vấn đề khó khăn ở đây là các phép kết nối có thể giảm hoặc tăng kích thước của các kết quả kết nối. Một giải pháp được sử dụng là đánh giá chi phí truyền thông của tất cả các chiến lược và chọn ra chiến lược tốt nhất. Tuy nhiên số các chiến lược tăng nhanh khi số các quan hệ tăng nên thường dùng phương pháp tìm kiếm gần đúng (heuristic) để loại trừ một số trường hợp xấu. 4. Tối ưu hóa các truy vấn phân tán Tối ưu hóa các truy vấn phân tán được thực hiện thống qua các giải thuật tối ưu hóa. Các giải thuật này có thể phân thành 4 hướng tiếp cận chính bao gồm: hướng tiếp cận sử dụng phép toán bán kết nối (semijoin), hướng tiếp cận tĩnh (static approach), hướng tiếp cận động (dynamic approach) và hướng tiếp cận kết hợp (hybrid approach). Trong phần này, tác giả sẽ đi sâu trình bày 3 giải thuật chính đại diện cho ba hướng tiếp cận đầu tiên. Hướng tiếp cận cuối cùng là xuy hướng trong đó các giải thuật của ba hướng tiếp cận đầu tiên được sử dụng kết hợp nhằm mục tiêu tăng độ tối ưu và thường gắn với một thiết kế CSDLPT cụ thể. 4.1 Thuật toán tối ưu hóa truy vấn phân tán SDD-1 Ý tưởng chính của thuật toán là dựa trên phép toán bán kết nối. Phép kết nối làm việc như một thuật toán rút gọn kích thước cho một quan hệ trước khi truyền. Kết nối 2 quan hệ R và S trên thuộc tính A, lưu tại trạm 1 và trạm 2 tương ứng, có thể tính toán bằng cách thay một hoặc 2 toán hạng quan hệ bởi phép bán kết nối với các quan hệ khác, sử dụng các quy tắc sau: Việc chọn một trong ba chiến lược bán kết nối trên đòi hỏi đánh giá các chi phí tương ứng của chúng. Sử dụng phép bán kết nối có lợi khi chi phó kết xuất và truyền nó tới trạm khác là nhỏ hơn chi phí truyền toàn bộ toán hạng quan hệ và thực hiện phép kết nối. Để thấy được lợi ích tiềm tang của phép bán kết nối, ta so sánh chi phí của hai lựa chọn R  A S và , giả sử size(R)<size(S). Chương trình sử dụng phép bán kết nối sau: 1. ∏A (S)  trạm 1. 2. Trạm 1 tính toán 3. R’  trạm 2 4. Trạm 2 tính toán Cách tiếp cận bán kết nối là tốt nếu: 48 Cách tiếp cận bán kết nối là tốt hơn nếu phép bán kết nối hoạt động như một toán tử rút gọn đầy đủ, tức là nếu một số ít bộ của R tham gia vào kết nối. - Thuật toán SDD-1: Thuật toán sử dụng phép bán kết nối, hàm mục tiêu tối thiểu tổng chi phí truyền thông (chi phí địa phương và thời gian trả lời không được xét). Bước chính của thuật toán bao gồm việc xác định và sắp thứ tự các phép kết nối có lợi, tức là các phép bán kết nối có chi phí nhỏ hơn lợi ích của nó. Để chọn ra phép bán kết nối hiệu quả, thuật toán sử dụng các đánh giá về chi phí (cost) và lợi ích (benefit) được xác định như sau: + Chi phí truyền của phép bán kết nối: Cost(Râ A S)=CMSG + CTR * size(∏A (S) ) + Đánh giá về lợi ích: Benefit(Râ A S)=(1 – SFSJ(S.A)) * size(R) * CTR Thuật toán SDD-1 nhận đầu vào là đồ thị câu truy vấn với n quan hệ, các thống kê cơ sở dữ liệu của mỗi quan hệ. Đầu ra của thuật toán là chiến lược để thực thi câu truy vấn. Thuật toán được tiến hành theo 4 giai đoạn: khởi đầu, chọn các phép bán kết nối có lợi, chọn trạm thực hiện và tối ưu hóa. Thuật toán SDD – 1 – QOA: Input: QG: Đồ thị truy vấn với n quan hệ, các thống kê của mỗi quan hệ Output: ES: Chiến lược thực hiện BEGIN ES local-operations(QG) Sửa đổi các thống kê để phản ánh kết quả xử lý của địa phương BS Φ {Tập các phép bán kết nối có lợi} For mỗi phép bán kết nối SJ trong QG do If (cost(SJ)<benefit(SJ) then BS BS  SJ Endif Endfor While BS  do {Chọn các phép kết nối có lợi} Begin SJ most_benefit(BS) {SJ: semijoin có benefit_cost lớn nhất} BSBS-SJ {Loại SJ khỏi BS} ESES+SJ Sửa đổi các thống kê để phản ánh kết quả của SJ thêm vào BSBS-các phép bán kết nối không có lợi BSBS  các phép bán kết nối có lợi mới 49 End Endwhile {Chọn trạm thực hiện} AS(ES)  chọn trạm i mà i chứa số lượng dữ liệu lớn nhất sau tất cả các phép toán cục bộ ES ES  sự truyền của các quan hệ trung gian tới AS(ES) {Tối ưu hóa sau} For mỗi quan hệ Ri tại AS(ES) do For mỗi phép nửa kết nỗi SJ của Ri với Rj do If (cost(ES)<cost(ES-SJ) then ES  ES - SJ Endif Endfor Endfor END. {SDD – 1 – QOA} Thuật toán này được diễn giải như sau: Giai đoạn khởi đầu: sinh ra một tập những phép bán kết nối có lợi (BS), vào một chiến lược thực thi (ES) bao gồm các xử lý địa phương. Giai đoạn tiếp theo: Lặp lại lựa chọn ra các phép bán kết nối có lợi (SJi) từ BS, sửa đổi các thống kê cơ sở dữ liệu và BS. Sự sửa đổi ảnh hưởng đến các thống kê của quan hệ R liên quan trong SJi và phép bán kết nối còn lại trong BS mà sử dụng quan hệ R. Vòng lặp kết thúc khi tất cả các phép bán kết nối được thêm vào ES sẽ là thứ tự thực thi của chúng. Giai đoạn chọn các trạm thực hiện: Với mỗi trạm đề cử đánh giá chi phí truyền tất cả dữ liệu được yêu cầu tới nó và chọn trạm có chi phí nhỏ nhất. Giai đoạn tối ưu hoá sau: Loại bỏ những phép kết nối trong chiến lược thực thi chỉ ảnh hưởng đến quan hệ được lưu trữ tại trạm thực hiện. 4.2 Thuật toán System R* Thuật toán System R* dành cho CSDLPT là đại diện cho các thuật toán sử dụng hướng tiếp cận tĩnh (static approach), trong CSDLPT thuật toán này còn có tên gọi khác là R*-QOA. Thuật toán này sử dụng cách tìm kiếm toàn bộ (exhautive search) trên tất cả các chiến lược thực thi của một câu truy vấn ở mức cao để tìm ra các chiến lược thực thi có chi phí tốt nhất. Chiến lược tìm kiếm toàn bộ có chi phí thời gian rất lớn, tuy nhiên chi