Tối ưu hóa các truy vấn phân tán
tải về 54.21 Kb.
|
- Điều hướng trang này:
- Thuật toán tối ưu hóa truy vấn phân tán SDD-1
8.4 Tối ưu hóa các truy vấn phân tánTối ưu hóa các truy vấn phân tán được thực hiện thống qua các giải thuật tối ưu hóa. Các giải thuật này có thể phân thành 4 hướng tiếp cận chính bao gồm: hướng tiếp cận sử dụng phép toán bán kết nối (semijoin), hướng tiếp cận tĩnh (static approach), hướng tiếp cận động (dynamic approach) và hướng tiếp cận kết hợp (hybrid approach). Trong phần này, nhóm em sẽ đi sâu trình bày 3 giải thuật chính đại diện cho ba hướng tiếp cận đầu tiên. Hướng tiếp cận cuối cùng là xuy hướng trong đó các giải thuật của ba hướng tiếp cận đầu tiên được sử dụng kết hợp nhằm mục tiêu tăng độ tối ưu và thường gắn với một thiết kế CSDLPT cụ thể. Thuật toán tối ưu hóa truy vấn phân tán SDD-1Ý tưởng chính của thuật toán là dựa trên phép toán bán kết nối. Phép kết nối làm việc như một thuật toán rút gọn kích thước cho một quan hệ trước khi truyền. Kết nối 2 quan hệ R và S trên thuộc tính A, lưu tại trạm 1 và trạm 2 tương ứng, có thể tính toán bằng cách thay một hoặc 2 toán hạng quan hệ bởi phép bán kết nối với các quan hệ khác, sử dụng các quy tắc sau: Việc chọn một trong ba chiến lược bán kết nối trên đòi hỏi đánh giá các chi phí tương ứng của chúng. Sử dụng phép bán kết nối có lợi khi chi phó kết xuất và truyền nó tới trạm khác là nhỏ hơn chi phí truyền toàn bộ toán hạng quan hệ và thực hiện phép kết nối. Để thấy được lợi ích tiềm tang của phép bán kết nối, ta so sánh chi phí của hai lựa chọn R A S và , giả sử size(R) Chương trình sử dụng phép bán kết nối sau: ∏A (S) trạm 1. Trạm 1 tính toán R’ trạm 2 Trạm 2 tính toán Cách tiếp cận bán kết nối là tốt nếu: Cách tiếp cận bán kết nối là tốt hơn nếu phép bán kết nối hoạt động như một toán tử rút gọn đầy đủ, tức là nếu một số ít bộ của R tham gia vào kết nối. Thuật toán SDD-1: Thuật toán sử dụng phép bán kết nối, hàm mục tiêu tối thiểu tổng chi phí truyền thông (chi phí địa phương và thời gian trả lời không được xét). Bước chính của thuật toán bao gồm việc xác định và sắp thứ tự các phép kết nối có lợi, tức là các phép bán kết nối có chi phí nhỏ hơn lợi ích của nó. Để chọn ra phép bán kết nối hiệu quả, thuật toán sử dụng các đánh giá về chi phí (cost) và lợi ích (benefit) được xác định như sau: + Chi phí truyền của phép bán kết nối: Cost(Râ A S)=CMSG + CTR * size( ∏A (S) ) + Đánh giá về lợi ích: Benefit(Râ A S)=(1 – SFSJ(S.A)) * size(R) * CTR Thuật toán SDD-1 nhận đầu vào là đồ thị câu truy vấn với n quan hệ, các thống kê cơ sở dữ liệu của mỗi quan hệ. Đầu ra của thuật toán là chiến lược để thực thi câu truy vấn. Thuật toán được tiến hành theo 4 giai đoạn: khởi đầu, chọn các phép bán kết nối có lợi, chọn trạm thực hiện và tối ưu hóa. Thuật toán SDD – 1 – QOA: tải về 54.21 Kb. Chia sẻ với bạn bè của bạn:
|