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

Input: MVQ: Truy vấn đa biến với n biến Output

tải về 54.21 Kb.

trang	5/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

Endfor

Input: MVQ: Truy vấn đa biến với n biến Output: Kết quả của truy vấn đa biến cuối cùng BEGIN
^For^{mỗi OVQ}i ^{có thể tách ra in MVQ}^do^{{chạy tất cả các truy vấn một biến}}^Run(OVQi⁾
(1)

Endfor

MVQ’_list  REDUCE(MVQ)
{thay thế MVQ bởi n truy vấn không thể rút gọn} (2)
While n0 do {n – số truy vấn không thể rút gọn} (3)

Begin

{Chọn truy vấn không thể rút gọn liên quan đến các mảnh nhỏ nhất} MVQ’ select _ query(MVQ’_list); (3.1)
{Xác định các đoạn để truyền và trạm xử lý MVQ’} Fragmen- site- list  SELECT_RATEGY(MVQ’); (3.2)
{truyền các mảnh đã chọn tới các trạm đã chọn}
For mỗi cặp (F,S) trong Fragnemt – site – list do (3.3) Chuyển đoạn F tới trạm S;

Endfor

Run(MVQ’); nn-1; (3.4)
Endwhile {đầu ra của thuật toán là kết quả của MVQ’ cuối cùng}

END. (D- INGRES - QOA)

Diễn giải thuât toán như sau:
Bước 1: Xử lý địa phương tất cả các truy vấn một biến (phép chọn và phép chiếu).
Bước 2: Thuật toán thu gọn được áp dụng cho truy vấn ban đầu, tách các truy vấn không thể rút gọn và các truy vấn một biến ra. Bỏ qua các truy vấn một biến vị đã xử lý ở bước 1
Bước 3: Áp dụng cho các câu truy vấn không thể rút gọn.
Bước 3.1: Chọn các truy vấn chưa được xử lý và liên quan đến các mảnh nhỏ
hơn.
Bước 3.2: Chọn chiến lược tốt nhất để xử lý truy vấn MVQ’ (truy vấn không thể
rút gọn và có ít nhất hai biến). Chiến lược này được mô tả bởi một danh sách các cặp (F,S), trong đó F là một mảnh để truyền tới trạm xử lý S.
Bước 3.3: Truyền tất cả các mảnh tới trạm xử lý chúng.
Bước 3.4: Thực hiện MVQ’. Nếu có các truy vấn con còn lại, thuật toán quay lại bước 3 và thực hiện bước lặp tiếp theo, ngược lại thuật toán kết thúc.
Ví dụ: Giả sử các quan hệ EMP, ASG và PROJ được lưu trữ trên các trạm khác nhau, trong đó quan hệ EMP bị phân mảnh và lưu trữ trên hai trạm 1 và 2, quan hệ ASG và PROJ không bị phân mảnh nhưng được lưu trữ ở các trạm khác nhau, cấu trúc lưu trữ được thể hiện như sau.

Khi thực hiện phép kết nối 3 quan hệ này, có nhiều chiến lược thực hiện như sau:

Thực hiện câu truy vấn đầy đủ trên phép kết nối 3 quan hệ trên

(EMP ⊳𝖺 ASG ⊳𝖺 PROJ) bằng cách gửi toàn bộ dữ liệu EMP1 và ASG sang trạm 2.

Thực hiện (EMP ⊳𝖺 ASG) ⊳𝖺 PROJ bằng cách gửi (EMP1 ⊳𝖺 ASG) và ASG sang trạm 2 và tiếp tục thực hiện kết nối (EMP2 ⊳𝖺 ASG), sau đó ghep hai kết quả kết nối trên để thực hiện kết nối với PROJ.

Việc lựa chọn chiến lược tối ưu giữa các chiến lược khả thi đòi hỏi việc ước lượng được kích thước của các kết quả trung gian. Ví dụ, trong trường hợp trên, nếu kích thước size(EMP1 ⊳𝖺 ASG) > size(EMP1), chiến lược đầu tiên sẽ tốt hơn chiến lược thứ 2. Vậy việc ước lượng các kết quả trung gian là bắt buộc trong thuật toán INGRES. Quá trình thực hiện ước lượng và lựa chọn tối ưu được thực hiện trong bước 3.1 và 3.2 của thuật toán INGRES.

tải về 54.21 Kb.

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

1 2 3 4 5