Luận văn ThS: Tối ưu hoá truy vấn trong hệ cơ sở dữ liệu phân tán

(7)
138 lượt xem
Share

Luận văn Tối ưu hoá truy vấn trong hệ cơ sở dữ liệu phân tán giới thiệu tổng quan vấn đề nghiên cứu; tìm hiểu các thuật toán tối ưu hóa truy vấ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; thực nghiệm và đánh giá kết quả.

Mục lục nội dung

Luận văn ThS: Tối ưu hoá truy vấn trong hệ cơ sở dữ liệu phân tán

1. Mở đầu

1.1 Lí do chọn đề tài

Ngày nay cùng với sự phát triển công nghệ Doanh nghiệp thông minh (Business Intelligence) và kho lưu trữ dữ liệu (Data Warehouse), số lượng dữ liệu cần phải xử lý trong cơ sở dữ liệu của các công ty là rất lớn. Các hệ thống kho dữ liệu lại cần phải được tích lũy dữ liệu trong rất nhiều năm cho nên số lượng dữ liệu càng lúc càng lớn hơn nữa. Bên cạnh yếu tố lưu trữ dữ liệu là yếu tố vị trí xử lý dữ liệu. Các công ty lớn thường có nhiều nhân viên làm việc ở các văn phòng đặt tại nhiều vị trí khác nhau. Chính vì vậy, nhu cầu lưu trữ dữ liệu phân tán là rất lớn. Tuy nhiên, khi lưu trữ dữ liệu trên hệ thống phân tán, quá trình tối ưu hóa dữ liệu trở nên phức tạp hơn rất nhiều so với hệ thống cơ sở dữ liệu tập trung.

1.2 Đối tượng phạm vi nghiên cứu

Đề tài được đầu tư nghiên cứu các kỹ thuật tối ưu cho các dạng truy vấn khác nhau trong hệ phân tán. Phạm vi nghiên cứu giới hạn chỉ xem xét các truy vấn trong đại số quan hệ liên quan đến sự kết hợp của các phép toán như là phép chọn, phép chiếu và phép kết. Luận văn tập trung vào các phần sau:

  • Trình bày quá trình xử lý trên hệ phân tán, vấn đề khó khăn trong việc đánh giá xử lý song song trong một kế hoạch thực thi.
  • Trình bày ưu khuyết điểm của ba thuật toán lựa chọn kế hoạch thực thi tối ưu: DP, IDP1, DPccp.
  • Kết hợp hai thuật toán IDP1 và DPccp để tạo ra thuật toán hiệu quả hơn là IDP1ccp.
  • Trình bày thực nghiệm áp dụng các thuật toán tối ưu trên các đồ thị truy vấn dạng chuỗi, dạng vòng, dạng sao, dạng chùm.

2. Nội dung

2.1 Tổng quan

Tổng quan tối ưu hóa truy vấn

Các nghiên cứu liên quan

Quá trình xử lý truy vấn hệ phân tán 

  • Danh mục hệ thống
  • Chi phí truyền tải mạng

Các thách thức của hệ phân tán

  • Kích thước không gian tìm kiếm
  • Chi phí thiết lập kế hoạch truy vấn

Hướng nghiên cứu của đề tài

2.2 Các thuật toán tối ưu hóa truy vấn

Thuật toán quy hoạch động

  • Mô tả thuật toán
  • Mở rộng trong môi trường phân tán
  • Chương trình thuật toán DP

Thuật toán quy hoạch động lặp

  • Mô tả thuật toán
  • Ví dụ thuật toán IDP1 kế hoạch tốt nhất tiêu chuẩn
  • Biến thể IDP cân bằng
  • Ví dụ thuật toán IDP1 kế hoạch tốt nhất cân bằng

Thuật toán quy hoạch động cặp đồ thị con liên thông bù

  • Các định nghĩa liên quan
  • Công thức tính #csg and #ccp
  • Mô tả thuật toán
  • Thuật toán liệt kê các tập con liên thông Enumerate-CSG
  • Ví dụ minh họa Enumerate-CSG
  • Thủ tục liệt kê các tập con bù Enumerate-CMP
  • Ví dụ minh họa Enumerate-CMP

Thuật toán kết hợp IDP1ccp

  • Chương trình thuật toán IDP1ccp 
  • Mô tả thuật toán
  • Ví dụ minh họa IDP1ccp

2.3 Thực nghiệm và đánh giá

Chuẩn bị các tập tin dữ liệu đầu vào 

  • Cấu trúc tập tin danh mục
  • Phát sinh truy vấn
  • Đồ thị kết hợp
  • Kế hoạch thực thi truy vấn

Các giai đoạn thực nghiệm

Kết quả thực nghiệm

Nhận xét và đánh giá kết quả

3. Kết luận

Sau quá trình tìm hiểu và nghiên cứu, luận văn đã đạt được một số điểm sau:

  • Góp phần tổng hợp lý thuyết và phân tích quá trình xử lý tối ưu hóa truy vấn trong hệ tập trung cũng như hệ phân tán để đưa ra một bức tranh tổng quát về quá trình tối ưu hóa truy vấn. Trong quá trình phân tích, những điểm mạnh và điểm yếu của hệ quản trị cơ sở dữ liệu phân tán cũng đã được trình bày.
  • Mô tả phương pháp xây dựng mô hình chi phí đánh giá truy vấn dựa trên nhiều tác vụ song song trong hệ phân tán khi thực hiện lựa chọn kế hoạch tối ưu.
  • Trình bày được nội dung và ý nghĩa của các thuật toán tối ưu hóa trên hệ phân tán cải tiến từ thuật toán Dynamic Programming cổ điển như thuật toán IDP1, thuật toán DPccp.
  • Kiểm chứng thuật toán kết hợp IDP1ccp đã tận dụng được điểm mạnh của các thuật toán IDP1 và thuật toán DPccp để mang lại hiệu quả tối ưu truy vấn tốt hơn trên hệ phân tán.
  • Kiểm chứng thuật toán kết hợp IDP1ccp đã tận dụng được điểm mạnh của các thuật toán IDP1 và thuật toán DPccp để mang lại hiệu quả tối ưu truy vấn tốt hơn trên hệ phân tán.

4. Tài liệu tham khảo

TS.Nguyễn Đình Thuân (2013), Bài giảng Distributed Database, Chương 4,5,7, Trường Đại học Công nghệ Thông tin ĐHQG-HCM.

Robert Taylor (2010), Query Optimization for Distributed Database Systems, Master Thesis, University of Oxford.

G. Ramakrishnan (2003), McGrawHill. Database Management Systems, Third Edition, McGrawHill

D. Kossmann (2000), The state of the art in distributed query processing, pages 422–469, ACM Computing Surveys....

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận văn Thạc sĩ trên ---

(7)
138 lượt xem
Share
Ngày:31/08/2020 Chia sẻ bởi:Tuyết Trịnh
TẢI VỀ XEM ONLINE

CÓ THỂ BẠN QUAN TÂM