Ma Trận Sqf Sau Biến Đổi (Chuyển Vị Của Ma Trận Qsf Sau Biến Đổi).

Hình 2.1: Lược đồ CSDL với các ma trận QMU và QSF

2.2.3. Thông tin về mạng

Ma trận chi phí giao tiếp giữa các trạm kí hiệu là SSC (Site Site Cost) biểu diễn chi phí giao tiếp giữa các trạm. Đơn vị chi phí là thời gian (chẳng hạn chọn giây) cần thiết để truyền một đơn vị dữ liệu (chẳng hạn chọn Byte) giữa hai trạm. Ví dụ về một ma trận chi phí giữa các trạm như Bảng 2.4.

Bảng 2.4: Ma trận SSC

s1	s2	s3
s1	0	50	70
s2	50	0	30
s3	70	30	0

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

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

2.2.4. Bảng các kí hiệu sử dụng

Bảng 2.5: Bảng các kí hiệu sử dụng

Kí hiệu

Mô tả ý nghĩa
Ci	Lớp thứ i trong CSDL HĐT PT.
Ai	Tập các thuộc tính của lớp Ci.
a i j	Thuộc tính thứ j của lớp Ci.
Mi	Tập các phương thức của lớp Ci.
mi j	Phương thức thứ j của lớp Ci.
Qi	Tập các truy vấn vào lớp Ci.
qi j	Truy vấn thứ j vào lớp Ci.
S	Tập các trạm
sk	Trạm thứ k
MAUi	Ma trận biểu diễn sự sử dụng thuộc tính của phương thức của lớp Ci.

Kí hiệu

Mô tả ý nghĩa
QMUi	Ma trận biểu diễn sự sử dụng phương thức của truy vấn của lớp Ci.
QSFi	Ma trận biểu diễn tần suất truy cập vào trạm của các truy vấn của lớp Ci.
SQFi	Ma trận chuyển vị của ma trận QSFi.
SSC	Ma trận chi phí giao tiếp giữa các trạm.
Fi	Tập các mảnh của lớp Ci.
f i j	Mảnh thứ j của lớp Ci.
MSizei	Mảng kích thước các phương thức của lớp Ci
MSitei	Mảng chứa thông tin trạm của các phương thức (sau khi phân mảnh và cấp phát)

2.3. Hàm mục tiêu của phân mảnh và cấp phát

Mục tiêu của phân mảnh và cấp phát là tối thiểu hóa chi phí xử lý các truy vấn, chi phí này bao gồm chi phí lưu trữ dữ liệu, chi phí truyền dữ liệu, chi phí đọc dữ liệu. Trong môi trường phân tán, chi phí truyền dữ liệu là chi phí quan trọng nhất, vì vậy các thuật toán đề xuất trong luận án tập trung vào việc giảm chi phí truyền dữ liệu. Tổng chi phí truyền dữ liệu được xác định như sau:

𝑇𝐶 = ∑ ∑ ∑ 𝑄𝑀𝑈𝑖(𝑞𝑖, 𝑚𝑖) ∗ 𝑆𝑆𝐶(𝑀𝑆𝑖𝑡𝑒(𝑚𝑖), 𝑠𝑘) ∗ 𝑀𝑆ize(𝑚𝑖) ∗ 𝑄𝑆𝐹𝑖(𝑞𝑖, 𝑠𝑘)

qi Qi 𝑠𝑘 S 𝑚𝑖 𝑀𝑖

𝑙 𝑗

𝑗 𝑗 𝑙

l 𝑗

(2.1)

Trong công thức 2.1 chi phí được tính là tổng chi phí thức hiện tất cả các truy vấn. Với mỗi truy vấn tính chi phí thực hiện truy vấn đó trên từng trạm, nếu truy vấn có sử dụng một phương thức của lớp mà phương thức đó không cùng trạm với truy vấn thì phải tính chi phí chuyển phương thức từ trạm đang định vị sang trạm mà truy vấn đang thực hiện.

2.4. Biến đổi các tham số đầu vào theo các quan hệ

Trước hết phải biến đổi ma trận sử dụng phương thức và ma trận tần suất truy cập trạm theo các quan hệ trong CSDL HĐT vì các quan hệ này ảnh hưởng đến sự phân mảnh và cấp phát. Các mối quan hệ được xem xét theo ba kiểu: quan hệ kế thừa, quan hệ bao gồm (thuộc tính phức), phương thức phức.

Đầu tiên xét quan hệ kế thừa. Các truy vấn vào các lớp con cháu hoàn toàn có thể sử dụng các phương thức từ lớp cha, vì vậy phải bổ sung thông tin các truy vấn này vào các ma trận QMU và QSF của lớp cha để đảm bảo tính đủ tần suất các truy vấn vào lớp cha.

Thuật toán 2.1 - Modify_1(Ci)

//Biến đổi QMUi và QSFi theo quan hệ kế thừa Đầu vào:

- CSDL gồm tập C các lớp trong đó có lớp Ci cần phân mảnh

- Các ma trận QMU and QSF của các lớp

Đầu ra:

- QMUi và QSFi sau khi biến đổi

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

for (each Ch C) do

𝑘

if (Ch inherited from class Ci) then//Ch kế thừa Ci for (each 𝑞ℎ Qh) do //mỗi truy vấn trên lớp Ch

if (𝑞ℎ uses methods 𝑚𝑖 of class Ci) then

𝑘 𝑗

begin

𝑘

//Thêm 1 dòng tương ứng 𝑞ℎ vào QMUi và QSFi;

𝑘

AddRow(𝑞ℎ, QMUi, QSFi); end; {if 𝑞ℎ}

𝑘

end; {for 𝑞ℎ}

end; {for Ch}

end; {Thuật toán 2.1}

Tiếp theo là xét đến quan hệ bao gồm hay còn gọi là chứa (trong lớp có các thuộc tính phức tạp). Các truy vấn vào các lớp chứa có thể sử dụng các phương

thức từ lớp được chứa bên trong, vì vậy phải bổ sung thông tin các truy vấn này vào các ma trận QMU và QSF của lớp được chứa.

Thuật toán 2.2 - Modify_2(Ci)

//Biến đổi QMUi và QSFi theo quan hệ bao gồm Đầu vào:

- CSDL gồm tập C các lớp trong đó có lớp Ci cần phân mảnh

- Các ma trận QMU and QSF của các lớp

Đầu ra:

- QMUi và QSFi sau khi biến đổi

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

for (each Ch C) do

if (Ch is a container of class Ci) then

𝑘

// Ch có một thuộc tính là đối tượng của lớp Ci for (each 𝑞ℎ Qh) do // mỗi truy vấn trên lớp Ch

if (𝑞ℎ uses methods 𝑚𝑖 of class Ci) then

𝑘 𝑗

begin

𝑘

//Thêm 1 dòng tương ứng 𝑞ℎ vào QMUi và QSFi;

𝑘

AddRow(𝑞ℎ, QMUi, QSFi); end; {if 𝑞ℎ}

𝑘

end; {for 𝑞ℎ}

end; {for Ch} end; {Thuật toán 2.2}

Cuối cùng là xét đến phương thức phức tạp, đó là trường hợp phương thức trong một lớp gọi phương thức của chính lớp này hoặc phương thức của một lớp khác. Các truy vấn vào các lớp chứa phương thức phức tạp có thể sử dụng các phương thức từ lớp khác, vì vậy phải bổ sung thông tin các truy vấn này vào các ma trận QMU và QSF của lớp chứa các phương thức được gọi.

Thuật toán 2.3 - Modify_3(Ci)

//Biến đổi QMUi và QSFi theo phương thức phức tạp Đầu vào:

- CSDL gồm tập C các lớp trong đó có lớp Ci cần phân mảnh

- Các ma trận QMU and QSF của các lớp

Đầu ra:

- QMUi và QSFi sau khi biến đổi

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

for (each Ch C)do

𝑗

for (each 𝑚ℎ Mh)do

if (𝑚ℎ invokes 𝑚𝑖) then

𝑗 𝑙

//phương thức của Ch gọi phương thức của Ci

𝑘

for (each 𝑞ℎ Qh)do //mỗi truy vấn trên lớp Ch if (𝑞ℎ uses methods 𝑚ℎ of class Ch) then

𝑘 𝑗

begin

𝑘

//Thêm 1 dòng tương ứng 𝑞ℎ vào QMUi và QSFi;

𝑘

AddRow(𝑞ℎ, QMUi, QSFi); end; {if 𝑞ℎ}

𝑘

end; {for 𝑞ℎ}

𝑗

end; {for 𝑚ℎ}

end; {for Ch }

end; {Thuật toán 2.3}

Thuật toán 2.4 mô tả việc thêm một dòng tương ứng k

QMUi và QSFi được sử dụng chung cho ba thuật toán ở trên.

𝑘

Thuật toán 2.4: AddRow(𝑞ℎ, QMUi, QSFi)

𝑘

//Thêm 1 dòng tương ứng 𝑞ℎ vào QMUi và QSFi

vào các ma trận

𝑘

Đầu vào: 𝑞ℎ, QMUi và QSFi

Đầu ra: QMUi và QSFi sau khi thêm dòng Các bước của thuật toán:

𝑘

Qi = Qi ᴜ {𝑞ℎ}

𝑗

for (each 𝑚𝑖 Mi) do

if (𝑞ℎ use 𝑚𝑖)then

𝑘 𝑗

QMUi(𝑞ℎ,𝑚𝑖)=1;

𝑘 𝑗

else

QMUi(𝑞ℎ, 𝑚𝑖)=0;

𝑘 𝑗

𝑘

end {if 𝑞ℎ}

𝑗

end; {for 𝑚𝑖}

for (each sl S) do

QSFi(𝑞ℎ,sl) = QSFh(𝑞ℎ,sl);

𝑘 𝑘

end; {for sl}

end; {Thuật toán 2.4}

Ví dụ 2.4: Khi xét các truy vấn đến lớp GiaoVienMoi, có truy vấn q1 và q2 truy cập đến phương thức m1 và m3 của lớp GiaoVien, như vậy sẽ bổ sung vào ma trận QMU hai dòng tương ứng là q4 và q5 (chính là q1 và q2 của lớp GiaoVienMoi). Khi xét các truy vấn đến lớp Khoa, có truy vấn q2 truy cập đến phương thức m1 của lớp GiaoVien, như vậy sẽ bổ sung vào ma trận QMU một dòng q6 (chính là q2 của lớp Khoa). Ma trận QSF cũng tương ứng thêm ba dòng cho các truy vấn vừa xét. Ma trận QMU và SQF (SQF là ma trận chuyển vị của ma trận QSF) của lớp GiaoVien trong Bảng 2.2 và Bảng 2.3 sẽ được biến đổi thành Bảng 2.6 và Bảng 2.7.

Bảng 2.6: Ma trận QMU sau biến đổi

m1	m2	m3	m4	m5	m6
q1	1	0	1	0	1	0
q2	1	1	0	0	0	0
q3	0	0	0	1	0	1
q4	1	0	0	0	0	0
q5	1	0	1	0	0	0
q6	1	0	0	0	0	0

Bảng 2.7: Ma trận SQF sau biến đổi (chuyển vị của ma trận QSF sau biến đổi).

q1	q2	q3	q4	q5	q6
s1	10	10	20	10	10	0
s2	15	15	15	15	15	15
s3	5	0	5	5	5	5

2.5. Thuật toán AttrFrag phân mảnh dựa trên thuộc tính

Phân mảnh đựa trên tương quan thuộc tính là một phương pháp kinh điển trong CSDL phân tán quan hệ. Trong CSDL HĐT PT Ezeife [25], [24] đã đề xuất các thuật toán phân mảnh dựa trên tương quan phương thức. Theo thuật toán của Ezeife, có những trường hợp dữ liệu sử dụng cho một phương thức và phương thức đó không cùng một mảnh. Điều này dẫn đến việc thực hiện phương thức phải có chi phí truyền dữ liệu. Do đó, chúng tôi đề xuất một thuật toán phân mảnh dọc dựa trên thuộc tính. Sau khi phân mảnh xong thuộc tính sẽ nhóm các phương thức sử dụng thuộc tính về cùng nhóm với nhau và các phương thức có thể được nhân bản ở một số mảnh nếu các thuộc tính trong các mảnh này cùng được sử dụng bởi phương thức.

2.5.1. Xây dựng ma trận truy vấn sử dụng thuộc tính

Định nghĩa 2.8: Với mỗi truy vấn 𝑞𝑖 truy cập vào lớp Ci và một thuộc tính 𝑎𝑖

𝑗 𝑙

của lớp Ci, giá trị 𝑄𝐴𝑈(𝑞𝑖 , 𝑎𝑖 ) được định nghĩa như sau:

𝑗 𝑙

𝑖

𝑙

1 Nếu 𝑞𝑖 sử dụng 𝑎𝑖

𝑄𝐴𝑈(𝑞𝑗

, 𝑎𝑖 ) = {

𝑗 𝑙

0 Ngược lại

QAU với dụng ý viết tắt của Query Attribute Usage mang ý nghĩa sự sử dụng thuộc tính của truy vấn ứng dụng. Giá trị 𝑄𝐴𝑈 được tính thông qua QMU và MAU: Sau khi biến đổi các ma trận truy vấn sử dụng phương thức (QMU) và ma trận tần suất truy cập của truy vấn vào các trạm (QSF), nhân ma trận QMU với ma trận MAU sẽ được ma trận truy vấn sử dụng thuộc tính QAU.

Xem tất cả 136 trang.

Ngày đăng: 10/06/2022