Báo cáo 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

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THƯƠNG MẠI ĐỀ TÀI NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG 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 MÃ SỐ: CS-16-05 Chủ nhiệm đề tài: ThS. Cù Nguyên Giáp Bộ môn: Tin Học Hà Nội, năm 2017 2 MỤC LỤC DANH MỤC HÌNH VẼ .................................................................................................. 4 DANH MỤC TỪ VIẾT TẮT .......................................................................................... 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 3 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 4 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 5 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ộ 6 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 7 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. 8 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. Tro