Luận án Tiến sĩ Toán học: 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

Chia sẻ: Hàn Thiên Ngạo | Ngày: | Loại File: PDF | Số trang:131

Thêm vào BST

Báo xấu

50
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án được thực hiện với mục tiêu nhằm 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 truy vấn hướng đối tượng; 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, phục vụ xử lý truy vấn hiệu quả hơn;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Toán học: 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 KHOA HỌC VÀ CÔNG NGHỆ 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 LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – 2017
VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ 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 LUẬN ÁN TIẾN SĨ TOÁN HỌC Chuyên ngành: Cơ sở Toán học cho Tin học Mã số: 62 46 01 10 Người hướng dẫn khoa học: 1. PGS. TS. Đoàn Văn Ban 2. TS. Nguyễn Mạnh Hùng HÀ NỘI – 2017
LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các đồng tác giả đã được sự chấp thuận của các tác giả trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tác giả Mai Thúy Nga
LỜI CÁM ƠN Luận án đượ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. Tác giả xin được bày tỏ lòng biết ơn chân thành và sự kính trọng sâu sắc đối với PGS.TS Đoàn Văn Ban. Tác giả đã nhận được sự hướng dẫn tận tình và các kinh nghiệm nghiên cứu khoa học quý giá của Thầy trong suốt quá trình học nghiên cứu sinh. Tác giả cũng chân thành cám ơn TS Nguyễn Mạnh Hùng với những định hướng nghiên cứu và góp ý để luận án được hoàn thiện. Trong thời gian làm nghiên cứu sinh, tác giả đã nhận được những kiến thức quý giá và sự góp ý chân thành từ các Thầy, Cô giáo của Học viện Khoa học và Công nghệ. Tác giả xin gửi tới các Thầy, Cô lời cảm ơn chân thành nhất. Tác giả xin chân thành cảm ơn Ban lãnh đạo Viện Công nghệ thông tin, Học viện Khoa học và Công nghệ, Bộ phận Quản lý Nghiên cứu sinh và các Phòng ban chức năng của Viện Công nghệ thông tin và Học viện Khoa học và Công nghệ đã tạo mọi điều kiện thuận lợi trong quá trình học tập, nghiên cứu của tác giả. Tác giả xin cảm ơn Ban Giám hiệu, Bộ môn Tin học trường Đại học Thăng Long đã quan tâm giúp đỡ mọi mặt để tác giả hoàn thành nhiệm vụ học tập. Xin chân thành cảm ơn sự quan tâm, động viên và những đóng góp quý báu của các đồng nghiệp. Cuối cùng, tác giả xin dành những lời cám ơn tới mọi thành viên trong gia đình, sự khuyến khích và động viên của gia đình là động lực để tác giả hoàn thành luận án này.
MỤC LỤC MỤC LỤC ........................................................................................................................ i DANH MỤC CÁC THUẬT NGỮ ............................................................................................ iv BẢNG VIẾT TẮT CÁC THUẬT NGỮ......................................................................................v DANH MỤC HÌNH MINH HỌA ............................................................................................. vi DANH MỤC BẢNG ................................................................................................................ vii MỞ ĐẦU ........................................................................................................................1 CHƯƠNG 1 - CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG PHÂN TÁN ...............................7 1.1. Cơ sở dữ liệu hướng đối tượng ............................................................................. 7 1.1.1. Đối tượng ........................................................................................................ 8 1.1.2. Kiểu và lớp...................................................................................................... 9 1.1.3. Hợp phần....................................................................................................... 11 1.1.4. Phân lớp con và tính kế thừa ........................................................................ 12 1.2. Cơ sở dữ liệu hướng đối tượng phân tán ............................................................. 14 1.2.1. Mô hình cơ sở dữ liệu hướng đối tượng phân tán ........................................ 14 1.2.2. Các ưu điểm của CSDL phân tán ................................................................. 15 1.2.3. Các vấn đề cần giải quyết trong CSDL phân tán .......................................... 16 1.2.4. Kiến trúc CSDL hướng đối tượng phân tán.................................................. 20 1.2.5. Quản lý đối tượng ......................................................................................... 22 1.2.6. Quản lý giao dịch .......................................................................................... 25 1.3. Đánh giá hiệu năng CSDL HĐT với thư viện OO7 ............................................ 25 1.3.1. Giới thiệu ...................................................................................................... 25 1.3.2. Một số nghiên cứu khác về đánh giá hiệu năng CSDL HĐT ....................... 26 1.3.3. Thiết kế CSDL của OO7............................................................................... 27 1.3.4. Kịch bản đánh giá hiệu năng ........................................................................ 30 1.3.5. Kết quả thực nghiệm ..................................................................................... 32 1.4. Kết luận chương 1 ............................................................................................... 36 CHƯƠNG 2 - PHÂN MẢNH VÀ CẤP PHÁT LỚP CÁC ĐỐI TƯỢNG PHÂN TÁN ....37
ii 2.1. Phân mảnh và cấp phát lớp các đối tượng........................................................... 38 2.1.1. Mục tiêu của phân mảnh và cấp phát ........................................................... 38 2.1.2. Phân mảnh lớp các đối tượng ....................................................................... 38 2.1.3. Cấp phát lớp .................................................................................................. 41 2.2. 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 .................. 42 2.2.1. Thông tin về CSDL ....................................................................................... 42 2.2.2. Thông tin về ứng dụng .................................................................................. 45 2.2.3. Thông tin về mạng ........................................................................................ 48 2.2.4. Bảng các kí hiệu sử dụng .............................................................................. 48 2.3. Hàm mục tiêu của phân mảnh và cấp phát .......................................................... 49 2.4. Biến đổi các tham số đầu vào theo các quan hệ .................................................. 50 2.5. Thuật toán AttrFrag phân mảnh dựa trên thuộc tính ........................................... 54 2.5.1. Xây dựng ma trận truy vấn sử dụng thuộc tính ............................................ 54 2.5.2. Xây dựng ma trận tương quan thuộc tính ..................................................... 55 2.5.3. Sử dụng thuật toán BEA để phân mảnh ....................................................... 55 2.5.4. Bổ sung các phương thức vào các mảnh ...................................................... 57 2.5.5. Thuật toán AttrFrag phân mảnh dựa trên tương quan thuộc tính ................. 57 2.6. Thuật toán FragAlloS phân mảnh đồng thời cấp phát ........................................ 58 2.6.1. Mô hình chi phí ............................................................................................. 59 2.6.2. Thuật toán FragAlloS ................................................................................... 60 2.6.3. Ví dụ minh họa ............................................................................................. 62 2.6.4. Đánh giá thuật toán ....................................................................................... 63 2.6.5. Thực nghiệm thuật toán FragAlloS trên OO7 .............................................. 64 2.7. So sánh các thuật toán ......................................................................................... 68 2.8. Kết luận chương 2 ............................................................................................... 70 CHƯƠNG 3 - 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 ........................................................................................72 3.1. Xử lý truy vấn trong cơ sở dữ liệu quan hệ ......................................................... 72 3.1.1. Tổng quan về xử lý truy vấn phân tán .......................................................... 72
iii 3.1.2. Các tầng xử lý truy vấn ................................................................................. 77 3.2. Xử lý truy vấn đối tượng phân tán ...................................................................... 83 3.2.1. Giới thiệu ...................................................................................................... 83 3.2.2. Các kỹ thuật tối ưu hóa truy vấn đối tượng .................................................. 85 3.3. Thuật toán BloomOpt tối ưu hóa truyền dữ liệu trong biểu thức đường dẫn ..... 88 3.3.1. Giới thiệu ...................................................................................................... 88 3.3.2. Truy vấn có biểu thức đường dẫn ................................................................. 89 3.3.3. Bộ lọc Bloom ................................................................................................ 90 3.3.4. Sử dụng bộ lọc Bloom để giảm chi phí giao tiếp ......................................... 92 3.3.5. Thảo luận về các tham số.............................................................................. 97 3.4. Tối ưu hóa biểu thức đường dẫn – Thuật toán PathExpOpt ............................... 97 3.4.1. Đồ thị biểu diễn truy vấn dạng các biểu thức đường dẫn ............................. 97 3.4.2. Mô hình tối ưu hoá truy vấn ....................................................................... 100 3.4.3. Tách cây truy vấn thành các cây con cảm sinh........................................... 101 3.4.4. Nguyên lý tối ưu hóa .................................................................................. 103 3.4.5. Thuật toán tối ưu hóa PathExpOpt ............................................................. 105 3.4.6. Đánh giá độ phức tạp và cài đặt thuật toán ................................................. 109 3.4.7. Kết quả thực nghiệm ................................................................................... 110 3.5. Kết luận chương 3 ............................................................................................. 112 KẾT LUẬN ....................................................................................................................113 DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ ..............................................................115 TÀI LIỆU THAM KHẢO .......................................................................................................116
iv DANH MỤC CÁC THUẬT NGỮ Biểu thức đường dẫn Path expression Bộ lọc Bloom Bloom filter Cây con cảm sinh Induced subtree Cấp phát lớp Class allocation Duyệt đối tượng Object traversal Đồ thị con cảm sinh Induced subgraph Đối tượng phức hợp Composite object Lớp/kiểu sưu tập Collection class Lược đồ đối tượng Object schemas Mô hình chi phí Cost model Mối quan hệ kế thừa Inheritance relationship Phân cấp lớp Class hierarchy Phân mảnh lớp Class fragmentation Phương thức đơn giản Simple method Phương thức phức tạp Complex method Tối ưu hóa truy vấn Query optimization Thuộc tính đơn giản Simple attribute Thuộc tính phức tạp Complex attribute
v BẢNG VIẾT TẮT CÁC THUẬT NGỮ CSDL (Database) Cơ sở dữ liệu CSDL PT (Distributed Database) Cơ sở dữ liệu phân tán CSDL HĐT (Object Oriented Database) Cơ sở dữ liệu hướng đối tượng CSDL HĐT PT (Distributed Object Oriented Cơ sở dữ liệu hướng đối tượng Database) phân tán DDL (Data Difinition Language) Ngôn ngữ định nghĩa dữ liệu ODL (Object Definition Language) Ngôn ngữ định nghĩa đối tượng ODMG (Object Database Management Group) Nhóm quản trị CSDL đối tượng, tổ chức đề xuất mô hình ODMG và ngôn ngữ OQL OID (Object Identifier) Định danh đối tượng OQL (Object Query Language) Ngôn ngữ truy vấn đối tượng
vi DANH MỤC HÌNH MINH HỌA Hình 1.1: Môi trường của hệ CSDL phân tán ................................................................ 14 Hình 1.2: Mối liên hệ giữa các vấn đề trong CSDL PT ................................................. 19 Hình 1.3: Kiến trúc Server theo đối tượng ..................................................................... 21 Hình 1.4: Kiến trúc Server theo trang ............................................................................ 22 Hình 1.5: Đồ thị kết nối đối tượng của OO7 .................................................................. 28 Hình 1.6: Mô hình hóa thiết kế CSDL của OO7 ............................................................ 29 Hình 1.7: Biểu đồ thao tác duyệt dạng COLD ............................................................... 33 Hình 1.8: Biểu đồ thao tác duyệt dạng HOT.................................................................. 34 Hình 1.9: Biểu đồ truy vấn dạng COLD ........................................................................ 35 Hình 1.10: Biểu đồ truy vấn dạng HOT ......................................................................... 35 Hình 2.1: Lược đồ CSDL với các ma trận QMU và QSF .............................................. 47 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 ............ 65 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) ........................................................................................................................................ 65 Hình 2.4: Phương án phân mảnh và cấp phát ngẫu nhiên .............................................. 66 Hình 2.5: Biểu đồ so sánh chi phí các phương án .......................................................... 68 Hình 2.6: So sánh chi phí của các thuật toán Ezeife, AttrFrag và FragAlloS ................ 70 Hình 3.1: Lược đồ phân tầng tổng quát để xử lý truy vấn phân tán .............................. 77 Hình 3.2: Rút gọn truy vấn ............................................................................................. 81 Hình 3.3: Minh hoạ các lớp có thuộc tính phức hợp...................................................... 89 Hình 3.4: Các lớp truy vấn ............................................................................................. 98 Hình 3.5: Đồ thị truy vấn ............................................................................................... 99 Hình 3.6: Minh họa kết quả thử nghiệm ...................................................................... 110 Hình 3.7: Biểu đồ so sánh chi phí PathExpOpt với các thuật toán khác ..................... 111
vii DANH MỤC BẢNG Bảng 1.1: Các tham số CSDL chính của OO7 ............................................................... 27 Bảng 1.2: Các kịch bản duyệt đối tượng ........................................................................ 30 Bảng 1.3: Kich bản truy vấn .......................................................................................... 31 Bảng 1.4: Môi trường thực nghiệm ................................................................................ 32 Bảng 2.1: Ma trận MAU của lớp GiaoViên ................................................................... 44 Bảng 2.2: Matrận QMU của lớp Giáo viên .................................................................... 45 Bảng 2.3: Ma trận QSF của lớp Giáo viên ..................................................................... 46 Bảng 2.4: Ma trận SSC................................................................................................... 48 Bảng 2.5: Bảng các kí hiệu sử dụng ............................................................................... 48 Bảng 2.6: Ma trận QMU sau biến đổi ............................................................................ 53 Bảng 2.7: Ma trận SQF sau biến đổi (chuyển vị của ma trận QSF sau biến đổi). ......... 54 Bảng 2.8: Ma trận tương quan thuộc tính đã phân nhóm (CA) ..................................... 56 Bảng 2.9: Ma trận request .............................................................................................. 62 Bảng 2.10: Ma trận pay .................................................................................................. 62 Bảng 2.11: Bảng các dữ liệu thử nghiệm với OO7 ........................................................ 64 Bảng 2.12: Kết quả chạy với phương án 1 ..................................................................... 66 Bảng 2.13: Kết quả chạy với phương án 2 ..................................................................... 67 Bảng 2.14: Kết quả chạy với phương án 3 ..................................................................... 67 Bảng 2.15: So sánh độ phức tạp các thuật toán.............................................................. 68 Bảng 2.16: Chi phí của các thuật toán Ezeife, AttrFrag và FragAlloS .......................... 70 Bảng 3.1: Độ phức tạp của phép tính đại số quan hệ ..................................................... 74 Bảng 3.2: Minh hoạ xây dựng bộ lọc Bloom ................................................................. 91 Bảng 3.3: Các cây con cảm sinh .................................................................................. 102 Bảng 3.4: So sánh PathExpOpt với các thuật toán khác .............................................. 111
MỞ ĐẦU Sự phát triển của các ứng dụng dữ liệu chuyên sâu đã vượt quá khả năng xử lý của Hệ thống quản trị cơ sở dữ liệu quan hệ. Có thể liệt kê 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. Các hạn chế của cơ sở dữ liệu quan hệ đã thúc đẩy sự phát triển của Hệ thống cơ sở dữ liệu hướng đối tượng (CSDL HĐT). CSDL HĐT ra đời từ những năm 60 và đã được thương mại hóa, có rất nhiều ứng dụng loại CSDL này vào các bài toán thực tế. 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. Các nghiên cứu cho thấy CSDL HĐT sẽ tiếp tục phát triển và cung cấp các khả năng nổi trội trong việc xử lý dữ liệu phức tạp. Các hệ thống quản trị CSDL HĐT được phát triển, điển hình như Cache, DB4o, Versant, O2, Orion, ObjectStore, … 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. Tuy nhiên, không giống như mô hình quan hệ, chưa có một mô hình đối tượng nào được thừa nhận rộng rãi và đặc tả được một cách hình thức và chính xác các đặc trưng khác nhau của hệ thống hướng đối tượng. Một số mô hình đối tượng chuẩn đã được phát triển như mô hình ODMG [22] trong đó bao gồm ngôn ngữ định nghĩa dữ liệu ODL và ngôn ngữ truy vấn dữ liệu OQL, mô hình SQL3 [41] mở rộng từ mô hình quan hệ. Trong các hệ thống CSDL HĐT, ngoài vấn đề về chức năng và độ phù hợp của loại CSDL HĐT trong các bài toán ứng dụng thì vấn đề hiệu năng của chúng cũng luôn được cân nhắc nhằm đánh giá xem CSDL HĐT đã thực sự hiệu quả trong quá trình triển khai dự án hay chưa. Trong các tiêu chuẩn đánh giá hiệu năng CSDL HĐT, OO7 [17] đượ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 theo nhiều góc độ khác nhau. Thư viện OO7 với các đặc tả chi tiết về lược đồ dữ liệu cho phép đánh giá hiệu năng một số loại CSDL HĐT phổ biến như Db4o, Versant, …, trên nhiều khía cạnh khác nhau đặc biệt là cấu trúc CSDL và các thao tác xử lý đối tượng.
2 Để đáp ứng nhu cầu của doanh nghiệp lớn với dữ liệu phân tán ở nhiều 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). Với các lợi thế về mặt công nghệ của các giao thức và chuẩn về phần mềm, phần cứng và mạng truyền thông, việc phát triển các hệ thống CSDL PT ngày càng cần thiết và dễ dàng hơn. 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, … Phần lớn các nhà cung cấp hệ thống CSDL lớn đều đưa ra các sản phẩm hỗ trợ sự phân tán dữ liệu, ví dụ IBM, Oracle, Microsoft, Sybase, ... Mô hình phân tán 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. Một số vấn đề có thể giải quyết được bằng các giải pháp đã áp dụng cho CSDL quan hệ. Tuy nhiên, với các đặc điểm riêng của CSDL HĐT có những vấn đề đòi hỏi những kỹ thuật chuyên biệt. Trong các vấn đề đó, việc xử lý truy vấn đối tượng phân tán để nâng cao hiệu năng của hệ thống đặt ra nhiều thách thức cho các nhà nghiên cứu. 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 được chia thành hai giai đoạn chính là 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 khác nhau mà khi kết hợp các phần lại chúng ta lại có được CSDL nguyên thủy ban đầu và đảm bảo không bị mất mát thông tin. Sự phân mảnh hợp lí sẽ giảm các truy cập vào các dữ liệu không cần thiết trong các ứng dụng. Kết quả của giai đoạn phân mảnh là tập các mảnh được định nghĩa theo một lược đồ phân mảnh. Phân mảnh được thực hiện với hai kỹ thuật chính là phân mảnh dọc và phân mảnh ngang. Có rất nhiều các nghiên cứu về phân mảnh dọc và ngang trong CSDL quan hệ đã được thực hiện, từ các đề xuất sử dụng các thuật toán kinh điển như thuật toán năng lượng nối [5], thuật toán đồ thị [43] đến các thuật toán heuristic, tiến hóa [19], [33], [27]. Cấp phát là qui trình gán các mảnh đã phân chia vào các trạm trên mạng. Mục đích của cấp phát là tối thiểu hóa chi phí truyền dữ liệu và tối thiểu hóa số các thông điệp cần xử lý để đáp ứng yêu cầu của các ứng dụng thực tế. Cũng như phân mảnh,
3 cấp phát trong CSDL quan hệ đã có rất nhiều nghiên cứu được công bố, có thể liệt kê một số thuật toán trong các nghiên cứu gần đây [3], [7], [8], [10], [28]. 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. Ezeife và Barker đề nghị thuật toán phân mảnh dựa trên thuật toán năng lượng nối cho cả trường hợp phân mảnh dọc [24] và ngang [25]. Lee và Lim đưa ra thuật toán phân mảnh các thuộc tính [50]. Baiao đưa ra thuật toán phân mảnh hỗn hợp [12]. Darabant chứng minh thứ tự phân mảnh các lớp cũng ảnh hưởng đến hiệu quả phân mảnh, từ đó đề nghị thuật toán tìm thứ tự phân mảnh tốt nhất [21]. Một số thuật toán phân mảnh khác trong CSDL HĐT PT theo các hướng khác nhau như dựa trên tác tử thông minh [32], tiếp cập theo hướng heuristic [39], phân cụm dựa trên lý thuyết mờ [20]. 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. Các nghiên cứu tập trung tìm ra các thuật toán cấp phát nhằm tối thiểu hóa chi phí. Không nhiều nghiên cứu đề cập đến vấn đề cấp phát trong CSDL HĐT PT. Trong [13], K. Barker và S. Bhar đã đưa ra các khái niệm cơ bản để thiết lập mô hình cho bài toán cấp phát lớp, trong đó các tác giả cũng đề nghị một hướng tiếp cận đồ thị để giải quyết bài toán. Trong [6] và [37] đề cập đến thuật toán di truyền để chọn ra phương án cấp phát gần tối ưu. Các giải thuật heuristic cho bài toán cấp phát lớp trong CSDL HĐT PT được đề cập trong [14] và [29]. Phân mảnh và cấp phát trong CSDL HĐT PT 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. Một hạn chế của các phương pháp phân mảnh dựa trên phương thức là khi phân mảnh một lớp con đã đưa các phương thức của lớp cha vào để phân mảnh cùng các phương thức của lớp con nhưng lại không đưa các thuộc tính của lớp cha vào lớp con, như vậy khi thực hiện phương thức rất có thể vẫn phải truy cập thuộc tính từ một trạm khác. Một hạn chế khác của các phương pháp là hai giai đoạn phân mảnh và cấp phát tách biệt nhau, phân mảnh xong rồi mới đến cấp phát.
4 Trong quá trình phân mảnh không sử dụng thông tin về chi phí giữa các trạm trong mạng, tuy nhiên trong nghiên cứu của Ma H. [38] cho CSDL quan hệ đã chỉ ra rằng thông tin chi phí này sẽ ảnh hưởng đến phương án phân mảnh. Tiếp theo là bài toán tối ưu hóa truy vấn, bài toán này rất khó phân tích trong môi trường phân tán bởi có nhiều yếu tố liên quan. Trong phạm vi luận án chúng tôi tập trung vào vấn đề tối ưu hóa các biểu thức đường dẫn, một dạng truy vấn phổ biến trong CSDL HĐT. 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. Tối ưu hóa việc tính toán biểu thức đường dẫn là một bài toán được nhiều nghiên cứu quan tâm. Mục tiêu của tối ưu hóa truy vấn 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 môi trường phân tán hiện nay, chi phí đáng kể nhất là chi phí truyền dữ liệu. Chiến lược thực thi thường phân thành hai kiểu: duyệt từ trên xuống hoặc từ dưới lên. Đã có một số nghiên cứu về tối ưu hóa biểu thức đường dẫn trong môi trường tập trung như hướng tiếp cận heuristic của Ozkan trong [45], hay viết lại các biểu thức đường dẫn phức tạp về dạng đơn giản trong luận án tiến sĩ của Trương Ngọc Châu [2]. Tuy nhiên, có rất ít các nghiên cứu tập trung vào vấn đề xử lý truy vấn đối tượng trong môi trường phân tán. Các thuật toán đưa ra trong [52], [34] đều là các thuật toán qui hoạch động. Thuật toán của Sun W. và các công sự trong [52] mới chỉ xét từng biểu thức đường dẫn, chưa kết hợp các biểu thức đường dẫn, như vậy nếu một truy vấn có hai hay nhiều biểu thức đường dẫn mà các biểu thức đường dẫn này có phần chung thì những phần chung này sẽ được thực hiện lặp lại. Thuật toán của Kim H. và Lee S. trong [34] chưa đề cập đến việc lọc các thông tin không cần thiết cho các truy vấn từ các mảnh lớp, thuật toán sinh đồ thị con trong nghiên cứu này cũng chưa chính xác. Từ phân tích về các nghiên cứu hiện tại, 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 truy vấn hướng đối tượng. Với mục tiêu này, nội dung nghiên cứu của luận án bao gồm:
5  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, phục vụ xử lý truy vấn hiệu quả hơn.  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 và đề 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á kết quả. 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,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í. Thuật toán (2) có độ phức tạp chỉ tương đương các thuật toán phân mảnh thông thường nhưng lại thực hiện được đồng thời cả hai giai đoạn phân mảnh và cấp phát. Kết quả của giai đoạn phân mảnh và cấp phát phục vụ cho việc tối ưu hóa truy vấn CSDL HĐT PT.
6  Đề 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, từ các định nghĩa cơ bản đến kiến trúc tổng thể của một hệ quản trị 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. Phần cuối là so sánh đánh giá các thuật toán dựa trên độ phức tạp và kết quả chạy thực nghiệm chương trình. Chương III nghiên cứu các vấn đề liên quan đến tối ưu hóa truy vấn. Mô hình tối ưu hóa truy vấn bao gồm việc liêt kê các kế hoạch thực thi truy vấn, xây dựng mô hình chi phí và chiến lược tìm kiếm để đạt chi phí tối thiểu. Luận án đề xuất thuật toán tối ưu biểu thức đường dẫn trong CSDL HĐT PT, thuật toán 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.
CHƯƠNG 1 - CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG PHÂN TÁN Chương này trình bày các khái niệm cơ bản trong cơ sở dữ liệu hướng đối tượng và cơ sở dữ liệu hướng đối tượng phân tán, các ưu điểm và các vấn đề cần xử lý trong cơ sở dữ liệu hướng đối tượng phân tán. Phần cuối chương tập trung phân tích thiết kế của thư viện OO7, cài đặt thực nghiệm thư viện này để đánh giá hiệu năng cơ sở dữ liệu hướng đối tượng phân tán trên các kịch bản duyệt đối tượng và truy vấn đối tượng. 1.1. Cơ sở dữ liệu hướng đối tượng Đến nay, mô hình Cơ sở dữ liệu (CSDL) quan hệ vẫn là mô hình tốt nhất và được áp dụng rộng rãi nhất hiện nay để giả quyết những bài toán có quy mô dữ liệu chưa thực sự quá lớn như Facebook hoặc Google. Tuy nhiên, mô hình CSDL quan hệ có những hạn chế khi phải thiết kế và thực hiện các ứng dụng CSDL phức tạp hơn. Ví dụ, CSDL dùng trong các 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, ... Các ứng dụng phức tạp này đòi hỏi cấu trúc dữ liệu phải mềm dẻo và linh hoạt hơn. 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 [1], [51], [44], [49]. CSDL HĐT có một số đặc điểm cơ bản như sau [4]: - 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. Hiện nay đã tồn tại một số hệ quản trị CSDL hướng đối tượng thương mại như GEMSTONE, Versant, ObjectStore. Ngoài ra các có các hệ thống CSDL hướng đối tượng khác như Orion, OpenOODB, IRIS, ...
8 1.1.1. Đối tượng Khái niệm cơ bản nhất trong CSDL HĐT 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. Khác với đối tượng trong ngôn ngữ lập trình hướng đối tượng chỉ tồn tại trong thời gian chương trình hoạt động, các đối tượng trong CSDL HĐT tồn tại lâu dài và được chia sẻ với nhiều chương trình và ứng dụng [4]. Đơn giản nhất, 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. OID được hệ thống tự động sinh ra và được sử dụng bên trong hệ thống để xác định từng đối tượng, tạo ra và quản lý các tham chiếu lẫn nhau giữa các đối tượng. Giá trị OID là bất biến trong suốt quá trình tồn tại của đối tượng trong hệ CSDL. 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 giá trị được định nghĩa bởi hệ thống 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 và A là miền các tên thuộc tính. Một giá trị của dữ liệu trong hệ thống đượ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)
9 Tập và bộ là các toán tử tạo lập dữ liệu, những toán tử này có vai trò chủ yếu trong các ứng dụng CSDL. Những toán tử tạo lập khác như danh sách và mảng, cũng được đưa vào để làm tăng sức mạnh của mô hình. 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]) Các đối tượng i1 và i2 là các đối tượng nguyên tử, còn i3 và i4 là các đối tượng được xây dựng. i3 là OID của một đối tượng với trạng thái của nó là một tập hợp, i4 cũng vậy. Khác biệt giữa i3 và i4 ở chỗ trạng thái của i4 là một tập các giá trị còn i3 gồm một tập các OID, vì thế i3 tham chiếu đến các đối tượng khác. Đối tượng i5 có trạng thái nhận giá trị bộ gồm bốn thuộc tính, giá trị mỗi thuộc tính là một đối tượng khác. Các đối tượng được hỗ trợ một số thao tác để cập nhật chuẩn định, cho phép thay đổi trạng thái đối tượng mà không thay đổi định danh của đối tượng. Điều này tương tự như khái niệm con trỏ trong ngôn ngữ lập trình, định danh còn tổng quát hơn con trỏ vì nó tồn tại trong hệ CSDL ngay cả khi chương trình đã kết thúc. Định danh đối tượng còn cho phép dùng chung đối tượng mà không gây ra vấn đề dư thừa dữ liệu. Các thuộc tính (attribute) thể hiện các đặc trưng của đối tượng và các phương thức (method) mô tả các hành động được phép thực hiện của những đối tượng này. Ví dụ, hành vi của một thang máy là “đi lên” hoặc “đi xuống”. 1.1.2. Kiểu và lớp Thuật ngữ kiểu (type) và lớp (class) trong CSDL HĐT có thể được sử dụng thay thế cho nhau, nhưng đôi khi chúng có nghĩa khác nhau. Chúng ta sử dụng thuật ngữ “lớp” khi đề cập đến cấu trúc mô hình đối tượng cụ thể và thuật ngữ “kiểu” được đề cập tới miền của các đối tượng.