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

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

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

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

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

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 Database)	Cơ sở dữ liệu hướng đối tượng 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