tục cấp phát a1, a2, a4 vào F1, cấp phát a1, a2, a3, a4 vào F2. Kết quả cuối cùng là F1= {a1, a2, a4, m1, m4, m6}, F2= {a1, a2, a3, a4, m1, m2, m3, m5}.
2.6.4. Đánh giá thuật toán
Thuật toán phân mảnh là chính xác vì nó thoả mãn ba nguyên tắc cơ bản của phân mảnh: Mỗi thuộc tính hoặc phương thức của lớp nằm trong một mảnh; lớp có thể được tái cấu trúc lại từ tất cả các mảnh của nó vì tất cả các mảnh đều có chứa định danh và phương thức truy cập định danh; ngoài phương thức truy cập định danh thì các phương thức còn lại chỉ thuộc một mảnh.
Độ phức tạp của thuật toán được xác định theo các bước như sau: Nếu một lớp cần phân mảnh có tập các thuộc tính là A, tập các phương thức là M, tập các truy vấn là Q. Mạng kết nối gồm tập các trạm S. Độ phức tạp của các thuật toán
2.1 và 2.2 là |C|*|Q|, độ phức tạp của thuật toán 2.3 là |C|*|M|*|Q|. Độ phức tạp của việc nhân hai ma trận (bước 3 trong thuật toán 2.6) là |M|*|Q|*|S|. Độ phức tạp của bước 4 trong thuật toán 2.6 là |M|*|S|+|M|*|A|. Vậy độ phức tạp của thuật toán 2.6 là (|C|*|Q|+|C|*|Q|+|C|*|M|*|Q|+|M|*|Q|*|S|+|M|*|S|+|M|*|A|), độ phức tạp này tương đương (|C|*|M|*|Q|+|M|*|Q|*|S|).
Hơn nữa, hiện nay độ phức tạp của thuật toán nhân hai ma trận N*N đã được cải tiến [36] đạt đến độ phức tạp N2.38, vì vậy độ phức tạp của bước 3 trong thuật toán 2.6 chỉ còn là N2.38 với N là giá trị lớn nhất trong ba giá trị |M|, |Q| và |S|.
Điểm quan trọng của thuật toán này là khả năng hoàn thành cả hai giai đoạn phân mảnh và cấp phát với độ phức tạp tính ở trên trong khi các thuật toán khác chỉ thực hiện một giai đoạn đã có độ phức tạp tương đương. Ví dụ độ phức tạp trong thuật toán phân mảnh dọc của Ezeife [24] là |C|*|Q|*|M|
+|M|*|M|+|F|*|M|*|A|, thuật toán cấp phát của Barker và Bhar [13] có độ phức tạp là |S|3*|Q|+|F|3/|S|3 trong đó |F| là số lượng các mảnh (chắc chắn |F|>|C|).
Có thể liệt kê các ưu điểm của hướng tiếp cận heuristic trong thuật toán FragAlloS:
Có thể bạn quan tâm!
-
Các Thông Tin Đầu Vào Của Bài Toán Phân Mảnh Dọc Và Cấp Phát Lớp -
Ma Trận Sqf Sau Biến Đổi (Chuyển Vị Của Ma Trận Qsf Sau Biến Đổi). -
Thuật Toán Attrfrag Phân Mảnh Dựa Trên Tương Quan Thuộc Tính -
Tối Ưu Hóa Biểu Thức Đường Dẫn Trong Cơ Sở Dữ Liệu Hướng Đối Tượng Phân Tán -
Xử Lý Truy Vấn Đối Tượng Phân Tán -
Thuật Toán Bloomopt Tối Ưu Hóa Truyền Dữ Liệu Trong Biểu Thức Đường Dẫn
Xem toàn bộ 136 trang tài liệu này.
Trong các phương thức thì chỉ các phương thức truy cập định danh mới lặp lại trong tất cả các mảnh.
Các thông tin về truy vấn và mạng được sử dụng trong cả hai giai đoạn phân mảnh và cấp phát.
Độ phức tạp của thuật toán là thấp và phụ thuộc vào số lớp, số phương thức, số truy vấn và số các trạm.
Số lượng tối đa các mảnh chỉ bằng số lượng các trạm.
2.6.5. Thực nghiệm thuật toán FragAlloS trên OO7
Thuật toán sinh ngẫu nhiên các bộ dữ liệu gồm có mã trận dữ liệu SSC, QMU, QSF. Để chứng minh tính hiệu quả của thuật toán, đề tài chọn ngẫu nhiên một bộ dữ liệu sau:
Bảng 2.11: Bảng các dữ liệu thử nghiệm với OO7
Kết quả phân mảnh và cấp phát vào các trạm sau khi chạy thuật toán như sau
- [m1, m3, m8, m10]->s1
- [m1, m6]->s2
- [m1, m7, m9]->s3
- [m1, m2, m4, m5]->s4
Mô phỏng dữ liệu chạy thử với OO7 được thực hiện như sau:
- Sử dụng đối tượng Module như là các trạm
- Lớp cần đánh giá sẽ được mở rộng từ đối tượng AtomicPart sẵn có của OO7 bằng cách bổ sung các phương thức như thiết lập ở các ma trận trên.
Với cách thiết kế lược đồ CSDL nói trên, bài toán đánh giá được thực hiện theo 3 phương án phân mảnh như sau:
- Phương án 1: Phương án phân mảnh và cấp phát được sinh ra theo thuật toán FragAlloS, biểu diễn như Hình 2.2.
- Phương án 2: Cấp phát tất cả các phương thức mi vào một trạm s1 (hoặc s2, s3, s4), biểu diễn như Hình 2.3.
- Phương án 3: Cấp phát ngẫu nhiên, biểu diễn như Hình 2.4.
Hình 2.2: Phương án phân mảnh và cấp phát sinh ra bởi thuật toán FragAlloS
Hình 2.3: Phương án không phân mảnh và cấp phát tại cùng trạm s1 (tương tự với s2/s3/s4)
Hình 2.4: Phương án phân mảnh và cấp phát ngẫu nhiên
Ma trận SSC được cài đặt vào chương trình bằng cách đặt chi phí là hằng số cố định khi có lời gọi từ trạm này sang trạm khác và cài đặt này là cố định trong tất cả các kịch bản chạy truy vấn theo ma trận QMU. Tuy nhiên khi thực hiện các truy vấn qi (q1 đến q5) thì thuật toán chạy lần lượt cùng một truy vấn qi tại các trạm từ s1 tới s4 để cho ra các kết quả khác nhau cho cùng một câu truy vấn qi.
Kết quả chạy thực nghiệm với từng phương án có chi phí tương ứng (được tính theo công thức 2.1) trong các Bảng 2.12, Bảng 2.13 và Bảng 2.14. Đơn vị chi phí được xác định theo đơn vị thời gian nhân với đơn vị kích thước dữ liệu.
Bảng 2.12: Kết quả chạy với phương án 1
Bảng 2.13: Kết quả chạy với phương án 2
Bảng 2.14: Kết quả chạy với phương án 3
Chi phí của các phương án được biểu diễn theo biểu đồ như Hình 2.5, kết quả thử nghiệm cho thấy phương án sinh ra do thuật toán FragAlloS (phương án 1) có chi phí thấp nhất.
Hình 2.5: Biểu đồ so sánh chi phí các phương án
2.7. So sánh các thuật toán
So sánh về độ phức tạp: Bảng 2.15 là kết quả so sánh về độ phức tạp của hai thuật toán đề xuất (FragAlloS và AttrFrag) với các thuật toán khác. Thuật toán FragAlloS với độ phức tạp chỉ tương đương thuật toán của Ezeife mà thuậttoán Ezeife chỉ thực hiện một giai đoạn là phân mảnh.
Bảng 2.15: So sánh độ phức tạp các thuật toán
Cài đặt thử nghiệm:
Luận án đã cài đặt ba thuật toán FragAlloS, AttrFrag, Ezeife trên ngôn ngữ Java.
Phương pháp tiến hành thử nghiệm: Vì hai thuật toán AttrFrag và Ezeife chỉ thực hiện phân mảnh, thuật toán FragAlloS thực hiện cả phân mảnh và cấp phát nên luận án đề xuất cách tính chi phí (theo công thức 2.1) để so sánh ba thuật toán như sau:
o Lấy kết quả phân mảnh và cấp phát của FragAlloS, tính chi phí, gọi là FragAlloS _Cost
o Lấy kết quả phân mảnh của AttrFrag, kiểm tra vét cạn tất cả các phương án cấp phát để tìm phương án có chi phí nhỏ nhất, gọi là AttrFrag_minCost.
o Lấy kết quả phân mảnh của Ezeife, kiểm tra vét cạn tất cả các phương án cấp phát để tìm phương án có chi phí nhỏ nhất, gọi là Ezeife_minCost.
Dữ liệu thử nghiệm:
o Sinh ngẫu nhiên bộ dữ liệu QSF, QMU, MAU, SSC
o Sinh ngẫu nhiên dữ liệu về kích thước các phương thức và thuộc tính.
So sánh 3 chi phí FragAlloS _Cost, AttrFrag_minCost và Ezeife_minCost trên cùng các bộ dữ liệu, kết quả như sau:
o AttrFrag và Ezeife: 20% bộ dữ liệu cho kết quả thuật toán AttrFrag có chi phí nhỏ hơn Ezeife. 80% bộ dữ liệu cho kết quả thuật toán AttrFrag có chi phí bằng Ezeife.
o FragAlloS và Ezeife: 70% bộ dữ liệu cho kết quả thuật toán FragAlloS có chi phí nhỏ hơn Ezeife. 30% bộ dữ liệu cho kết quả thuật toán FragAlloS có chi phí bằng Ezeife.
Kết quả thử nghiệm chi phí ba thuật toán trên năm bộ dữ liệu trong Bảng 2.16 và so sánh chi phí biểu diễn bởi Hình 2.6.
Bảng 2.16: Chi phí của các thuật toán Ezeife, AttrFrag và FragAlloS
Hình 2.6: So sánh chi phí của các thuật toán Ezeife, AttrFrag và FragAlloS
2.8. Kết luận chương 2
Phân mảnh và cấp phát là các kỹ thuật thiết kế CSDL mức logic nhằm giảm bớt các truy xuất không cần thiết đến dữ liệu, cho phép thực hiện song song các truy vấn trên các mảnh, nhờ đó hiệu năng của hệ thống sẽ được cải thiện. Do mô hình CSDL hướng đối tượng có các đặc trưng riêng như tính đóng gói, kế thừa, thuộc tính và phương thức phức tạp nên để áp dụng những phương pháp phân mảnh từ mô hình quan hệ sang mô hình đối tượng phải biến đổi các tham số đầu vào theo cấu trúc lớp và mối quan hệ giữa các lớp trong CSDL HĐT PT.
Luận án đề xuất hai thuật toán phân mảnh và cấp phát trong CSDL HĐT PT:
(1) Thuật toán AttrFrag phân mảnh dựa trên tương quan thuộc tính. (2) Thuật toán heuristic FragAlloS thực hiện phân mảnh và cấp phát đồng thời với độ phức tạp