Bài giảng cơ sở dữ liệu - Bài 4: Tối ưu truy vấn trên hệ cơ sở dữ liệu phân tán - Đỗ Phúc

Bài 4: TỐI ƯU TRUY VẤN TRÊN HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN Khoa Hệ thống thông tin Trường Đại học Công nghệ thông tin, ĐHQG-HCM 2NỘI DUNG MỞ ĐẦU I. TỔNG QUAN VỀ XỬ LÝ TRUY VẤN PHÂN TÁN 1. Bài toán xử lý truy vấn phân tán 2. Mục tiêu của tối ưu truy vấn phân tán 3. Độ phức tạp của các phép toán đại số quan hệ 4. Các vấn đề của tối ưu truy vấn phân tán 5. Các tầng xử lý truy vấn phân tán II. XỬ LÝ TRUY VẤN PHÂN TÁN 1. Phân rã truy vấn 2. Cục bộ hoá dữ liệu phân tánIII. III.TỐI ƯU TRUY VẤN PHÂN TÁN 1. Tối ưu hoá truy vấn 2. Các thuật toán tối ưu hoá truy vấn phân tán KẾT LUẬN 3MỞ ĐẦU • Vấn đề tối ưu hoá trên hệ CSDL phân tán là rất quan trọng do tính phân mảnh, nhân bản, tốn kém chi phí cho việc truyền dữ liệu. • Thuật toán tối ưu truy vấn phân tán cổ điển là vét cạn và leo đồi: – Thuật toán vét cạn không phù hợp với sự bùng nổ dữ liệu. – Thuật toán leo đồi chỉ tìm kiếm được tối ưu cục bộ. • Để khắc phục, các giải thuật tìm kiếm ngẫu nhiên và Heuristic được đề xuất có thể tìm ra các giải pháp gần tối ưu chấp nhận được. 4I. TỔNG QUAN VỀ XỬ LÝ TRUY VẤN PHÂN TÁN Xét một CSDL mẫu mô hình hoá cho một công ty máy tính. Các thuộc tính của CSDL bao gồm: ENO: mã số nhân viên ENAME: tên nhân viên TITLE: chức vụ trong công ty SALE: mức lương RESP: nhiệm vụ trong dự án DUR: thời gian được phân công trong dự án PNO: mã số dự án PNAME: tên dự án BUDGET: ngân sách dự án BÀI TOÁN XỬ LÝ TRUY VẤN PHÂN TÁN 5CÁC QUAN HỆ Đà CHUẨN HOÁ EMP ASG ENO ENAME TITLE ENO PNO RESP DUR E1 E2 E3 E4 E5 E6 E7 E8 J. Doe M. Smith A. Lee J. Miller B. Casey L. Chu R. David J. Jones Elect. Eng. Syst. Anal. Mech. Eng. Programmer Syst. Anal. Elect. Eng. Mech. Eng. Syst. Anal. E1 E2 E2 E3 E3 E4 E5 E6 E7 E8 P1 P1 P2 P3 P4 P2 P2 P4 P3 P3 Manager Analyst Analyst Consultant Engineer Programmer Manager Manager Engineer Manager 12 24 6 10 48 18 24 48 36 40 PROJ PAY PNO PNAME BUDGET TITLE SAL P1 P2 P3 P4 Instrumentation Database Develop CAD/CAM Maintenance 150000 135000 250000 310000 Elect. Eng. Syst. Anal. Mech. Eng. Programmer 40000 34000 27000 24000 6CHỌN LỰA CHIẾN LƯỢC SELECT ENAME FROM EMP, ASG WHERE EMP.ENO = ASG.ENO AND DUR > 37 Chiến lược 1 πENAME(σDUR>37 ∧ EMP.ENO=ASG.ENO(EMP x ASG)) Chiến lược 2 πENAME(EMP ENO (σDUR>37 (ASG))) Chiến lược 2 tránh được việc sử dụng tích Descartes nên “tốt hơn” 7CÁC CHIẾN LƯỢC THỰC THI TRUY VẤN TƯƠNG ĐƯƠNG Site 1 Site 2 Site 3 Site 4 Site 5 EMP1=σENO≤“E3”(EMP) EMP2=σENO>“E3”(EMP)ASG2=σENO>“E3”(ASG)ASG1=σENO≤“E3”(ASG) Result Site 4 result1 = EMP1’∪EMP2’ Site 3 Site 1 Site 2 EMP2’=EMP2 ENOASG2’EMP1’=EMP1 ENOASG1’ ASG1’=σDUR>37(ASG1) ASG2’=σDUR>37(ASG2) Site 5 ASG2’ASG1’ EMP1’ EMP2’ Chiến lược 2a Site 5 Site 1 Site 2 Site 3 Site 4 ASG1 EMP1 EMP2ASG2 result2=(EMP1∪EMP2) ENOσDUR>37(ASG1∪ASG2) Chiến lược 2b 8CHI PHÍ CỦA CÁC CHIẾN LƯỢC Giả sử • size(EMP) = 400, size(ASG) = 1000 • Chi phí truy xuất 1 bộ TA = 1; Chi phí truyền 1 bộ TT = 10 Chiến lược 2a 1. Tạo ASG’ bằng cách chọn trên ASG: (10 + 10) * TA = 20 2. Truyền ASG’ đến các vị trí (site) của EMP: (10 + 10) * TT = 200 3. Tạo EMP’ bằng cách nối ASG’ và EMP’: (10 + 10) * TA * 2 = 40 4. Truyền EMP’ đến vị trí (site) nhận kết quả: (10 + 10) * TT = 200 Tổng chi phí 460 Chiến lược 2b 1. Truyền EMP đến vị trí (site) 5: 400 * TT = 4,000 2. Truyền ASG đến vị trí (site) 5: 1000 * TT = 10,000 3. Tạo ASG’ bằng cách chọn trên ASG: 1000 * TA = 1,000 4. Nối EMP và ASG’: 400 * 20 * TA = 8,000 Tổng chi phí 23,000 9MỤC TIÊU CỦA TỐI ƯU TRUY VẤN • Cực tiểu hàm chi phí truy vấn Chi phí I/O + chi phí CPU + chi phí truyền thông Có những khác biệt về trọng số trong những môi trường phân tán khác nhau. • Mạng diện rộng - Chi phí truyền thông có ảnh hưởng lớn Œ Dải thông thấp Œ Tốc độ thấp - Hầu hết các giải thuật đều bỏ qua các thành phần chi phí khác trong quá trình xử lý cục bộ • Mạng cục bộ - Chi phí truyền thông không có ảnh hưởng lớn - Hàm chi phí tổng cộng cần phải được xem xét 10 ĐỘ PHỨC TẠP CỦA CÁC PHÉP TOÁN QUAN HỆ Giả sử số quan hệ của lực lượng là n 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*logn) Nối Nối nửa Chia Các phép toán tập hợp O(n*logn) Tích Descartes O(n2) 11 CÁC KIỂU TỐI ƯU • Giải thuật tìm kiếm vét cạn - Dựa trên chi phí - Tối ưu - Tổ hợp phức tạp trong một số quan hệ • Giải thuật Heuristics - Không tối ưu - Nhóm lại các biểu thức con chung - Thực hiện các phép chọn và chiếu trước - Thay thế các nối bằng một tổ hợp các nối nửa - Sắp xếp lại thứ tự thực hiện các phép toán để giảm các quan hệ trung gian - Tối ưu các phép toán riêng lẻ 12 THỜI ĐIỂM TỐI ƯU • Tĩnh - Biên dịch→ tối ưu hoá trước khi thực hiện truy vấn - Khó khăn trong việc ước lượng kích thước của các kết quả trung gian → lỗi truyền - Có thể truyền lại cho nhiều thực thi khác - R* • Động - Tối ưu hoá trong khi thực hiện truy vấn - Thông tin chính xác về kích thước của các quan hệ trung gian - Phải tối ưu lại với các thực thi bội nên tốn nhiều chi phí - INGRES • Lai (hỗn hợp) - Biên dịch sử dụng một giải thuật tĩnh - Nếu xảy ra lỗi do việc ước lượng kích thước > ngưỡng, phải tối ưu hoá lại lúc chạy chương trình 13 VỊ TRÍ QUYẾT ĐỊNH • Tập trung - Chỉ một vị trí xác định chiến lược tốt nhất - Đơn giản - Cần tri thức về CSDL phân tán toàn vẹn • Phân tán - Nhiều vị trí tham gia vào quá trình chọn ra chiến lược tốt nhất - Chỉ cần thông tin về vị trí • Lai (Hỗn hợp) - Một ví trí xác định các quyết định chính - Các vị trí khác đưa ra chọn lựa cục bộ - System R* 14 CẤU HÌNH MẠNG • Mạng diện rộng (WAN) - Đặc điểm Œ Dải thông thấp Œ Tốc độ thấp - Chi phí truyền thông chiếm ưu thế, có thể bỏ qua các nhân tố chi phí khác - Sắp xếp toàn thể để tối ưu hoá chi phí truyền thông - Sắp xếp cục bộ kéo theo tối ưu truy vấn tập trung • Mạng cục bộ (LAN) - Chi phí truyền thông không đáng kể - Hàm tổng chi phí phải được xem xét 15 CÁC TẦNG XỬ LÝ TRUY VẤN PHÂN TÁN Truy vấn dạng phép tính trên các quan hệ phân tán Vị trí điều khiển Các vị trí cục bộ Phân rã truy vấnPhân rã truy vấn Cục bộ hoá dữ liệuCục bộ hoá dữ liệu Truy vấn dạng đại số trên các quan hệ phân tán Tối ưu hoá toàn cụcTối ưu hoá toàn cục Truy vấn theo mảnh Tối ưu hoá cục bộTối ưu hoá cục bộ Truy vấn theo mảnh đã tối ưu cùng với các phép toán truyền Các truy vấn cục bộ đã tối ưu Lược đồ toàn cục Lược đồ toàn cục Lược đồ mảnh Lược đồ mảnh Số liệu trên các mảnh Số liệu trên các mảnh Lược đồ cục bộ Lược đồ cục bộ 16 II. XỬ LÝ TRUY VẤN PHÂN TÁN 1. PHÂN Rà TRUY VẤN • Chuẩn hoá - Biến đổi câu truy vấn thành dạng chuẩn để xử lý tiếp • Phân tích - Tìm và loại bỏ các truy vấn không đúng hoặc không cần thiết - Có thể chỉ có một tập con của quan hệ toán • Loại bỏ dư thừa - Loại các vị từ thừa • Viết lại câu truy vấn - Truy vấn phép toán quan hệ  truy vấn đại số quan hệ - Cấu trúc lại câu truy vấn đại số - Sử dụng các quy tắc biến đổi 17 CHUẨN HOÁ DỮ LIỆU • Phân tích cú pháp và từ vựng - Kiểm tra tính hợp lệ (tương tự bộ biên dịch) - Kiểm tra các thuộc tính và quan hệ • Đưa vào dạng chuẩn - Dạng chuẩn hội (p11 ∨ p12 ∨∨ p1n) ∧∧ (pm1 ∨ pm2 ∨ ∨ pmn) - Dạng chuẩn tuyển (p11 ∧ p12 ∧∧ p1n) ∨∨ (pm1 ∧ pm2 ∧∧ pmn) - OR (∨) được ánh xạ vào phép hội - AND (∧) được ánh xạ vào phép nối và chọn 18 PHÂN TÍCH • Loại bỏ những câu truy vấn sai • Sai kiểu - Nếu có bất kỳ thuộc tính hoặc tên quan hệ trong câu truy vấn chưa được khai báo trong lược đồ toàn cục. - Nếu các phép toán áp dụng cho các thuộc tính có kiểu không thích hợp • Sai nghĩa - Các thành phần của nó không tham gia vào việc tạo ra kết quả - Các câu truy vấn không chứa các tuyển và phủ định - Để tìm kiếm câu truy vấn sai, sử dụng: ƒ Đồ thị truy vấn ƒ Đồ thị kết nối 19 PHÂN TÍCH – VÍ DỤ SELECT ENAME,RESP FROM EMP, ASG, PROJ WHERE EMP.ENO = ASG.ENO AND ASG.PNO = PROJ.PNO AND PNAME = "CAD/CAM" AND DUR ≥ 36 AND TITLE = "Programmer" Đồ thị truy vấn Đồ thị kết nối DUR≥36 PNAME=“CAD/CAM” ENAME EMP.ENO=ASG.ENO ASG.PNO=PROJ.PNO RESULT TITLE = “Programmer” RESP ASG.PNO=PROJ.PNOEMP.ENO=ASG.ENO ASG PROJEMP EMP PROJ ASG 20 PHÂN TÍCH Nếu đồ thị truy vấn không liên thông, truy vấn bị sai. SELECT ENAME,RESP FROM EMP, ASG, PROJ WHERE EMP.ENO = ASG.ENO AND PNAME = "CAD/CAM" AND DUR ≥ 36 AND TITLE = "Programmer" PNAME=“CAD/CAM” ENAME RESULT RESP ASG PROJEMP DUR≥36 EMP.ENO=ASG.ENO ASG.PNO=PROJ.PNO TITLE = “Programmer” 21 LOẠI BỎ DƯ THỪA – VÍ DỤ SELECT TITLE FROM EMP WHERE EMP.ENAME = “J. Doe” OR (NOT(EMP.TITLE = “Programmer”) AND (EMP.TITLE = “Programmer” OR EMP.TITLE = “Elect. Eng.”) AND NOT(EMP.TITLE = “Elect. Eng.”)) Ø SELECT TITLE FROM EMP WHERE EMP.ENAME = “J. Doe” 22 VIẾT LẠI CÂU TRUY VẤN • Biến đổi câu truy vấn từ phép tính quan hệ thành đại số quan hệ • Tạo cây truy vấn • Ví dụ “Tìm tên các nhân viên trừ J. Doe đã làm cho dự án CAD/CAM trong một hoặc hai năm” SELECT ENAME FROM EMP, ASG, PROJ WHERE EMP.ENO = ASG.ENO AND ASG.PNO = PROJ.PNO AND ENAME ≠ “J. Doe” AND PNAME = “CAD/CAM” AND (DUR = 12 OR DUR = 24) ΠENAME σDUR=12 OR DUR=24 σPNAME=“CAD/CAM” σENAME≠“J. DOE” PROJ ASG EMP Project Select Join PNO ENO 23 VIẾT LẠI CÂU TRUY VẤN ΠENAME σPNAME=“CAD/CAM” ∧ (DUR=12 ∨ DUR=24) ∧ ENAME ≠ “J. DOE” × PROJASG EMP PNO ∧ ENO EMP ΠENAME σENAME ≠ "J. Doe" ASGPROJ ΠPNO,ENAME σPNAME = "CAD/CAM" ΠPNO σDUR =12 ∧ DUR=24 ΠPNO,ENO ΠPNO,ENAME PNO ENO Cây toán tử đã được viết lại Cây toán tử tương đương 24 CỤC BỘ HOÁ DỮ LIỆU PHÂN TÁN Giả sử – EMP được tách thành ba mảnh ngang EMP1, EMP2, EMP3 như sau: • EMP1= σ ENO≤“E3”(EMP) • EMP2= σ“E3”<ENO≤“E6”(EMP) • EMP3= σ ENO≥“E6”(EMP) – ASG được tách thành hai mảnh ngang ASG1 and ASG2 như sau: • ASG1= σ ENO≤“E3”(ASG) • ASG2= σ ENO>“E3”(ASG) Thay thế EMP bằng (EMP1 ∪ EMP2 ∪ EMP3 ) và ASG bằng (ASG1 ∪ ASG2) trong câu truy vấn ΠENAME σDUR=12 OR DUR=24 σPNAME=“CAD/CAM” σENAME≠“J. DOE” PROJ ∪ ∪ EMP1 EMP2 EMP3 ASG1 ASG2 PNO ENO 25 RÚT GỌN CHO PHÂN MẢNH NGANG Rút gọn với phép chọn Cho quan hệ R và FR = {R1, R2, , Rw} trong đó Rj= σpj(R) σpi(Rj)= φ nếu ∀x thuộc R: ¬(pi(x) ∧ pj(x)) Ví dụ: SELECT * FROM EMP WHERE ENO=“E5” σ ENO=“E5” ∪ EMP1 EMP2 EMP3 EMP2 σ ENO=“E5” 26 RÚT GỌN CHO PHÂN MẢNH NGANG Rút gọn với nối Ví dụ: Giả sử EMP được phân mảnh thành ASG1: σ ENO ≤ "E3"(ASG); ASG2: σ ENO > "E3"(ASG) Xem câu truy vấn SELECT * FROM EMP, ASG WHERE EMP.ENO=ASG.ENO ∪ ∪ EMP1 EMP2 EMP3 ASG1 ASG2 ENO Truy vấn gốc 27 RÚT GỌN CHO PHÂN MẢNH NGANG – Phân phối nối trên hợp – Áp dụng quy tắc rút gọn ∪ EMP1 ASG1 EMP2 ASG2 EMP3 ASG2 ENO ENO ENO Truy vấn đã rút gọn 28 RÚT GỌN CHO PHÂN MẢNH DỌC Tìm các quan hệ trung gian vô dụng (không rổng) Quan hệ R được định nghĩa trên các thuộc tính A = {A1, ..., An} và được phân mảnh dọc thành Ri = ΠA' (R) trong đó A' ⊆ A: ΠD,K(Ri) là vô dụng nếu tập các thuộc tính chiếu D không trong A' Ví dụ: EMP1= ΠENO,ENAME (EMP) EMP2= ΠENO,TITLE (EMP) SELECT ENAME FROM EMP ΠENAME EMP1EMP1 EMP2 ΠENAME ⇒ENO 29 RÚT GỌN CHO PHÂN MẢNH DẪN XUẤT Quy tắc – Phân phối các nối trên hợp – Áp dụng việc loại bỏ các nối trên phân mảnh ngang Ví dụ ASG1 = ASG ENO EMP1 ASG2 = ASG ENO EMP2 EMP1 = σ TITLE=“Programmer” (EMP) EMP2 = σ TITLE=“Programmer” (EMP) Truy vấn SELECT * FROM EMP, ASG WHERE ASG.ENO = EMP.ENO AND EMP.TITLE = “Mech. Eng.” 30 RÚT GỌN CHO PHÂN MẢNH DẪN XUẤT Truy vấn gốc Phép chọn trước ∪ ∪ ASG1 σ TITLE=“Mech. Eng.” ASG2 EMP1 EMP2 ∪ ASG1 ASG2 EMP2 σ TITLE=“Mech. Eng.” ENO ENO 31 RÚT GỌN CHO PHÂN MẢNH DẪN XUẤT Nối trên các hợp ∪ ASG1 EMP2 Loại bỏ các quan hệ trung gian rỗng (loại bỏ cây con trái) EMP2 σ TITLE=“Mech. Eng.” ASG2 σ TITLE=“Mech. Eng.” ASG2 EMP2 σ TITLE=“Mech. Eng.” ENO ENO ENO 32 RÚT GỌN CHO PHÂN MẢNH HỖN HỢP Kết hợp các quy tắc đã có: • Loại bỏ các quan hệ rỗng được tạo ra bởi các phép chọn mâu thuẫn trên các mảnh ngang; • Loại bỏ các quan hệ vô dụng được tạo ra từ các phép chiếu trên các mảnh dọc; • Phân phối các nối cho các hợp nhằm cô lập và loại bỏ các nối vô dụng. 33 RÚT GỌN CHO PHÂN MẢNH HỖN HỢP Ví dụ – Giả sử có phân mảnh hỗn hợp sau: EMP1= σ ENO≤"E4" (ΠENO,ENAME (EMP)) EMP2= σ ENO>"E4" (ΠENO,ENAME (EMP)) EMP3= ΠENO,TITLE (EMP) – Và câu truy vấn SELECT ENAME FROM EMP WHERE ENO=“E5” EMP2 σ ENO=“E5” ΠENAME Ä EMP1 EMP2 ∪ EMP3 σ ENO=“E5” ΠENAME ENO 34 III. TỐI ƯU TRUY VẤN PHÂN TÁN Input: Truy vấn phân mảnh Tìm kế hoạch tổng quát tốt nhất (không nhất thiết phải tối ưu) – Cực tiểu hoá hàm chi phí – Xử lý các nối phân tán, sử dụng nối nửa. – Phương pháp nối: Lặp lồng và thứ tự nối (nối trộn và nối băm) Không gian tìm kiếm – Tập của các biểu thức đại số tương đương (các cây truy vấn). Hàm chi phí (trong quan hệ thời gian) – Chi phí I/O + chi phí CPU + chi phí truyền Thuật toán tìm kiếm – Di chuyển bên trong không gian tìm kiếm – Các thuật giải heuristic (lặp cải tiến, mô phỏng luyện thép, di truyền,) 35 TỐI ƯU HOÁ TRUY VẤN Tạo ra không gian tìm kiếm Search Strategy QEP tương đương Câu truy vấn Quy tắc biến đổi Mô hình chi phí QEP tốt nhất 36 KHÔNG GIAN TÌM KIẾM PROJ ASGEMP Không gian tìm kiếm đặc trưng bởi việc chọn lựa hoạch định thực thi Trọng tâm trên cây nối Với N quan hệ, có O(N!) cây nối tương đương có thể thu được bằng cách áp dụng các quy tắc giao hoán và kết hợp SELECT ENAME,RESP FROM EMP, ASG, PROJ WHERE EMP.ENO=ASG.ENO AND ASG.PNO=PROJ.PNO PROJ ASG EMP PROJ ASG EMP × ENO ENO PNO PNO ENO,PNO 37 CHIẾN LƯỢC TÌM KIẾM Cách di chuyển trong không gian tìm kiếm Đơn định – Bắt đầu từ các quan hệ cơ sở và xây dựng các hoạch định bằng cách thêm vào một quan hệ ở mỗi bước – Quy hoạch động: theo chiều ngang – Thuật toán thiển cận: theo chiều sâu Ngẫu nhiên – Tìm kiếm lời giải tối ưu xung quanh một số điểm đặc biệt – Đánh đổi thời gian tối ưu với thời gian thực thi – Tốt nhất khi số quan hệ lớn hơn 5-6 – Mô phỏng luyện thép (Simulated Annealing) – Lặp cải tiến (Iterative improvement) 38 CHIẾN LƯỢC TÌM KIẾM Đơn định Ngẫu nhiên R2R1 R3 R3R1 R2 R2R1 R3 R4 R2R1 R2R1 R3 39 MÔ HÌNH CHI PHÍ PHÂN TÁN • Tổng thời gian (hay Tổng chi phí): Tổng các thành phần chi phí • Thời gian đáp ứng: Thời gian tính từ khi khởi hoạt cho đến khi hoàn thành câu truy vấn • Mạng diện rộng WAN – Khởi tạo và truyền thông điệp với chi phí cao – Xử lý cục bộ có chi phí thấp (với mainframes hoặc minicomputers) – Tỷ lệ truyền và thời gian xuất nhập có chi phí = 20:1 • Mạng cục bộ LAN – Phải xét cả chi phí cục bộ lẫn chi phí truyền – Tỷ lệ = 1:1.6 40 CÁC THUẬT TOÁN TỐI ƯU TRUY VẤN PHÂN TÁN Ba thuật toán cơ bản đại diện cho nhiều lớp thuật toán khác nhau là: • Ingres phân tán • System R* • SDD-1 • Ingres dùng thời điểm tối ưu hoá động còn các hệ kia dùng thời điểm tĩnh. • Hàm chi phí của SDD-1 và R* là hạ thấp tối đa tổng thời gian, còn Ingres phân tán là giảm tổ hợp thời gian đáp ứng và tổng thời gian. • Cấu hình mạng được giả thiết là mạng diện rộng điểm - điểm theo SDD-1. Các thuật toán Ingres và R* có thể thực thi trên cả mạng LAN và WAN. • SDD-1 sử dụng nối nửa như một kỹ thuật tối ưu hoá. • Ingres có thể xử lý các mảnh. 41 THUẬT TOÁN INGRES PHÂN TÁN Nguyên liệu: MRQ (Multi Relation Query, truy vấn đa quan hệ) Thành phẩm: kết quả cuối cùng của truy vấn đa quan hệ Begin {thực hiện mọi truy vấn một quan hệ} For mỗi ORQi khả tách trong MRQ do Run(ORQi) End For {thay MRQ bằng một danh sách có n truy vấn đã tối giản (bất khả tách)} MRQ’_list← REDUCE(MRQ) 42 THUẬT TOÁN INGRES PHÂN TÁN (tt) While n 0 do Begin {chọn một truy vấn bất khả tách có chứa các mảnh nhỏ nhất} MRQ’← SELECT_QUERY(MRQ’_list) {xác định các mảnh cần truyền và vị trí xử lý cho MRQ’} Fragment_site_list ← SELECT_STRATEGY(MRQ’) For mỗi cặp (F, S) trong Fragment_site_list do di_chuyển_mảnh_F_đến_vị_trí_S End For run(MRQ’) dec(n) End While {MRQ’ cuối cùng là thành phẩm} End. 43 THUẬT TOÁN SYSTEM R* Nguyên liệu: QT (Query Tree, cây truy vấn) Thành phẩm: strat (chiến lược có chi phí nhỏ nhất) Begin For mỗi quan hệ Ri ∈ QT do Begin For mỗi đường truy xuất Apij đến Ri do xác định cost(Apij); End For; best_Api← Apij có chi phí nhỏ nhất End; 44 THUẬT TOÁN SYSTEM R* (tt) For mỗi thứ tự (Ri1, Ri2, , Rin) với i = 1, , n! do Begin xây dựng chiến lược (((best_Api1 Ri2) Ri3) Rin) tính chi phí của chiến lược End For strat← chiến lược có chi phí nhỏ nhất For mỗi vị trí k có lưu quan hệ có mặt trong QT do Begin LSk← chiến lược cục bộ (chiến lược, k) {mỗi chiến lược cục bộ được tối ưu hoá tại vị trí k} send(LSk, vị trí k) End For; End. 45 THUẬT TOÁN SDD-1 Nguyên liệu: QG: đồ thị truy vấn có n quan hệ; số liệu thống kê cho mỗi quan hệ; Thành phẩm: ES: chiến lược thực thi truy vấn Begin ES← thao tác cục bộ (QG) sửa lại số liệu thống kê để phản ánh tác dụng của xử lý cục bộ BS← ∅ {tập các nối nửa lợi ích} For mỗi nối nửa SJ trong QG do If cost(SJ) < benefit(SJ) then BS← BS ∪ SJ End If End For While BS ∅ do {chọn các nối nửa lợi ích} 46 THUẬT TOÁN SDD-1 (tt) Begin SJ← most_benefit(BS) BS← BS – SJ ES← ES + SJ sửa lại số liệu thống kê để phản ánh tác dụng của việc gắn SJ BS← BS – các nối nửa không lợi ích BS← BS ∪ các nối nửa lợi ích mới End While; AS(ES)← chọn vị trí i sao cho i có chứa dữ liệu lớn nhất sau khi thực hiện tất cả mọi thao tác cục bộ ES← ES ∪ truyền các quan hệ trung gian đến AS(ES) For mỗi quan hệ Ri tại AS(ES) do For mỗi nối nửa SJ của Ri với Rj do If cost(ES) > cost(ES – SJ) then ES← ES – SJ End If End For End For End. 47 SO SÁNH CÁC THUẬT TOÁN TỐI ƯU HOÁ Thuật toán Thời điểm tối ưu Hàm mục tiêu Hệ số tối ưu hoá Topo mạng Nối nửa Số liệu thống kê Phân mảnh Dist. INGRES Động Thời gian đáp ứng hoặc tổng chi phí Kích thước TB, chi phí xử lý Tổng quát hoặc phát tán Không 1 Ngang R* Tĩnh Tổng chi phí Lượng TB, kích thước TB, IO, CPU Tổng quát hoặc cục bộ Không 1, 2 Không SDD-1 Tĩnh Tổng chi phí Kích thước TB Tổng quát Có 1, 3, 4, 5 Không 1. Lực lượng của quan hệ; 2. Số giá trị duy nhất của mỗi thuộc tính; 3. Hệ số tuyển chọn nối; 4. Kích thước của nối trong mỗi thuộc tính nối; 5. Kích thước thuộc tính và kích thước bộ 48 KẾT LUẬN • Mục tiêu của việc xử lý truy vấn phân tán là hạ thấp tối đa hàm chi phí • Nguyên liệu quan trọng của bài toán tối ưu truy vấn là số liệu thống kê CSDL và các công thức dùng để đánh giá kích thước các kết quả trung gian. • Phép toán quan trọng nhất trong xử lý truy vấn phân tán là phép toán nối. • Việc sử dụng thuật toán nào là còn tuỳ theo từng điều kiện cụ thể: – Với mạng diện rộng WAN, nên sử dụng thuật toán SDD-1. – Với mạng cục bộ LAN, có thể dùng thuật toán D-Ingres hoặc R* do không sử dụng các nối nửa, trong đó ƒ D-Ingres tối ưu động thích hợp với phân mảnh ngang ƒ R* tối ưu tĩnh thích hợp với các truy vấn được dùng thường xuyên. 49 TÀI LIỆU THAM KHẢO [1] Fragkiskos Pentaris; Distributed Query Optimization by Query Trading; 2006. [2] Ravindra Guravannavar, Ramanujam H.S.; Optimizing Nested Queries with Parameter Sort Orders; 2006. [3] Fabio Porto; Distributed Query Processing; 2005. [4] Farnoush Banaei-Kashani; Distributed Databases; 2005. [5] Yongluan Zou, Beng Chin Ooi; An Adaptable Distributed Query Processing; 2005. [6] Đỗ Phúc; Bài giảng môn học Cơ sở dữ liệu nâng cao; 2004. [7] Donald Kossmann; The State of Art in Distributed Query Processing; 2000. [8] M. Tamer Ozsu, Patrick Valduriez; Principles of Distributed Database Systems; 1999.