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

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

Có thể bạn quan tâm!

Xem toàn bộ 136 trang tài liệu này.

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

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.

Để đá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,

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.

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:

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

 Đề 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.