Tối Ưu Hóa Biểu Thức Đường Dẫn

 Gửi các đối tượng của Cj mà thỏa mãn điều kiện lọc ở trên từ R đến P, rồi từ P đến S

 Thực hiện việc truy vấn từ các đối tượng của Ci và Cj tại S

 Truyền kết quả từ S về P

o Nếu transCost (S, P) > transCost (R, P)

 Xây dựng bộ lọc Bloom cho tất cả các đối tượng thuộc lớp Cj theo giá trị thuộc tính định danh, gọi là BF(Cj).

 Gửi BF(Cj) đến P, rồi từ P gửi tiếp BF(Cj) đến S. BF(Cj) được sử dụng để lọc các đối tượng của Ci.

 Gửi các đối tượng của Ci mà thỏa mãn điều kiện lọc ở trên từ S đến P, rồi từ P đến R

 Thực hiện việc truy vấn từ các đối tượng của Ci và Cj tại R

 Truyền kết quả từ R về P

Thuật toán 3.3 – Case3(Ci, Cj, R, S, P)

Đầu vào:

- Lớp Ci ở trạm R và lớp Cj ở trạm S

- Truy vấn tại trạm P

Đầu ra:

- result là kết quả của phép nối Ci và lớp Cj tại trạm P

Các bước thực hiện:

cost1 = transCost(S,R) + transCost(R, P); cost2 = transCost(R,S) + transCost(S, P); cost3 = transCost(S,P) + transCost(R, P); cost = min(cost1, cost2, cost3);

if (min = cost1)then begin

end;

result = case1(Ci,Cj,R,S); send(result,S, P);

else if (min = cost2)then begin

result = case2(Ci,Cj,R,S); send (result,R,P);

end; else

if (transcost(S, P)<=transCost(R, P))then begin

BF(Ci)=createBloomFilter(Ci,ak); send(BF(Ci),S,P);

send(BF(Ci),P,R);

Cj’=filter(Cj, BF(Ci));

send(Cj’, R, P);

send(Cj’, P, S); result = join(Ci, Cj’);

end; else

begin

BF(Cj)=createBloomFilter(Cj,oid(Cj)); send(BF(Cj),R,P);

send(BF(Ci),P,S);

Ci’=filter(Ci, BF(Cj));

send(Ci’, S, P);

send(Ci’, P, R);

result = join(Ci’, Cj, R); send(result, R, P);

end;

end; {Thuật toán 3.3}

Thuật toán BloomOpt như sau:

Thuật toán 3.4 – BloomOpt(Ci, Cj, R, S, P)

Đầu vào:

- Lớp Ci ở trạm R và lớp Cj ở trạm S

- Truy vấn tại trạm P

Đầu ra:

- result là kết quả của phép nối Ci và lớp Cj tại trạm P

Các bước thực hiện:

if (P=R) then Case1(Ci, Cj, R, S);

else if (P=S) then Case2(Ci, Cj, R, S); else Case3(Ci, Cj, R, S, P);

end; {Thuật toán 3.4}

3.3.5. Thảo luận về các tham số

Trong phần trước chúng ta đã phân tích sai số và có công thức n = − mlnp .

(ln2)2

Khi chọn p là một sai số cố định có giá trị đủ bé thì kích thước bộ lọc Bloom n tuyến tính với số lượng các giá trị khóa, trong trường hợp này là số lượng đối tượng của lớp cần xây dựng bộ lọc Bloom (Ci hoặc Cj). Bộ lọc Bloom có thể xây dựng một lần cho mỗi lớp và sử dụng nhiều lần khi có nhiều kết nối với các lớp khác nhau.

3.4. Tối ưu hóa biểu thức đường dẫn – Thuật toán PathExpOpt

3.4.1. Đồ thị biểu diễn truy vấn dạng các biểu thức đường dẫn

Ví dụ 3.5: Truy vấn liên quan đến các lớp: DeTai (Đề tài), CanBo (Cán bộ), ToChuc (Tổ chức), DiaChi (Địa chỉ), ThanhPho (Thành phố), Sach (Sách), LoaiSach (Loại sách). Lớp DeTai có thuộc tính chuNhiem là một đối tượng của lớp CanBo. Lớp CanBo co thuộc tinh coQuan là một đối tượng của lớp ToChuc và thuộc tính tacGiaSach là một tập các đối tượng của lớp Sach. Lớp CoQuan có thuộc tính diaChi là một đối tượng của lớp DiaChi, lớp DiaChi có thuộc tính

thanhPho. Lớp Sach có thuộc tính theLoai là một đối tượng của lớp LoaiSach. Các lớp truy vấn biểu diễn như Hình 3.4.

Hình 3.4: Các lớp truy vấn

Giả sử truy vấn ở đây là liệt kê mã số và tên các đề tài mà chủ nhiệm đề tài là các cán bộ của các cơ quan thuộc thành phố Hà nội và có viết sách thuộc thể loại CNTT. Truy vấn có thể viết dưới dạng:

SELECT d.maSo, d.ten FROM DeTai as d

WHERE d.chuNhiem.coQuan.diaChi.thanhPho=”Hà nội” AND d.chuNhiem.tacGiaSach.theLoai.ten=”CNTT”

Truy vấn được biểu diễn bởi dưới dạng của một đồ thị có hướng gọi là đồ thị truy vấn. Mỗi đỉnh của đồ thị truy vấn tương ứng một lớp liên quan trong truy vấn và mỗi cạnh từ đỉnh A đến đỉnh B nghĩa là miền của thuộc tính của lớp A là lớp

B. Mỗi đỉnh có một nhãn chỉ ra trạm mà các đối tượng của lớp được lưu trữ và mỗi cạnh cũng có một nhãn biểu diễn thuộc tính phức của mối quan hệ tham chiếu. Lớp mà truy vấn hướng tới được gọi là lớp đích. Thuật toán chỉ xét trường hợp đồ thị vô hướng tương ứng với đồ thị truy vấn là một cây.

Giả sử lớp DeTai và lớp DiaChi được lưu trữ ở trạm 1, lớp CanBo được lưu trữ ở trạm 2 và lớp ToChuc được lưu trữ ở trạm 3, lớp Sach và LoaiSach được lưu trữ ở trạm 4. Lớp đích của truy vấn là lớp DeTai. Truy vấn có thể biểu diễn như một đồ thị trong Hình 3.5.

DeTai (1)

chuNhiem

CanBo (2)

ToChuc (3)

coQuan

tacGiaSach

Sach (4)

diaChi

theLoai

DiaChi (1)

LoaiSach (4)

Hình 3.5: Đồ thị truy vấn

Liệt kê các đối tượng của lớp đích đòi hỏi tất cả các đối tượng mà nó tham chiếu thông qua thuộc tính phức phải được liệt kê đệ qui. Trong cây truy vấn ở Hình 3.5, mối quan hệ tham chiếu giữa các lớp DeTai và CanBo có thể được biểu diễn như là một vị từ nối, đó là DeTai.chuNhiem = OID(CanBo). Giá trị của thuộc tính phức chuNhiem là các định danh của lớp CanBo, và vị từ này có nghĩa thao tác nối giữa lớp DeTai và CanBo sử dụng các định danh cho lớp CanBo như là giá trị thuộc tính nối.

Xem các định danh kết nối là các OID được sử dụng như là các giá trị của thuộc tính kết nối của một phép kết nối ẩn. Các định danh đối tượng cho một lớp không phải lớp gốc được sử dụng chỉ để thực hiện phép kết nối ẩn giữa lớp đó và lớp được kết nối với nó. Để giảm việc truyền dữ liệu, chỉ cần giữ lại các thuộc tính cần thiết của các lớp, đó là: định danh các lớp, các thuộc tính cần hiển thị của lớp đích, các thuộc tính nối. Sau mỗi phép kết nối sẽ bớt đi OID của lớp được nối đến nếu lớp đó không phải là lớp đích.

Để thực hiện một phép kết nối ẩn, các lớp hoặc kết quả trung gian liên quan phải ở cùng trạm. Nếu chúng không ở cùng trạm, một trong chúng phải được chuyển từ trạm này đến trạm kia hoặc cả hai phải được chuyển đến trạm thứ ba. Trong trường hợp cuối, phép kết nối ẩn trình tự con giữa kết quả trung gian của phép kết nối ẩn ở trạm thứ ba và lớp lưu trữ tại đây có thể được thực hiện mà

không cần phép truyền. Khi một lớp được truyền, chỉ các thuộc tính được giữ lại được truyền.

Như vậy, các biểu thức đường dẫn thực hiện các phép kết nối ẩn liên tiếp nhau và truyền nếu chúng bị yêu cầu để thực hiện các phép kết nối ẩn. Do đó, để thực hiện một truy vấn có hiệu quả, chúng ta phải quyết định thứ tự duyệt tốt nhất để chỉ ra trình tự thực hiện của phép kết nối ẩn và phép truyền được thực hiện với chi phí thấp nhất.

3.4.2. Mô hình tối ưu hoá truy vấn

Bộ tối ưu hoá truy vấn phân tán có thể được định nghĩa như một thuật toán để chọn ra một chiến lược cho một câu truy vấn. Thiết kế của các bộ tối ưu hoá chia thành ba thành phần:

- Không gian thực thi là tập hợp tất cả các kế hoạch thực thi

- Mô hình chi phí dự đoán chi phí của một kế hoạch thực thi

- Chiến lược tìm kiếm để đạt được kế hoạch có chi phí tối thiểu

Tập hợp tất cả các cách thực thi truy vấn gọi là không gian thực thi. Mỗi cách thực thi truy vấn bao gồm tập các phép truyền dữ liệu giữa hai trạm và phép kết nối tại một trạm.

Dựa trên chi phí của phép kết nối ẩn và phép truyền trong một kế hoạch thực thi, chúng ta tính được chi phí thực hiện theo một kế hoạch. Chi phí truyền dữ liệu theo cách tính đơn giản nhất là tích của kích thước dữ liệu và chi phí truyền một đơn vị dữ liệu giữa hai trạm. Chi phí cho phép kết nối được tính theo thuật toán kết nối, có nhiều thuật toán kết nối, trong phần này sử dụng thuật toán nối với bộ lọc Bloom đã được trình bày trong phần 3.3.

Chiến lược tìm kiếm sử dụng trong bài báo này là kỹ thuật quy hoạch động. Một bài toán quy hoạch động chia bài toán thành nhiều bài toán con, giải quyết các bài toán con một cách đệ qui, sau đó kết hợp các giải pháp để giải quyết bài toán ban đầu. Mỗi khi một bài toán con được giải quyết, câu trả lời được lưu lại để sử dụng lại trong các tính toán khác để tránh việc tính toán lại nhiều lần một

bài toán con. Dễ thấy quy hoạch động là một kỹ thuật giải quyết bài toán theo kiểu từ dưới lên.

3.4.3. Tách cây truy vấn thành các cây con cảm sinh

Nguyên lí tối ưu hóa đặt vấn đề rằng một kế hoạch thực thi tối ưu cho một truy vấn được tạo ra từ các kế hoạch thực thi tối ưu cho các truy vấn con. Và do đó, để tạo ra một kế hoạch tối ưu cho một truy vấn bởi quy hoạch động, các kế hoạch tối ưu cho các truy vấn con phải được tạo ra trước đó. Gọi truy vấn ban đầu là truy vấn n-lớp, truy vấn i-lớp là một truy vấn con của truy vấn ban đầu. Để tạo ra một kế hoạch tối ưu cho truy vấn i-lớp bởi quy hoạch động, kế hoạch tối ưu hóa cho truy vấn con của nó từ 1-lớp đến (i-1)-lớp phải được tạo ra trước. Nếu tạo ra được một kế hoạch tối ưu cho tất cả các truy vấn i-lớp (i = 1, 2,.., n), chúng ta sẽ tạo được một kế hoạch tối ưu cho truy vấn n-lớp ban đầu.

Chúng ta sẽ xét khái niệm đồ thị con cảm sinh để thấy các truy vấn con có đồ thị truy vấn là các đồ thị con cảm sinh của đồ thị truy vấn ban đầu.

Đồ thị con cảm sinh: Giả sử có đồ thị vô hướng G = (V, E), trong đó V là tập các đỉnh, E là tập các cạnh. Giả sử S là một tập con của V, khi đó mỗi đồ thị con G’

= (S, E’) với E’ là tập tất cả các cạnh của G và có 2 đỉnh thuộc S được gọi là một đồ thị con cảm sinh của G. Nếu G là một cây thì G’ là cây con cảm sinh của G.

Một truy vấn i-lớp có thể được tách thành một cặp truy vấn con r-lớp và (i- r)-lớp. Đồ thị tương ứng với truy vấn i-lớp bị chia thành hai đồ thị con liên thông lần lượt có r đỉnh và (i-r) đỉnh. Trong một cây, việc loại bỏ một cạnh sinh hai đồ thị con cũng là các cây, hai cây con này là các cây con cảm sinh của cây ban đầu. Cạnh được loại bỏ bao hàm một phép kết nối ẩn bởi vì một cạnh của đồ thị truy vấn mang nghĩa các tham chiếu đối tượng. Kết quả của truy vấn i-lớp được sinh ra bởi sự thực hiện phép kết nối ẩn giữa các kết quả của các truy vấn con r-lớp và (i-r)-lớp. Trước khi thực hiện phép kết nối ẩn, việc truyền dữ liệu phải được thực hiện nếu các kết quả của các truy vấn con không ở cùng trạm. Do đó, chi phí của môt truy vấn i-lớp có thể được tính bởi tổng các chi phí của truy vấn con r-lớp và (i-r)-lớp, chi phí thực hiện phép kết nối ẩn giữa các kết quả của các truy vấn con, và chi phí cho việc truyền dữ liệu nếu cần.

Có (i-1) cách chia một truy vấn i-lớp thành một cặp các truy vấn con vì có (i-

1) cạnh tồn tại trong đồ thị truy vấn tương ứng. Với mỗi cách chúng ta phải tính chi phí từ chi phí cho các cặp truy vấn con. Trong các cách chọn cách có chi phí thấp nhất và coi đó là chi phí của kế hoạch tối ưu cho truy vấn i-lớp. Nếu những tính toán này có thể áp dụng cho mỗi truy vấn i-lớp ở tất cả các trạm liên quan với i từ 2 đến (n-1), kế hoạch chi phí tối thiểu của truy vấn n-lớp được đưa ra ở một trạm truy vấn cuối cùng sẽ đạt được. Kế hoạch tối ưu hóa với chi phí tương ứng của mỗi truy vấn i-lớp ở các trạm được lưu lại để sử dụng lại khi truy vấn này được sử dụng như một truy vấn con của một truy vấn lớn khác ở một trạm cụ thể.

Như các phân tích ở trên, thuật toán tối ưu hoá sử dụng các cây con cảm sinh của cây truy vấn làm đầu vào. Do vậy việc đầu tiên là liệt kê các cây con cảm sinh, chúng ta có thể liệt kê cây con cảm sinh theo thuật toán sử dụng tính chất của đồ thị k-degenerate của nhóm tác giả đại học Hokkaido [9]. Các cây con cảm sinh được sinh được kí hiệu là Ti, j trong đó i là số đỉnh của cây, j là số thứ tự của cây cảm sinh i đỉnh. Đánh số các lớp DeTai, CanBo, ToChuc, DiaChi, Sach, LoaiSach lần lượt là 1, 2, 3, 4, 5, 6 thì các cây con cảm sinh của đồ thị truy vấn ở Hình 3.5 được sinh ra như Bảng 3.3.

Bảng 3.3: Các cây con cảm sinh

T1,1

1	T3,3	2 3 4
T1,2	2	T3,4	2 3 5
T1,3	3	T3,5	2 5 6
T1,4	4	T4,1	1 2 3 4
T1,5	5	T4,2	1 2 3 5
T1,6	6	T4,3	1 2 5 6
T2,1	1 2	T4,4	2 3 4 5
T2,2	2 3	T4,5	2 3 5 6
T2,3	2 5	T5,1	1 2 3 4 5
T2,4	3 4	T5,2	1 2 3 5 6
T2,5	5 6	T5,3	2 3 4 5 6