Tối ƣu Hóa Cơ Sở Dữ Liệu: Giải Pháp và Đề Xuất

• Người hướng dẫn: PTS. Hồ Thụy Hữu
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Tối ƣu Hóa Cơ Sở Dữ Liệu: Giải Pháp và Đề Xuất
• Loại tài liệu: luận văn
• Năm xuất bản: 2006
• Địa điểm: Hà Nội

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN
• 1.1. Cơ sở dữ liệu quan hệ
• 1.2. Ngôn ngữ dữ liệu quan hệ
• 1.3. Hệ cơ sở dữ liệu phân tán
• 1.4. Các mục tiêu của hệ quả quản trị CSDL PT
• 1.5. Kiến trúc hệ quả quản trị CSDL PT
• 1.6. Phân mảnh, nhân bản và cập nhật dữ liệu
• 2. CHƯƠNG 2: MỘT SỐ NGUYÊN LÝ CHUNG CỦA TỐI ƯU HÓA TRUY VẤN
• 2.1. Mục tiêu của bài toán xử lý truy vấn
• 2.2. Độ phức tạp của các phép toán đại số quan hệ
• 2.3. Các thuật toán tối ưu hóa truy vấn trong môi trường phân tán
• 3. CHƯƠNG 3: MỘT SỐ ĐỀ XUẤT KHẢO VỀ XỬ LÝ PHÉP NỐI TRONG CƠ SỞ HỆ CSDL
• 3.1. Ứng dụng lý thuyết đồ thị trong tối ưu hóa truy xuất CSDL để thực hiện phép nối
• 3.2. Sử dụng chỉ mục để thực hiện phép nối
• 3.3. Thuật toán Heuristic để làm giảm lượng bộ nhớ đệm trên thiết bị
• 3.4. Lược đồ bộ nhớ đệm dựa trên cơ sở lưu trữ toàn bộ trang
• 3.5. Xác định kích thước bộ nhớ đệm để thực hiện một truy xuất trên mỗi trang
• TÀI LIỆU THAM KHẢO

I. Tổng Quan Cơ Sở Dữ Liệu Phân Tán Khái Niệm Ưu Điểm

Cơ sở dữ liệu (CSDL) là lĩnh vực quan trọng trong công nghệ thông tin. Từ những năm 60, nhiều thế hệ quản trị CSDL đã ra đời, ứng dụng rộng rãi trong khoa học kỹ thuật và kinh tế. Nghiên cứu CSDL ngày càng phong phú. Mô hình dữ liệu quan hệ của E.F. Codd từ những năm 70 tạo nền tảng vững chắc cho nghiên cứu CSDL. Ưu điểm về tính cấu trúc và khả năng hình thức hóa giúp CSDL quan hệ dễ dàng mô phỏng hệ thống thông tin đa dạng, tăng khả năng xử lý, quản trị và khai thác dữ liệu. Nhiều hệ quản trị CSDL thương mại xây dựng trên mô hình quan hệ như DBASE, ORACLE, MS SQL đã được sử dụng rộng rãi. Luận văn này tập trung vào 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à hệ phân tán nói chung là 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 của công nghệ truyền thông, mạng Internet và thương mại điện tử, CSDL phân tán đã thu hút sự quan tâm của các nhà nghiên cứu và sản xuất phần mềm.

1.1. Định Nghĩa Cơ Sở Dữ Liệu Quan Hệ Relational Database

CSDL quan hệ là CSDL được cấu trúc theo dạng bảng. Một quan hệ r được xác định trên tập thuộc tính. Mỗi hàng của quan hệ được gọi là một bộ (tuple). Quan hệ r là một tập hợp các n-bộ. Số thuộc tính của quan hệ gọi là bậc của quan hệ. Quan hệ r có thể bị thay đổi theo thời gian do việc thực hiện các phép toán cập nhật trên r (thêm vào, loại bỏ, sửa đổi các bộ). Một lược đồ quan hệ Γ là một cặp có thứ tự Γ = <Λ, F>, trong đó Λ là tập hữu hạn các thuộc tính của quan hệ, F là tập các điều kiện giữa các thuộc tính (F còn gọi là tập các ràng buộc toàn vẹn). Khi nói đến một lược đồ quan hệ, trong đó chỉ tập trung vào khía cạnh mô tả cấu trúc của một quan hệ mà không quan tâm đến bộ cụ thể, ta sẽ dùng ký hiệu: Γ(A1, A2, ..., An) với Γ là tên của quan hệ, A1, A2, ..., An là danh sách tên các thuộc tính.

1.2. Các Ưu Điểm Của Hệ Cơ Sở Dữ Liệu Phân Tán

Hệ CSDL phân tán có nhiều ưu điểm tiềm năng. Quản trị dữ liệu phân tán với nhiều mức trong suốt khác nhau. Hệ quản trị CSDL phân tán cung cấp khả năng trong suốt phân tán (distribution transparent) với ý nghĩa là che dấu các chi tiết như dữ liệu được lưu trữ ở đâu trong hệ thống. Hệ quản trị CSDL phân tán có thể cung cấp các khả năng trong suốt sau: Trong suốt phân tán, hay trong suốt mạng; Trong suốt nhân bản; Trong suốt phân mảnh. Tăng tính tin cậy và tính sẵn sàng. Cho phép dùng chung dữ liệu trong khi vẫn duy trì được biện pháp điều khiển cục bộ. Cải tiến hiệu năng.

II. Bài Toán Tối Ưu Hóa Truy Vấn Mục Tiêu Độ Phức Tạp

Thành cô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ược thực hiện truy vấn sao cho có thể tối thiể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.

2.1. Mục Tiêu Của Bài Toán Xử Lý Truy Vấn Query Processing

Mục tiêu của bài toán xử lý truy vấn là tìm ra một kế hoạch thực thi truy vấn hiệu quả nhất. Kế hoạch này bao gồm việc xác định thứ tự thực hiện các phép toán, lựa chọn các thuật toán phù hợp cho từng phép toán, và phân bổ tài nguyên một cách tối ưu. Chi phí thực thi truy vấn thường được đo bằng thời gian thực thi, số lượng I/O, hoặc lượng tài nguyên sử dụng.

2.2. Độ Phức Tạp Của Các Phép Toán Đại Số Quan Hệ

Các phép toán đại số quan hệ như chọn, chiếu, kết, hợp, trừ, tích Descartes có độ phức tạp khác nhau. Việc lựa chọn thứ tự thực hiện các phép toán này ảnh hưởng lớn đến hiệu năng của truy vấn. Ví dụ, phép kết thường có độ phức tạp cao hơn các phép toán khác, do đó việc tối ưu hóa phép kết là rất quan trọng.

2.3. Các Thuật Toán Tối Ưu Hóa Truy Vấn Trong Môi Trường Phân Tán

Trong môi trường phân tán, việc tối ưu hóa truy vấn trở nên phức tạp hơn do phải xem xét đến chi phí truyền thông giữa các site. Các thuật toán tối ưu hóa truy vấn trong môi trường phân tán thường tập trung vào việc giảm thiểu lượng dữ liệu truyền qua mạng, lựa chọn site thực hiện phép toán, và phân bổ công việc giữa các site.

III. Đề Xuất Giải Pháp Xử Lý Phép Nối Trong Hệ CSDL

Để 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 tối thiể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. Với những nét chính ở trên, nội dung của bản luận văn này trình bày các nguyên lý chung, các kỹ thuật, thuật toán liên quan đến vấn đề tối ưu hóa truy vấn và một số phương án đề xuất cho việc giải quyết bài toán tối ưu này.

3.1. Ứng Dụng Lý Thuyết Đồ Thị Trong Tối Ưu Hóa Truy Xuất CSDL

Lý thuyết đồ thị có thể được sử dụng để biểu diễn các mối quan hệ giữa các bảng trong CSDL. Bằng cách sử dụng các thuật toán đồ thị, ta có thể tìm ra thứ tự thực hiện các phép nối tối ưu, giảm thiểu chi phí truy xuất dữ liệu. Đồ thị nối (join graph) là một công cụ hữu ích để biểu diễn các phép nối trong một truy vấn.

3.2. Sử Dụng Chỉ Mục Để Thực Hiện Phép Nối Hiệu Quả

Chỉ mục (index) là một cấu trúc dữ liệu giúp tăng tốc độ tìm kiếm dữ liệu trong CSDL. Sử dụng chỉ mục để thực hiện phép nối có thể giảm đáng kể thời gian thực thi truy vấn. Có nhiều loại chỉ mục khác nhau, và việc lựa chọn loại chỉ mục phù hợp phụ thuộc vào đặc điểm của dữ liệu và truy vấn.

3.3. Các Heuristic Để Giảm Lượng Bộ Nhớ Đệm Cần Thiết

Bộ nhớ đệm (buffer) được sử dụng để lưu trữ dữ liệu tạm thời trong quá trình thực thi truy vấn. Giảm lượng bộ nhớ đệm cần thiết có thể cải thiện hiệu năng của hệ thống. Các heuristic có thể được sử dụng để ước lượng lượng bộ nhớ đệm cần thiết và tối ưu hóa việc sử dụng bộ nhớ đệm.

IV. Phương Án Tiếp Cận Xử Lý Nối Phân Tán Khác Ưu Nhược

Một số phương án tiếp cận xử lý nối phân tán khác bao gồm sử dụng thông tin phụ thuộc vị trí (placement dependency) để thực hiện nối. Các yếu tố quyết định đến việc tối thiể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. Với những nét chính ở trên, nội dung của bản luận văn này trình bày các nguyên lý chung, các kỹ thuật, thuật toán liên quan đến vấn đề tối ưu hóa truy vấn và một số phương án đề xuất cho việc giải quyết bài toán tối ưu này.

4.1. Sử Dụng Thông Tin Phụ Thuộc Vị Trí Để Thực Hiện Nối

Thông tin phụ thuộc vị trí (placement dependency) cho biết dữ liệu được lưu trữ ở đâu trong hệ thống phân tán. Sử dụng thông tin này có thể giúp tối ưu hóa việc truyền dữ liệu giữa các site, giảm chi phí thực thi truy vấn. Tuy nhiên, việc duy trì thông tin phụ thuộc vị trí có thể tốn kém.

4.2. Xử Lý Truy Vấn Trong Môi Trường CSDL Liên Kết Federated Database

CSDL liên kết (federated database) là một hệ thống tích hợp nhiều CSDL độc lập. Xử lý truy vấn trong môi trường CSDL liên kết đòi hỏi phải giải quyết các vấn đề về tương thích dữ liệu, bảo mật, và hiệu năng. Các kỹ thuật tối ưu hóa truy vấn trong CSDL liên kết thường tập trung vào việc giảm thiểu lượng dữ liệu truyền giữa các CSDL thành viên.