Tóm tắt Luận án 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

ề 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. 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 Trạm 5 Trạm 1 Trạm 2 Mạng truyền dữ liệu Trạm 4 Trạm 3 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. 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. Quản lý thư mục Thiết kế CSDL phân tán Điều khiển tương tranh Độ tin cậy Sao chép Xử lý truy vấn Quản lý khóa gài 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ả Small Medium Large NumModule Số lượng module 1 1 10 NumCompPerModule Số lượng đối tượng phức hợp của một module 500 500 500 NumAtomicPerComp 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 C i 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 i ja 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. i jm Phương thức thứ j của lớp Ci. Qi Tập các truy vấn vào lớp Ci. i jq 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 i jf 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(𝑚𝑗 𝑖) ∗ 𝑄𝑆𝐹𝑖(𝑞𝑙 𝑖, 𝑠𝑘) 𝑚𝑗 𝑖𝑀𝑖𝑠𝑘S ii l Qq  (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//C h kế thừa Ci for (each h kq  Qh) do //mỗi truy vấn trên lớp Ch if ( h kq uses methods i jm of class Ci) then begin //Thêm 1 dòng tương ứng h kq vào QMUi và QSFi; AddRow( h kq , QMUi, QSFi); end {if h kq } end {for h kq } 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 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. (2.2) 16 2.5.1. Mô hình chi phí Chi phí truy cập một phương thức i jm ở 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 i jm trên trạm sk, chi phí này được kí hiệu request và thiết lập như sau: Để 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 i jm vào một trạm sk là chi phí truy cập vào phương thức i jm 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: Để 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 đề nghị là một thuật toán heuristic, mục tiêu của thuật toán là định vị i jm vào trạm sk mà giá trị )m ,(spay ijk i 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ấ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 i jm 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 (2.7) (2.8)    ii l i l i k i l ii jk i Qq )m ,(q QMU * )s ,(q QSF )m ,(s request ij    Sl lk i jk ii jk i s )s ,(s SSC*)m ,(s request )m ,(spay 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. 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. ,0 1000000,0 2000000,0 3000000,0 4000000,0 5000000,0 6000000,0 7000000,0 8000000,0 9000000,0 10000000,0 Phương án 1 Phương án 2/s1 Phương án 2/s2 Phương án 2/s3 Phương án 2/s4 Phương án 3 19 CHƯƠNG 3 - TỐI ƯU HÓA BIỂU THỨC ĐƯỜNG DẪN TRONG CSDL HĐT PT Để hạn chế việc truyền dữ liệu chúng tôi đề xuất thuật toán BloomOpt để lọc các dữ liệu không cần thiết. Tiếp đến là đề xuất thuật toán quy hoạch động ExpPathOpt để tối ưu hóa truy vấn có các biểu thức truy vấn kết hợp với nhau qua toán tử AND. Thuật toán ExpPathOpt xây dựng phương án tối ưu từ các phương án tối ưu của các truy vấn con, tương ứng với việc tách đồ thị truy vấn thành các đồ thị con. Các kết quả được trình bày trong các bài báo (2) và (5). 3.1. Tối ưu hóa truyền dữ liệu trong biểu thức đường dẫn - Thuật toán BloomOpt 3.1.1. Truy vấn có biểu thức đường dẫn Khi thực hiện truy vấn trong CSDL HĐT, nếu các lớp có các thuộc tính phức tạp sẽ dẫn dắt truy vấn tới các đối tượng lồng nhau theo một biểu thức đường dẫn. Giả sử truy vấn ở đây là liệt kê họ tên các cán bộ nghiên cứu trong thành phố Hà nội và có thể viết dưới dạng: SELECT c.ten FROM CanBoNghienCuu as c WHERE c.coQuan.diaChi.thanhPho =”Hà nội” c.coQuan.diaChi.thanhPho là một biểu thức đường dẫn hay còn gọi là kết nối ẩn. Mỗi đối tượng của lớp có một định danh duy nhất (OID) được hệ thống khởi tạo, các kết nối ẩn được thực hiện thông qua các định danh này. 3.1.2. Bộ lọc Bloom Bộ lọc Bloom là một cấu trúc dữ liệu xác suất để kiểm tra xem một phần tử có nằm trong một tập hợp hay không. Cấu trúc của một bộ lọc Bloom bao gồm: - Một dãy gồm n bit, được khởi tạo tất cả các giá trị là 0 - Một tập các hàm băm h1, h2, ..hk. Mỗi hàm băm sẽ ánh xạ các giá trị khóa vào một giá trị trong khoảng từ 1 đến n, tương ứng bit của bộ lọc - Một tập S gồm m giá trị khóa Với mỗi giá trị khóa k trong S: băm nó theo các hàm băm, hàm băm thứ i có giá trị hi(k), thiết lập bit thứ hi(k) của bộ lọc Bloom thành giá trị 1. Chức năng của bô ̣loc̣ Bloom là xác điṇh môṭ phần tử x có thuôc̣ tâp̣ S hay không. Nó đươc̣ dùng là bước tiền xử lý của quá trình tìm kiếm. Nếu sau khi loc̣ qua bô ̣loc̣ Bloom trả về kết quả “không” thì không cần thưc̣ hiêṇ viêc̣ tìm kiếm nữa, nếu trả về kết quả “có thể có” thì thưc̣ hiêṇ tìm kiếm. Với bộ lọc Bloom sẽ không có khả năng xảy ra lỗi false negative mà chỉ có thể gặp phải lỗi false positive với xác suất rất nhỏ. Xác xuất false positive có thể giảm xuống nếu chọn giá trị n, k, và m thích hợp. Trong trường hợp tốt nhất, giá trị k tối ưu là 𝑘 = 𝑛 𝑚 𝑙𝑛2 , khi đó xác suất false positive được cực tiểu hóa theo k và sẽ là 𝑝 = 2−𝑘 = 2−𝑛𝑙𝑛2/𝑚 => 𝑛 = − 𝑚𝑙𝑛𝑝 (𝑙𝑛2)2 . 20 3.1.3. Thuật toán tối ưu hóa biểu thức đường dẫn 3.1.3.1 Sử dụng bộ lọc Bloom để giảm chi phí giao tiếp Giả sử lớp Ci có một thuộc tính ak là một đối tượng của lớp Cj, lớp Ci đặt tại trạm S, lớp Cj đặt tại trạm R. Giả sử có truy vấn chứa biểu thức đường dẫn từ lớp Ci sang lớp Cj. Ý tưởng chính ở đây là thay vì truyền toàn bộ các đối tượng của Cj từ S đến R đề kết hợp với Ci (hoặc ngược lại), chúng ta sẽ lọc một số đối tượng của Cj mà cần thiết cho việc kết nối với Ci. Cơ chế lọc sẽ được thực hiện bởi bộ lọc Bloom. Trường hợp 1: Truy vấn tại trạm S - Xây dựng bộ lọc Bloom cho tất cả các đối tượng thuộc lớp Ci theo giá trị thuộc tính ak, gọi là BF(Ci). - Gửi BF(Ci) đến R (trạm chứa Cj), BF(Ci) được sử dụng để lọc các đối tượng của Cj. - Gửi các đối tượng của Cj mà thỏa mãn điều kiện lọc ở trên đế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 Trường hợp 2: Truy vấn tại trạm R - 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 S (trạm chứa Ci), 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 đế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 Trường hợp 3: Truy vấn tại trạm không chứa cả Ci và Cj, giả sử là trạm P (P ≠ S, P ≠ R) - So sánh chi phí để truyền dữ liệu giữa 3 trạm và chọn trường hợp tốt nhất để thực hiện, cũng sử dụng bộ lọc Bloom để giảm truyền dữ liệu. 3.1.3.2 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 𝑛 = − 𝑚𝑙𝑛𝑝 (𝑙𝑛2)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.2. Tối ưu hóa biểu thức đường dẫn – Thuật toán PathExpOt 3.2.1. Đồ thị biểu diễn truy vấn dạng các biểu thức đường dẫ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” 21 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. Ví dụ về một đồ thị trong Hình 3.5. Hình 3.5. Đồ thị truy vấn 3.2.2. Thuật toán tối ưu hóa 3.2.2.1 Mô hình tối ưu hoá 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 Chi phí cho phép nối được tính theo thuật toán nối với bộ lọc Bloom. Chiến lược tìm kiếm sử dụng trong bài báo này là kỹ thuật lập trình động. 3.2.2.2 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 con cho các truy vấn con. 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 lập trình độ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. 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 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 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 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 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. 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. 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. 3.2.2.3 Thuật toán tối ưu hóa Thuật toán bao gồm ba bước diaChi coQuan theLoai CanBo (2) tacGiaSach chuNhiem DeTai (1) LoaiSach (4) DiaChi (1) ToChuc (3) Sach (4) 22 - Khởi tạo: Rút gọn các lớp (hoặc mảnh lớp) bằng các phép chiếu trên các thuộc tính cần để lại (OID, thuộc tính nối, thuôc tính cần hiển thị sau truy vấn) - Tìm phương án tối ưu cho các cây con cảm sinh, lần lượt từ các cây có một đỉnh đến cây có n đỉnh - Thực thi phương án tối ưu đã tìm được Thuật toán tìm phương án tối ưu - Bước 1: Khởi tạo chi phí các cây có một đỉnh, chi phí của cây một đỉnh tại mỗi trạm chính là chi phí truyền cây từ trạm của nó đến trạm này. - Bước 2: Xây dựng các phương án tối ưu cho các cây từ 2 đỉnh. o Bước 2.1: Tìm phương án tối ưu thực hiện Ti,j qua các phép nối (Find_JoinPlan). Với mỗi cây Ti, j duyệt tất cả các cách tách cây thành 2 cây con cảm sinh Tr ,p và Ti-r, q, tìm cách tách mà chi phí Ti, j là nhỏ nhất. Chi phí Ti, j tại trạm t được tính bằng tổng chi phí Tr ,p và Ti-r, q tại trạm t và chi phí nối 2 cây này tại trạm t. Lưu lại phương án thực hiện tối ưu. o Bước 2.2: Tìm phương án tối ưu thực hiện Ti, j qua các phép truyền (Find_TransPlan). Chi phí Ti, j tại trạm t sẽ được tính lại nếu chi phí này lớn hơn tổng chi phí của Ti, j tại trạm x và chi phí truyền Ti, j từ trạm x tới trạm t. Lưu lại phương án thực hiện tối ưu. Thuật toán 3.5 PathExpOpt Đầu vào: - G =(V, E); V={F1, F2,, Fn}; - fragSize: Mảng lưu kích thước của các mảnh - fragSite: Mảng lưu trạm mà các mảnh định vị - transCost: Mảng lưu chi phí giữa các trạm - T: Các cây con cảm sinh của cây truy vấn ban đầu - treeSize: Mảng kích thước các cây con, được tính khi sinh cây Đầu ra: Optimal Solution (result) Các bước của thuật toán: //Bước 1: Khởi tạo chi phí các cây con 1 đỉnh for (u=1; u<=n; u++) //n là số các mảnh begin x = fragSiteu; for (t = 1; t<=s; t++) //s là số các trạm Cost_Transt(T1,u)= fragSizeu * transCostx,t; end; {for u} //Bước 2: Xây dựng các phương án tối ưu cho các cây từ 2 đỉnh for (i=2; i<=n; i++) //Bước 2.1: Tìm phương án tối ưu thực hiện Ti,j qua các phép nối for (j=1; j<mi; j++) //mi là số cây con cảm sinh có i đỉnh for (t = 1; t<=s; t++) JoinPlant(Ti,j)= Find_JoinPlan(Ti,j); end; {for t} 23 end; {for j} //Bước 2.2: Tìm phương án tối ưu thực hiện Ti,j qua phép truyền for (t = 1; t<=s; t++) for (j=1; j<mi; j++) TransPlant(Ti,j)= Find_TransPlant(Ti,j); end; {for j} end; {for t} end; {for i} result = TransPlank(Tn,1); //k là trạm phát sinh truy vấn end; {Thuật toán 3.5} 3.2.2.4 Đánh giá độ phức tạp Trường hợp tốt nhất đồ thị truy vấn là đồ thị chuỗi (tương ứng với truy vấn chuỗi) thì số cây con cảm sinh có i đỉnh là n-i+1, khi đó độ phức tạp của thuật toán là O(sn3). Trong trường hợp xấu nhất đồ thị truy vấn là đồ thị sao (tương ứng với truy vấn hình sao) thì số cây con cảm sinh có i đỉnh là 𝐶𝑖−1 𝑛−1, độ phức tạp của thuật toán trong trường hợp này là O(s2n-1). 3.2.3. So sánh các thuật toán khác Hình 3.1: Biểu đồ so sánh chi phí PathExpOpt với các thuật toán khác 3.3. Kết luận chương 3 Với bộ lọc Bloom thay vì gửi toàn bộ dữ liệu chúng ta chỉ gửi đại diện của nó đến nơi cần kiểm tra, như vậy chi phí truyền sẽ giảm đi. Đặc biệt với các mảnh dữ liệu chỉ làm nhiệm vụ thực hiện phép kết nối ẩn trung gian mà không cần lấy ra thông tin gì thì bộ lọc Bloom thực sự hiệu quả vì chỉ cần gửi bộ lọc để lọc dữ liệu, không cần lấy các bộ dữ liệu đã lọc gửi trả lại để thực hiện phép kết nối dữ liệu. Luận án đề xuất thuật toán BloomOpt thực hiện việc tối ưu hóa kết nối hai lớp trong biểu thức đường dẫn bằng cách sử dụng bộ lọc Bloom. Truy vấn với biểu thức đường dẫn qua nhiều lớp có thể biểu diễn bởi một đồ thị truy vấn. Đồ thị này có thể tách thành các đồ thị con cảm sinh, các đồ thị con cảm sinh này tương ứng với các truy vấn con. Luận án đề xuất thuật toán PathExpOpt theo hướng tiếp cận quy hoạch động tách bài toán thành nhiều bài toán nhỏ hơn, tương đương với việc tách đồ thị thành các đồ thị con. Mô hình chi phí được xây dựng giúp cho việc lựa chọn các bài toán con tối ưu. ,0 50000,0 100000,0 150000,0 200000,0 250000,0 Bộ dữ liệu 1 Bộ dữ liệu 2 Bộ dữ liệu 3 Bộ dữ liệu 4 PathExpOpt Sun et al Kim and Lee So sánh chi phí thực hiện phương án tối ưu của thuật toán PathExpOpt và hai thuật toán của Sun và các cộng sự, và Kim và Lee trên một số bộ dữ liệu. Thuật toán chúng tôi đề xuất có chi phí tốt nhất vì đã kết hợp các biểu thức đường dẫn để thực hiện cũng như dùng bộ lọc Bloom để hạn chế việc truyền dữ liệu. 24 KẾT LUẬN Mục đích của luận án là nghiên cứu các vấn của bài toán đánh giá hiệu năng, thiết kế và tối ưu hóa truy vấn trong môi trường CSDL HĐT PT. 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ư Db4o 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 các thuật toán cho phân mảnh và cấp phát các lớp đối tượng: Thuật toán AttrFrag phân mảnh dựa trên tương quan thuộc tính và thuật toán FragAlloS phân mảnh và cấp phát đồng thời. Thuật toán FragAlloS là một thuật toán heuristic thực hiện cả phân mảnh và cấp phát với độ phức tạp chỉ tương đương các thuật toán phân mảnh và chưa thực hiện cấp phát.  Đề xuất thuật toán BloomOpt truyền dữ liệu bằng bộ lọc Bloom để thực hiện truy vấn có chưa biểu thức đường dẫn và thuật toán PathExpOpt tối ưu hóa biểu thức đường dẫn trong CSDL HĐT PT. Thuật toán PathExpOpt là thuật toán quy hoạch động sử dụng cơ chế sinh cây con cảm sinh để tối ưu hóa biểu thức đường dẫn trong CSDL HĐT PT. Các kết quả nghiên cứu của luận án đã được công bố trong các công trình (1), (2), (3), (4), và (5). Nhìn vào xu hướng phát triển hiện nay, điện toán đám mây là một môi trường phân tán nổi trội, môi trường này sử dụng các máy chủ trung tâm từ xa và mạng internet để duy trì dữ liệu và các ứng dụng. Các hệ thống CSDL PT nói chung và CSDL HĐT PT nói riêng khi phát triển trong môi trường điện toán đám mây sẽ đòi hỏi các kỹ thuật nâng cao về phân mảnh, cấp phát và sao chép. Những kỹ thuật này là một trong những hướng nghiên cứu tiếp theo của luận án. Hơn nữa, một trong những xu hướng lớn nhất của khoa học dữ liệu là dữ liệu lớn (big data) với các loại dữ liệu có cấu trúc và dữ liệu không cấu trúc. NoSQL (Not Only SQL) là loại cơ sở dữ liệu hỗ trợ lưu trữ dữ liệu không cấu trúc. Trong danh sách các cơ sở dữ liệu NoSQL có sự góp mặt của các CSDL HĐT PT như Versant, Db4o, GemStone, Như vậy CSDL HĐT PT trong môi trường dữ liệu lớn với các vấn đề như thiết kế phân tán, tối ưu hóa truy vấn cần được quan tâm nghiên cứu. Tóm lại, từ các xu thế phát triển của khoa học dữ liệu và từ kết quả của luận án đặt ra các hướng nghiên cứu tiếp theo như sau:  Thiết kế các thuật toán phân mảnh, cấp phát, tối ưu hóa truy vấn trong CSDL HĐT PT để thử nghiệm trên Hadoop nhằm nâng cao hiệu quả của thuật toán trong môi trường dữ liệu lớn trên điện toán đám mây.  Nghiên cứu cách kết hợp giữa hai hướng tiếp cận dựa trên tương quan và heuristic dựa trên chi phí trong phân mảnh và cấp phát CSDL HĐT PT để đạt hiệu quả tốt hơn.  Xây dựng các thuật toán heuristic dựa trên chi phí để tối ưu hóa biểu thức đường dẫn trong CSDL HĐT PT hiệu quả hơn, cải thiện độ phức tạp thuật toán hiện tại trong trường hợp xấu nhất (truy vấn hình sao).  Nghiên cứu về tối ưu hóa biểu thức đường dẫn trong các trường hợp tổng quát hơn và nghiên cứu các dạng khác của truy vấn trong CSDL HĐT PT. 25 DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ (1.) Mai Thúy Nga, Đoàn Văn Ban, Nguyễn Mạnh Hùng (2015), “Thuật toán phân mảnh dọc và cấp phát đồng thời trong Cơ sở dữ liệu hướng đối tượng phân tán”, Tạp chí Khoa học và công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, 53(3), tr. 265-276. (2.) Mai Thúy Nga, Đoàn Văn Ban, Nguyễn Mạnh Hùng (2015), “Xử lý truy vấn trong Cơ sở dữ liệu hướng đối tượng phân tán sử dụng bộ lọc Bloom”, Tạp chí Khoa học, Trường Đại học Sư phạm Hà nội, 60(7A), tr. 196-203. (3.) Mai Thuy Nga, Doan Van Ban (2016), “ Heuristic algorithm for fragmentation and allocation in distributed object-oriented database”, Journal of Computer Science and Cybernertics, Vietnam Academy of Science and Technology, 32(1), pp. 45-58. (4.) Mai Thúy Nga, Đoàn Văn Ban (2014), “Thuật toán Heuristic để phân mảnh và cấp phát đồng thời trong Cơ sở dữ liệu hướng đối tượng phân tán”, Kỷ yếu Hội thảo Khoa học Quốc gia lần thứ XVII Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, Nhà xuất bản Khoa học và Kỹ thuật, Hà nội, tr. 318–323. (5.) Mai Thúy Nga, Đoàn Văn Ban, Nguyễn Mạnh Hùng (2015), “Tối ưu hóa truy vấn trong Cơ sở dữ liệu hướng đối tượng phân tán”, Kỷ yếu Hội thảo Khoa học Quốc gia lần thứ XVIII Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, Nhà xuất bản Khoa học và Kỹ thuật, Hà nội, tr. 318–323.