Tối ưu hóa truy vấn trong các cơ sở dữ liệu phân tán

GIỚI THIỆU

1. Lý do chọn đề tài

Cơ sở dữ liệu phân tán đã đáp ứng một phần lớn các nhu cầu trong thực tế về dữ liệu phục vụ công tác quản lý ngày càng lớn và đa dạng. Đặc biệt, các hệ quản trị cơ sở dữ liệu phân tán đã giải quyết được vấn đề lưu trữ dữ liệu và phục vụ cho nhiều người dùng ở phân tán khắp mọi nơi.

Khi khối lượng thông tin phải xử lý ngày càng lớn, đa dạng và phong phú, dữ liệu được phân bố nhiều nơi thì vấn đề đặt ra là xử lý thông tin như thế nào để giảm chi phí đến mức tối thiểu. Một trong các giải pháp có tính khả thi là phải tối ưu hóa các câu lệnh khi truy vấn dữ liệu. Nghiên cứu về tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán là cần thiết để khai thác có hiệu quả dữ liệu phân tán. Do đó, tôi chọn nghiên cứu đề tài “Tối ưu hóa truy vấn trong các cơ sở dữ liệu phân tán” làm luận văn tốt nghiệp của mình.

2. Mục đích nghiên cứu

Đề tài phân tích, trình bày một cách có hệ thống các nghiên cứu về cơ sở dữ liệu quan hệ, nghiên cứu các phương pháp thiết kế cơ sở dữ liệu phân tán, các kỹ thuật tối ưu hóa câu truy vấn trong cơ sở dữ liệu phân tán, cài đặt thử nghiệm một số thuật toán tối ưu hóa câu truy vấn trong cơ sở dữ liệu phân tán, từ đó đưa ra lựa chọn phù hợp với từng bài toán trên thực tế.

3. Đối tượng và phạm vi nghiên cứu

Đối tượng và phạm vi nghiên cứu của luận văn là cơ sở dữ liệu phân tán, các câu truy vấn phân tán, một số thuật toán tối ưu hóa truy vấn phân tán và cài đặt một thuật toán tối ưu hóa truy vấn.

4. Phương pháp nghiên cứu

Có thể bạn quan tâm!

Xem toàn bộ 103 trang tài liệu này.

Nghiên cứu lý thuyết: Tìm hiểu các nghiên cứu từ các tài liệu, tạp chí và các bài viết trên mạng internet… sau đó tổng hợp so sánh để viết thành luận văn.

Nghiên cứu thực nghiệm: Cài đặt thử nghiệm thuật toán R*

5. Bố cục luận văn

Với những yêu cầu trên, nội dung của bản luận văn này trình bày khái quát chung về cơ sở dữ liệu phân tán, các kỹ thuật xây dựng cơ sở dữ liệu phân tán, tối ưu hóa truy vấn trong quá trình xử lý truy vấn, trình bày một số thuật toán tối ưu hóa truy vấn phân tán, cài đặt thuật toán R* để tối ưu hóa truy vấn. Luận văn được chia làm 3 chương:

Chương 1: Khái quát về cơ sở dữ liệu phân tán. Trong chương này trình bày khái quát về cơ sở dữ liệu phân tán: Khái niệm về cơ sở dữ liệu phân tán, ưu nhược điểm của cơ sở dữ liệu phân tán, các mức trong suốt phân tán, kiến trúc tham chiếu của cơ sở dữ liệu phân tán, các kỹ thuật xây dựng cơ sở dữ liệu phân tán.

Chương 2: Trình bày tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán: Quá trình xử lý truy vấn, tối ưu hóa truy vấn dựa vào phương pháp tối ưu đàn kiến, trình bày một số thuật toán tối ưu hóa truy vấn

Chương 3: Cài đặt thuật toán tối ưu hóa truy vấn phân tán: Xác định bài toán, mô hình phân tán cơ sở dữ liệu, sử dụng thuật toán R* để áp dụng, trình bày kết quả thử nghiệm và kết luận thực nghiệm.

CHƯƠNG 1. CƠ SỞ DỮ LIỆU PHÂN TÁN

1.1. Khái niệm về hệ cơ sở dữ liệu phân tán

1.1.1. Khái niệm

Cơ sở dữ liệu phân tán là một tập hợp các dữ liệu phụ thuộc logic lẫn nhau của cùng một hệ thống và được lưu trữ trên các trạm của một mạng máy tính. Cơ sở dữ liệu phân tán làm tăng khả năng truy nhập tới cơ sở dữ liệu lớn trên mạng. Trong hệ thống đó mỗi máy tính quản lý một cơ sở dữ liệu thành phần được gọi là 1 node hoặc site và nhấn mạnh hai khía cạnh quan trọng của cơ sở dữ liệu phân tán [4].

- Tính chất phân tán: Thực tế dữ liệu không nằm ở cùng một trạm mà nằm trên nhiều trạm thuộc một mạng máy tính.

- Quan hệ logic: Trong CSDL phân tán dữ liệu có một số đặc tính liên kết, ràng buộc với nhau như tính kết nối, mối quan hệ, điều này giúp chúng ta có thể phân biệt một CSDL phân tán với một tập hợp CSDL cục bộ hoặc các tệp nằm tại các vị trí khác nhau trong một mạng máy tính.

1.1.2. Hệ quản trị cơ sở dữ liệu phân tán

Các hệ quản trị cơ sở dữ liệu phân tán có chức năng hỗ trợ việc tạo và bảo trì cơ sở dữ liệu phân tán, chúng có các thành phần tương tự như một hệ quản trị cơ sở dữ liệu tập trung thành các thành phần hỗ trợ trong 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ị cơ sở dữ liệu phân tán thương mại phải có:

- Quản trị dữ liệu (Database management): DB

- 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 mạng

- Cơ sở dữ liệu phân tán (Distributed Database): DDB Hệ quản trị cơ sở dữ liệu phân tán được phân làm 2 loại:

- Cơ sở dữ liệu phân tán thuần nhất: Là hệ cơ sở dữ liệu mà tất cả các nút sử dụng cùng một loại hệ quản trị cơ sở dữ liệu, công nghệ cơ sở dữ liệu là như nhau, dữ liệu tại các vị trí khác nhau có các định nghĩa và khuôn dạng chung (các hệ quản trị cơ sở dữ liệu ở các nút có sự tương thích cao)

- Cơ sở dữ liệu phân tán không thuần nhất: Là hệ cơ sở dữ liệu mà có ít nhất một nút không cùng một loại hệ quản trị cơ sở dữ liệu với hệ cơ sở dữ liệu ở các nút còn lại, có nghĩa là dữ liệu trên các vị trí thường không tương thích. Các mâu thuẫn điển hình bao gồm sự khác biệt về cú pháp và các khác biệt về ngữ nghĩa.

1.1.3. Những ưu điểm của cơ sở dữ liệu phân tán

Lợi ích cơ bản nhất của cơ sở dữ liệu phân tán là dữ liệu của các cơ sở dữ liệu vật lý riêng biệt được tích hợp logic với nhau làm cho nhiều người sử dụng trên mạng có thể truy nhập được [11].

a) Cho phép quản lý dữ liệu với nhiều mức trong suốt

Hệ quản trị cơ sở dữ liệu phải được trong suốt phân tán theo nghĩa làm cho người sử dụng không cần biết vị trí của dữ liệu và không cần biết sự phức tạp truy cập qua mạng.

b) Tăng độ tin cậy và khả năng sẵn sàng

Độ tin cậy là khả năng hệ thống đang làm việc (không bị ngừng) tại một thời điểm nào đó, tính sẵn sàng là khả năng hệ thống tiếp tục làm việc trong một khoảng thời gian nào đó. Khi dữ liệu và cơ sở dữ liệu phân tán trên một vài trạm, một trạm có thể có sự cố trong khi các trạm khác vẫn có thể hoạt động hoặc sử dụng các thành phần khác của cơ sở dữ liệu. Chỉ trên trạm bị sự cố, dữ liệu và ứng dụng không thể truy cập được. Để nâng cao độ tin cậy và tính sẵn sàng, có thể áp dụng cơ chế tạo bản sao trên nhiều trạm [1].

c) Cải thiện hiệu năng

Một hệ quản trị cơ sở dữ liệu phân tán, phân đoạn cơ sở dữ liệu có thể làm

cho dữ liệu sẽ được lưu giữ tại gần nơi sử dụng nhất. Dữ liệu được lưu giữ cục bộ làm giảm cạnh tranh CPU (bộ xử lý trung tâm), giảm các phục vụ I/O (các thiết bị nhâp, xuất) và giảm tương tranh truy nhập trên mạng. Dữ liệu được phân tán tại các trạm nên dung lượng dữ liệu cục bộ sẽ nhỏ hơn, các xử lý giao tác và truy vấn cục bộ sẽ được thực hiện tốt hơn. Hơn nữa trên mỗi trạm có ít các giao tác hơn số các giao tác trên cơ sở dữ liệu tập trung vì vậy cũng tăng hiệu suất hệ thống.

d) Dễ dàng mở rộng

Việc thêm cơ sở dữ liệu mới, tăng kích cỡ cơ sở dữ liệu hoặc thêm bộ xử lý trong môi trường phân tán là dễ hơn vì cũng chỉ như là thêm các cơ sở dữ liệu thành phần.

1.1.4. Những nhược điểm của cơ sở dữ liệu phân tán [3]

Tuy có những ưu điểm vượt trội so với CSDL tập trung, CSDL phân tán có những điểm yếu nhất định có thể tóm gọn lại trong 4 vấn đề sau:

 Độ phức tạp thiết kế và cài đặt hệ thống tăng: Hệ quản trị cơ sở dữ liệu phân tán phải bổ sung thêm các chức năng như:

 Theo dõi dấu vết dữ liệu

 Xử lý các truy vấn phân tán

 Quản lý giao dịch phân tán

 Phục hồi cơ sở dữ liệu phân tán

 Quản lý các bản sao

 Quản lý thư mục - catalog phân tán

 Khó điều khiển tính nhất quán về dữ liệu

 Các phần mềm hệ thống đảm bảo quản trị, duy trì kết nối, trao đổi dữ liệu trên mạng.

 Bảo mật khó khăn: Trong cơ sở dữ liệu phân tán các máy được kết nối qua mạng máy tính, việc đảm bảo an ninh trong môi trường mạng ra phức tạp hơn.

Ở mức vật lý, những nhân tố chính sau là để phân biệt một hệ cơ sở dữ liệu phân tán với hệ cơ sở dữ liệu tập trung:

 Có nhiều máy tính được gọi là các trạm hay các nút.

 Các trạm này phải được kết nối bởi một kiểu mạng truyền thông để truyền dữ liệu.

Trong mô hình dữ liệu tập trung, tài nguyên tập trung tại một máy tính. Trong hệ thống cơ sở dữ liệu phân tán, cơ sở dữ liệu được chứa trong nhiều máy tính, các máy tính này được nối với nhau qua các hệ thống truyền thông, chúng không chia sẻ bộ nhớ chung cũng như không dùng chung đồng hồ. Các bộ xử lý trong hệ thống phân tán có kích cỡ và chức năng khác nhau (chẳng hạn có thể bao gồm các bộ vi xử lý, trạm làm việc, máy tính mini, hay các máy lớn vạn năng). Trong hệ thống cơ sở dữ liệu phân tán gồm nhiều trạm thì mỗi trạm có thể truy nhập dữ liệu ở các trạm khác.

1.2. Các đặc trưng trong suốt của cơ sở dữ liệu phân tán

1.2.1. Trong suốt phân tán

 Cho phép xử lý dữ liệu trên hệ cơ sở dữ liệu phân tán giống như đối với cơ sở dữ liệu tập trung.

 Người sử dụng không cần biết: Dữ liệu đã được phân đoạn như thế nào, các bản sao dữ liệu để ở đâu, vị trí vật lý lưu trữ dữ liệu ở đâu.

 Trong suốt phân tán thể hiện:

 Trong suốt địa điểm: Người dùng không cần biết cũng như không cần quan tâm tới vị trí của các tài nguyên trên hệ thống vì vị trí của chúng không ảnh hưởng đến cách thức truy xuất.

 Trong suốt tên: Khi một đối tượng đã được đặt tên thì có thể truy nhập chính xác không cần đặc tả thêm.

 Trong suốt bản sao: Sự nhân bản là quá trình sao chép và duy trì dữ liệu trong hệ cơ sở dữ liệu phân tán. Cùng một dữ liệu (được lưu trữ vật lý tại một vị trí) có thể sử dụng được trên nhiều vị trí khác nhau.

Các bản sao có thể được lưu trữ trên nhiều trạm làm tăng hiệu suất, độ tin cậy và tính sẵn sàng của hệ thống. Các ứng dụng có thể truy nhập dữ liệu tại các trạm mà không cần phải truy cập từ xa giảm truyền tải trên mạng lớn. Hệ thống cho phép tiếp tục thực hiện nếu như các trạm từ xa có sự cố. Trong suốt bản sao đảm bảo người dùng không biết đó là các bản sao vì dữ liệu luôn được cập nhật và đồng bộ với dữ liệu gốc.

 Trong suốt phân đoạn: Một quan hệ trong cơ sở dữ liệu phân tán có thể phân đoạn ngang hoặc phân đoạn dọc nghĩa là được tách thành các bộ dữ liệu hoặc các quan hệ con và lưu trữ trên nhiều trạm khác nhau. Trong suốt phân đoạn cho phép người sử dụng không cần biết có sự phân đoạn, các truy vấn dữ liệu vẫn được viết như cơ sở dữ liệu tập trung.

1.2.2. Trong suốt giao dịch

Cơ sở dữ liệu phân tán cho phép một giao dịch có thể cập nhật, sửa đổi dữ liệu trên các trạm khác nhau. Để đảm bảo dữ liệu nhất quán trên toàn hệ thống, các trạm trong giao dịch chỉ ủy thác khi tất cả các trạm đã ủy thác thành công hoặc rollback (lùi cơ sở dữ liệu về một trạng thái cũ) khi một trạm bị thất bại.

1.2.3. Trong suốt thất bại

Đảm bảo tại một trạm của hệ thống bị hỏng thì hệ thống vẫn làm việc bình thường (do cơ chế tạo bản sao hoặc làm việc trên các trạm không bị sự cố). Nếu mạng hoặc hệ thống có sự cố trong khi ủy thác của giao dịch cơ sở dữ liệu phân tán thì giao dịch đó được giải quyết tự động và trong suốt theo nghĩa khi mạng hoặc hệ thống khôi phục thì tất các các trạm này hoặc là ủy thác hoặc là rollback lại giao tác đó.

1.2.4. Trong suốt thao tác

Cho phép các câu lệnh thao các dữ liệu đơn giản để truy nhập được các cơ sở dữ liệu tại trạm cục bộ hoặc trạm từ xa. Các thao tác xử lý dữ liệu từ xa

không phức tạp và vẫn đảm bảo vẫn giống như khi thao tác dữ liệu trên hệ cơ sở dữ liệu không phân tán.

1.2.5. Trong suốt về tính không thuần nhất

Cho phép hỗn hợp nhiều hệ quản trị cơ sở dữ liệu khác nhau với các khả năng trao đổi dữ liệu, xử lý cập nhật dữ liệu, xử lý giao tác phân tán trên toàn hệ thống.

1.3. Kiến trúc tham chiếu của cơ sở dữ liệu phân tán

Kiến trúc tham chiếu không được cài đặt rõ ràng trên tất cả cơ sở dữ liệu phân tán, tuy nhiên các mức của nó được khái quát chính xác, thích hợp để mô tả tổ chức chung cho mọi hệ cơ sở dữ liệu phân tán.

 Lược đồ tổng thể: Mô tả tổng thể và thống nhất chung nhất của tất cả dữ liệu của cơ sở dữ liệu phân tán độc lập với môi trường phân tán.

 Phân đoạn: Mối quan hệ tổng thể có thể được chia thành vài phần không giao nhau được gọi là các đoạn. Lược đồ phân đoạn định nghĩa ánh xạ giữa các quan hệ tổng thể và các phân đoạn. Ánh xạ này là một nhiều, một số đoạn tương ứng với một quan hệ tổng thể, nhưng chỉ một quan hệ tổng thể tương ứng với một đoạn. Ký hiệu Ri là đoạn thứ i của quan hệ tổng thể R.

 Lược đồ định vị: Định nghĩa ánh xạ từ các phân đoạn vào những trạm chứa những phân đoạn đó. Tất cả các đoạn tương ứng với cùng quan hệ tổng thể R và được đặt tại cùng trạm j tạo thành hình ảnh vật lý của quan hệ tổng thể R tại trạm j.

 Lược đồ ánh xạ địa phương: Ánh xạ các hình ảnh vật lý tới các đối tượng được thao tác bởi các hệ quản trị cơ sở dữ liệu địa phương. Trong hệ không thuần nhất ta có các kiểu ánh xạ địa phương khác nhau tại các trạm khác nhau.