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
TỔNG QUAN NGHIÊN CỨU ĐỀ TÀI
Tính cấp thiết nghiên cứu của đề tài
Xã hội phát triển nhanh chóng dẫn đến khối lượng thông tin cần xử lý và lưu trữ trong các hệ thống thông tin ngày càng gia tăng Dữ liệu lớn với hàng triệu bản ghi cần được cập nhật thường xuyên gây khó khăn cho mô hình cơ sở dữ liệu tập trung, ảnh hưởng đến tốc độ xử lý tại máy chủ và băng thông đường truyền, từ đó làm giảm tính sẵn sàng của hệ thống.
Các doanh nghiệp và tổ chức thường hoạt động trên một vùng địa lý rộng lớn, có thể trải dài qua nhiều thành phố, quốc gia hoặc thậm chí toàn cầu Do đó, việc lưu trữ và xử lý dữ liệu một cách tập trung trở nên không khả thi, vì dữ liệu cần được phân tán và lưu trữ tại nhiều địa điểm khác nhau nơi mà các cơ quan, tổ chức hoặc doanh nghiệp hoạt động.
Khi dữ liệu không còn được lưu trữ tập trung, việc quản lý và truy xuất dữ liệu một cách hiệu quả trở thành một thách thức quan trọng Điều này đã dẫn đến sự phát triển của cơ sở dữ liệu phân tán (CSDLPT), nơi dữ liệu được lưu trữ trên nhiều trạm riêng biệt Tuy nhiên, hệ thống quản lý được thiết kế để người dùng có thể truy vấn dữ liệu giống như trong cơ sở dữ liệu tập trung (CSDLTT), đảm bảo rằng công tác chuyên môn không bị ảnh hưởng hay gián đoạn.
Khi khối lượng thông tin ngày càng lớn và đa dạng, việc tối ưu hóa câu lệnh truy vấn dữ liệu trở nên cần thiết để giảm chi phí xử lý Tối ưu hóa truy vấn trên cơ sở dữ liệu phân tán (CSDLPT) yêu cầu áp dụng nhiều kỹ thuật phức tạp hơn so với cơ sở dữ liệu thông thường, do dữ liệu được lưu trữ ở nhiều vị trí khác nhau.
Việc nghiên cứu và tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán (CSDLPT) là cần thiết và có tính ứng dụng cao trong doanh nghiệp Do đó, 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” để tìm hiểu Đề tài này nhằm hệ thống hóa các vấn đề liên quan đến việc xây dựng và tối ưu hóa câu truy vấn trong môi trường đặc trưng của CSDLPT.
Tổng quan về đề tài nghiên cứu
Hiện nay, việc quản lý và khai thác thông tin, dữ liệu đang thu hút sự quan tâm lớn từ các nước tiên tiến về công nghệ thông tin, đặc biệt trong bối cảnh ngành công nghiệp nội dung số phát triển mạnh mẽ Các công nghệ như kỹ thuật dữ liệu, tìm kiếm thông tin, xử lý dữ liệu và cơ sở dữ liệu lưới đang được nghiên cứu sâu rộng tại các trường đại học hàng đầu Những chương trình này nhận được sự hỗ trợ từ một ngành công nghiệp lớn, nhằm nhanh chóng ứng dụng các thành tựu công nghệ mới vào thực tiễn Chính phủ các nước cũng đang thúc đẩy sự phát triển này.
Bảy quốc gia 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 công nghệ mới là nhiệm vụ sống còn cho việc xây dựng hạ tầng thông tin, phục vụ lợi ích quốc gia và thúc đẩy sự phát triển kinh tế.
Nhiều hiệp hội nghiên cứu và phát triển công nghệ quản lý thông tin và dữ liệu đã ra đời và có ảnh hưởng lớn trên toàn cầu, với SIGMOD thuộc ACM và Data Engineering của IEEE là hai tổ chức nổi bật nhất Mặc dù cả hai đều có nguồn gốc từ Mỹ, nhưng chúng được công nhận rộng rãi trên thế giới, và nhiều quốc gia tiên tiến cũng đã thành lập các phân hội địa phương Đ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 Ngoài ra, nhiều quốc gia cũng có các tổ chức quốc gia riêng về công nghệ xử lý dữ liệu, như SIGMOD-Japan và Tổ chức xử lý thông tin Nhật Bản, đều hỗ trợ mạnh mẽ cho công nghệ xử lý dữ liệu lớn, bao gồm nghiên cứu về cơ sở dữ liệu phân tán.
Trong hệ thống cơ sở dữ liệu phân tán, việc lưu trữ và dư thừa dữ liệu giúp phục hồi lỗi nhưng cũng làm phức tạp quá trình xử lý truy vấn Do đó, tối ưu hóa và xử lý truy vấn trở thành công nghệ quan trọng trong nghiên cứu CSDLPT Nghiên cứu này áp dụng toán tử bán kết hợp để nâng cao hiệu suất truy vấn và giảm thời gian tìm kiếm.
Tác giả Lin Zhou đã trình bày khái niệm và đặc điểm của hệ thống cơ sở dữ liệu phân tán, đồng thời tóm tắt các mục tiêu tối ưu hóa truy vấn trong hệ thống này Bài viết phân tích các quy trình tối ưu hóa truy vấn dựa trên toán tử, kết hợp với các ứng dụng thực tế và thuật toán cổ điển SDD-1 để thực hiện tối ưu hóa hiệu quả trong cơ sở dữ liệu phân tán.
Tối ưu hóa truy vấn là quá trình áp dụng phương án tốt nhất để nâng cao hiệu suất truy vấn, đặc biệt trong cơ sở dữ liệu phân tán, nơi gặp nhiều khó khăn hơn so với cơ sở dữ liệu tập trung Các yếu tố ảnh hưởng đến truy vấn trong cơ sở dữ liệu phân tán bao gồm phương pháp chèn dữ liệu từ xa và thời gian phản hồi giữa các máy chủ Thời gian trả lời của truy vấn phụ thuộc vào thời gian truyền và tốc độ xử lý của máy cục bộ Do đó, việc xây dựng một mô hình ước lượng chi phí truy vấn chính xác là rất quan trọng, tạo nền tảng cho việc ước lượng chi phí các phương thức tối ưu hóa khác nhau và lựa chọn phương án tối ưu nhất.
Trong nghiên cứu của Shyam Padia, vấn đề tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán quy mô lớn được xác định là NP - khó, cho thấy sự phức tạp của bài toán này Khi số lượng quan hệ và mối ràng buộc trong một truy vấn tăng lên, độ phức tạp của việc tối ưu hóa cũng gia tăng Nghiên cứu đã giới thiệu một số chiến lược tối ưu hóa khác nhau và chỉ ra rằng hiệu suất của tối ưu hóa truy vấn phân tán có thể được cải thiện khi áp dụng thuật toán đàn kiến trong các thuật toán tối ưu hóa.
Tại Việt Nam, tầm quan trọng của các hệ thống thông tin tự động hóa cao trong quản lý nhà nước và phát triển kinh tế chưa được đánh giá đúng mức Nghiên cứu về cơ sở dữ liệu (CSDL) chủ yếu tập trung vào lý thuyết, sử dụng các mô hình toán học mà chưa chú trọng đến ứng dụng thực tế Mặc dù có nhiều dự án xây dựng CSDL, nhưng việc nghiên cứu và đánh giá tổng thể vẫn còn hạn chế, dẫn đến việc chưa khai thác hết các tính năng của công nghệ CSDL hiện đại Sự chênh lệch giữa lý thuyết và ứng dụng là một vấn đề cần được giải quyết.
Hệ thống phân tán là một hệ thống cơ sở dữ liệu phức tạp, yêu cầu tổ chức hạ tầng vật lý và mô hình kết nối mạng tinh vi Việc tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán là rất quan trọng để nâng cao hiệu năng hệ thống, giúp hệ thống này mang lại những lợi ích tương tự như cơ sở dữ liệu tập trung Bài viết đã trình bày các nguyên lý tối ưu hóa, bao gồm chiến lược tổng quát, kỹ thuật tối ưu hóa cơ bản và biến đổi đại số, đồng thời giới thiệu các thuật toán tối ưu hóa như INGRES phân tán, System R*, SDD-1 và AHY Tác giả cũng đã thực hiện thử nghiệm thuật toán System R* trong một hệ thống cơ sở dữ liệu phân tán mô phỏng Nghiên cứu của Phạm Thị Thu Huyền đã đề cập đến các vấn đề cơ bản của cơ sở dữ liệu phân tán và tập trung, cùng với các kỹ thuật tối ưu hóa truy vấn và thử nghiệm thuật toán SDD-1 để tối ưu hóa truy vấn trong hệ thống cơ sở dữ liệu phân tán đơn giản.
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, như đã được chứng minh qua các nghiên cứu toàn cầu và tại Việt Nam Các nghiên cứu quốc tế đã phân tích sâu sắc các khía cạnh kỹ thuật trong tối ưu hóa xử lý câu truy vấn, trong khi Việt Nam cũng đã tiến hành cài đặt và thử nghiệm các thuật toán tối ưu hóa Do đó, bài viết này sẽ trình bày một cách 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 những cách tiếp cận khác nhau trong tối ưu hóa câu truy vấn cho CSDLPT.
Mục tiêu nghiên cứu
Tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán (CSDLPT) là một lĩnh vực rộng lớn, và trong nghiên cứu này, tác giả áp dụng một phương pháp thực tiễn Mục tiêu chính của nghiên cứu là cải thiện hiệu suất truy vấn trong CSDLPT.
Hệ thống hóa nghiên cứu và lý thuyết liên quan đến cơ sở dữ liệu phân tán, bao gồm các nguyên lý chung, kỹ thuật và thuật toán về truy vấn cũng như 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
- 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 là tài liệu tham khảo quan trọng cho các học phần liên quan đến phân tích và thiết kế hệ thống thông tin, cũng như hệ thống thông tin quản lý Tài liệu này cung cấp cái nhìn sâu sắc về các phương pháp và công cụ cần thiết để phát triển hệ thống thông tin hiệu quả.
Đối tượng và phạm vi nghiên cứu
Nghiên cứu tập trung vào các vấn đề liên quan đến cơ sở dữ liệu phân tán, bao gồm nguyên lý chung, kỹ thuật và thuật toán nhằm tối ưu hóa truy vấn trong hệ thống thông tin.
Đề tài nghiên cứu này tập trung vào việc phân tích truy vấn và áp dụng các kỹ thuật tối ưu hóa truy vấn trong hệ thống cơ sở dữ liệu phân tán.
Phương pháp nghiên cứu
Bài viết sử dụng phương pháp nghiên cứu tài liệu để khám phá lý thuyết cơ sở dữ liệu phân tán và các kỹ thuật truy vấn Nguồn tư liệu bao gồm sách chuyên ngành và bài báo từ các tạp chí uy tín, nhằm cung cấp cái nhìn tổng quan về cách xử lý truy vấn trong cơ sở dữ liệu phân tán.
Phương pháp thu thập dữ liệu trong nghiên cứu này bao gồm việc áp dụng các phương pháp thống kê và so sánh để làm nổi bật sự khác biệt giữa việc xử lý truy vấn trong cơ sở dữ liệu tập trung và cơ sở dữ liệu phân tán.
Đề tài này kết hợp nghiên cứu lý thuyết và thực nghiệm nhằm phân tích các ví dụ minh họa cho các thao tác tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán trong hệ thống thông tin.
Kết cấu báo cáo nghiên cứu
Báo cáo được cấu trúc thành 5 chương, bao gồm các phần quan trọng như mục lục, danh mục hình vẽ, danh mục từ viết tắt, tài liệu tham khảo và phụ lục.
Chương 1: Tổng quan nghiên cứu đề tài
Chương này sẽ tổng quan về đề tài nghiên cứu, bao gồm tính cấp thiết và tình hình nghiên cứu trong và ngoài nước Nó cũng sẽ trình bày mục tiêu nghiên cứu, đối tượng và phạm vi nghiên cứu, cùng với các phương pháp nghiên cứu liên quan đến truy vấn và tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán của hệ thống thông tin.
Chương 2: Tổng quan về cơ sở dữ liệu phân tán
Chương này sẽ cung cấp cái nhìn tổng quan về cơ sở dữ liệu phân tán, bao gồm các khái niệm, đặc trưng và kiến trúc của nó Đồng thời, chương cũng giới thiệu một số 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
Chương này sẽ trình bày nguyên lý xử lý truy vấn và các chiến lược tối ưu hóa truy vấn cơ bản, cùng với một số phép biến đổi đại số và kỹ thuật tối ưu hóa tập trung, là nền tảng cho việc tối ưu hóa trong cơ sở dữ liệu phân tán.
Chương 4: Tối ưu hóa truy vấn phân tán
Chương này sẽ khám phá tối ưu hóa truy vấn, bao gồm phân rã câu truy vấn, phương pháp định vị dữ liệu phân tán, cùng với các chiến lược và thuật toán để tối ưu hóa truy vấn phân tán Ngoài ra, chương cũng nêu rõ những hạn chế hiện có trong nghiên cứu và đề xuất các hướng phát triển nghiên cứu trong tương lai.
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN
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 xử lý tập trung, cơ sở dữ liệu phát triển từ mô hình xử lý dữ liệu, trong đó mỗi ứng dụng định nghĩa một hoặc nhiều tệp dữ liệu riêng biệt Dữ liệu được ánh xạ sang mô hình định nghĩa và được quản lý một cách tập trung, dẫn đến sự độc lập dữ liệu Điều này có nghĩa là các ứng dụng duy trì tính ổn định tương đối về cấu trúc lưu trữ và chiến lược truy cập dữ liệu.
Trong các hệ xử lý phân tán, các thành phần hoạt động độc lập về mặt vật lý và kết nối lỏng lẻo qua mạng, khiến cho "hệ dữ liệu phân tán" trở thành công cụ quan trọng để tối ưu hóa quá trình xử lý dữ liệu Sự phát triển của cơ sở dữ liệu phân tán là cần thiết trong mô hình xử lý thông tin này.
Cơ sở dữ liệu phân tán là một hệ thống bao gồm nhiều cơ sở dữ liệu có mối liên hệ logic, được phân bố trên nhiều máy tính trong một mạng.
Trong mô hình cơ sở dữ liệu phân tán, cơ sở dữ liệu được lưu trữ trên nhiều máy tính khác nhau trong một mạng, với đặc trưng nổi bật là tính phân bố và liên đới logic giữa các CSDL Tuy nhiên, việc phân biệt giữa một cơ sở dữ liệu phân tán có liên đới logic và một tập hợp các CSDL rời rạc vẫn còn gặp khó khăn Hiện tại, chưa có định nghĩa rõ ràng về các liên đới logic trong cơ sở dữ liệu phân tán, nhưng một định nghĩa phổ biến được chấp nhận là cần thiết để hiểu rõ hơn về mô hình này.
Liên đới logic trong CSDLPT là tập hợp các thuộc tính ràng buộc dữ liệu với nhau, giúp phân biệt CSDL phân tán với các CSDL cục bộ hoặc tập tin lưu trữ tại nhiều vị trí khác nhau trong mạng máy tính.
Hệ CSDL phân tán không chỉ là tập hợp các tệp dữ liệu rời rạc trong mạng máy tính, mà còn yêu cầu một cấu trúc giao diện chung để tạo ra cơ chế truy cập lẫn nhau giữa các tệp dữ liệu.
Cơ sở dữ liệu quan hệ thường được tổ chức 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 để lưu trữ trên nhiều máy trạm trong mạng máy tính thường được thực hiện theo hai cách: phân mảnh theo chiều dọc và phân mảnh theo chiều ngang.
Quan hệ PROJ bao gồm các thuộc tính PNO, BUDGET, PNAME và LOG có thể được phân tách thành hai quan hệ riêng biệt: PROJ1 với các thuộc tính PNO và BUDGET, và PROJ2 với các thuộc tính PNO, PNAME và LOG Hai quan hệ này có thể được lưu trữ trên hai máy trạm khác nhau.
Giả sử quan hệ PROJ có dữ liệu như sau
Khi đó: PROJ1 = 𝜋 𝑃𝑁𝑂,𝐵𝑈𝐷𝐺𝐸𝑇 (𝑃𝑅𝑂𝐽) và có kết quả tương ứng là
P4 139000 Đồng thời: PROJ2 = 𝜋𝑃𝑁𝑂,𝑃𝑁𝐴𝑀𝐸,𝐿𝑂𝐺(𝑃𝑅𝑂𝐽) và có kết quả tương ứng là
Vậy trong CSDLPT quan hệ PROJ sẽ được lưu trữ dưới dạng hai quan hệ PROJ1 và PROJ2
Với sự phát triển của các cấu trúc tổ chức kinh tế xã hội và hoạt động phân tán của các cơ quan tổ chức trên phạm vi quốc gia hoặc toàn cầu, việc thiết kế và cài đặt hệ CSDL phân tán trở nên cần thiết để đáp ứng nhu cầu truy xuất dữ liệu Công nghệ phần cứng và mạng truyền thông phát triển mạnh mẽ đảm bảo cho các hệ thống sử dụng CSDL phân tán có độ tin cậy và tính sẵn sàng cao, đồng thời giảm chi phí truyền thông và nâng cao 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ị cơ sở dữ liệu (CSDL) là tập hợp các chương trình giúp người dùng định nghĩa, tạo lập và bảo trì CSDL, đồng thời cung cấp truy cập có điều kiện đến các CSDL này Mục tiêu chính của hệ CSDL là mang lại cho người dùng cái nhìn trừu tượng về dữ liệu, che giấu những chi tiết phức tạp liên quan đến việc lưu trữ và bảo trì dữ liệu Đối với hệ CSDL phân tán, cần có một hệ quản trị CSDL phân tán với những đặc điểm riêng biệt để đáp ứng các yêu cầu đặc thù.
Hệ quản trị cơ sở dữ liệu phân tán cung cấp các công cụ cần thiết để tạo lập và quản lý cơ sở dữ liệu phân tán Chức năng chính của hệ thống này là hỗ trợ việc tạo và bảo trì cơ sở dữ liệu, với các thành phần tương tự như trong hệ quản trị cơ sở dữ liệu tập trung, đồng thời hỗ trợ 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ị 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:
CSDLPT được coi là thuần nhất khi tất cả các nút trong mạng máy tính, nơi lưu trữ toàn bộ CSDLPT, đều sử dụng cùng một loại hệ quản trị CSDL.
CSDLPT thuần nhất được hình thành bằng cách phân chia một cơ sở dữ liệu thành nhiều tập CSDL cục bộ Phương pháp này giúp tối ưu hóa hiệu suất xử lý và tạo điều kiện thuận lợi cho việc mở rộng và phát triển cơ sở dữ liệu.
Cơ sở dữ liệu phân tán hỗn tạp:
Trong CSDLPT hỗn tạp, các nút có khả năng hoạt động trên nhiều hệ quản trị CSDL khác nhau, trái ngược với CSDLPT thuần nhất Tình huống này thường xuất hiện khi một CSDL mới được hình thành từ một tập hợp các nút mạng đã có sẵn CSDL riêng Thay vì xây dựng lại các CSDL cục bộ, hệ thống mới được thiết lập bằng cách tích hợp các CSDL cục bộ đã tồn tại.
Các đặc trưng của cơ sở dữ liệu phân tán
CSDL phân tán không chỉ là phiên bản phân tán của các CSDL tập trung, mà còn cho phép thiết kế những đặc trưng khác biệt so với CSDL truyền thống Các đặc điểm của CSDL truyền thống như điều khiển tập trung, độc lập dữ liệu, giảm dư thừa dữ liệu, và bảo mật dữ liệu đã có sự thay đổi đáng kể trong CSDL phân tán, mở ra một hướng đi mới trong việc xây dựng các hệ thống thông tin.
Trong cơ sở dữ liệu tập trung, khả năng quản lý toàn bộ nguồn tài nguyên thông tin của tổ chức được coi là yếu tố quan trọng nhất dẫn đến sự phát triển của cơ sở dữ liệu Những hệ thống này được hình thành như một bước tiến trong việc cải tiến hệ thống thông tin, trong đó mỗi ứng dụng sở hữu các tập tin riêng biệt.
Trong cơ sở dữ liệu phân tán, khái niệm về điều khiển tập trung không được nhấn mạnh nhiều, điều này phụ thuộc vào kiến trúc của hệ thống Kiến trúc của cơ sở dữ liệu phân tán sẽ được trình bày chi tiết trong phần tiếp theo.
CSDLPT được thiết kế dựa trên kiến trúc client/server, đặc biệt là mô hình multi-client/single-server, mang lại khả năng điều khiển tập trung cao hơn so với các kiến trúc khác, chẳng hạn như kiến trúc CSDLPT ngang hàng (peer-to-peer).
Trong cơ sở dữ liệu phân tán, độc lập dữ liệu giữ vai trò quan trọng tương tự như trong cơ sở dữ liệu truyền thống Một khía cạnh mới trong khái niệm này là tính trong suốt phân tán, cho phép các chương trình ứng dụng tương tác với cơ sở dữ liệu mà không cần quan tâm đến việc tổ chức phân tán Điều này đảm bảo rằng độ chính xác của chương trình không bị ảnh hưởng bởi việc di chuyển dữ liệu giữa các trạm, tuy nhiên, tốc độ thực hiện của chúng có thể bị ảnh hưởng.
Trong CSDLPT, việc đảm bảo tính trong suốt phân tán dựa vào các phương pháp ẩn kỹ thuật rời rạc hóa dữ liệu Tính trong suốt này được chia thành các vấn đề nhỏ như trong suốt phân đoạn, trong suốt về vị trí, trong suốt ánh xạ địa phương và trong suốt nhân bản Mặc dù các kỹ thuật này không phải là trọng tâm của nghiên cứu, nhưng thông tin chi tiết về chúng có thể được tìm thấy trong các tài liệu tham khảo kèm theo báo cáo.
2.3 Giảm dư thừa dữ liệu
Trong cơ sở dữ liệu truyền thống, việc giảm thiểu dữ liệu dư thừa rất quan trọng để tránh sự không tương thích giữa nhiều bản sao của cùng một tập dữ liệu và tiết kiệm không gian lưu trữ Giải pháp hiệu quả để giảm thiểu dư thừa là chia sẻ dữ liệu, cho phép nhiều ứng dụng cùng truy cập vào các bản tin và bản ghi.
Trong cơ sở dữ liệu phân tán, việc giảm thiểu dư thừa trở nên phức tạp hơn do nhiều yếu tố Một trong những lý do chính là việc tăng cường hoạt động của các trình ứng dụng khi dữ liệu được sao chép ở tất cả các vị trí cần thiết Ngoài ra, tính thường trực của hệ thống cũng được cải thiện, vì nếu xảy ra lỗi tại một trạm, các ứng dụng ở các trạm khác vẫn có thể tiếp tục hoạt động nếu dữ liệu đã được sao chép.
2.4 Độ tin cậy qua các giao dịch phân tán
Hệ quản trị cơ sở dữ liệu (CSDL) phân tán nâng cao độ tin cậy thông qua các giao dịch phân tán, nhờ vào việc nhân bản các thành phần để hạn chế vị trí lỗi đơn lẻ Khi xảy ra lỗi tại một trạm hoặc trong quá trình truyền thông, hệ thống vẫn có thể hoạt động mà không bị gián đoạn hoàn toàn Điều này có nghĩa là mặc dù một số dữ liệu có thể không truy cập được, người dùng vẫn có khả năng truy cập các phần khác của CSDL phân tán nếu biết cách hỗ trợ các giao dịch và áp dụng các giao thức thích hợp.
Hiệu năng của CSDL phân tán được nâng cao dựa trên hai đặc điểm:
Hệ quản trị cơ sở dữ liệu phân tán (CSDL PT) có khả năng phân mảnh dữ liệu khái niệm và cho phép cụ bộ hóa dữ liệu, mang lại hai ưu điểm chính Đầu tiên, mỗi trạm chỉ xử lý một phần của CSDL, giúp giảm thiểu sự tranh chấp về CPU và các dịch vụ vào/ra so với hệ CSDL tập trung Thứ hai, tính cụ bộ giúp giảm độ trễ truy cập từ xa thường gặp trên các mạng diện rộng.
Tính song song trong các hệ thống phân tán cho phép thực hiện song song liên truy vấn và truy vấn nội bộ Liên truy vấn song song cho phép nhiều truy vấn được thực hiện đồng thời, trong khi nội truy vấn song song là phương pháp phân chia một truy vấn đơn thành nhiều truy vấn con, mỗi truy vấn con được thực hiện tại các trạm khác nhau, truy cập các phần khác nhau của cơ sở dữ liệu phân tán.
2.6 Dễ dàng mở rộng hệ thống
Trong môi trường phân tán, việc mở rộng kích thước dữ liệu trở nên dễ dàng và hiếm khi cần sửa đổi hệ thống lớn Mở rộng thường được thực hiện bằng cách tăng khả năng lưu trữ và xử lý của mạng Tuy nhiên, trong Hệ CSDL, việc gia tăng năng lực lưu trữ và xử lý không thể diễn ra một cách tuyến tính do chi phí phân tán, bao gồm chi phí tính toán và thời gian truyền tải dữ liệu Dù vậy, khả năng mở rộng của CSDL phân tán vẫn vượt trội hơn so với CSDL tập trung và mang lại tính kinh tế cao hơn.
Kiến trúc cơ bản của cơ sở dữ liệu phân tán
Sơ đồ này xác định dữ liệu sẽ được lưu trữ trong cơ sở dữ liệu phân tán, với khả năng định nghĩa chính xác như trong cơ sở dữ liệu không phân tán Mô hình quan hệ được sử dụng để xây dựng sơ đồ tổng thể, trong đó bao gồm định nghĩa của một tập hợp các quan hệ tổng thể.
Hình 1: Sơ đồ tổng thể
Mỗi quan hệ tổng thể có thể được chia thành các đoạn không giao nhau, gọi là fragments Việc phân chia này có thể thực hiện theo nhiều cách khác nhau Sơ đồ tổng thể mô tả mối quan hệ giữa các quan hệ tổng thể và các đoạn được định nghĩa trong sơ đồ phân đoạn, với ánh xạ một-nhiều Mặc dù có thể có nhiều đoạn liên kết với một quan hệ tổng thể, nhưng mỗi đoạn chỉ liên kết với tối đa một quan hệ tổng thể Các đoạn được chỉ định bằng tên của quan hệ tổng thể kết hợp với tên chỉ mục đoạn.
Các đoạn trong một quan hệ tổng thể được xác định tại nhiều vị trí vật lý trên mạng, và sơ đồ định vị xác định vị trí của từng đoạn tại các trạm khác nhau Kiểu ánh xạ trong sơ đồ này quyết định tính dư thừa của cơ sở dữ liệu phân tán Tất cả các đoạn liên kết với cùng một quan hệ tổng thể R và cùng một trạm j tạo thành ảnh vật lý của R tại trạm đó Do đó, có thể thiết lập một ánh xạ một-một giữa ảnh vật lý và cặp (quan hệ tổng thể, trạm) Các ảnh vật lý được xác định thông qua tên của quan hệ tổng thể và chỉ mục trạm tương ứng.
Sơ đồ ánh xạ địa phương 1
HQTCSDL (DBMS) tại vị trí 1
CSDL địa phương tại vị trí 1
Sơ đồ ánh xạ địa phương 2
HQTCSDL (DBMS) tại vị trí 2
CSDL địa phương tại vị trí 2
Ví dụ: ký hiệu Ri chỉ tới đoạn thứ i của quan hệ tổng thể R (hình 2)
Ký hiệu Rj là ảnh vật lý của quan hệ tổng thể R tại trạm j (hình 2)
Hình 2: Sơ đồ định vị
3.4 Sơ đồ ánh xạ địa phương
Mô hình quản trị dữ liệu của các hệ thống quản trị cơ sở dữ liệu (HQT CSDL) địa phương hoàn toàn độc lập với lược đồ ở mức cao hơn Do đó, ở mức thấp hơn, các mô hình vật lý cần phải được ánh xạ thành các đối tượng mà các HQT CSDL địa phương quản lý và thực hiện.
Sơ đồ ánh xạ địa phương liên quan đến việc ánh xạ các ảnh vật lý tới các đối tượng mà các hệ quản trị cơ sở dữ liệu (CSDL) địa phương thao tác tại các trạm Ánh xạ này phụ thuộc vào từng hệ quản trị CSDL địa phương cụ thể Do đó, trong một hệ thống không đồng nhất, cần thiết phải có các kiểu ánh xạ địa phương khác nhau tại các trạm khác nhau.
Các mô hình xử lý phân tán
Quá trình thiết kế cơ sở dữ liệu (CSDL) bắt đầu bằng việc phân tích thông tin từ thế giới thực mà CSDL cần lưu trữ, cùng với các mối quan hệ giữa các thành phần thông tin này Cấu trúc của CSDL thường được mô tả bằng một ngôn ngữ đặc biệt hoặc một tập hợp ký hiệu thích hợp để thể hiện thiết kế CSDL.
4.1 Mô hình xử lý Master - Slave
Các hệ quản trị cơ sở dữ liệu Client/Server sở hữu kiến trúc hai lớp, bao gồm chức năng Server và Client, giúp đơn giản hóa việc quản lý sự phức tạp của các hệ thống CSDL hiện đại cũng như việc phân tán dữ liệu.
Server đảm nhiệm hầu hết các công việc quản lý dữ liệu, bao gồm xử lý và tối ưu hóa truy vấn, quản lý giao dịch và lưu trữ Trong khi đó, Client chỉ cần có ứng dụng và giao diện người dùng, cùng với một module hệ quản trị CSDL để quản lý dữ liệu và khóa giao dịch Sự trao đổi giữa Client và Server diễn ra thông qua các câu lệnh SQL, trong đó Client gửi truy vấn SQL đến Server, và Server thực hiện truy vấn rồi trả lại kết quả cho Client.
Kiến trúc Client/Server đơn giản bao gồm một Server phục vụ nhiều Client, được gọi là đa Client-đơn Server Quản lý dữ liệu trong mô hình này tương tự như trong hệ thống CSDL tập trung, với dữ liệu chỉ được lưu trữ trên Server và có phần mềm quản lý đi kèm Tuy nhiên, điểm khác biệt quan trọng so với hệ thống tập trung là cách thực thi giao dịch và quản lý bộ nhớ Cache.
Loại kiến trúc có nhiều Server trong hệ thống được gọi là đa Client- đa Server
Có hai chiến lược quản lý kết nối giữa Client và Server: một là Client tự quản lý kết nối của mình với Server, và hai là Client chỉ biết đến Server chủ và liên lạc với các Server khác thông qua Server chủ khi cần thiết Chiến lược đầu tiên đơn giản hóa cho các Server nhưng lại gia tăng trách nhiệm cho Client, tạo ra hệ thống máy khách tự phục vụ Ngược lại, chiến lược thứ hai tập trung vào việc quản lý dữ liệu tại Server, cung cấp tính trong suốt cho việc truy cập dữ liệu qua giao diện Server.
Hình 3: Kiến trúc khách/chủ
4.2 Các hệ phân tán ngang hàng
Trong các hệ thống ngang hàng, tổ chức dữ liệu và lưu trữ trên các máy khác nhau có thể khác nhau, đòi hỏi phải có một định nghĩa nội tại riêng cho mỗi vị trí, gọi là lược đồ nội tại cục bộ (LIS) Đồng thời, lược đồ khái niệm toàn cục mô tả cấu trúc logic của dữ liệu tại mọi vị trí.
Dữ liệu trong cơ sở dữ liệu phân tán thường được phân mảnh và nhân bản ở nhiều vị trí khác nhau, do đó cần mô tả tổ chức lưu trữ dữ liệu vật lý tại các vị trí này Để cải thiện kiến trúc cơ sở dữ liệu 3 mức, cần bổ sung thêm tầng thứ cấp là lược đồ khái niệm cục bộ (LCS) Lược đồ khái niệm toàn cục (GCS) sẽ là hợp của các lược đồ khái niệm cục bộ, giúp quản lý dữ liệu một cách hiệu quả hơn.
Khung nhìn dữ liệu của người sử dụng, hay còn gọi là lược đồ ngoài (External Schema), phản ánh cách mà người dùng khác nhau tiếp cận và hiểu dữ liệu Kiến trúc của hệ cơ sở dữ liệu phân tán được tổ chức thành ba mức, trong đó có nhiều khung nhìn dữ liệu tại lược đồ ngoài Tuy nhiên, chỉ tồn tại một mô hình khái niệm toàn cục duy nhất, kèm theo nhiều mô hình khái niệm cục bộ tương ứng với lược đồ tại từng vị trí cụ thể.
Hình 4: Các hệ phân tán ngang hàng
Trong môi trường tính toán đa tầng, mô hình tính toán phân cấp được hình thành nhờ khả năng xử lý hợp tác và xử lý phân tán Trong mô hình này, tài nguyên tính toán được phân bổ theo chiều dọc, tối ưu hóa hiệu suất và khả năng sử dụng tài nguyên.
Tầng thứ 2 thường có một máy chủ LAN mạnh, đóng vai trò trung gian, vừa là client của một máy tính lớn, vừa là server cho các máy trạm làm việc và máy tính cá nhân ở tầng thứ 3.
Hình 5: Môi trường đa tầng
Có ba nhóm mô hình dữ liệu đã được đề xuất, bao gồm: mô hình logic dựa trên đối tượng, mô hình logic dựa trên bản ghi và mô hình vật lý.
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
Mục tiêu chung của bài toán toán truy vấn trong CSDLPT
Mục tiêu của bài toán truy vấn trong môi trường cơ sở dữ liệu (CSDL) phân tán là chuyển đổi câu truy vấn cấp cao, mà người dùng vẫn coi như CSDL tập trung, thành một chiến lược thực hiện hiệu quả Chiến lược này được diễn tả bằng ngôn ngữ cấp thấp trên các CSDL cục bộ Trong đó, ngôn ngữ cấp cao được hiểu là phép tính quan hệ, trong khi ngôn ngữ cấp thấp là một dạng mở rộng của đại số quan hệ kèm theo các thao tác truyền dữ liệu.
Xét các quan hệ: EMP (ENO, ENAME, TITLE)
ASG (ENO, PNO, RESP, DUR)
Và câu truy vấn: “Cho biết các nhân viên hiện đang quản lý một dự án”
Câu SQL là: SELECT ENAME
WHERE EMP.ENO = ASG.ENO
Hai biểu thức tương đương đại số quan hệ do biến đổi từ câu truy vấn trên là:
Với mục tiêu giảm thiểu việc sử dụng tài nguyên nên câu truy vấn thứ hai sẽ được dùng
Hệ xử lý truy vấn tập trung có nhiệm vụ chọn ra câu truy vấn đại số quan hệ tối ưu nhất từ các câu truy vấn tương đương đã cho Bài toán này trở nên phức tạp khi số lượng quan hệ tăng cao, do đó, việc tìm kiếm một giải pháp tối ưu là yêu cầu cần thiết.
Trong quan hệ phân tán, đại số quan hệ không đủ để diễn tả các chiến lược thực thi, cần bổ sung các phép tính toán trao đổi dữ liệu giữa các vị trí Bên cạnh việc chọn thứ tự cho các phép toán đại số quan hệ, việc lựa chọn vị trí tốt nhất để xử lý dữ liệu và cách biến đổi dữ liệu cũng rất quan trọng Những yêu cầu này làm tăng không gian lời gian, khiến cho việc xử lý dữ liệu phân tán trở nên khó khăn hơn.
Giới thiệu về xử lý truy vấn
Chức năng chính của bộ xử lý câu truy vấn là chuyển đổi câu truy vấn của người dùng từ mức cao xuống mức thấp hơn, đảm bảo tính chính xác và hiệu quả Mỗi phương pháp biến đổi đều ảnh hưởng đến việc sử dụng tài nguyên.
Trong một hệ thống phân tán với 23 nguyên máy tính khác nhau, việc tối ưu hóa tài nguyên là rất quan trọng Các phép đại số quan hệ không đủ để biểu diễn các chiến lược thực thi, vì vậy cần bổ sung thêm các phép toán truyền dữ liệu giữa các trạm Bộ xử lý câu truy vấn phân tán không chỉ cần chọn thứ tự thực hiện các phép toán đại số mà còn phải xác định các trạm tốt nhất để xử lý dữ liệu hiệu quả.
Các mục tiêu của xử lý câu truy vấn
Bộ xử lý truy vấn phân tích và chuyển đổi các câu truy vấn cấp cao, được thể hiện dưới dạng các phép toán quan hệ, thành những câu truy vấn tương đương ở cấp thấp hơn.
Hình 6: Mô tả bộ xử lý truy vấn
Các giai đoạn xử lý câu truy vấn:
Xử lý truy vấn bao gồm nhiều tầng quan trọng, bắt đầu từ phân rã truy vấn, tiếp theo là cục bộ hóa dữ liệu, sau đó là tối ưu hóa truy vấn toàn cục và cuối cùng là tối ưu hóa truy vấn cục bộ.
Hình 7: Mô tả các giai đoạn trong xử lý truy vấn
Các giai đoạn trong xử lý truy vấn CSDLPT
3.1 Phân rã câu truy vấn
Phân rã câu truy vấn là quá trình chuyển đổi câu truy vấn từ các phép tính quan hệ thành câu truy vấn đại số trên các quan hệ tổng thể, với cả hai câu truy vấn vào và ra đều không phụ thuộc vào tính phân tán của dữ liệu Quá trình này áp dụng cho cả quan hệ tập trung và phân tán, giả định rằng câu truy vấn vào là chính xác Sau khi hoàn thành phân rã, câu truy vấn ra sẽ đạt chuẩn và loại bỏ được các công việc dư thừa.
Giai đoạn này chia làm 4 bước [3] :
- Chuẩn hoá: Đưa câu truy vấn về một trong hai dạng chuẩn: dạng hội (˄) của những phép tuyển (˅) và dạng tuyển (˅) của những phép hội (˄)
- Phân tích: Bước phân tích câu truy vấn cho phép loại bỏ những câu truy vấn đã được chuẩn hóa nhưng sai kiểu hoặc không đúng ngữ pháp
Để tối ưu hóa câu truy vấn, cần loại bỏ các tân từ dư thừa, điều này giúp giảm thiểu công việc không cần thiết Việc đơn giản hóa điều kiện bằng cách áp dụng các luật lũy đẳng đã biết sẽ giúp cải thiện hiệu quả truy vấn.
Bước cuối cùng trong quá trình phân rã truy vấn là chuyển đổi câu truy vấn thành đại số quan hệ Quy trình này có thể được chia thành hai bước nhỏ hơn để thực hiện hiệu quả hơn.
Biến đổi câu truy vấn phép tính quan hệ sang đại số quan hệ giúp tối ưu hóa quá trình truy vấn dữ liệu Đồng thời, việc cấu trúc lại câu truy vấn đại số quan hệ cũng góp phần cải thiện hiệu năng, đảm bảo hệ thống hoạt động hiệu quả hơn.
Tầng cục bộ dữ liệu chuyển đổi câu truy vấn đại số trên các quan hệ tổng thể thành câu truy vấn đại số tương ứng trên các phân đoạn vật lý Việc định vị dựa vào thông tin lưu trữ trên lược đồ phân mảnh, với chương trình đại số quan hệ tái tạo quan hệ tổng thể từ các phân đoạn, được gọi là chương trình định vị Trong phần này, chúng ta sẽ không xem xét đến sự nhân bản của các đoạn dữ liệu, mặc dù điều này có thể cải thiện hiệu năng, và sự nhân bản sẽ được đề cập trong phần sau.
Một giải pháp tự nhiên để xác định câu truy vấn phân tán là thay thế mỗi quan hệ tổng thể bằng chương trình định vị tương ứng Phương pháp này tương tự như việc thay thế các nút lá trong cây đại số quan hệ của câu truy vấn bằng các cây con tương ứng với chương trình định vị Tuy nhiên, cách tiếp cận này thường không hiệu quả vì câu truy vấn ban đầu có thể được cấu trúc lại và đơn giản hóa Trong phần này, chúng tôi sẽ trình bày các kỹ thuật rút gọn cho từng kiểu phân đoạn nhằm tạo ra các câu truy vấn tối ưu và đơn giản hơn.
- Rút gọn cho việc phân đoạn ngang nguyên thủy:
- Rút gọn cho phân đoạn dọc
- Rút gọn phân đoạn gián tiếp
- Rút gọn phân đoạn hỗn hợp
3.3 Tối ưu hóa toàn cục (tối ưu hóa truy vấn phân tán)
Bộ tối ưu bao gồm ba thành phần chính: không gian tìm kiếm, mô hình chi phí và chiến lược tìm kiếm.
Hình 8: Mô hình tối ưu hóa truy vấn
Không gian tìm kiếm bao gồm các chiến lược thực thi truy vấn đa dạng Để làm nổi bật đặc điểm của bộ tối ưu hóa, chúng ta cần chú ý đến các cây kết nối, là các cây toán tử thực hiện phép nối hoặc tích Descartes.
Với N quan hệ, có O(N!) cây kết nối tương đương, dẫn đến việc đánh giá trong không gian tìm kiếm lớn có thể tốn nhiều thời gian, thậm chí hơn cả thời gian thực thi thực tế Tuy nhiên, trong cây tuyến tính, kích thước không gian tìm kiếm được rút gọn xuống còn O(2N).
Chiến lược tìm kiếm phổ biến là quy hoạch động, đặc trưng bởi tính đơn định Chiến lược này xây dựng các phương án thực thi từ các quan hệ cơ sở, mở rộng thêm nhiều quan hệ qua từng bước cho đến khi đạt được các phương án khả thi Quy hoạch động tạo ra phương án khả thi theo chiều rộng, trong khi chiến lược tham lam phát triển cây theo chiều sâu Các chiến lược vét cạn chỉ đảm bảo tìm ra các phương án khả thi với chi phí chấp nhận được khi số lượng quan hệ trong câu truy vấn không lớn.
Chi phí cho một chiến lược thực hiện phân tán có thể được thể hiện qua tổng chi phí hoặc thời gian trả lời Tổng chi phí là tổng hợp tất cả các thành phần chi phí, trong khi thời gian trả lời tính từ khi bắt đầu đến khi kết thúc câu truy vấn.
Công thức tính tổng chi phí:
Trong công thức này, chi phí đầu tiên bao gồm chi phí địa phương, trong khi hai thành phần tiếp theo đại diện cho chi phí truyền thông Chi phí truyền thông để chuyển #bytes dữ liệu giữa các trạm được giả định là một hàm tuyến tính của biến #bytes.
Khi tối ưu hóa hàm mục tiêu để trả lời các truy vấn, cần xem xét cả xử lý địa phương và truyền thông song song Công thức tổng quát để tính thời gian trả lời (response time) được áp dụng trong quá trình này.
Trong quá trình thực thi câu truy vấn, seq_#x (với x có thể là các lệnh CPU, I/O, thông báo, hoặc các bytes) là số lớn nhất của x cần được thực hiện theo thứ tự.
Các đặc trưng về xử lý truy vấn trong CSDLPT
Việc ước lượng và đánh giá các phương thức xử lý truy vấn trong CSDLTT và CSDLPT là rất khó khăn do sự khác biệt về nhiều mặt Một số đặc trưng của xử lý truy vấn trong CSDLPT được thiết lập như nền tảng cơ bản để so sánh với CSDLTT Trong số các đặc trưng này, một số giống với xử lý truy vấn trong CSDLTT, trong khi một số khác chỉ có ở CSDLPT.
Ngôn ngữ xây dựng truy vấn cơ sở dữ liệu thường được áp dụng trong bối cảnh cơ sở dữ liệu quan hệ, cho phép phân rã thành nhiều dạng câu truy vấn đại số khác nhau Trong cơ sở dữ liệu phân tán, các trạm có thể sử dụng các kiến trúc hệ quản trị khác nhau, dẫn đến sự tồn tại của nhiều phương thức ánh xạ giữa ngôn ngữ truy vấn đầu vào và ngôn ngữ truy vấn thực hiện ở đầu ra.
Sự khác biệt giữa các ngôn ngữ thể hiện tạo ra nhiều khó khăn trong việc so sánh các phương thức tối ưu hóa truy vấn trong CSDLPT
4.2 Các dạng tối ưu hóa (types of optimization)
Tối ưu hóa là quá trình tìm kiếm điểm tốt nhất trong không gian giải pháp Phương pháp tìm kiếm toàn bộ, mặc dù hiệu quả, gặp khó khăn khi không gian tìm kiếm lớn Để giảm thiểu nhược điểm này, các phương pháp như thuật toán lặp cải tiến và simulated annealing được đề xuất Những phương pháp này giúp tìm giải pháp tốt với chi phí tìm kiếm thấp hơn về bộ nhớ và thời gian, mặc dù chưa chắc chắn đạt được giải pháp tối ưu.
Một phương pháp tiếp cận hiệu quả là sử dụng các giải thuật gần đúng (heuristic), giúp giới hạn không gian tìm kiếm bằng cách chỉ xem xét những không gian khả thi cao Trong cơ sở dữ liệu phân tán (CSDLPT), phương pháp này đặc biệt quan trọng vì nó cho phép thay thế phép toán kết nối bằng phép toán “bán kết nối” (semijoin), từ đó tối ưu hóa việc trao đổi dữ liệu.
4.3 Thời gian tối ưu hóa (optimization timing)
Tối ưu hóa truy vấn có thể diễn ra tại nhiều thời điểm khác nhau, bao gồm cả trước khi thực hiện truy vấn (tối ưu hóa tĩnh) và trong quá trình thực hiện truy vấn (tối ưu hóa động).
Tối ưu hóa tĩnh diễn ra trong giai đoạn biên dịch câu truy vấn, giúp giảm thời gian tối ưu hóa khi thực hiện truy vấn nhiều lần, tỷ lệ nghịch với số lần truy vấn Nếu kích thước không gian tìm kiếm chỉ được xác định khi thực hiện truy vấn, việc ước lượng sẽ dựa vào dữ liệu thống kê của CSDL, dẫn đến khả năng giải quyết bài toán chỉ đạt được tối ưu cục bộ.
Tối ưu hóa động được thực hiện khi xử lý câu truy vấn, giúp ước lượng trực tiếp các tham số cần thiết mà không cần dữ liệu thống kê tĩnh Phương pháp này hạn chế các lựa chọn không hiệu quả so với việc sử dụng dữ liệu tĩnh Tuy nhiên, nhược điểm lớn là việc tối ưu hóa liên tục cho các yêu cầu truy vấn, dẫn đến thời gian tối ưu hóa kéo dài, đặc biệt đối với các yêu cầu lớn và tốn kém.
Phương thức kết hợp (hybrid) tận dụng lợi thế của các tối ưu hóa để cải thiện hiệu suất truy vấn Thông thường, tối ưu hóa động được áp dụng khi có sự chênh lệch đáng kể giữa dữ liệu thống kê và dữ liệu thực tế trong cơ sở dữ liệu tại thời điểm thực hiện.
Cả tối ưu hóa tĩnh và tối ưu hóa động đều sử dụng thông tin thống kê từ cơ sở dữ liệu, phụ thuộc vào phương thức phân đoạn, tập hợp phân đoạn, kích thước đoạn và số lượng giá trị sao lưu cho các thuộc tính Để giảm thiểu lỗi, các lược đồ chi tiết về giá trị thuộc tính được áp dụng như một phần mở rộng của hệ thống quản lý chi phí và được cập nhật thường xuyên.
Trong tối ưu hóa tĩnh, sự biến động của dữ liệu thống kê có thể tác động đến quá trình tối ưu hóa lại các câu truy vấn.
4.5 Tối ưu hóa tập trung & tối ưu hóa phân tán (Decision sites)
Khi tối ưu hóa tĩnh được lựa chọn, việc xử lý tối ưu hóa có thể được thực hiện tập trung hoặc thực hiện phân tán
Trong mô hình tối ưu hóa tập trung, một đơn vị xử lý được chọn để thực hiện tối ưu hóa, nhưng tối ưu hóa nên được thực hiện trên nhiều thành phần trong hệ thống, gọi là tối ưu hóa phân tán Mặc dù tối ưu hóa tập trung dễ cài đặt, nó yêu cầu một hệ thống thông tin đầy đủ về toàn bộ CSDLPT, trong khi tối ưu hóa phân tán chỉ cần thông tin tại từng địa phương.
Mô hình kết hợp cho phép một số trạm tối ưu hóa các truy vấn chính, trong khi các trạm khác thực hiện các tối ưu hóa cục bộ Ví dụ, thuật toán System R* áp dụng phương pháp tiếp cận kết hợp để nâng cao hiệu quả xử lý.
4.6 Sử dụng kiến trúc mạng (Exploitation of the network topology)
Kiến trúc mạng (network topology) đóng vai trò quan trọng trong việc xử lý truy vấn phân tán, đặc biệt trong các mạng diện rộng Việc tối ưu hóa hàm giá trị có thể bị giới hạn trong một số khía cạnh nhất định.
Để tối ưu hóa chi phí truyền thông, yếu tố chi phối chính là việc giảm thiểu chi phí này Giả thiết này giúp đơn giản hóa quá trình tối ưu hóa truy vấn phân tán, trong đó bao gồm hai vấn đề riêng biệt: lựa chọn chiến lược thực thi toàn cục dựa trên việc trao đổi thông tin giữa các trạm và lựa chọn chiến lược thực thi cục bộ dựa trên thuật toán xử lý truy vấn cục bộ.
Trong mạng nội bộ (LAN), chi phí truyền thông thường được so sánh với chi phí vào ra (I/O cost) Mặc dù chi phí truyền thông có thể tăng, xu hướng xử lý song song vẫn tiếp tục được áp dụng.
Các kỹ thuật tối ưu hóa tập trung
Phần này sẽ trình bày hai kỹ thuật tối ưu hoá câu truy vấn đối với hệ tập trung
Sự biểu diễn này là điều kiện để tối ưu hóa câu truy vấn phân tán với ba lý do:
- Một câu truy vấn phân tán được biến đổi thành các câu truy vấn địa phương được xử lý theo cách tập trung
- Các kỹ thuật tối ưu hoá câu truy vấn phân tán thường là sự mở rộng các kỹ thuật đối với hệ tập trung
Tối ưu hóa thường liên quan đến việc giảm thiểu chi phí truyền thông, điều này dẫn đến việc tối ưu hóa các câu truy vấn phân tán trở nên phức tạp hơn.
INGRES áp dụng thuật toán tối ưu hóa câu truy vấn động để phân chia các truy vấn phép tính quan hệ thành những truy vấn nhỏ hơn Đầu tiên, một truy vấn đa biến được phân tích thành chuỗi các truy vấn con, mỗi truy vấn con chỉ có một biến duy nhất chung và dựa vào kết quả của truy vấn con trước đó Sau đó, từng truy vấn con sẽ được xử lý một cách riêng biệt.
Bộ xử lý truy vấn một biến (OVQP) tối ưu hóa việc truy cập tới một quan hệ đơn bằng cách lựa chọn phương pháp truy cập tốt nhất như chỉ số hoặc quét tuần tự Chẳng hạn, khi gặp tân từ dạng , việc sử dụng chỉ số trên A là lựa chọn hợp lý; trong khi đó, với tân từ dạng , quét tuần tự sẽ là phương pháp hiệu quả hơn.
Câu truy vấn q được phân tích thành hai câu truy vấn con qi-1và qi, ký hiệu qi-
1→qi, nghĩa là qi-1 được thực hiện trước và kết quả của nó được sử dụng bởi qi
Bộ xử lý câu truy vấn INGRES phân tích q thành n câu truy vấn q1→q2→q3
→qn Sự phân tích này sử dụng hai kỹ thuật cơ bản phân tách và thay thế
Hệ thống R thực hiện tối ưu hóa truy vấn tĩnh bằng cách nhận đầu vào là cây đại số quan hệ từ việc phân tích truy vấn SQL Đầu ra của quá trình này là sơ đồ thực hiện cây đại số quan hệ đã được tối ưu Thuật toán tối ưu hóa bao gồm hai bước chính.
- Dự đoán phương pháp truy nhập tới mỗi quan hệ đơn tốt nhất dựa trên một giả thiết chọn
Đối với mỗi quan hệ R, việc đánh giá thứ tự kết nối tối ưu sẽ được thực hiện bằng cách sử dụng phương pháp truy nhập quan hệ - đơn tốt nhất để truy cập R trước tiên.
Có hai phương pháp để xét các phép kết nối trong cơ sở dữ liệu Khi kết nối hai quan hệ, quan hệ ngoài chứa các bộ đọc trước, trong khi quan hệ trong chứa các bộ được tìm thấy dựa trên giá trị từ quan hệ ngoài Một quyết định quan trọng trong mỗi phương pháp là xác định hướng truy cập tới quan hệ trong với chi phí thấp nhất.
Phương pháp 1, được gọi là các vòng lặp lồng nhau, thực hiện việc tích hai quan hệ Mỗi bộ của quan hệ ngoài sẽ có các bộ của quan hệ trong thoả mãn giả thiết kết nối.
Để tạo ra quan hệ kết quả, cần gọi ra 31 lần Nếu không đánh chỉ số, chi phí của thuật toán này sẽ là n1 nhân n2, với các quan hệ được lưu trữ theo thứ tự trên n1 và n2 bộ bản ghi.
Phương pháp kết nối trộn là kỹ thuật kết nối hai quan hệ đã sắp xếp dựa trên thuộc tính kết nối Khi sử dụng kết nối bằng, chi phí kết nối giữa hai quan hệ n1 và n2 là n1 + n2, do đó phương pháp này được ưu tiên khi có kết nối bằng và các quan hệ đã được sắp xếp Nếu chỉ có một hoặc không có quan hệ nào được sắp xếp, cần so sánh chi phí của vòng lặp lồng nhau với chi phí của phương pháp trộn cộng với chi phí sắp xếp, trong đó chi phí sắp xếp n bản ghi là n log2 n.