Tài liệu Xử lý và tối ưu hóa truy vấn trong cơ sở dữ liệu hướng đối tượng phân tán

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHCN VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ……..….***………… MAI THÚY NGA XỬ LÝ VÀ TỐI ƯU HÓA TRUY VẤN TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG PHÂN TÁN Chuyên ngành: Cơ sở Toán học cho Tin học Mã số: 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – 2017 Công trình được hoàn thành tại: Học viện Khoa học và công nghệ - Viện Hàn lâm Khoa học và công nghệ Việt Nam Người hướng dẫn khoa học 1: PGS. TS Đoàn Văn Ban Người hướng dẫn khoa học 2: TS Nguyễn Mạnh Hùng Phản biện 1: TS Nguyễn Long Giang Phản biện 2: PGS. TS Bùi Thu Lâm Phản biện 3: PGS. TS Trần Đăng Hưng Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và công nghệ Việt Nam vào hồi … giờ …’, ngày … tháng … năm 2017 Có thể tìm hiểu luận án tại: MỞ ĐẦU Đối với một số lĩnh vực chuyên sâu của Cơ sở dữ liệu như Multimedia, địa lí, CAD/CAM/CIM và các hệ thống tài chính phức tạp, CSDL quan hệ bộc lộ những hạn chế. Cơ sở dữ liệu hướng đối tượng (CSDL HĐT) ra đời để khắc phục các hạn chế này. CSDL HĐT cũng được xây dựng với mục đích tích hợp với ngôn ngữ lập trình hướng đối tượng, loại ngôn ngữ lập trình phổ biến nhất trong các ứng dụng ngày nay. Trong CSDL HĐT, “đối tượng” là đơn vị trung tâm, mỗi đối tượng được lưu trữ không chỉ dữ liệu mà còn thao tác trên chúng. CSDL HĐT có các đặc trưng cơ bản là tính đóng gói, kế thừa, đa hình. Ngoài vấn đề về chức năng và độ phù hợp với bài toán, các hệ thống CSDL HĐT cần được đánh giá về hiệu năng. Trong các tiêu chuẩn đánh giá hiệu năng CSDL HĐT, OO7 có thể được coi là tiêu chuẩn và là thư viện phổ biến, cung cấp khá đầy đủ các kịch bản kiểm thử để đánh giá các loại CSDL HĐT từ nhiều góc độ khác nhau. Để đáp ứng nhu cầu của doanh nghiệp lớn với dữ liệu phân tán ở nhiều trạm ở các vị trí địa lý khác nhau, CSDL được phát triển trong môi trường mạng tạo thành mô hình cơ sở dữ liệu phân tán (CSDL PT). Một số mục tiêu của việc phát triển một hệ thống CSDL PT là tăng độ tin cậy và tính sẵn sàng, đáp ứng tính phân tán của tổ chức, có khả năng mở rộng, … Thiết kế phân tán CSDL ban đầu cũng phát triển trong ngữ cảnh mô hình dữ liệu quan hệ, sau đó mở rộng trong mô hình dữ liệu hướng đối tương tạo thành mô hình cơ sở dữ liệu hướng đối tượng phân tán (CSDL HĐT PT). Trong CSDL HĐT PT rất nhiều vần đề cần được nghiên cứu, trong đó có việc xử lý truy vấn đối tượng phân tán. Xử lý truy vấn liên quan đến vấn đề thiết kế phân tán và tối ưu hóa phân tán. Bài toán thiết kế phân tán nhằm mục tiêu nâng cao hiệu quả của hệ thống, được chia thành hai giai đoạn chính là phân mảnh và cấp phát. Cả hai bài toán phân mảnh và cấp phát đều là bài toán NP-khó với không gian tìm kiếm rất lớn. Trong CSDL HĐT PT phân mảnh và cấp phát thực hiện trên các lớp đối tượng. Phân mảnh dọc nhằm mục đích chia một lớp thành các phần nhỏ hơn, mỗi phần gồm một số thuộc tính và phương thức. Phân mảnh ngang chia các đối tượng trong cùng một lớp thành các phần khác nhau, mỗi phần gồm một số đối tượng. Các thuật toán phân mảnh lớp đã được thực hiện trong các nghiên cứu khác theo các hướng khác nhau như dựa trên thuật toán năng lượng nối, phân mảnh dựa trên thuộc tính, dựa trên phương thức, dựa trên heuristic, dựa trên tác tử, dựa trên lý thuyết mờ, ... Cấp phát là định vị các mảnh đối tượng vào các trạm tương ứng của mạng liên kết. Không nhiều nghiên cứu đề cập đến vấn đề cấp phát trong CSDL HĐT PT, trong đó có thuật toán đồ thị, giải thuật di truyền, heuristic. Luận án cũng tập trung vào vấn đề tối ưu hóa truy vấn và thảo luận trên bài toán thực thi các biểu thức đường dẫn. Biểu thức đường dẫn là một dãy tham chiếu để truy xuất đến các đối tượng theo các thuộc tính hoặc phương thức. Mục tiêu của tối ưu hóa biểu thức đường dẫn là tìm một chiến lược thực thi biểu thức đường dẫn một cách hợp lý nhằm tối thiểu hóa chi phí. Chi phí được tính toán ở đây là chi phí theo thao tác xuất nhập, chi phí tính toán và chi phí truyền dữ liệu, trong đó chi phí đáng kể nhất là chi phí truyền dữ liệu. Mục tiêu nghiên cứu của luận án là nghiên cứu các vấn đề xử lý truy vấn để nâng cao hiệu năng của hệ thống. Với mục tiêu này, nội dung nghiên cứu của luận án là: 2 - Nghiên cứu các hệ thống đánh giá hiệu năng của CSDL HĐT trong môi trường tập trung và phân tán - Nghiên cứu các thuật toán phân mảnh và cấp phát đối tượng. Đề xuất thuật toán phân mảnh và cấp phát đối tượng phân tán mới. - Nghiên cứu các thuật toán tối ưu hóa truy vấn có chứa biểu thức đường dẫn trong CSDL HĐT. Đề xuất thuật toán tối ưu hóa biểu thức đường dẫn mới trong CSDL HĐT PT. Đối tượng nghiên cứu của luận án là CSDL HĐT PT, các thư viện đánh giá hiệu năng, các thuật toán phân mảnh, cấp phát và tối ưu hóa truy vấn đã có. Phạm vi nghiên cứu của luận án là bài toán phân mảnh và cấp phát các lớp, tối ưu hóa biểu thức đường dẫn. Phương pháp nghiên cứu là nghiên cứu lý thuyết, xây dựng các thuật toán và đánh giá độ phức tạp các thuật toán, cài đặt thực nghiệm các thuật toán, kiểm tra trên các bộ dữ liệu để so sánh đánh giá. Các đóng góp chính của luận án bao gồm:  Đánh giá hiệu năng một số CSDL HĐT phổ biến như Versant thông qua thư viện OO7 trên các tiêu chí chính: Tốc độ xử lí trong việc duyệt đối tượng, mức độ hiệu quả trong việc thay đổi đối tượng (tạo, xóa và cập nhật), hiệu quả của việc xử lý các loại câu truy vấn đối tượng.  Đề xuất hai thuật toán cho việc phân mảnh và cấp phát trong CSDL HĐT: (1) Thuật toán phân mảnh dọc các lớp đối tượng dựa trên tương quan thuộc tính. (2) Thuật toán heuristic thực hiện phân mảnh dọc và cấp phát đồng thời các lớp đối tượng dựa trên chi phí.  Đề xuất thuật toán truyền dữ liệu để thực hiện truy vấn biểu thức đường dẫn trong CSDL HĐT PT bằng bộ lọc Bloom. Đề xuất thuật toán tối ưu hóa biểu thức đường dẫn trong CSDL HĐT PT bằng quy hoạch động sử dụng cơ chế sinh cây con cảm sinh và cơ chế truyền dữ liệu bằng bộ lọc Bloom. Luận án được tổ chức thành phần mở đầu, ba chương nội dung và kết luận. Chương I giới thiệu các khái niệm cơ bản trong CSDL HĐT và CSDL HĐT PT. Phần cuối chương tập trung phân tích thư viện OO7, cài đặt thư viện này để đánh giá hiệu năng của các hệ quản trị CSDL HĐT PT. Chương II trình bày các thông tin đầu vào và cách biến đổi các tham số đầu vào của bài toán phân mảnh và cấp phát theo các quan hệ trong CSDL HĐT PT. Tiếp theo, đề xuất thuật toán phân mảnh dựa trên tương quan thuộc tính và thuật toán heuristic để phân mảnh dọc và cấp phát lớp một cách đồng thời. Chương III nghiên cứu các vấn đề liên quan đến tối ưu hóa truy vấn. Luận án đề xuất thuật toán tối ưu biểu thức đường dẫn trong CSDL HĐT PT sử dụng phương pháp liệt kê cây con cảm sinh trong một đồ thị và cơ chế của bộ lọc Bloom để giảm chi phí truyền dữ liệu giữa hai trạm. Phần kết luận cuối cùng nêu những đóng góp của luận án, các hướng nghiên cứu tiếp theo được đặt ra từ kết quả của luận án. 3 CHƯƠNG 1 - CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG PHÂN TÁN 1.1. Cơ sở dữ liệu hướng đối tượng Các ứng dụng phức tạp như thiết kế và sản xuất công nghiệp (CAD/CAM và CIM), các thí nghiệm khoa học, viễn thông, hệ bản đồ và CSDL đa phương tiện, ... đòi hỏi cấu trúc dữ liệu phải mềm dẻo và linh hoạt. Mô hình CSDL hướng đối tượng (CSDL HĐT) được đề xuất để giải quyết các vấn đề này. CSDL HĐT có một số đặc điểm cơ bản sau: - Cung cấp khả năng lưu trữ và thao tác với các kiểu dữ liệu trừu tượng hơn (như hình ảnh, bản đồ) và khả năng cho phép người dùng định nghĩa các kiểu cho từng ứng dụng. - Cung cấp khả năng biểu diễn quan hệ giữa các đối tượng dữ liệu theo quan hệ tự nhiên của thế giới thực. Ví dụ trong đối tượng tài liệu có chứa một đối tượng video và một đối tượng văn bản có đề mục. - Có khả năng tích hợp trực tiếp với các ngôn ngữ lập trình hướng đối tượng, ngôn ngữ mà ngày nay được sử dụng trong phần lớn các ứng dụng. 1.1.1. Đối tượng Khái niệm cơ bản nhất trong CSDL hướng đối tượng là đối tượng (object). Đối tượng biểu diễn một thực thể có thực trong hệ thống được mô hình hóa. Mỗi đối tượng biểu diễn bằng một bộ (OID, trạng thái, giao diện), trong đó OID (Object Identifier) là một định danh của đối tượng và trạng thái (state) tương ứng là một biểu diễn trạng thái nào đó cho trạng thái hiện tại của đối tượng, giao diện (interface) định nghĩa các hành vi của đối tượng. Trạng thái của đối tượng là một giá trị nguyên tử hoặc một giá trị được xây dựng. Gọi D là tập các miền do hệ thống định nghĩa và miền các kiểu dữ liệu trừu tượng do người dùng định nghĩa, gọi I là miền định danh được dùng để đặt tên đối tượng, A là miền các tên thuộc tính. Một giá trị được định nghĩa như sau: 1. Một phần tử của D là một giá trị và được gọi là giá trị nguyên tử (atomic value) 2. [a1: v1,…, an: vn] được gọi là một giá trị bộ (tuple value), trong đó ai là một phần tử của A và vi là một giá trị hoặc một phần tử của I. [ ] được gọi là toán tử tạo lập bộ (tuple constructor) 3. {v1,…, vn} được gọi là giá trị tập hợp hoặc trị tập (set value), với vi là một giá trị hoặc là một phần tử của I. { } được gọi là toán tử tạo lập tập (set constructor) Ví dụ 1.1: Xem xét các đối tượng sau (i1, 230) (i2,”Sinh viên”) (i3, {i6, i11}) (i4, {1, 6, 9}) (i5, [LF: i7, RF: i8, LR: i9, RR: i10]) 1.1.2. Lớp Một lớp là một mẫu cho một nhóm các đối tượng, định nghĩa một kiểu chung cho các đối tượng có thể được tạo nên từ mẫu này. Một lớp mô tả kiểu của dữ liệu bằng cách cung cấp một miền của dữ liệu với cùng cấu trúc, cùng với các phương thức có thể áp dụng lên các phần tử của 4 miền đó. Khả năng trừu tượng hóa của các lớp, được đề cập bằng tính đóng gói, dấu các cài đặt chi tiết của các phương thức, tương tác với bên ngoài thông qua một giao diện. Ví dụ 1.2: Mô hình hóa một chiếc ô tô với nhiều bộ phận (động cơ, giảm sóc, bánh xe) và sẽ lưu các thông tin khác như hãng sản xuất, số seri, … type XeHoi attributes dongCo: DongCo cacGiamSoc: {GiamSoc} cacBanhXe: [traiTruoc: BanhXe, phaiTruoc: BanhXe, traiSau: BanhXe, phaiSau: BanhXe] hangSanXuat: HangSanXuat methods tuoi: Real() thayBanh(diaDiem,banhXe) Cấu trúc dữ liệu giao diện của một lớp có thể phức tạp và lớn tùy ý. Lớp cung cấp hai ưu điểm chính: Dễ dàng mở rộng từ kiểu nguyên thủy của hệ thống sang các kiểu do người dùng định nghĩa. 1.1.3. Hợp phần Trong ví dụ 1.2, một số thuộc tính dựa trên đối tượng, chẳng hạn thuộc tính hangSanXuat với miền của nó là tập các đối tượng có kiểu HangSanXuat. Trong trường hợp này, kiểu XeHoi là một kiểu hợp phần (composite type) và các thể hiện của nó được gọi là các đối tượng hợp phần (composite object). Hợp phần cho phép chia sẻ các đối tượng. Ví dụ 1.3: Giả sử x1 là một thể hiện của kiểu XeHoi. Nếu những điều sau đúng thì chứng tỏ Hung và Nam có chung một chiếc xe. (i2, [ten: Hung, soHuuXe: x1]) (i3, [ten: Nam, soHuuXe: x1]) 1.1.4. Phân lớp con và tính kế thừa Các hệ đối tượng cung cấp khả năng mở rộng các kiểu, lớp từ các kiểu, lớp đã có. Điều này được thực hiện thông qua định nghĩa các lớp nhờ toán tử tạo lập kiểu hoặc bằng định nghĩa các lớp dựa vào các lớp đã có sẵn và bổ sung các thành phần để tạo ra các lớp con. Sinh lớp con dựa vào mối liên hệ chuyên biệt hóa giữa các lớp. Một lớp chuyên biệt (lớp con) được định nghĩa chi tiết hơn so với lớp mà từ đó nó được chuyên biệt (lớp cha). Ví dụ 1.4: Xe sẽ định nghĩa những tính chất chung của tất cả các kiểu xe. type Xe as Object attributes dongCo: DongCo hangSanXuat: HangSanXuat methods tuoi(): Real; 5 Định nghĩa XeHoi kế thừa từ kiểu Xe và thêm một số thuộc tính. type XeHoi as Xe attributes cacGiamSoc: {GiamSoc} cacBanhXe: [traiTruoc: BanhXe, phaiTruoc: BanhXe, traiSau: BanhXe, phaiSau: BanhXe] soCho: Integer Khai báo rằng một kiểu là kiểu con của một kiểu khác tạo ra sự kế thừa (inheritance), kế thừa cho phép tái sử dụng. Nếu một kiểu kế thừa từ một kiểu khác gọi là đơn kế thừa, nếu một kiểu kế thừa từ nhiều kiểu khác gọi là đa kế thừa. 1.2. Cơ sở dữ liệu hướng đối tượng phân tán 1.2.1. Mô hình cơ sở dữ liệu hướng đối tượng phân tán Một Cơ sở dữ liệu (CSDL) phân tán là một tập hợp nhiều CSDL có liên quan logic và được phân bố trên một mạng máy tính, biểu diễn như Hình 1.1. Có hai đặc điểm quan trọng trong định nghĩa CSDL phân tán:  Liên quan logic: Dữ liệu trong hệ phân tán có một số thuộc tính ràng buộc chúng với nhau.  Phân tán: Dữ liệu không cư trú trên một vị trí mà được phân bố rộng khắp trên nhiều máy tính đặt tại nhiều vị trí khác nhau. Trạm 5 Trạm 1 Trạm 2 Mạng truyền dữ liệu Trạm 3 Trạm 4 Hình 1.1: Môi trường của hệ CSDL phân tán Với lợi thế về công nghệ mạng truyền thông, mô hình CSDL phân tán phù hợp với sự phân tán về mặt tổ chức của các công ty, đặc biệt là các công ty toàn cầu. Sự phân bố của cơ sở dữ liệu hướng đối tượng theo mô hình cơ sở dữ liệu phân tán gọi là cơ sở dữ liệu hướng đối tượng phân tán (CSDL HĐT PT). 1.2.2. Các ưu điểm của CSDL phân tán - Quản lý dữ liệu phân tán với các mức trong suốt khác nhau - Tăng độ tin cậy của các giao dịch phân tán 6 - Cải thiện hiệu năng Dễ mở rộng 1.2.3. Các vấn đề cần giải quyết trong CSDL phân tán Các vấn đề cần giải quyết trong CSDL PT và mối quan hệ của chúng biểu diễn trong Hình 1.2. Thiết kế CSDL phân tán là trung tâm và ảnh hưởng đến các vấn đề khác. Chẳng hạn thiết kế ảnh hưởng đến việc quản lý thư mục bởi vì định nghĩa các mảnh và vị trí chứa chúng sẽ xác định nội dung thư mục. Những thông tin về mảnh và vị trí cũng được bộ xử lý truy vấn dùng để xác định chiến lược truy vấn. Ngược lai, các thông tin truy vấn được sử dụng cho các thuật toán phân mảnh. Quản lý thư mục Xử lý truy vấn Thiết kế CSDL phân tán Độ tin cậy Sao chép Điều khiển tương tranh Quản lý khóa gài Hình 1.2: Mối liên hệ giữa các vấn đề trong CSDL PT 1.2.4. Kiến trúc cơ sở dữ liệu hướng đối tượng phân tán Kiến trúc các hệ CSDL HĐT PT theo kiến trúc client/server. Trong các vấn đề cần nghiên cứu về CSDL HĐT PT luận án tập trung giải quyết ba vấn đề: Đánh giá hiệu năng, thiết kế phân tán (phân mảnh và cấp phát), tối ưu hóa truy vấn phân tán. Thiết kế trong CSDL HĐT PT phức tạp hơn, chẳng hạn: - - Do tính đóng gói, cấu trúc mỗi đối tượng bao gồm các phương thức và trạng thái. Vấn đề cần đặt ra là có nên phân mảnh trên các thuộc tính và nhân các các phương thức cho mỗi mảnh hay phân mảnh luôn cả các phương thức. Mỗi thuộc tính và phương thức lại có thể có kiểu đơn giản hoặc phức hợp. Khi phân mảnh các thuộc tính và phương thức phức hợp chúng ta phải xét đến các lớp liên quan bởi các thuộc tính và phương thức này. Tối ưu hóa truy vấn phân tán có một số khó khăn nảy sinh như: - Các hệ đối tượng có các hệ thống kiểu phong phú hơn. Kết quả của các phép toán đại số đối tượng thường là các tập đối tượng thuộc những kiểu khác nhau. Đóng gói các phương thức và dữ liệu trong đối tượng khả năng truy cập các thông tin và đánh giá chi phi khó hơn. 7 - Các đối tượng thường có cấu trúc phức tạp và có phân cấp kế thừa, do đó việc tối ưu hóa phức tạp hơn. 1.3. Đánh giá hiệu năng CSDL HĐT với thư viện OO7 1.3.1. Giới thiệu OO7 là một thư viện được xây dựng để đánh giá hiệu năng các hệ thống CSDL HĐT dựa trên các tiêu chí chính sau: - Tốc độ xử lý trong việc duyệt (traversal) các đối tượng, kể cả sử dụng bộ nhớ đệm hay duyệt trực tiếp trên ổ đĩa. Mức độ hiệu quả trong việc thay đổi đối tượng (tạo, xóa và cập nhật), kể cả đối tượng sử dụng index và không sử dụng index, dữ liệu lặp và dữ liệu dư thừa. Hiệu năng của việc xử lý các loại câu truy vấn đối tượng. 1.3.2. Thiết kế CSDL của OO7 Hai thành phần chính của bản thiết kế dữ liệu OO7 tập “Đối tượng nguyên tố” (atomic object) và “Đối tượng phức hợp” (composite object). Tập hợp các đối tượng nguyên tố theo một số kết nối nào đó theo mô hình đồ thị sẽ cấu thành một đối tượng phức hợp, mỗi thành phần phức hợp tương ứng với một thiết kế cơ bản nào đó của ứng dụng thực tế. Đồ thị kết nối giữa các đối tượng Atomic trong một đối tượng Comp như Hình 1.5. Mỗi thiết kế CSDL gồm nhiều module và mỗi module bao gồm nhiều assembly mà ở đó một assembly là sự đóng gói của nhiều đối tượng phức hợp và nguyên thủy với nhau và có thể đóng gói ngay cả các assembly. Các assembly lại có thể được đóng gói để hình thành các assemply phức hợp và các assembly này được liên kết theo hình cây. Mỗi module được thiết kế gồm một đối tượng dữ liệu kích thước lớn để mô phỏng trong việc đánh giá hiệu năng với các đối tượng cực lớn. Mô hình hóa bản thiết kế CSDL của OO7 được minh họa như Hình 1.6. Các tham số cho phép cấu hình CSDL ở các mức nhỏ, vừa và lớn. Ví dụ về cấu hình các tham số như trong Bảng 1.1. Mọi đối tượng và các thuộc tính của bản thiết kế OO7 đưa ra đều nhằm mục đích mô phỏng tốt nhất các bài toán hướng đối tượng trong thực tế. Kể cả với dạng hướng đối tượng phân tán, thiết 8 kế trên cũng có thể mô phỏng được các đối tượng tại các địa điểm cục bộ hoặc phân tán khác nhau mà ở đó mỗi module được minh họa như một trạm xử lý của hệ phân tán. Bảng 1.1: Các tham số CSDL chính của OO7 Tham số Mô tả NumModule Số lượng module NumCompPerModule NumAtomicPerComp Small Medium Large 1 1 10 Số lượng đối tượng phức hợp của một module 500 500 500 Số lượng đối tượng nguyên thủy trong một đối tượng phức hợp 200 200 200 1.3.3. Kịch bản đánh giá hiệu năng Kịch bản đánh giá gồm mười kịch bản duyệt đối tượng và tám kịch bản truy vấn. Kịch bản duyệt sẽ thực hiện ở hai dạng là Hot và Cold. Dạng Cold sẽ hoàn toàn không sử dụng bộ nhớ cache, với dạng duyệt Hot thì bước chuẩn bị chạy giống như Cold nhưng sau đó chạy lại ba lần cùng thao tác duyệt như Cold và sử dụng lại cache đã có từ lần chạy đầu tiên. 1.3.4. Kết quả thực nghiệm Một số tham số của CSDL được thay đổi để kiểm tra dưới nhiều góc độ: - Sử dụng cấu hình CSDL dạng nhỏ (small) với cấu hình client/server và dạng tệp trực tiếp trên ổ đĩa (embedded file) Sử dụng index (index on) và không sử dụng index (index off) Tải dữ liệu dạng đầy đủ (eager load) và dạng không đầy đủ (lazy load) Chương trình bổ sung dạng CSDL vừa (medium) thiết lập sẵn index on và eager load. 1.3.4.1 Kết quả duyệt dạng COLD Hình 1.7: Biểu đồ thao tác duyệt dạng COLD - Khi sử dụng index kết quả có tốt hơn khoảng 5% thời gian xử lý, kết quả này không thực sự phản ánh tốt tính năng index do phần lớn các thao tác duyệt có xử lý update dữ liệu (index phù hợp cho việc đọc hơn là update dữ liệu). 9 - - Với thao tác duyệt đầy đủ dữ liệu như Trav1/Trav2x/Trav3x thì kết quả tải dữ liệu không đầy đủ không tốt hơn so với dạng tải dữ liệu đầy đủ. Tuy nhiên với dạng duyệt không toàn bộ như Trav6 thì kết quả tải dữ liệu không đầy đủ tốt hơn nhiều so với dạng tải dữ liệu đầy đủ, đây chính là ưu điểm của việc sử dụng tính năng tải dữ liệu không đầy đủ khi duyệt dữ liệu rút gọn. Với dạng CSDL dạng tệp dữ liệu trực tiếp trên ổ đĩa, kết quả tốt hơn nhiều. Với CSDL dạng vừa, thời gian tăng đột biến từ 8-10 lần do phải xử lý số lượng dữ liệu rất lớn. 1.3.4.2 Kết quả duyệt dạng HOT Hình 1.8: Biểu đồ thao tác duyệt dạng HOT - - Duyệt dạng HOT cho kết quả tốt hơn rất nhiều so với dạng COLD do dữ liệu được tái sử dụng và cache trong bộ nhớ. Phần lớn các thao tác duyệt chỉ đọc không quá một giây và các thao tác duyệt có cập nhật dữ liệu cũng không quá một giây đối với CSDL dạng nhỏ. Khác với dạng COLD, kết quả của tải dữ liệu không đầy đủ với các thao tác duyệt đầy đủ có cập nhật Trav1/Trav2x/Trav3x kém hơn nhiều so với dạng tải dữ liệu đầy đủ (thời gian cao gấp khoảng 3 lần). Với các thao tác duyệt không đầy đủ Trav6/Trav8/Trav9 thì kết quả là tương đương giữa tải đữ liệu không đầy đủ và tải dữ liệu đầy đủ. 1.3.4.3 Kết quả truy vấn dạng COLD Hình 1.9: Biểu đồ truy vấn dạng COLD 10 - Kết quả nạp dữ liệu không đầy đủ thể hiện ưu điểm với các thao tác truy vấn dữ liệu, kết quả tốt hơn nhiều so với nạp dữ liệu đầy đủ. Ví dụ với Query1, nạp dữ liệu không đầy đủ chỉ mất dưới một giây, còn nạp dữ liệu đầy đủ cần tới hơn 7 giây. - Với truy vấn liệt kê toàn bộ đối tượng Query7 và truy vấn tìm kiếm có quan hệ liên kết Query8, kết quả sử dụng tải dữ liệu không đầy đủ còn tốt hơn rất nhiều. Với CSDL dạng vừa thì Query7 mất tới vài ngày và Query8 mất tới cả tháng. 1.3.4.4 Kết quả truy vấn dạng HOT - Truy vấn dạng HOT cho kết quả rất tốt so với dạng COLD với các dạng tìm kiếm theo giá trị như các truy vấn từ Query1 đến Query5. - Còn với dạng truy vấn liệt kê toàn bộ Query7 và truy vấn tìm kiếm quan hệ liên kết như Query8 thì kết quả không khác nhiều so với dạng HOT. Hình 1.10: Biểu đồ truy vấn dạng HOT 1.4. Kết luận chương 1 CSDL quan hệ có những hạn chế khi áp dụng với các hệ thống lớn, phức tạp. Mô hình CSDL HĐT được đề xuất để giải quyết các vấn đề phức tạp trong các hệ thống ứng dụng. Đặc trưng chính của CSDL HĐT là cung cấp khả năng đặc tả cấu trúc của các đối tượng phức và quản lý hoạt động của các đối tượng. CSDL HĐT phát triển trong môi trường mạng hình thành mô hình CSDL hướng đối tượng phân tán. Kiến trúc của hệ CSDL HĐT PT chủ yếu là kiến trúc clien/server. Trong các vấn đề của CSDL HĐT PT, xử lý truy vấn là một hướng nghiên cứu quan trọng. Xử lý truy vấn phân tán liên quan đến việc đánh giá hiệu năng, phân mảnh và cấp phát lớp các đối tượng, tối ưu hóa truy vấn. Chương một của luận án đã trình bày các khái niệm và các vấn đề trong CSDL HĐT và CSDL HĐT PT, đồng thời chương này cũng đã đề cập đến việc đánh giá hiệu năng các CSDL HĐT bằng thư viện OO7. Trong chương tiếp theo luận án sẽ trình bày những kiến thức và đề xuất các thuật toán để thực hiện việc phân mảnh và cấp phát lớp các đối tượng. CHƯƠNG 2 - THIẾT KẾ TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG PHÂN TÁN Bài toán thiết kế dữ liệu phân tán chia thành hai bài toán chính: phân mảnh và cấp phát. Phân mảnh là chia nhỏ dữ liệu thành các phần nhỏ hơn. Cấp phát là định vị các mảnh vào các trạm. Với mô hình đối tượng việc phân mảnh nảy sinh các vấn đề phức tạp mới do các đặc tính của hướng đối tượng, đó là tính đóng gói, kế thừa, phân cấp lớp. Chương 2 của luận án sẽ trình bày các thuật toán phân mảnh và cấp phát cho CSDL HĐT PT. Những kết quả đã được đăng ở các bài báo (1), (3), và (4). 2.1. Các thông tin đầu vào bài toán phân mảnh dọc và cấp phát lớp 2.1.1. Thông tin về CSDL Dữ liệu trong CSDL HĐT bao gồm tập các đối tượng được đóng gói, mỗi đối tượng bao gồm các thuộc tính và phương thức. Định nghĩa 2.1 [24]: Một lớp thứ i trong CSDL HĐT được biểu diễn bởi Ci = (Ki, Ai, Mi, Ii) trong đó: Ki là tập các định danh, Ai là tập các thuộc tính, Mi là tập các phương thức và Ii là tập các đối tượng được định nghĩa bởi Ai và Mi. Thuộc tính trong một lớp chia thành hai kiểu đơn giản và phức tạp: Thuộc tính đơn giản là thuộc tính có miền giá trị là các lớp nguyên thủy. Thuộc tính phức tạp là thuộc tính có miền giá trị không phải là các lớp nguyên thủy, khi đó giá trị thuộc tính có thể là định danh của các đối tượng khác. Phương thức trong một lớp cũng chia thành hai kiểu đơn giản và phức tạp: Phương thức đơn giản là phương thức khi thực hiện không gọi các phương thức khác. Phương thức phức tạp là phương thức khi thực hiện gọi phức thức khác trong cùng lớp đó hoặc các phương thức của lớp khác Định nghĩa 2.2: Một phương án phân mảnh dọc của một lớp Ci là một cách là chia Ci thành tập các mảnh {𝑓1𝑖 , 𝑓2𝑖 ,..., 𝑓𝑛𝑖 }, mỗi mảnh 𝑓𝑣𝑖 = {Ki, 𝐴𝑖𝑣 , 𝑀𝑣𝑖 , Ii}, (v = 1, ... , n) , trong đó 𝐴𝑖𝑣 là tập con của Ai, 𝑀𝑣𝑖 là tập con của Mi. Cũng như CSDL quan hệ, phân mảnh dọc phải đảm bảo ba luật phân mảnh, cụ thể trong CSDL HĐT ba luật này thể hiện như sau: - Tính đầy đủ (completeness): Mỗi thuộc tính hoặc phương thức trong lớp Ci phải được tìm thấy trong ít nhất một mảnh 𝑓𝑗𝑖 . - Tính tái cấu trúc được (reconstruction): Có khả năng tái cấu trúc lại lớp Ci từ các mảnh tương ứng đã được phân chia. Tính tách biệt (disjointness): Chỉ định danh và các phương thức truy cập định danh mới được lặp lại trong các mảnh, các thuộc tính và phương thức khác của một lớp Ci chỉ thuộc duy nhất một mảnh 𝑓j𝑖 . Định nghĩa 2.3: Một phương án cấp phát cho lớp Ci là định vị tập các mảnh {𝑓1𝑖 , 𝑓2𝑖 ,..., 𝑓𝑛𝑖 } của lớp Ci vào một tập các trạm S = {s1, s2, …, sk} trong mạng liên kết sao cho tổng kích thước các 12 mảnh tại mỗi trạm không vượt quá kích thước của trạm. Nếu khả năng lưu trữ các trạm không hạn chế thì có thể bỏ qua tham số kích thước các trạm. Định nghĩa 2.4: Với mỗi phương thức 𝑚𝑗𝑖 và một thuộc tính 𝑎𝑙𝑖 của một lớp Ci, giá trị MAU(𝑚𝑗𝑖 , 𝑎𝑙𝑖 ) được định nghĩa như sau: MAU(𝑚𝑗𝑖 , 𝑎𝑙𝑖 ) 1 nếu 𝑚𝑗𝑖 sử dụng 𝑎𝑙𝑖 ={ 0 nếu ngược lại Thiết lập tất cả các giá trị MAU(𝑚𝑗𝑖 , 𝑎𝑙𝑖 ) cho tất cả các phương thức và thuộc tính của lớp Ci nhận được ma trận phương thức sử dụng thuộc tính MAUi. Định nghĩa 2.5: Với mỗi phương thức 𝑚𝑗𝑖 của của một lớp Ci và một phương thức 𝑚𝑙ℎ của một lớp Ch, giá trị MMU(𝑚𝑗𝑖 , 𝑚𝑙ℎ ) được định nghĩa như sau: MMU(𝑚𝑗𝑖 , 𝑚𝑙ℎ ) = { 1 nếu 𝑚𝑗𝑖 sử dụng 𝑚𝑙ℎ 0 nếu ngược lại 2.1.2. Thông tin về ứng dụng Với tính đóng gói của các đối tượng, các truy vấn ứng dụng chỉ truy cập được các đối tượng thông qua các phương thức. Định nghĩa 2.6: Với mỗi truy vấn 𝑞𝑗𝑖 truy cập vào lớp Ci và một phương thức 𝑚𝑙𝑖 của lớp Ci, giá trị 𝑄𝑀𝑈(𝑞𝑗𝑖 , 𝑚𝑙𝑖 ) được định nghĩa như sau: 𝑄𝑀𝑈(𝑞𝑗𝑖 , 𝑚𝑙𝑖 ) = { 1 nếu 𝑞𝑗𝑖 sử dụng 𝑚𝑙𝑖 0 nếu ngược lại Thiết lập tất cả các giá trị 𝑄𝑀𝑈(𝑞𝑗𝑖 , 𝑚𝑙𝑖 ) cho tất cả các truy vấn vào lớp Ci với các phương thức của lớp Ci nhận được ma trận truy vấn sử dụng phương thức QMUi. Định nghĩa 2.7: Với mỗi truy vấn 𝑞𝑗𝑖 truy cập vào lớp Ci và một trạm sk trong mạng kết nối, giá trị tần suất truy cập của truy vấn vào các trạm 𝑄𝑆𝐹(𝑞𝑗𝑖 , 𝑠𝑘 ) là số lần truy cập của truy vấn 𝑞𝑗𝑖 vào trạm sk. Thiết lập tất cả các giá trị 𝑄𝑆𝐹(𝑞𝑗𝑖 , 𝑠𝑘 ) cho tất cả các truy vấn vào lớp Ci với tất cả các trạm sk nhận được ma trận tần suất truy cập các truy vấn vào các trạm QSFi. 2.1.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. 2.1.4. Bảng tóm tắt các kí hiệu đầu vào Bảng 2.1: Tóm tắt 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. 13 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. m ij Phương thức thứ j của lớp Ci. Qi Tập các truy vấn vào lớp Ci. q ij 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. 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. 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 ji 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.2. 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 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(𝑚𝑗𝑖 ) ∗ 𝑄𝑆𝐹 𝑖 (𝑞𝑙𝑖 , 𝑠𝑘 ) qil  Qi 𝑠𝑘  S 𝑚𝑗𝑖  𝑀𝑖 (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.3. Biến đổi sự sử dụng phương thức và tần suất truy cập 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), 14 phương thức phức. Các thông tin các truy vấn theo các quan hệ được bổ sung vào các ma trận QMU và QSF 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 q hk  Qh) do //mỗi truy vấn trên lớp Ch h if ( q k uses methods m ij of class Ci) then begin h //Thêm 1 dòng tương ứng q k vào QMUi và QSFi; h AddRow( q k , QMUi, QSFi); h end {if q k } h end {for q k } end {for Ch} end {Thuật toán 2.1} Thuật toán 2.2: Biến đổi QMUi và QSFi theo quan hệ bao gồm Thuật toán 2.3: Biến đổi QMUi và QSFi theo phương thức phức tạp 2.4. 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 đã đề nghị 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 các phương thức này và các 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 đề nghị một thuật toán phân mảnh 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, các phương thức có thể được nhân bản ở vài 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.4.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 nếu ngược lại 15 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. 2.4.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 số tần suất truy cập của tất cả các truy vấn vào cùng cả hai thuộc tính ở mọi site: 𝐴𝐴(𝑎𝑗𝑖 , 𝑎𝑙𝑖 ) = ∑ 𝑖 ,𝑎 𝑖 )=1&𝑄𝐴𝑈(𝑞 𝑖 ,𝑎 𝑖 )=1 𝑚|𝑄𝐴𝑈(𝑞𝑚 𝑚 𝑙 𝑗 𝑖 𝑖 ∑ 𝑟𝑒𝑓(𝑞𝑚 , 𝑠𝑘 )𝑄𝑆𝐹(𝑞𝑚 , 𝑠𝑘 ) (2.2) 𝑘 Trong đó: 𝑖 𝑖  𝑟𝑒𝑓(𝑞𝑚 , 𝑠𝑘 ) là số truy cập thuộc tính 𝑎𝑗𝑖 và 𝑎𝑙𝑖 cho mỗi truy vấn 𝑞𝑚 ở site sk. 𝑖 𝑖  𝑄𝑆𝐹 (𝑞𝑚 , 𝑠𝑘 ) 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.4.3. Sử dụng thuật toán BEA để phân mảnh Thuật toán BEA (Bond Energy Algorithm) đượ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. Sự phân đoạn các thuộc tính được ra dọc theo đường chéo chính của ma trận CA. 2.4.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 MAU, 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 giảm đi. 2.5. 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ẽ định vị 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. Luận án đề nghị 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. 16 2.5.1. Mô hình chi phí m ij Chi phí truy cập một phương thức ở một trạm sk là tổng tần suất truy cập của các truy vấn m ij có sử dụng phương thức trên trạm sk, chi phí này được kí hiệu request và thiết lập như sau: request i (s k , m ij )   q il  Q i QSFi (q il , s k ) * QMUi (q il , m ij ) (2.7) Để 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. i m 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 m từ tất cả các trạm sl ≠ sk, chi phí này được kí hiệu là pay và được thiết lập như sau: i j payi (s k , m ij )   request i (s k , m ij ) * SSC (s k , s l ) sl  S (2.8) Để 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 m ij toán đềi nghịi 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á pay (s k , m j ) trị là bé nhất. 2.5.2. Xây dựng thuật toán Thuật toán phân mảnh và cấpi phát đề xuất theo hướng tiếp cận heuristic như sau: Dựa vào ma m 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 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(SQFi, QMUi); //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 17 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.5.3. Đá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. 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 thì độ phức tạp của thuật toán được xác định là (|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 đạ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|. Có thể liệt kê các ưu điểm của hướng tiếp cận heuristic trong thuật toán này: - 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ề 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 Số lượng tối đa các mảnh chỉ bằng số lượng các trạm. 2.5.4. 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. 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 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) Phương án 3: Cấp phát ngẫu nhiên. 18 Chi phí của các phương án được biểu diễn theo biểu đồ như Hình 2.1, 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. 10000000,0 9000000,0 8000000,0 7000000,0 6000000,0 5000000,0 4000000,0 3000000,0 2000000,0 1000000,0 ,0 Phương án Phương án Phương án Phương án Phương án Phương án 1 2/s1 2/s2 2/s3 2/s4 3 Hình 2.1: Biểu đồ so sánh chi phí các phương án 2.6. So sánh các thuật toán So sánh về độ phức tạp: Thuật toán FragAlloS thực hiện cả cấp phát và phân mảnh với độ phức tạp chỉ tương đương thuật toán Ezeife mà Ezeife chỉ thực hiện một giai đoạn là phân mảnh. Cài đặt thử nghiệm: - Cài đặt 3 thuật toán đầu. Lấy kết quả phân mảnh của AttrFrag và thuật toán của Ezeife kiểm tra tất cả các phương án cấp phát và so sánh với phương án của FragAlloS - Sinh ngẫu nhiên các bộ dữ liệu QSF, QMU, MAU, SSC, kích thước các phương thức và thuộc tính. Kết quả: 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. 2.7. 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. Trong CSDL HĐT PT cũng có hai kiểu phân mảnh là phân mảnh ngang và phân mảnh dọc. Tuy nhiên, do mô hình CSDL hướng đối tượng có các đặc trưng riêng 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. Luận án đề xuất một thuật toán AttrFrag phân mảnh dựa trên tương quan thuộc tính, thuật toán này có hiệu quả tương đương thuật toán phân mảnh dựa trên tương quan phương thức của Ezeife. Thuật toán tiếp theo được đề xuất trong chương 2 là thuật toán heuristic FragAlloS, thuật toán FragAlloS thực hiện phân mảnh và cấp phát đồng thời, thuật toán FragAlloS đã được đánh giá tốt cả về độ phức tạp và kết quả thực nghiệm.