Mở đầu Trong chương này sẽ giới thiệu sự cấp thiết của đề tài nghiên cứu. Đồng thời nội dung chương cũng cho thấy được mục đích, đối tượng và phạm vi giới 4 hạn nghiên cứu của đề tài. Các ý nghĩa khoa học và ý nghĩa thực tiễn của đề tài nghiên cứu cũng được nêu rõ. Cuối chương là phần trình bày tóm tắt bố cục các phần của luận văn để thể hiện toàn cảnh của luận văn.
o Chương 2: Tổng quan Các khái niệm liên quan đến tối ưu hóa truy vấn mang lại cái nhìn tổng quan cho đề tài sẽ được trình bày trong phần này. Tác giả hệ thống một số công trình nghiên cứu đã có, nêu bật quá trình xử lý truy vấn và các thách thức cần giải quyết của hệ cơ sở dữ liệu phân tán. Đồng thời chương này cũng sẽ trình bày hướng nghiên cứu giải quyết của đề tài. o Chương 3: Các thuật toán tối ưu hóa truy vấn Nội dung chương sẽ tập trung vào phần mô tả quá trình hoạt động và các bước thực hiện của các chương trình thuật toán: Dynamic Programming, Iterative Dynamic Programming, DPccp, IDP1ccp.
Phân tích những ưu khuyết điểm của các thuật toán và cung cấp các ví dụ minh họa góp phần làm rõ quá trình thực hiện của các thuật toán. o Chương 4: Thực nghiệm và đánh giá Đây là chương mô tả các bước chuẩn bị trước khi làm thực nghiệm, cấu trúc các tập tin danh mục và tập tin truy vấn. Quá trình các giai đoạn thực nghiệm các thuật toán trên các dạng truy vấn khác nhau. Phần cuối của chương ghi nhận kết quả thực nghiệm, đánh giá và so sánh kết quả đạt được thông qua các biểu đồ minh họa.
o Chương 5: Kết luận Sau quá trình tìm hiểu và nghiên cứu, những kết quả đạt được của đề tài sẽ được tổng kết lại và đưa ra kết luận cho đề tài. Ngoài ra, trong chương này cũng sẽ nói rõ những điểm giới hạn của luận văn. Sau phần trình bày những điểm giới hạn này, một số hướng nghiên cứu tiếp theo cũng được gợi ý, góp phần mở rộng hướng nghiên cứu của đề tài trong tương lai. 5 CHƯƠNG 2: TỔNG QUAN 2.1 Tổng quan tối ưu hóa truy vấn Tối ưu hóa truy vấn được coi là thành phần quan trọng nhất của một hệ thống quản lý cơ sở dữ liệu.
Sau khi hệ thống tiếp nhận truy vấn, bộ tối ưu truy vấn của hệ thống có trách nhiệm phân tích truy vấn của người sử dụng, xây dựng các kế hoạch thực thi tương đương của truy vấn, ước tính chi phí và chọn lựa ra kế hoạch thực hiện truy vấn với chi phí tối ưu nhất. Kế hoạch thực thi truy vấn tối ưu sẽ được bộ tối ưu chuyển đến bộ thực thi để thực hiện truy vấn. Mỗi kế hoạch thực thi truy vấn, mặc dù đều dẫn đến một kết quả giống nhau nhưng chi phí thực hiện của mỗi kế hoạch lại khác nhau đáng kể. Khi hệ thống cơ sở dữ liệu tiếp nhận truy vấn, với mỗi câu truy vấn tiếp nhận, tập hợp các kế hoạch thực thi có thể xảy ra để xử lý truy vấn là rất lớn.
Tập hợp các kế hoạch thực thi này gọi là không gian tìm kiếm kế hoạch thực thi. Không gian tìm kiếm kế hoạch thực thi thường là rất lớn cho nên việc tìm kiếm kế hoạch tốt nhất gần như là không thể. Do đó, điều quan trọng của việc tối ưu hoá truy vấn không phải là tìm ra được kế hoạch thực thi tốt nhất mà đúng hơn là giúp cho hệ thống tìm ra một kế hoạch thực thi tối ưu, tránh sử dụng phải kế hoạch thực thi không tốt. Một vấn đề tiếp theo của quá trình tối ưu hóa truy vấn phải đối mặt đó là thứ tự xử lý các truy vấn của người dùng.
Thứ tự kết hợp các quan hệ cũng là một vấn đề cốt yếu mà bộ tối ưu phải giải quyết để tạo ra các kế hoạch tối ưu. Trong các hệ phân tán, đối với truy vấn trên dữ liệu không lớn, các hệ quản trị cơ sở dữ liệu thường xử lý bằng các thuật toán hiện có như thuật toán tối ưu hóa quy hoạch động (Dynamic Programming) cổ điển. Tuy nhiên, đối với các truy vấn phức tạp (có số lượng quan hệ nhiều hơn hoặc các truy vấn được thực thi phân bố trên nhiều địa điểm khác nhau), vấn đề tối ưu hóa sẽ trở nên khó khăn hơn và các thuật toán tối ưu hóa tập trung cổ điển sẽ rất khó khăn khi xử lý sự phức tạp này. 6 Sau khi đã xác định thứ tự thực hiện truy vấn theo các quan hệ trên các địa điểm khác nhau, bộ tối ưu truy vấn phải dựa trên một mô hình chi phí để quyết định lựa chọn kế hoạch thực thi nào là tối ưu nhất.
Mô hình chi phí trong hệ tập trung khác với mô hình chi phí trong hệ phân tán vì hệ tâp trung không quan tâm đến các phép toán có thể thực thi đồng thời trên nhiều địa điểm. Việc tìm ra một mô hình chi phí cho phép tính toán chi phí các phép toán có thể tiến hành song song trong hệ phân tán là một điều hết sức cần thiết. Luận văn sẽ tập trung nghiên cứu các vấn đề liên quan đến quá trình tối ưu hóa truy vấn bao gồm các mục tiêu chính như không gian tìm kiếm kế hoạch thực thi truy vấn, thứ tự kết hợp các quan hệ trong truy vấn, mô hình chi phí và các thuật toán tối ưu hóa truy vấn trong hệ tập trung và hệ phân tán.2 Các nghiên cứu liên quan Trong quá trình tối ưu hóa truy vấn, một trong những vấn đề quan trọng cần tối ưu là phải làm giảm kích thước không gian tìm kiếm các kế hoạch thực thi tương đương của truy vấn. Từ đó làm giảm thời gian liệt kê và lựa chọn kế hoạch thực thi tối ưu đối với truy vấn đầu vào.
Đã có rất nhiều công trình nghiên cứu và các thuật toán liên quan để giải quyết vấn đề này. Các thuật toán tối ưu hóa truy vấn (trên hệ tập trung) thường được xếp vào một trong ba loại thuật toán liệt kê sau đây: liệt kê toàn diện, liệt kê phỏng đoán kinh nghiệm và liệt kê ngẫu nhiên. Thuật toán tìm kiếm toàn diện Đây là thuật toán có thời gian chạy xấu nhất theo hàm mũ và độ phức tạp không gian tìm kiếm theo cấp số nhân. Khi không gian tìm kiếm của truy vấn lớn, thuật toán có thể dẫn đến tình trạng tràn bộ nhớ và không thể tối ưu hóa truy vấn, bởi vì chi phí thực hiện việc phân tích tìm kiếm quá lớn.
Các thuật toán tìm kiếm toàn diện thường liệt kê trên toàn bộ không gian tìm kiếm nên các thuật toán sẽ luôn luôn tìm thấy những kế hoạch tối ưu nhất định. Tuy nhiên, rất khó để áp dụng phương pháp vét cạn này để tìm kiếm kế hoạch tốt nhất đối với các truy vấn lớn có nhiều quan hệ [10]. 7 Thuật toán tiêu biểu cho thuật toán tìm kiếm toàn diện là thuật toán quy hoạch động (Dynamic Programming). Thuật toán phỏng đoán Thuật toán phỏng đoán được đề xuất với mục đích giải quyết các vấn đề thời gian chạy theo cấp số nhân của các thuật toán liệt kê toàn diện.
Các thuật toán phỏng đoán dựa theo kinh nghiệm hoặc các quy tắc cụ thể để điều hướng tìm kiếm vào tập hợp con của toàn bộ không gian tìm kiếm. Các thuật toán thuộc loại phỏng đoán tiêu biểu là thuật toán độ lựa chọn tối thiểu (Minimum Selectivity), phỏng đoán tham lam (Greedy heuristics) [11] và quy hoạch động lặp (IDP) biến thể [10]. Nguyên tắc chung khi sử dụng công nghệ phỏng đoán hầu hết đều là tìm kiếm kế hoạch tốt dựa trên kết quả của các tập hợp con trung gian nhỏ. Tuy nhiên, các thuật toán phỏng đoán vẫn có trường hợp chạy thời gian xấu và không gian hoạt động phức tạp.
Thuật toán ngẫu nhiên Thuật toán ngẫu nhiên xem xét không gian tìm kiếm là một tập hợp các phần tử, mỗi phần tử trong tập hợp đó tương ứng với một kế hoạch thực thi duy nhất. Một số thuật toán ngẫu nhiên tiêu biểu như Cải thiện lặp (Iterative Improvement-II) [24], mô phỏng luyện kim (Simulated Annealing-SA) [24], tối ưu hóa 2-pha (2PO) [27] và thuật toán di truyền [28]. Các thuật toán ngẫu nhiên thường chọn ngẫu nhiên một phần tử khởi đầu trong không gian và di chuyển đến các phẩn tử kế cận cũng được chọn ngẫu nhiên. Thuật toán ghi nhận lại tập hợp các phần tử cùng với chi phí di chuyển.
Thuật toán lặp lại quá trình tìm kiếm với một phần tử khởi đầu mới. Sau một thời gian kiểm thử và so sánh, kế hoạch với chi phí thấp nhất sẽ được trả về. Một số phương pháp khác đã được đề xuất như kỹ thuật viết lại truy vấn [25] và kỹ thuật đơn giản hóa truy vấn [26] sử dụng đồ thị truy vấn được giới hạn để nỗ lực làm giảm sự phức tạp của việc tối ưu hóa.3 Quá trình xử lý truy vấn hệ phân tán 2.1 Danh mục hệ thống Trong quá trình xử lý truy vấn, khi muốn dự đoán chi phí của các kế hoạch thực thi truy vấn, hệ quản trị cơ sở dữ liệu cần phải có các thông tin tham khảo như số lượng các quan hệ, số bộ dữ liệu trong một quan hệ, số lượng trang dữ liệu mà quan hệ đó đang chiếm giữ… Để có được các thông tin này, hệ quản trị cơ sở dữ liệu phải sử dụng thông tin được lưu trữ trong danh mục hệ thống. Đối với hệ thống cơ sở dữ liệu tập trung, danh mục được sử dụng để lưu trữ chủ yếu là lược đồ (schema), bao gồm thông tin về các quan hệ, các chỉ mục (indexes) và khung nhìn (view).
Thông tin của các quan hệ bao gồm tên quan hệ, tên thuộc tính, kiểu dữ liệu và các ràng buộc toàn vẹn cũng được lưu trữ trong danh mục. Ngoài ra, các số liệu thống kê khác cũng được lưu trữ trong danh mục như số lượng các khóa và lực lượng quan hệ. Các thống kê này là cơ sở hỗ trợ cho bộ tối ưu truy vấn trong việc ước tính kích thước của kết quả trung gian của kế hoạch thực hiện, nghĩa là cho phép bộ tối ưu xác định ước tính chi phí của kế hoạch. Thông tin về tình trạng hệ thống hiện tại cũng được lưu trữ sẵn sàng trong danh mục, bao gồm số lượng các trang đệm trong vùng đệm dữ liệu và kích thước trang hệ thống [3].
Trong hệ quản trị cơ sở dữ liệu phân tán, danh mục hệ thống lưu trữ thêm các thông tin bổ sung bao gồm vị trí của các quan hệ và vị trí bản sao của các quan hệ.
