Thuật Toán Attrfrag Phân Mảnh Dựa Trên Tương Quan Thuộc Tính

2.5.2. Xây dựng ma trận tương quan thuộc tính

Tương quan thuộc tính (Attribute Affinity) giữa hai thuộc tính 𝑎𝑖 và 𝑎𝑖 trong một

𝑗 𝑙

lớp Ci là tổng tần suất của tất cả các truy vấn vào cùng cả hai thuộc tính ở mọi trạm:

)

(2.2)

𝐴𝐴(𝑎𝑖, 𝑎𝑖) = ∑ ∑ 𝑟𝑒𝑓(𝑞𝑖 , 𝑠 )𝑄𝑆𝐹(𝑞𝑖 , 𝑠

𝑗 𝑙

𝑚|𝑄𝐴𝑈(𝑞𝑖 ,𝑎𝑖 )=1&𝑄𝐴𝑈(𝑞𝑖 ,𝑎𝑖)=1 𝑘

𝑚 𝑘

Trong đó:

𝑚 𝑗

𝑚 𝑙

𝑟𝑒𝑓(𝑞𝑖 , 𝑠 ) là số truy cập thuộc tính 𝑎𝑖 và 𝑎𝑖 cho mỗi truy vấn 𝑞𝑖 ở site

𝑚 𝑘 𝑗 𝑙 𝑚

sk. Giả sử 𝑟𝑒𝑓(𝑞𝑖 , 𝑠 ) = 1.

𝑚 𝑘

𝑄𝑆𝐹(𝑞𝑖 , 𝑠 ) là tần suất truy cập của 𝑞𝑖 ở site sk

𝑚 𝑘 𝑚

Xây dựng tương quan thuộc tính giữa tất cả các cặp thuộc tính trong lớp Ci cho ta một ma trận tương quan thuộc tính AA (Attributes Affinity matrix). Ma trận tương quan thuộc tính sẽ được dùng cho các thuật toán phân mảnh nói chung và các thuật toán phân mảnh dọc nói riêng.

2.5.3. Sử dụng thuật toán BEA để phân mảnh

Thuật toán BEA (Bond Energy Algorithm) [40] được sử dụng trong các thuật toán phân mảnh dọc theo tương quan thuộc tính. Thuật toán nhận đầu vào là ma trận tương quan thuộc tính, hoán vị các hàng và các cột rồi sinh ra ma trận tương quan thuộc tính được phân nhóm CA (Clustered Affinity matrix). Hoán vị được thực hiện sao cho số đo tương quan chung AM (global affinity measure) là lớn nhất. Mục đích của việc phân nhóm là kết hợp các giá trị gần nhau lại với nhau. Tiếp theo, sự phân đoạn các thuộc tính được thực hiện dọc theo đường chéo chính của ma trận CA.

Giả sử rằng có một điểm X tồn tại dọc theo đường chéo của ma trận CA. Điểm X chia ma trận CA thành hai tập các thuộc tính. Một tập ở khối phía trên bên trái (TA) và một tập ở phía dưới bên phải (BA) như Bảng 2.8. Mỗi tập các thuộc tính dọc theo mỗi khối TA và BA là một đoạn thuộc tính.

Bảng 2.8: Ma trận tương quan thuộc tính đã phân nhóm (CA)

𝑎𝑖 𝑎𝑖 .. 𝑎𝑖

1 2 𝑗−1

𝑎𝑖.. 𝑎𝑖

𝑗 𝑛

𝑎𝑖 𝑎𝑖 .. 𝑎𝑖

1 2 𝑗−1

𝑎𝑖.. 𝑎𝑖

𝑗 𝑛

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

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

Chúng ta qui ước:

 Q = {qi , qi , …, qi } – Tập các truy vấn vào lớp Ci

1 2 h

 AQ(qi) = { ai | QAU(qi, ai) = 1} – Tập các thuộc tính được truy cập bởi

j l j l

truy vấn qi

 TQ = {qi | AQ(qi)  TA} – Tập các truy vấn chỉ truy xuất các thuộc tính

j j

trong tập TA

 BQ = {qi | AQ(qi)  BA} – Tập các truy vấn chỉ truy xuất các thuộc tính

j j

trong tập BA

 OQ = Q - {TQ  BQ} - Tập các truy vấn truy xuất các thuộc tính thuộc cả hai tập TA và BA

Vị trí tốt nhất của điểm X trong Bảng 2.8 có thể tìm thấy bằng cách tính tổng số truy cập của các truy vấn vào chỉ một mảnh được tối đa trong khi tổng số truy cậpcủa các truy vấn tới cả hai mảnh được tối thiểu. Đếm các truy vấn vào các tập TQ, BQ và OQ.

𝐶𝑇𝑄 = ∑𝑚|𝑞𝑖 TQ ∑𝑘 𝑄𝑆𝐹(𝑞𝑖 , 𝑠 )

(2.3)

𝑚 𝑚 𝑘

𝐶B𝑄 = ∑𝑚|𝑞𝑖 𝐵Q ∑𝑘 𝑄𝑆𝐹(𝑞𝑖 , 𝑠 )

(2.4)

𝑚 𝑚 𝑘

𝐶O𝑄 = ∑𝑚|𝑞𝑖 𝑂Q ∑𝑘 𝑄𝑆𝐹(𝑞𝑖 , 𝑠 )

(2.5)

𝑚 𝑚 𝑘

CTQ và CBQ lần lượt là số truy cập tới các thuộc tính trong mảnh TA và BA. COQ là tổng số truy cập tới cả hai mảnh TA và BA. Thực hiện phân mảnh dựa trên đại lượng Z xác định giá trị của biểu thức như sau:

Z = CTQ * CBQ – COQ * COQ (2.6)

Bằng cách tìm ra cực đại của Z ta sẽ tìm ra điểm X trên đường chéo chính để có phương án phân mảnh thuộc tính theo chiều dọc tốt nhất. Nếu số các thuộc tính trong một lớp là n thì số vị trí có thể X dọc theo đường chéo chính của ma trận CA là n-1.

Thuật toán AttrFrag mở rộng thuật toán phân mảnh dựa trên tương quan thuộc tính trong CSDL quan hệ, điểm mở rộng ở đây là các ma trận QAU đã được tính dựa trên QMU và MAU trong đó QMU đã được biến đổi theo các mối quan hệ trong CSDL HĐT theo các thuật toán 2.1, 2.2, 2.3.

2.5.4. Bổ sung các phương thức vào các mảnh

Sau khi thực hiện phân hoạch các thuộc tính theo thuật toán BEA, bổ sung thuộc tính định danh vào tất cả các mảnh. Tiếp theo, dựa vào ma trận phương thức sử dụng thuộc tính QAU và bổ sung các phương thức vào cùng mảnh với thuộc tính mà nó sử dụng. Như vậy các phương thức có thể được nhân bản ở nhiều mảnh, điều này có thể làm chi phí lưu trữ tăng lên nhưng sẽ giúp cho chi phí xử lý truy vấn sẽ giảm đi.

Nếu muốn phương án phân mảnh đáp ứng yêu cầu chặt về tính tách biệt cần bổ sung thêm tương quan phương thức với các mảnh. Trong các mảnh cùng chứa một phương thức chọn chỉ để lại phương thức đó trong mảnh có tương quan lớn nhất với phương thức đó. Tương quan giữa phương thức và một mảnh có thể xác định bằng tổng tương quan của phương thức với tất cả các thuộc tính và phương thức của mảnh đó (đếm tổng số lần được truy cập cùng nhau).

2.5.5. Thuật toán AttrFrag phân mảnh dựa trên tương quan thuộc tính

Thuật toán 2.5 - AttrFrag(Ci)

//Phân mảnh dựa vào tương quan thuộc tính Đầu vào:

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

- Các ma trận QMU and QSF, MAU của các lớp. Đầu ra:

- Phương án phân mảnh lớp Ci

Các bước của thuật toán:

//Bước 1: Biến đổi QMU và QSF theo các thuật toán biến đổi

Modify_1(Ci); Modify_2(Ci); Modify_3(Ci);

//Bước 2: Xây dựng ma trận QAUi

QAUi = Nhan2MaTran(QMUi, MAUi);

//Bước 3: Xây dựng ma trận AAi và CAi theo thuật toán BEA

Tạo ma trận AAi từ hai ma trận QAUi và QSFi; Tạo ma trận CAi từ ma trận AAi;

//Bước 4: Xây dựng phương án phân mảnh dựa trên CAi

Tạo tập các mảnh Fi từ ma trận CAi;

//Thêm vào mỗi mảnh thuộc tính định danh

𝑗

for (each 𝑓𝑖 Fi) do

𝑓𝑖 = 𝑓𝑖 OID(Ci);

𝑗 𝑗

//Bước 5: Dựa vào MAU thêm các phương thức vào các mảnh

𝑗

𝑙

for (each 𝑚𝑖) do for (each 𝑎𝑖 ) do

if (MAU(𝑚𝑖 , 𝑎𝑖 )=1) then

𝑗 𝑙

Thêm 𝑚𝑖 vào mảnh có 𝑎𝑖 ;

𝑗 𝑙

𝑙

end; {if} end; {for 𝑎𝑖 }

𝑗

end; {for 𝑚𝑖}

end; {Thuật toán 2.5}

2.6. Thuật toán FragAlloS phân mảnh đồng thời cấp phát

Trong đa số các hướng tiếp cận về phân mảnh và cấp phát lớp các đối tượng, việc phân mảnh và cấp phát được thực hiện ở hai giai đoạn riêng biệt, phân mảnh được thực hiện trước, sau đó sẽ cấp phát các mảnh vào các trạm. Thông tin về mạng chỉ dùng trong cấp phát mà không dùng trong phân mảnh. Hơn nữa với các thuật toán dựa trên tương quan, khi thay đổi tần suất truy vấn tại mỗi trạm mà tổng tần suất truy vấn tại tất cả các trạm không đổi thì ma trận tương quan giữ nguyên,

nghĩa là phương án phân mảnh không thay đổi. Tuy nhiên, nếu kết hợp thêm thông tin về mạng thì việc thay đổi tần suất tại một số trạm sẽ phát sinh phương án phân mảnh mới tốt hơn phương án hiện thời.

Thuật toán FragAlloS đề xuất theo hướng tiếp cận phân mảnh và cấp phát đồng thời, sử dụng thông tin mạng cho cả phân mảnh và cấp phát để tăng tính hiệu quả của việc phân mảnh và cấp phát trong CSDL HĐT PT.

2.6.1. Mô hình chi phí

Chi phí đáng kể nhất trong CSDL HĐT PT là chi phí truyền dữ liệu giữa các trạm. Ở đây chúng ta thiết lập hàm chi phí để tính tổng các chi phí gọi các phương thức tại các trạm từ xa. Chi phí gọi một phương thức được biểu diễn bằng tổng chi phí giao tiếp giữa các trạm chứa phương thức được gọi và trạm thực hiện việc gọi. Tiếp đến khi tính thời gian thực hiện của bất kỳ phương thức nào, kiểu của nó sẽ được nhận ra đầu tiên. Nếu nó là một phương thức đơn giản, chi phí được xem xét chỉ là chi phí truyền dữ liệu kết quả từ việc thực hiện phương thức tới trạm đang gọi. Nếu nó là phương thức phức tạp, ta phải thêm vào chi phí thực hiện phương thức được gọi. Cần chú ý thêm về yêu cầu truyền các đối tượng từ xa, điều này xảy ra khi một phương thức yêu cầu các đối tượng trên các trạm từ xa để thực hiện, trong trường hợp này phải thêm vào chi phí truyền các đối tượng. Tóm lại, chi phí của bất kì phương thức nào cũng bao gồm:

 Chi phí dữ liệu trả về trạm đang gọi

 Chi phí truyền các đối tượng từ xa

 Chi phí của các phương thức được gọi

Thuật toán đề xuất ở đây mở rộng công thức tính chi phí mà Hui Ma và Markus [38] đã áp dụng trong mô hình CSDL quan hệ để tính cho CSDL HĐT.

Chi phí truy cập một phương thức j ở một trạm sk là tổng tần suất truy cập của

các truy vấn có sử dụng phương thức j trên trạm sk, chi phí này được kí hiệu

request và được xác định như sau:

request i (s

, mi ) 



qi  Qi

QSFi (qi , s

) * QMUi (qi ,

mi )

(2.7)

Giá trị request được tính dựa trên các tham số sau: tần suất các truy vấn tại các trạm và sự sử dụng phương thức của các truy vấn đó. Những tham số này được biến đổi theo các mối quan hệ trong CSDL HĐT: quan hệ kế thừa, lớp này chứa lớp kia (thuộc tính phức tạp), phương thức của lớp này gọi đến thuộc tính hoặc phương thức của lớp khác (phương thức phức tạp), các thuật toán 2.1, 2.2, 2.3 trong phần 2.3. Để thiết lập chi phí truy cập mỗi phương thức của một lớp Ci từ các trạm chúng ta sẽ xây dựng ma trận requesti, ma trận này chính là tích của hai ma trận SQFi (là ma trận chuyển vị của SQFi) và QMUi.

Chi phí khi định vị một phương thức j vào một trạm sk là chi phí truy cập

vào phương thức j từ tất cả các trạm sl ≠ sk, chi phí này được kí hiệu là pay và

payi (s , mi ) 

k j



sl S

request i (s , mi ) *SSC (s , s )

k j

k l

được thiết lập như sau:

(2.8)

Giá trị pay được tính dựa trên giá trị request và thông tin mạng kết nối, vì vậy giá trị pay phụ thuộc vào tần suất truy vấn, sự sử dụng phương thức của các truy vấn và chi phí giao tiếp giữa các trạm trong mạng kết nối. Để thiết lập chi phí định vị mỗi phương thức của một lớp Ci vào các trạm chúng ta sẽ xây dựng ma trận payi, ma trận này chính là tích của 2 ma trận requesti và SSC.

Dựa vào ma trận payi để xác định phương án cấp phát các phương thức của một Ci. Thuật toán đề xuất trong luận án là một thuật toán heuristic, mục tiêu của

thuật toán là định vị 𝑚𝑖 vào trạm sk mà giá trị 𝑝𝑎𝑦𝑖(𝑠 , 𝑚𝑖) là bé nhất.

𝑗

2.6.2. Thuật toán FragAlloS

𝑘 𝑗

Thuật toán phân mảnh và cấp phát đề xuất theo hướng tiếp cận heuristic như

sau: Dựa vào ma trận payi, định vị phương thức j

vào trạm sk

mà chi phí giao

tiếp là bé nhất. Thiết lập một phương án định vị, sau đó gom cụm các phương thức

ở cùng một trạm vào một mảnh. Trong mỗi mảnh, với từng phương thức xác định các thuộc tính mà các phương thức này sử dụng để đưa vào mảnh này. Thuật toán phân mảnh và cấp phát đồng thời được xây dựng như sau.

Thuật toán 2.6 - FragAlloS(Ci): Phân mảnh và cấp phát Đầu vào:

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

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

- Ma trận chi phí giữa các trạm SSC Đầu ra:

- Phương án phân mảnh và cấp phát cho lớp Ci Các bước của thuật toán:

//Bước 1: Biến đổi QMU và QSF theo các thuật toán biến đổi

Modify_1(Ci); Modify_2(Ci); Modify_3(Ci);

//Bước 2: Xây dựng ma trận requesti

requesti = Nhan2matran(QMUi, QSFi);

//Bước 3: Xây dựng ma trận payi

payi = Nhan2matran(requesti, SSC);

//Bước 4: Xác định phương án cấp phát dựa vào ma trận payi

𝑗

for (each 𝑚𝑖) do

begin

𝑗

Chọn sk mà giá trị 𝑝𝑎𝑦𝑖(𝑠𝑘, 𝑚𝑖 ) bé nhất;

𝑗

Cấp phát 𝑚𝑖 vào trạm sk; Thêm 𝑚𝑖 vào Fk;

𝑗

end {for 𝑚𝑖}

Thêm vào mỗi mảnh phương thức truy cập định danh

//Bước 5: Dựa vào MAU thêm các thuộc tính vào các mảnh

𝑗

𝑙

for (each 𝑚𝑖) do for (each 𝑎𝑖 ) do

if (MAU(𝑚𝑖,𝑎𝑖 )=1) then

𝑗 𝑙

begin

Thêm 𝑎𝑖 vào mảnh có 𝑚𝑖;

𝑙 𝑗

Định vị 𝑎𝑖 vào trạm mà 𝑚𝑖 định vị;

𝑙 𝑗

𝑙

end; {if} end; {for 𝑎𝑖 }

𝑗

end; {for 𝑚𝑖}

end; {Thuật toán 2.6}

2.6.3. Ví dụ minh họa

Nhân ma trận SQF với ma trận QMU từ Bảng 2.6 và Bảng 2.7 để xây dựng ma trận request như Bảng 2.9. Nhân ma trận SSC từ Bảng 2.4 với ma trận request ta có ma trận pay trong Bảng 2.10.

Bảng 2.9: Ma trận request

m1	m2	m3	m4	m5	m6
s1	40	10	20	20	10	20
s2	75	15	30	15	15	15
s3	20	0	10	5	5	5

Bảng 2.10: Ma trận pay

m1	m2	m3	m4	m5	m6
s1	5150	750	2200	1100	1100	1100
s2	2600	500	1300	1150	650	1150
s3	5050	1150	2300	1850	1150	1850

Phương án cấp phát như sau: m1 được định vị tại s2, m2 được định vị tại s2, m3 được định vị tại s2, m4 được định vị tại s1, m5 được định vị tại s2, m6 được định vị tại s1. Sau đó m4 và m6 được nhóm lại cùng một mảnh, m1, m2, m3, và m5 được nhóm lại vào mảnh thứ hai. Vì m1 là phương thức truy cập định danh, m1 được thêm vào mảnh chứa m4 và m6.

Như vậy các phương thức được phân mảnh dọc thành hai mảnh F1= {m1, m4, m6}, F2 = {m1, m2, m3, m5}. Dựa vào ma trận MAU trong Bảng 2.1 thuật toán tiếp