Báo Cáo Các thuật toán tối ưu hóa truy vấn trong môi trường phân tán

LỜI NÓI ĐẦU


Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực được quan tâm nhiều trong công nghệ thông tin. Ra đời từ những năm 60 đến nay, đã xuất hiện nhiều thế hệ quản trị CSDL, và cũng đã có nhiều ứng dụng trong khoa học kỹ thuật cũng như trong các ngành kinh tế khác.
Việc nghiên cứu CSDL đã và đang phát triển ngày càng phong phú, đa dạng. Từ những năm 70, mô hình dữ liệu quan hệ do E.F. Codd đưa ra đã tạo một cơ sở vững chắc cho các vấn đề nghiên cứu về CSDL. Với ưu điểm về tính cấu trúc, và khả năng hình thức hóa phong phú, CSDL quan hệ dễ dàng mô phỏng các hệ thống thông tin đa dạng trong thực tiễn, làm tăng khả năng xử lý, quản trị, khai thác dữ liệu, thông tin. Trên thực tế nhiều hệ quản trị CSDL thương mại, xây dựng trên mô hình quan hệ, đã và đang được lưu hành, sử dụng rộng rãi trên thị trường nhưdata:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=" class="mceSmilieSprite mceSmilie8" alt="" title="Big Grin ">BASE, ORACLE, MS SQL
Cho đến nay đã có hàng loạt các vấn đề về CSDL được nghiên cứu, giải quyết. Với mục đích tìm hiểu để nâng cao khả năng ứng dụng của của các hệ CSDL, bài thu hoạch này tập trung vào việc nghiên cứu vấn đề “tối ưu hóa câu truy vấn trong CSDL phân tán”. CSDL phân tán nói riêng và các hệ phân tán nói chung là một lĩnh vực nghiên cứu không mới, nhưng gần đây cùng với sự phát triển nhanh chóng và mạnh mẽ của công nghệ truyền thông, mạng Internet và đặc biệt là xu thế phát triển của thương mại điện tử, thì CSDL phân tán đã trở thành một lãnh vực thu hút nhiều sự quan tâm của các nhà nghiên cứu cũng như các nhà sản xuất phần mềm.
Như ta đã biết, thành công ngày càng tăng của công nghệ CSDL quan hệ trong việc xử lý dữ liệu một phần là do tính dễ dùng khả năng khai thác, tìm kiếm dữ liệu của các ngôn ngữ phi thủ tục (như SQL), và chính nó đã cải thiện đáng kể công việc phát triển ứng dụng và khả năng sáng tạo của người dùng. Các ngôn ngữ phi thủ tục của CSDL quan hệ đã cho phép diễn tả câu truy vấn phức tạp một cách chính xác và đơn giản. Đặc biệt là để có được câu trả lời cho một câu truy vấn thì người sử dụng không cần phải xác định chính xác trình tự tiến hành các thao tác/phép toán trong một câu truy vấn. Trình tự này được xử lý bởi Bộ xử lý truy vấn (query processor) của hệ quản trị CSDL, và đó là bài toán xử lý truy vấn hay tối ưu hóa truy vấn.
Tối ưu hóa truy vấn là việc xác định một chiến lượcthực hiện truy vấn sao cho có thể cực tiểu hóa được hàm chi phí. Đây là bài toán khó, đặc biệt là trong môi trường phân tán bài toán này thuộc lớp NP-Hard. Để tránh một chi phí tối ưu hóa quá lớn thì cách tiếp cận dùng các heuristic được sử dụng để có thể đạt được một chiến lược thực thi gần tối ưu. Các yếu tố cần được xem xét khi giải bài toán này là: sự phân tán dữ liệu, chi phí xử lý cục bộ, chi phí truyền
Các yếu tố quyết định đến việc cực tiểu hàm chi phí có thể có nhiều, nhưng những yếu tố quan trọng nhất là trình tự thực hiện tối ưu các phép nối, việc chọn các bản sao, các mảnh phải truy xuất, cũng như việc chọn các trạm thực hiện và việc sử dụng các giải thuật truy xuất dữ liệu cục bộ và phân tán.



[B]MỤC LỤC

LỜI NÓI ĐẦU 2
CHƯƠNG 1: CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ MỘT SỐ NGUYÊN LÝ CHUNG CỦA TỐI ƯU HOÁ TRUY VẤN 3[/B]
1. Các khái niệm về CSDL PT 3
2. Các mục tiêu của hệ quản trị CSDL PT 5
3. Kiến trúc hệ quản trị CSDL PT 5
4. Một số nguyên lý chung của tối ưu hóa truy vấn 8
4.1. Mục tiêu của bài toán xử lý truy vấn 8
4.2. Độ phức tạp của các phép toán đại số quan hệ. 11
4.3. Mô tả bộ xử lý truy vấn. 12
4.4 Phân rã truy vấn 15
4.4.1 Đưa về dạng chuẩn tắc (normalization) 15
4.4.2 Phân tích (analysis) 16
4.4.3. Loại bỏ dư thừa (simplification) 18
4.4.4. Viết lại truy vấn (restructuring) 18
[B]CHƯƠNG 2 : TỐI ƯU HÓA TRUY VẤN PHÂN TÁN 22[/B]
2.1. Tối ưu hóa truy vấn 22
2.1.1. Không gian tìm kiếm 23
2.1.2. Chiến lược tìm kiếm 24
2.1.3. Mô hình chi phí 25
2.2. Các thuật toán tối ưu hóa truy vấn trong môi trường phân tán 28
2.2.1. Các thuật toán dựa trên sắp xếp thứ tự nối (Ordering Joins) 28
2.2.1.1. Thuật toán INGRES phân tán 30
2.2.1.2. Thuật toán của System R* 31
2.3. Kết luận. 34
[B]TÀI LIỆU THAM KHẢO 36[/B]