Tối Ưu Hóa Biểu Thức Đường Dẫn Trong Cơ Sở Dữ Liệu Hướng Đối Tượng

chỉ tương đương các thuật toán phân mảnh thông thường. Các kết quả thực nghiệm, so sánh và đánh giá các thuật toán cho thấy thuật toán FragAlloS hiệu quả hơn các thuật toán AttrFrag và thuật toán của Ezeife do sử dụng thông tin về mạng cả cho giai đoạn phân mảnh. Các thuật toán đề xuất đã được công bố trong các bài báo (1), (3) và (4).

Tếp theo, trong chương 3 luận án tiếp tục nghiên cứu về tối ưu hóa truy vấn trong CSDL HĐT PT.

CHƯƠNG 3 - TỐI ƯU HÓA BIỂU THỨC ĐƯỜNG DẪN TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG PHÂN TÁN

Tiếp theo vấn đề thiết kế là bài toán xử lý truy vấn, trong môi trường phân tán bài toán này rất khó phân tích bởi có nhiều yếu tố liên quan. Lược đồ phân tầng được đề xuất trong [4] nhằm chia nhỏ quá trình xử lý truy vấn thành nhiều bài toán nhỏ. Bốn công việc chính được đưa ra trong lược đồ phân tầng: Phân rã truy vấn, cục bộ hóa dữ liệu, tối ưu hóa truy vấn toàn cục và tối ưu hóa truy vấn cục bộ. Luận án tập trung vào vấn đề tối ưu hóa truy vấn và thảo luận một bài toán đặc biệt của mô hình truy vấn đối tượng – đó là vấn đề thực thi các biểu thức đường dẫn.

Để hạn chế việc truyền dữ liệu chúng tôi đề xuất thuật toán BloomOpt để lọc các dữ liệu không cần thiết. Tiếp đến là đề xuất thuật toán qui hoạch động ExpPathOpt để tối ưu hóa truy vấn có các biểu thức truy vấn kết hợp với nhau qua toán tử AND. Thuật toán ExpPathOpt xây dựng phương án tối ưu từ các phương án tối ưu của các truy vấn con, tương ứng với việc tách đồ thị truy vấn thành các đồ thị con. Các kết quả được trình bày trong các bài báo (2) và (5).

3.1. Xử lý truy vấn trong cơ sở dữ liệu quan hệ

3.1.1. Tổng quan về xử lý truy vấn phân tán

3.1.1.1.Mục tiêu của xử lý truy vấn

Mục tiêu của việc xử lý truy vấn trong môi trường phân tán là ánh xạ câu truy vấn cấp cao trên CSDL phân tán mà người sử dụng xem như một CSDL duy nhất thành một chiến lược thực thi hiệu quả được diễn tả bằng một ngôn ngữ cấp thấp trên các CSDL cục bộ. Ngôn ngữ cấp cao là các phép tính đại số quan hệ, còn ngôn ngữ cấp thấp là một dạng mở rộng của đại số quan hệ đi kèm với các thao tác truyền dữ liệu. Chiến lược thực thi là quá trình biến đổi đúng đắn một câu truy vấn cấp cao. Vấn đề quan trọng trong xử lý truy vấnlà vấn đề tối ưu hóa, đó là tìm chiến lược sử dụng các tài nguyên một cách tối ưu nhất [4].

Chỉ số đánh giá mức độ sử dụng tài nguyên chính là tổng chi phí phải trả khi xử lý truy vấn. Tổng chi phí là tổng thời gian cần để xử lý các phép toán truy vấn

tại các vị trí khác nhau và truyền dữ liệu giữa các vị trí. Một tiêu chí khác là thời gian đáp ứng của câu truy vấn, là thời gian cần thiết để thực hiện câu truy vấn. Vì các phép toán có thể được thực hiện song song tại các vị trí khác nhau nên thời gian đáp ứng có thể nhỏ hơn nhiều so với tổng chi phí của nó.

Trong môi trường phân tán, tổng chi phí bao gồm chi phí CPU, chi phí nhập, xuất và chi phí truyền dữ liệu. Chi phí CPU là chi phí phải trả khi thực hiện các thao tác trên dữ liệu trong bộ nhớ chính. Chi phí nhập, xuất là thời gian cần thiết cho các thao tác nhập, xuất đĩa. Chi phí truyền tin là thời gian cần để trao đổi dữ liệu giữa các vị trí tham gia vào trong quá trình thực thi câu truy vấn. Hai thành phần đầu tiên (chi phí CPU và chi phí nhập, xuất) là các yếu tố đã được đề cập trong CSDL tập trung. Chi phí truyền là yếu tố quan trọng nhất được xét đến trong CSDL phân tán.

Ví dụ 3.1: Chúng ta xét một tập con của lược đồ CSDL gồm hai quan hệ: Quan hệ Nhân viên (NhanVien) gồm các thuộc tính mã số (MaSoNV), tên (TenNV), chức danh (ChucDanh). Quan hệ Thực hiện Dự án (THDuAn) gồm các thuộc tính mã số nhân viên (MaSoNV), mã số dự án (MaSoDA), vai trò của nhân viên trong dự án (VaiTro), thời gian được phân công trong dự án (ThoiGian).

NhanVien(MaSoNV, TenNV, ChucDanh) THDuAn(MaSoNV, MaSoDA, VaiTro, ThoiGian)

Xét câu truy vấn đơn giản “Cho biết tên các nhân viên hiện đang quản lý một dự án”. Biểu thức truy vấn bằng phép tính quan hệ theo cú pháp SQL là

SELECT TenNV

FROM NhanVien, THDuAn

WHERE NhanVien.MaSoNV = THDuAn.MaSoNV AND VaiTro = “Quản lý”

Hai biểu thức tương đương trong đại số quan hệ được biến đổi từ câu truy vấn trên là:

∏𝑇𝐸𝑁𝑁𝑉(𝜎VaiTro="Quản lý"∧NhanVien.MaSoNV=THDuAn.MaSoNV(NhanVien × 𝑇𝐻𝐷𝑢𝐴𝑛)

và ∏𝑇𝐸𝑁𝑁𝑉((𝑁ℎ𝑎𝑛𝑉𝑖𝑒𝑛 ⋈𝑀𝑎𝑆𝑜𝑁𝑉 (𝜎𝑉𝑎𝑖𝑇𝑟𝑜="𝑄𝑢ả𝑛 𝑙ý" (𝑇𝐻𝐷𝑢𝐴𝑛))

Câu truy vấn thứ 2 không dùng tích Descartes nên tiêu dùng ít tài nguyên hơn câu truy vấn thứ nhất.

3.1.1.2. Độ phức tạp của phép toán đại số quan hệ

Đại số quan hệ được sử dụng như một phương pháp cơ bản để diễn tả kết quả đầu ra của câu truy vấn. Vì vậy, độ phức tạp của các phép toán đại số quan hệ có ảnh hưởng trực tiếp đến kết quả truy vấn.

Bảng 3.1: Độ phức tạp của phép tính đại số quan hệ

Phép toán

Độ phức tạp
Chọn Chiếu (không loại bỏ trùng lặp)	O(n)
Chiếu (có loại bỏ trùng lặp) Gộp nhóm	O(n*log n)
Kết nối Kết nối nửa Chia Các phép toán tập hợp	O(n*log n)
Tích Descartes	O(n2)

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

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

Độ phức tạp được định nghĩa đơn giản nhất theo lực lượng của quan hệ. Độ phức tạp của các phép toán đại số quan hệ được trình bày trong Bảng 3.1 [4]. Tuy nhiên sử dụng bảng băm và bộ nhớ đủ để quản lý một quan hệ đã được băm có thể làm giảm độ phức tạp của các toán tử.

Đánh giá sơ lược về độ phức tạp cho thấy hai nguyên tắc. Trước tiên, bởi vì độ phức tạp có tính tương đối so với lực lượng của quan hệ, các thao tác có tính chọn lựa làm giảm đi lực lượng (thí dụ phép chọn) cần phải được thực hiện đầu tiên. Thứ hai, các phép toán cần phải được sắp xếp theo độ phức tạp để tránh thực hiện tích Descartes hoặc để lại thực hiện sau.

3.1.1.3. Đặc trưng của bộ xử lý truy vấn

Chúng ta có thể liệt kê tám đặc trưng quan trọng của bộ xử lý truy vấn, các đặc trưng này được sử dụng để so sánh các thuật toán tối ưu hóa truy vấn. Bốn đặc trưng đầu đều đúng cho các bộ xử lý tập trung lẫn phân tán, bốn đặc trưng sau chỉ có ở các bộ xử lý phân tán [4].

Ngôn ngữ: Ngôn ngữ đầu vào cho các bộ xử lý truy vấntrong các hệ quản trị CSDL quan hệ dựa trên phép tính quan hệ. Với các hệ quản trị CSDL đối tượng, ngôn ngữ này dựa trên phép tính đối tượng (object calculus). Phép tính đối tượng được mở rộng từ phép tính quan hệ, vì vậy việc phân rã trong đại số đối tượngcũng cần thiết. Cần có một giai đoạn phân rã câu truy vấn được biểu diễn bằng phép tính quan hệ thành đại số quan hệ. Trong ngữ cảnh phân tán, ngôn ngữ đầu ra nói chung là một dạng nội tại của đại số quan hệ được tăng cường thêm các phép toán truyền dữ liệu. Các phép toán của ngôn ngữ này được cài đặt trực tiếp trong hệ thống. Việc xử lý truy vấn phải ánh xạ hiệu quả từ ngôn ngữ đầu vào thành ngôn ngữ đầu ra.

Các kiểu tối ưu hóa: Tối ưu hóa truy vấn nhằm chọn ra một lời giải tốt nhất trong không gian các lời giải. Lời giải tốt nhất thường được chọn theo tiêu chí tối thiểu hóa chi phí. Tuy nhiên, không gian lời giải có thể rất lớn, cộng thêm số lượng các quan hệ hoặc các mảnh quá nhiều. Vì thế cách tìm kiếm vét cạn có thể sẽ gặp khó khăn. Các chiến lược sử dụng heuristic với tác dụng làm hẹp phạm vi tìm kiếm cũng thường được sử dụng. Một thuật giải heuristic thông dụng làm giảm kích thước các kết quả trung gian bằng cách thực hiện các phép toán một ngôi trước rồi sắp thứ tự thực hiện các phép tính hai ngôi theo kích thước tăng dần của kết quả trung gian được tạo ra. Một heuristic quan trọng trong các hệ phân tán là thay đổi các nối bằng các tổ hợp của các nối nửa nhằm hạ thấp chi phí truyền dữ liệu.

Thời điểm tối ưu hóa: Tối ưu hóa có thể thực hiện theo kiểu tĩnh trước khi thực thi truy vấn hoặc theo kiểu động trong khi thực thi truy vấn. Tối ưu hóa tĩnh được thực hiện vào lúc biên dịch. Tối ưu hóa động được tiến hành vào lúc thực thi. Ở mỗi thời điểm của quá trình thực thi, việc chọn ra một thao tác kế tiếp tốt nhất có thể dựa vào thông tin kết quả được thực hiện trước đó.

Số liệu thống kê: Hiệu quả của việc tối ưu hóa truy vấn dựa vào các số liệu thống kê về CSDL.Tối ưu hóa động cần đến các số liệu thống kê nhằm chọn lựa các thao tác cần phải thực hiện trước tiên. Tối ưu hóa tĩnh cần đến số liệu thống kê nhiều hơn vì kích thước các kết quả trung gian phải được đánh giá dựa vào các thông tin thống kê. Trong CSDL phân tán, số liệu thống kê dành cho tối ưu hóa được tính theo các mảnh, gồm có lực lượng của mảnh và kích thước, kích thước và số lượng giá trị phân biệt của mỗi thuộc tính. Độ chính xác của số liệu thống kê có được nhờ vào việc cập nhật theo định kỳ.

Vị trí quyết định: Phần lớn các hệ thống sử dụng phương pháp quyết định tập trung, trong đó chỉ một vị trí đề ra chiến lược trả lời truy vấn. Tuy nhiên, quá trình quyết định có thể được phân tán cho nhiều vị trí tham gia vào quá trình thỏa thuận để chọn ra chiến lược tốt nhất.

Tận dụng cấu hình mạng: Trong các mạng diện rộng WAN, hàm chi phí cần hạ thấp có thể giới hạn trong chi phí truyền dữ liệu, được xem là yếu tố chiếm đa phần, vì vậy cần chọn chiến lược thực thi toàn cục dựa trên việc truyền dữ liệu giữa các vị trí và chọn chiến lược thực thi cục bộ dựa vào thuật toán xử lý truy vấn tập trung. Trong các mạng cục bộ, chi phí truyền có thể so sánh với chi phí xuất nhập, vì vậy có thể tăng quá trình thực hiện song song.

Tận dụng các mảnh được nhân bản: quá trình ánh xạ các câu truy vấn phân tán trên quan hệ toàn cục thành các câu truy vấn trên các mảnh vật lý gọi là quá trình cục bộ hóa (localization). Để tăng độ tin cậy, chúng ta thường nhân bản các mảnh ở các vị trí khác nhau. Một số thuật toán tận dụng sự tồn tại của các nhân bản vào lúc chạy nhằm hạ thấp số lần truyền dữ liệu.

Sử dụng các bán kết nối: Bán kết nối có đặc tính quan trọng là làm giảm đi kích thước các bảng dữ liệu. Khi thành phần chính được xem xét là chi phí truyền, bán kết nối sẽ giúp cải thiện việc xử lý kết nối phân tán. Tuy nhiên, bán kết nối có thể làm tăng số lượng các thông báo và thời gian xử lý cục bộ.

3.1.2. Các tầng xử lý truy vấn

Bài toán xử lý truy vấn có thể được phân rã thành nhiều bài toán con tương ứng ở các tầng khác nhau. Lược đồ phân tầng tổng quát để xử lý truy vấn phân tán được mô tả trong Hình 3.1.

Truy vấn dạng phép tính

trên các quan hệ phân tán

PHÂN RÃ TRUY VẤN

Lược đồ

toàn cục

Truy vấn dạng đại số trên

các quan hệ phân tán

Vị trí điều khiển

CỤC BỘ HÓA DỮ LIỆU

Lược đồ

phân mảnh

Truy vấn theo mảnh

TỐI ƯU HÓA TOÀN CỤC

Lược đồ

cấp phát

Kế hoạch thực hiện truy vấn

phân tán

Các vị trí cục bộ

THỰC HIỆN PHÂN TÁN

Truy vấn cục bộ đã tối ưu

Hình 3.1: Lược đồ phân tầng tổng quát để xử lý truy vấn phân tán

Tầng thứ nhất phân rã câu truy vấn phân tán dạng phép tính quan hệ thành dạng đại số quan hệ trên các quan hệ toàn cục. Thông tin cần cho quá trình biến đổi này được mô tả trong lược đồ khái niệm toàn cục và các quan hệ toàn cục. Tuy nhiên, thông tin về việc phân tán dữ liệu không được dùng ở tầng này mà được dùng ở tầng tiếp theo. Vì vậy, những kỹ thuật được sử dụng ở tầng này là của các hệ quản trị CSDL tập trung. Phân rã truy vấn có thể được xem như bốn bước liên tiếp. Trước tiên, câu truy vấn bằng phép tính quan hệ được viết lại ở dạng chuẩn tắc, thích hợp cho các biến đổi sau đó. Tiếp đến, truy vấn đã chuẩn hóa được phân tích về mặt ngữ nghĩa nhằm phát hiện và loại bỏ các câu truy vấn sai càng sớm càng tốt. Thứ ba, câu truy vấn đúng (vẫn được diễn tả bằng phép tính quan hệ) được đơn giản hóa, chẳng hạn loại bỏ các vị từ thừa. Cuối cùng, câu truy vấn bằng phép tính quan hệ sẽ được tái cấu trúc như một truy vấn đại số.

Tầng thứ hai làm nhiệm vụ cục bộ hóa dữ liệu. Đầu vào cho tầng thứ hai là một truy vấn đại số trên các quan hệ phân tán. Vai trò chính của tầng này là cục bộ hóa dữ liệu của câu truy vấn nhờ sử dụng các thông tin về phân bố dữ liệu. Tầng này xác định xem những mảnh nào cần cho câu truy vấn và biến đổi câu truy vấn thành câu truy vấn trên các mảnh.

Tầng thứ ba thực hiện tối ưu hóa truy vấn toàn cục. Đầu vào cho tầng thứ ba là câu truy vấn theo mảnh, nghĩa là một câu truy vấn đại số trên các mảnh. Mục đích của việc tối ưu hóa truy vấn là tìm ra một chiến lược thực thi gần tối ưu cho câu truy vấn.

Tầng cuối cùng thực hiện truy vấn phân tán, tầng này được thực hiện tại các vị trí có các mảnh cần cho câu truy vấn. Mỗi câu truy vấn con được thực hiện tại một vị trí, được gọi là truy vấn cục bộ, sẽ được tối ưu hóa bằng cách sử dụng lược đồ cục bộ của vị trí. Tối ưu hóa truy vấn cục bộ sử dụng các thuật toán của các hệ thống tập trung.

3.1.2.1. Phân rã truy vấn

Phân rã truy vấn là giai đoạn đầu tiên của quá trình xử lý câu truy vấn, nó biến đổi câu truy vấn ở dạng phép tính quan hệ thành câu truy vấn đại số quan hệ. Các truy vấn nhập và xuất đều tham chiếu đến các quan hệ toàn cục và không dùng