Rút Gọn Cho Phân Mảnh Ngang Dẫn Xuất

vô dụng được bỏ đi khi các lượng từ hoá của các mảnh có mâu thuẫn.

Ví dụ 2.9: Cho 2 quan hệ NV(MaNV, TênNV, CVụ) và PC (MaNV, MaDA, NVụ, Tg) được phân mảnh tương ứng như sau:

NV1 = MaNV  E3 (NV) PC1 = MaNV  E3 (PC)

NV2 = E3 < MaNV  E6 (NV) PC2 = MaNV > E3 (PC) NV3 = MaNV > E6 (NV)

NV1 và PC1 cùng định nghĩa bởi vị từ MaNV ≤ E3. Vị từ định nghĩa trong PC2 là hợp của các vị từ được định nghĩa trong NV2 và NV3:

MaNV > E3 = (E3 < MaNV ≤ E6)  (MaNV > E6)

Xét câu truy vấn sau: Select * From NV, PC

Where NV.MaNV = PC.MaNV



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

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



PC2 NV1 NV2

NV3

Câu truy vấn được rút gọn bằng cách phân phối các nối trên các hợp và áp dụng quy tắc: Ri Rj =  nếu x thuộc Ri , y thuộc Rj:  ( pi(x) ʌ pj(y)) có thể cài đặt như hợp của ba nối từng phần được thực hiện song song.

PC1



PC1 NV1 PC2 NV2 PC3 NV3

a. Cây đại số quan hệ truy vấn gốc b. Rút gọn phân mảnh ngang với phép

kết nối

Hình 2.10: Rút gọn phân mảnh ngang

2.2.2.2. Rút gọn cho phân mảnh dọc.

Phân mảnh dọc phân tán một quan hệ dựa trên các thuộc tính chiếu. Vì vậy, phép kết nối sẽ là phép toán tái xây dựng các phân mảnh dọc. Chương trình cục bộ hoá cho một quan hệ phân mảnh dọc bao gồm các kết nối của các mảnh theo thuộc tính chung.

Ví dụ 2.10: Giả sử quan hệ NV(MaNV, TênNV, CVụ) được phân mảnh như sau:

NV1 = MaNV, TênNV(NV) NV2 = MaNV, CVụ(NV)

Khi đó chương trình cục bộ hoá cho quan hệ phân mảnh dọc là: NV = NV1 NV2

Cũng như phân mảnh ngang, các câu truy vấn trên các mảnh dọc được rút

gọn bằng cách xác định các quan hệ trung gian vô dụng và loại bỏ các cây con đã sinh ra chúng. Cho quan hệ R định nghĩa trên tập các thuộc tính A= {A1, A2, ...} và được phân mảnh dọc thành Ri = A‟(R) trong đó A‟  A. Quy tắc được phát biểu một cách hình thức như sau:

D,A‟(Ri) là vô dụng nếu tập thuộc tính chiếu D không thuộc A‟

Ví dụ 2.11: Cho quan hệ NV(MaNV, TênNV, CVụ) được phân mảnh dọc thành:

NV1 = MaNV, TênNV(NV) NV2 = MaNV, CVụ(NV)

Xét câu truy vấn:

Select TênNV From NV

Bằng cách hoán vị phép chiếu và phép kết nối, nghĩa là thực hiện phép chiếu trên thuộc tính TenNV. Khi đó, có thể nhận thấy rằng phép chiếu trên thuộc tính TenNV trên quan hệ NV2 là vô dụng, vì TenNV không phải thuộc tính của NV2. Vì vậy, phép chiếu chỉ cần thực hiện trên NV1 (xem Hình 2.11)

NV1

NV2

TênNV

NV1

TênNV

Hình 2.11: Rút gọn phân mảnh dọc

2.2.2.3. Rút gọn cho phân mảnh ngang dẫn xuất

Phân mảnh ngang dẫn xuất là một cách để phân phối hai quan hệ mà nhờ đó có thể cải thiện khả năng xử lý các điểm giao nhau giữa phép chọn và phép nối.

Nếu quan hệ R phải phân mảnh dẫn xuất theo quan hệ S, các mảnh của R và S giống nhau ở thuộc tính kết nối sẽ nằm cùng vị trí. Ngoài ra, S có thể được phân mảnh theo vị từ chọn.

Vì các bộ của quan hệ R được đặt tùy chọn theo các bộ của S. Để đơn giản, giả sử chỉ xét mảnh dẫn xuất chỉ được sử dụng cho mối liên hệ một – nhiều, trong đó một bộ của S tương ứng với n bộ của R và một bộ của R chỉ khớp đúng một bộ của S

Ví dụ 2.12: Cho mối quan hệ một – nhiều NV  PC. Giả sử các quan hệ được phân mảnh như sau:

NV(MaNV, TênNV, CVụ)

PC(MaNV, MaDA, NVụ, Tg)

NV1= Cvụ=‟TP‟(NV) NV2 = Cvụ‟TP‟(NV) PC1 = PC NV1

PC2 = PC NV2

Xét câu truy vấn “Đưa ra tất cả các thuộc tính của NV, PC với NVụ =”PP””, dạng SQL như sau:

Select *

From NV, PC

Where NV.MaNV = PC.MaNV and NV.CVụ = ”PP”

b. Câu truy vấn gốc

Câu truy vấn trên các mảnh NV1, NV2, PC1, PC2 đã được định nghĩa. Đẩy phép chọn xuống các mảnh NV1, NV2 câu truy vấn rút gọn lại do mâu thuẫn với vị từ chọn của NV1 = > loại bỏ NV1 (xem Hình 2.12)

MaNV

Cvụ=‟PP‟



MaNV



Cvụ=‟PP‟

NV2

PC1

PC2

NV1

NV2

PC1 PC2

a. Câu truy vấn sau khi đẩy phép chọn xuống



MaNV

PC1

Cvụ=‟PP‟

PC2

Cvụ=‟PP‟

PC2

NV2

d. Câu truy vấn đã rút gọn

NV2

c. Câu truy vấn sau khi đẩy phép hợp xuống

NV2

Hình 2.12: Rút gọn cho phân mảnh ngang dẫn xuất

2.2.2.4. Rút gọn cho phân mảnh hỗn hợp

Mục đích của phân mảnh hỗn hợp là hỗ trợ một cách hiệu quả các câu truy vấn có chứa phép chiếu, chọn và phép kết nối.

Câu truy vấn trên các mảnh hỗn hợp có thể được rút gọn bằng cách tổ hợp các quy tắc tương ứng đã được dùng trong các phân mảnh ngang nguyên thuỷ, phân mảnh dọc, phân mảnh ngang dẫn xuất.

Quy tắc:

1. Loại bỏ các quan hệ rỗng được tạo ra bởi các phép toán chọn mâu thuẫn như trên các mảnh ngang.

2. Loại bỏ các quan hệ vô dụng được tạo ra bởi các phép chiếu trên các mảnh

dọc.

3. Phân phối các kết nối cho các phép hợp nhằm cô lập và loại bỏ các kết nối

vô dụng.

Ví dụ 2.13: Cho quan hệ NV (MaNV, TênNV, CVụ) được phân mảnh hỗn hợp như sau: NV1 = MaNV  E4 (MaNV, TênNV (NV) )

NV2 = MaNV > E4 (MaNV, TênNV (NV) )

NV3 = MaNV, CVụ (NV)

Chương trình cục bộ hoá: NV = (NV1  NV2 ) NV3 Xét câu truy vấn: Tên của nhân viên có mã E5

MaNV=‟E5‟

NV2

TênNV

MaNV=‟E5‟



NV3

NV1

NV2

Câu truy vấn được rút gọn như trong Hình 2.13

a. Truy vấn gốc

b. Truy vấn đã rút gọn

Hình 2.13: Rút gọn phân mảnh hỗn hợp

2.2.3. Tối ưu hóa toàn cục

Bước này sẽ xác định thứ tự thực thi truy vấn các mảnh, trạm nào hiệu quả để truyền dữ liệu, nơi mà từng phần của câu truy vấn sẽ được thực thi.

Tối ưu hóa truy vấn là một vấn đề khó khăn trong môi trường phân tán do nhiều yếu tố như phân bổ dữ liệu, tốc độ kênh truyền, việc lập chỉ mục, tính sẵn sàng của bộ nhớ, kích thước của CSDL, việc lưu trữ các kết quả trung gian...Vai trò của bộ tối ưu truy vấn là tạo ra một kế hoạch thực thi truy vấn (query execution plan, QEP) với chi phí tối thiểu. Một bộ tối ưu truy vấn là một module phần mềm thực hiện tối ưu hóa truy vấn trên cơ sở của ba thành phần quan trọng của một truy vấn là không gian tìm kiếm, chiến lược tìm kiếm và mô hình chi phí.

CÂU TRUY VẤN

TẠO RA KHÔNG

GIAN TÌM KIẾM

QUY TẮC BIẾN ĐỔI

QEP TƯƠNG ĐƯƠNG

CHIẾN LƯỢC

TÌM KIẾM

MÔ HÌNH CHI PHÍ

QEP TỐT NHẤT

Hình 2.14: Bộ tối ưu truy vấn

2.2.3.1. Không gian tìm kiếm

Đối với một câu truy vấn đã cho, không gian tìm kiếm có thể được định nghĩa như một tập các cây toán tử tương đương, có được bằng cách áp dụng các quy tắc biến đổi. Để nêu bật các đặc trưng của bộ tối ưu hóa truy vấn, chúng ta thường tập trung các cây nối (join tree), là cây toán tử với các phép kết nối hoặc tích Đề các.

Ví dụ 2.14: Xét câu truy vấn sau: SELECT TênNV

FROM NV, PC, DA

WHERE NV.MNV=PC.MNV AND PC.MDA=DA.MDA

Hình 2.15 minh họa ba cây nối tương đương cho truy vấn trên, thu được bằng cách sử dụng tính chất kết hợp của các toán tử hai ngôi. Mỗi cây có thể được gán một chi phí dựa trên chi phí của mỗi toán tử. Cây nối (c) bắt đầu với một tích Đề các có thể có chi phí cao hơn rất nhiều so với cây còn lại.

Với một câu truy vấn có N quan hệ thì sẽ có O(N!) cây nối có thể thu được từ việc áp dụng tính giao hoán và kết hợp.

MDA

⋈

MDV ⋈

MDV

⋈

MDA ⋈

(a)

(b)

MDV, MDA

(c)

Hình 2.15: Các cây nối

Các công việc một bộ tối ưu hóa truy vấn cần thực hiện như sau:

- Xác định thứ tự thực hiện của các phép kết nối.

- Xác định phương thức truy cập các phép kết nối.

- Xác định hình dạng của cây nối trong không gian tìm kiếm có được. Nó có thể là các dạng: Linear Trees (Left Deep Trees), Right Deep trees, Bushy Join Trees, Binary Trees hoặc Zig-Zag (Xem Hình 2.14)

- Xác định thứ tự dịch chuyển của dữ liệu giữa các trạm để giảm số lượng dữ liệu và chi phí truyền thông.

Hình 2.16: Hình dáng của một số cây nối

Chiến lược tìm kiếm là muốn nói đến các thuật toán được áp dụng để xác định kế hoạch thực thi truy vấn tốt nhất từ không gian tìm kiếm giảm chi phí tối ưu hóa truy vấn. Có hai chiến lược cơ bản:

- Chiến lược xác định (Deterministic Strategy): Chiến lược này tiến hành bằng cách xây dựng các kế hoạch, bắt đầu từ các quan hệ cơ sở, sau đó nối thêm một hoặc nhiều quan hệ ở mỗi bước cho đến khi thu được mọi kế hoạch khả hữu. Để giảm chi phí tối ưu hóa, những kế hoạch không dẫn đến giải pháp tối ưu được