Tối ưu hóa các truy vấn phân tán

Input: QG: Đồ thị truy vấn với n quan hệ, các thống kê của mỗi quan hệ Output

tải về 54.21 Kb.

trang	2/5
Chuyển đổi dữ liệu	09.02.2023
Kích	54.21 Kb.
	#54199

1 2 3 4 5

8.4 tối ưu hóa phân tán - Copy

Endif Endfor
End Endwhile

Input: QG: Đồ thị truy vấn với n quan hệ, các thống kê của mỗi quan hệ
Output: ES: Chiến lược thực hiện
BEGIN
ES local-operations(QG)
Sửa đổi các thống kê để phản ánh kết quả xử lý của địa phương BS Φ {Tập các phép bán kết nối có lợi}
For mỗi phép bán kết nối SJ trong QG do If (cost(SJ)then
BS BS  SJ

Endif Endfor

While BS <>  do {Chọn các phép kết nối có lợi}

Begin

SJ most_benefit(BS) {SJ: semijoin có benefit_cost lớn nhất} BSBS-SJ {Loại SJ khỏi BS}
ESES+SJ
Sửa đổi các thống kê để phản ánh kết quả của SJ thêm vào BSBS-các phép bán kết nối không có lợi
BSBS  các phép bán kết nối có lợi mới

End Endwhile

{Chọn trạm thực hiện}
AS(ES)  chọn trạm i mà i chứa số lượng dữ liệu lớn nhất sau tất cả các phép toán cục bộ
ES ES  sự truyền của các quan hệ trung gian tới AS(ES)
{Tối ưu hóa sau}
^For^mỗi^quan^hệ^Ri ^tại^AS(ES)^do
^For^mỗi^phép^nửa^kết^nỗi^SJ^{của R}i ^với^Rj ^doIf (cost(ES)then
ES  ES - SJ

Endif Endfor

Endfor

END. {SDD – 1 – QOA}

Thuật toán này được diễn giải như sau:
Giai đoạn khởi đầu: sinh ra một tập những phép bán kết nối có lợi (BS), vào một chiến lược thực thi (ES) bao gồm các xử lý địa phương.
^{Giai đoạn tiếp theo: Lặp lại lựa chọn ra các phép bán kết nối có lợi (SJ}i^{) từ BS,}sửa đổi các thống kê cơ sở dữ liệu và BS. Sự sửa đổi ảnh hưởng đến các thống kê của ^{quan hệ R liên quan trong SJ}i ^{và phép}^{bán kết nối còn lại trong BS mà sử dụng quan}hệ R. Vòng lặp kết thúc khi tất cả các phép bán kết nối được thêm vào ES sẽ là thứ tự thực thi của chúng.
Giai đoạn chọn các trạm thực hiện: Với mỗi trạm đề cử đánh giá chi phí truyền tất cả dữ liệu được yêu cầu tới nó và chọn trạm có chi phí nhỏ nhất.
Giai đoạn tối ưu hoá sau: Loại bỏ những phép kết nối trong chiến lược thực thi chỉ ảnh hưởng đến quan hệ được lưu trữ tại trạm thực hiện.

tải về 54.21 Kb.

Chia sẻ với bạn bè của bạn:

1 2 3 4 5