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

Luận án tiến sĩ toán học tập trung 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, nâng cao hiệu suất hệ thống.

• Tác giả: Mai Thúy Nga
• Người hướng dẫn: PGS.TS Đoàn Văn Ban
• Trường học: 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
• Chuyên ngành: Cơ sở Toán học cho Tin học
• Đề tài: 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
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2017
• Địa điểm: Hà Nội

Tóm tắt

I. Giới thiệu về luận án tiến sĩ

Luận án tiến sĩ này tập trung vào việ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. Nghiên cứu nhằm giải quyết các thách thức trong việc nâng cao hiệu suất của hệ thống truy vấn, đặc biệt trong môi trường phân tán. Cơ sở dữ liệu hướng đối tượng phân tán (CSDL HĐT PT) là một mô hình dữ liệu phức tạp, kết hợp giữa tính hướng đối tượng và sự phân tán dữ liệu. Luận án đề xuất các thuật toán mới để phân mảnh, cấp phát lớp, và tối ưu hóa truy vấn, nhằm giảm thiểu chi phí truyền dữ liệu và tăng hiệu suất hệ thống.

1.1. Mục tiêu nghiên cứu

Mục tiêu chính của luận án là nghiên cứu và đề xuất các giải pháp để tối ưu hóa truy vấn trong CSDL HĐT PT. Cụ thể, nghiên cứu tập trung vào việc phân mảnh dọc và cấp phát lớp các đối tượng, cũng như tối ưu hóa biểu thức đường dẫn trong truy vấn. Các giải pháp này nhằm giảm chi phí truyền dữ liệu và tăng hiệu suất xử lý truy vấn trong môi trường phân tán.

1.2. Đối tượng và phạm vi nghiên cứu

Đố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, và các thuật toán phân mảnh, cấp phát, và tối ưu hóa truy vấn. Phạm vi nghiên cứu bao gồm bài toán phân mảnh và cấp phát lớp, cũng như tối ưu hóa biểu thức đường dẫn trong truy vấn. Luận án sử dụng phương pháp nghiên cứu lý thuyết, xây dựng thuật toán, và thực nghiệm để đánh giá hiệu quả.

II. Cơ sở dữ liệu hướng đối tượng phân tán

Cơ sở dữ liệu hướng đối tượng phân tán (CSDL HĐT PT) là sự kết hợp giữa mô hình hướng đối tượng và sự phân tán dữ liệu. Mô hình này cho phép quản lý dữ liệu phức tạp và phân tán trên nhiều vị trí địa lý khác nhau. CSDL HĐT PT có các đặc trưng như tính đóng gói, kế thừa, và đa hình, giúp xử lý dữ liệu phức tạp hiệu quả hơn so với mô hình quan hệ truyền thống.

2.1. Kiến trúc CSDL HĐT PT

Kiến trúc của CSDL HĐT PT bao gồm các thành phần chính như quản lý đối tượng, quản lý giao dịch, và xử lý truy vấn. Mô hình này được thiết kế để tăng độ tin cậy, tính sẵn sàng, và khả năng mở rộng của hệ thống. Các hệ thống CSDL HĐT PT thường được triển khai trong các doanh nghiệp lớn với dữ liệu phân tán trên nhiều vị trí địa lý.

2.2. Các vấn đề trong CSDL HĐT PT

Một trong những vấn đề chính trong CSDL HĐT PT là xử lý truy vấn và tối ưu hóa hiệu suất. Các thách thức bao gồm việc phân mảnh dữ liệu, cấp phát lớp, và tối ưu hóa biểu thức đường dẫn. Các giải pháp hiện tại thường tách biệt giữa phân mảnh và cấp phát, dẫn đến hiệu suất không tối ưu. Luận án đề xuất các thuật toán mới để giải quyết các vấn đề này.

III. Phân mảnh và cấp phát lớp trong CSDL HĐT PT

Phân mảnh và cấp phát lớp là hai giai đoạn quan trọng trong thiết kế CSDL HĐT PT. Phân mảnh giúp chia nhỏ dữ liệu thành các phần nhỏ hơn, trong khi cấp phát lớp định vị các mảnh dữ liệu vào các trạm trên mạng. Mục tiêu của hai giai đoạn này là giảm chi phí truyền dữ liệu và tăng hiệu suất xử lý truy vấn.

3.1. Phân mảnh dọc và ngang

Phân mảnh dọc 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. Các thuật toán phân mảnh hiện tại thường tách biệt giữa phân mảnh và cấp phát, dẫn đến hiệu suất không tối ưu. Luận án đề xuất thuật toán phân mảnh dựa trên tương quan thuộc tính để giải quyết vấn đề này.

3.2. Thuật toán FragAlloS

Luận án đề xuất thuật toán FragAlloS để thực hiện phân mảnh dọc và cấp phát lớp một cách đồng thời. Thuật toán này sử dụng mô hình chi phí để tối ưu hóa quá trình phân mảnh và cấp phát, giúp giảm chi phí truyền dữ liệu và tăng hiệu suất xử lý truy vấn. Kết quả thực nghiệm cho thấy thuật toán FragAlloS có hiệu suất vượt trội so với các thuật toán truyền thống.

IV. Tối ưu hóa truy vấn trong CSDL HĐT PT

Tối ưu hóa truy vấn là một bài toán quan trọng trong CSDL HĐT PT, đặc biệt là với các truy vấn có chứa biểu thức đường dẫn. Mục tiêu của tối ưu hóa là tìm chiến lược thực thi truy vấn hiệu quả nhất, giảm thiểu chi phí truyền dữ liệu và tăng hiệu suất hệ thống.

4.1. 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 các đối tượng theo các thuộc tính hoặc phương thức. Tối ưu hóa biểu thức đường dẫn là một bài toán phức tạp, đặc biệt trong môi trường phân tán. Luận án đề xuất thuật toán PathExpOpt để tối ưu hóa biểu thức đường dẫn bằng cách sử dụng cơ chế sinh cây con cảm sinh và bộ lọc Bloom.

4.2. Thuật toán PathExpOpt

Thuật toán PathExpOpt được đề xuất để tối ưu hóa biểu thức đường dẫn trong CSDL HĐT PT. Thuật toán sử dụng quy hoạch động để tìm chiến lược thực thi tối ưu, giảm thiểu chi phí truyền dữ liệu và tăng hiệu suất xử lý truy vấn. Kết quả thực nghiệm cho thấy thuật toán PathExpOpt có hiệu suất vượt trội so với các thuật toán truyền thống.

Trích đoạn nội dung tài liệu

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. 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,. Đố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.

{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.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”. 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. 10 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 đó. Chúng ta không phân biệt giữa các đối tượng nguyên thủy (các giá trị), các đối tượng cấu trúc (bộ hoặc tập) và các đối tượng do người dùng định nghĩa. 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 miền đó.

Khả năng trừu tượng hóa của các lớp, được thể hiện qua tính đóng gói nhằm che dấu các cài đặt chi tiết của các phương thức và tương tác với thế giới bên ngoài thông qua các giao diện.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, … Định nghĩa kiểu của XeHoi như sau: type XeHoi attributes dongCo: DongCo cacGiamSoc: {GiamSoc} cacBanhXe: [traiTruoc: BanhXe, phaiTruoc: BanhXe, traiSau: BanhXe, phaiSau: BanhXe] hangSanXuat: HangSanXuat model: String namSanXuat: Date so_Serie: String soCho: Integer methods tinhTuoi(): Real thayBanh(diaDiem,banhXe) Định nghĩa lớp XeHoi có 8 thuộc tính và 2 phương thức. Bốn thuộc tính (model, namSanXuat, so_Serie, soCho) là những thuộc tính dựa trên giá trị, còn các thuộc tính còn lại dựa trên đối tượng. Thuộc tính cacGiamSoc nhận giá trị tập, thuộc tính cacBanhXe nhận giá trị bộ. Cũng chú ý ở đây thuộc tính dùng chữ thường và kiểu dùng chữ hoa, ví dụ dongCo là một thuộc tính còn DongCo là một kiểu của hệ thống.

Phương thức tinhTuoi() nhận ngày của hệ thống và giá trị thuộc 11 tính namSanXuat rồi tính ra ngày tháng (hai thuộc tính này đều có tính chất nội tại đối với đối tượng). Phương thức thayBanh() yêu cầu người dùng cung cấp tham số bên ngoài: diaDiem (nơi thực hiện thay thế bánh xe), và banhXe (bánh xe được thay thế là bánh xe nào). 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 ý. Ví dụ, lớp XeHoi có thể bổ sung các thao tác phức tạp hơn như tính giá quảng cáo dựa vào thời điểm của năm sản xuất.

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. Các thao tác của lớp biểu thị các phần của chương trình ứng dụng có liên kết chặt chẽ với dữ liệu. Như vậy, lớp cho phép mô hình hóa cả dữ liệu lẫn các thao tác, tuy nhiên các thao tác có thể không lưu cùng với các dữ liệu. Một khái niệm khác cần lưu ý, đó là sưu tập (collection).

Một sưu tập nhóm các đối tượng lại, một chuỗi các lớp là một kiểu cụ thể của sưu tập. Có thể phân biệt giữa sưu tập và lớp: Sưu tập không thể tạo ra đối tượng, nó là một lớp trừu tượng. Một đối tượng có thể tồn tại trong nhiều sưu tập, nhưng chỉ là một phần tử của một lớp duy nhất. Hợp phần Trong ví dụ 1.2, một số thuộc tính dựa trên giá trị, như là model và namSanXuat, còn những thuộc tính khác 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 (composition, aggregation) là một trong những đặc trưng mạnh của mô hình đối tượng. Nó cho phép chia sẻ các đối tượng, các đối tượng tham chiếu đến các đối tượng khác bằng OID giống như giá trị các thuộc tính dựa trên đối tượng.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.

Đối tượng phức hợp khác đối tượng hợp phần ở chỗ là không cho phép chia sẻ tham chiếu. Ví dụ kiểu XeHoi có thể có một thuộc tính với miền kiểu của nó là BanhXe. Với hai thể hiện của kiểu XeHoi như x1 và x2 thì sẽ không hợp lý khi cho chúng tham chiếu đến cùng một tập thể hiện của BanhXe vì trong thực tế người ta không cho rằng các bánh xe cùng lúc được dùng trên nhiều xe. Mối liên hệ đối tượng hợp phần giữa các kiểu có thể được biểu diễn bởi đồ thị hợp phần (composite graph) hoặc phân cấp hợp phần (aggregation hiearachy) trong trường hợp các đối tượng phức.

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ó.