Luận án tiến sĩ ngành máy tính một số phương pháp xử lý truy vấn mới trên cơ sở

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Ệ ----------------------------- NGUYỄN TẤN THUẬN MỘT SỐ PHƯƠNG PHÁP XỬ LÝ TRUY VẤN MỚI TRÊN CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG MỜ LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH HÀ NỘI – 2021 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Ệ ----------------------------- Nguyễn Tấn Thuận MỘT SỐ PHƯƠNG PHÁP XỬ LÝ TRUY VẤN MỚI TRÊN CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG MỜ Chuyên ngành: Hệ thống thông tin Mã số: 9 48 01 04 LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. Trương Ngọc Châu Hà Nội – Năm 2021 1 Danh mục các thuật ngữ.5 Bảng các ký hiệu, từ viết tắt.6 Danh sách bảng biểu.7 Danh sách hình vẽ. 10 Chương 1 TỔNG QUAN VỀ BÀI TOÁN XỬ LÝ TRUY VẤN TRÊN MÔ HÌNH CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG MỜ.1 Giới thiệu bài toán.2 Các nghiên cứu liên quan.1 Các mô hình CSDL HĐT mờ.2 Tiền xử lý dữ liệu (đối sánh và gom cụm) cho mô hình CSDL HĐT mờ .3 Xử lý và tối ưu hóa truy vấn mờ.3 Các vấn đề nghiên cứu và giải pháp.1 Biểu diễn thông tin không hoàn hảo trong mô hình khái niệm dữ liệu mờ .2 Mô hình hóa UML của dữ liệu mờ.4 Giá trị thuộc tính mờ.5 Biểu diễn các giá trị thuộc tính mơ hồ cho đối tượng mờ.6 Quan hệ tổng quát hóa mờ.7 Quan hệ kết tập mờ.8 Quan hệ kết hợp mờ.9 Quan hệ phụ thuộc mờ.10 Ánh xạ mô hình dữ liệu UML mờ vào mô hình cơ sở dữ liệu hướng đối tượng mờ.1 Mô hình cơ sở dữ liệu hướng đối tượng mờ (FOODB).2 Chuyển đổi biểu đồ lớp UML mờ.3 Chuyển đổi các lớp.4 Chuyển đổi quan hệ kết tập.5 Chuyển đổi quan hệ kết hợp.6 Chuyển đổi các quan hệ phụ thuộc.11 Truy vấn mờ FOQL.4 Giải pháp cho bài toán.5 Kết luận chương 1. 51 Chương 2 CÁC PHƯƠNG PHÁP XỬ LÝ TRUY VẤN MỜ DỰA VÀO ĐỘ ĐO TƯƠNG TỰ VÀ GOM CỤM DỮ LIỆU.1 Xử lý truy vấn mờ dựa vào độ đo tương tự.1 So sánh tính tương tự của hai đối tượng mờ.1 Độ đo tương tự và phi tương tự.2 Độ đo ngữ nghĩa của dữ liệu mờ.3 So sánh hai đối tượng dựa vào độ đo tương tự mờ.2 Thuật toán xử lý truy vấn dựa vào độ đo tương tự.2 Xử lý truy vấn mờ dựa vào kỹ thuật gom cụm dữ liệu và phân khoảng mờ.1 Phương pháp gom cụm dữ liệu bằng thuật toán EM.1 Mô hình Gaussian Mixture Model.2 Thuật toán EM.3 Thuật toán gom cụm cải tiến EMC sử dụng mô hình thống kê hỗn hợp GMM.4 Đánh giá thuật toán EMC dựa trên Log Likelihood.5 Đánh giá thuật toán EMC bằng phương pháp phân tích sự khác biệt giữa các nhóm.2 Phân các khoảng mờ.3 Xử lý truy vấn dựa trên các khoảng mở.4 Thuật toán xử lý truy vấn trên các cụm.3 Xử lý truy vấn dựa vào đại số gia tử.4 Đánh giá thực nghiệm.5 Kết luận chương 2.

96 Chương 3 XỬ LÝ VÀ TỐI ƯU HÓA TRUY VẤN TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG MỜ.1 Các phép toán đại số trong cơ sở dữ liệu hướng đối tượng mờ.1 Đại số đối tượng.2 Đại kết hợp mờ.3 Mô hình đại số kết hợp các đối tượng mờ.4 Các phép toán đại số kết hợp mờ.2 Kết nối mờ ⋈.3 Phép hợp mờ 𝖴.4 Phép trừ mờ ≃.5 Phép giao mờ ∩.6 Phép chia mờ ÷.5 Các phép toán mở rộng.1 Phép chiếu mờ 𝜫.2 Phép chọn mờ.2 Ngôn ngữ truy vấn mờ FOQL.1 Truy vấn mờ FOQL.2 Mô hình lớp mờ.3 Cấu trúc câu truy vấn mờ.4 Phương pháp xử lý truy vấn mờ.1 Các bước của phương pháp.2 Quy trình xử lý truy vấn mờ.3 Cây truy vấn và đồ thị truy vấn.3 Tối ưu hóa truy vấn mờ.1 Các phép biến đổi tương đương.1 Tối ưu hóa kế hoạch thực thi truy vấn.2 Không gian tìm kiếm và các luật chuyển đổi.3 Thuật toán tối ưu hóa truy vấn mờ.4 Đánh giá thực nghiệm.4 Kết luận chương 3.122 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.124 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ.126 TÀI LIỆU THAM KHẢO.127 5 Danh mục các thuật ngữ Đại số kết hợp mờ Fuzzy association algebra Đồ thị lược đồ mờ Fuzzy object schema Graph Độ lệch chuẩn Standard deviation Hiệp phương sai Covariance Hệ số biến thiên Coefficient. Giá trị chân lý Truth value Kết hợp mờ Fuzzy association Không gian ngữ nghĩa Semantic space Kỳ vọng Mean Lớp cha Superclass Lớp con Subclass Mối quan hệ kế thừa Inheritance relationship Mối quan hệ đối tượng với lớp Object and Class relationship Mối quan hệ kết hợp mờ Fuzzy association relationship Mối quan hệ kết nhập mờ Fuzzy aggregation relationship Mối quan hệ tổng quát hóa Fuzzy genralization relationship Phân cấp kế thừa mờ Fuzzy inheritance hierarchy 6 Bảng các ký hiệu, từ viết tắt EM (Expectation maximization) Thuật toán Cực đại hóa Kì vọng EMC (Expectation maximization Thuật toán Cực đại hóa Kì vọng dựa Coefficient) vào hệ số biến thiên FA (Fuzzy Association) Kết hợp mờ FC (Fuzzy Class) Lớp mờ GMM (Gaussian Mixture Model) Mô hình Gaussian hỗn hợp OQL (Object Query Language) Ngôn ngữ truy vấn hướng đối tượng ODMG (Object Database Management Nhóm quản trị CSDL đối tượng, tổ Group) chức đề xuất mô hình ODMG và OQL OID (Object Indentifier) Định danh đối tượng rõ OODBMS (Object-Oriented Data Base Hệ quản trị cơ sở dữ liệu hướng đối Management System) tượng FOID (Fuzzy Object Indentifier) Định danh đối tượng mờ FOQL (Fuzzy Object Query Language) Ngôn ngữ truy vấn đối tượng mờ FOODBMS (Fuzzy Object Oriented Hệ quản trị cơ sở dữ liệu hướng đối Database Management System) tượng mờ SQL (Structured Query Language) Ngôn ngữ truy vấn có cấu trúc 7 Danh sách bảng biểu Bảng 2.1: Danh sách dữ liệu phòng của các đối tượng mờ.2: Danh sách dữ liệu phòng từ kết quả truy vân của trường hợp 1. Danh sách dữ liệu phòng từ kết quả truy vân của trường hợp 2.4: Bảng dữ liệu của các đối tượng về "Điểm Toán".5: Kết quả phân cụm của thuật toán EMC.6: Bảng kết quả thống kê dữ liệu.7: Xác định khoảng mờ của thuộc tính định lượng "Điểm toán".8: Danh sách dữ liệu từ kết quả truy vấn trực tiếp trên các vùng mờ cho trường hợp 1.9: Các giá trị khoảng mờ của thuộc tính Điểm Toán.10: Danh sách dữ liệu từ kết quả truy vấn trực tiếp trên các vùng mờ cho trường hợp 2.11: Kết quả truy vấn với mức độ thỏa mãn điều kiện truy vấn "Điểm Toán hơi cao".12: Thời gian thực thi của thuật toán.13: Sử dụng bộ nhớ trong các thuật toán.96 8 Danh sách hình vẽ Hình 1. Biểu diễn dữ liệu mờ tuổi.

Quan hệ tổng quát mờ.Mối quan hệ kết tập mờ.Mối quan hệ kết hợp mờ. Mối quan hệ phụ thuộc mờ.Mô hình dữ liệu UML mờ.Chuyển đổi các lớp trong UML mờ sang lược đồ cơ sở dữ liệu hướng đối tượng mờ.Chuyển đổi các lớp con trong UML mờ sang lược đồ cơ sở dữ liệu hướng đối tượng mờ.Chuyển đổi các tập hợp trong UML mờ sang lược đồ cơ sở dữ liệu hướng đối tượng mờ.Chuyển đổi các liên kết trong UML mờ sang lược đồ cơ sở dữ liệu hướng đối tượng mờ.Nghiên cứu điển hình về so sánh các đối tượng mờ. Tính toán sự giống nhau giữa hai đối tượng mờ 𝑜1 và 𝑜2. Trường hợp I (a) so sánh hai phòng.Trường hợp I (a) Đại diện mờ về chất lượng và giá cả của hai phòng (Sử dụng các hàm thành viên khác nhau).5: Trường hợp I (b) So sánh phòng.6: Trường hợp I (a) Đại diện mờ về chất lượng và giá cả của hai (Sử dụng các hàm thành viên khác nhau).7: Trường hợp II Các phòng được mô tả bởi các thuộc tính rõ và mờ.8: Đồ thị biểu diễn một vòng lặp của thuật toán EM.10: Thời gian thực thi trong thuật toán.11: Đánh giá việc sử dụng bộ nhớ cho các bộ dữ liệu khác nhau.1: Phương pháp xử lý truy vấn hướng đối tượng mờ.2: Cây truy vấn.3: Đồ thị truy vấn.4: Đồ thị lược đồ phân cấp lớp mờ.5: Hai cây truy vấn cho truy vấn FQ2.

(a) Cây truy vấn tương ứng với biểu thức đại số đối tượng mờ cho FQ2. (b) Cây truy vấn ban đầu (chuẩn của FOQL) cho truy vấn FQ2. (c) Đồ thị truy vấn cho FQ2.6: Các cây xử lý truy vấn tương đương.7: Cây đại số đối tượng tối ưu hóa truy vấn mờ.8: Kết quả đánh gia thực nghiệm tối ưu hóa truy vấn mờ.122 10 MỞ ĐẦU Ngày nay, tính khả thi và tính hữu ích của toán học mờ như lý thuyết xác suất, lý thuyết tập mờ, lý thuyết khả năng, quan hệ tương tự [1] - [6], ., đã được minh chứng cho sự thành công trong một loạt các lĩnh vực gồm: kỹ thuật, khoa học máy tính, trí tuệ nhân tạo, xử lý thông tin và các hệ thống cơ sở dữ liệu (CSDL) [7] - [11]. Cùng với sự phát triển của toán học mờ, các mô hình CSDL hướng đối tượng đã được nghiên cứu và áp dụng rộng rãi trong việc phát triển các hệ thống phần mềm, nhiều hệ quản trị CSDL hướng đối tượng có tính thương mại đã được tạo ra như GEMSTONE, ORION, VBASE, OBJECTSTORE, POET, ….

Một mô hình dữ liệu đối tượng chuẩn ODMG đã được phát triển và dựa vào đó để thiết lập một số khái niệm cơ sở được gọi là mô hình hạt nhân cho mô hình CSDL hướng đối tượng. Mô hình hạt nhân đủ mạnh để thỏa mãn nhiều đòi hỏi của các ứng dụng mới, hơn nữa còn được dùng làm cơ sở để xác định những khác biệt chính giữa mô hình dữ liệu hướng đối tượng và các mô hình dữ liệu liệu truyền thống khác. Tuy nhiên, cả hai mô hình CSDL quan hệ và CSDL hướng đối tượng có khả năng đủ để xử lý đối tượng phức tạp nhưng bị hạn chế đối với các đại diện dữ liệu không chính xác hoặc không chắc chắn. Thêm vào đó, các hệ thống này chỉ có thể xử lý dữ liệu "cứng" (chính xác và xác định) trong thực tế.

Tuy nhiên, nhiều ứng dụng trên thế giới thực thường liên quan đến dữ liệu "mềm" (mơ hồ và không chính xác). Do đó, việc nghiên cứu ứng dụng cơ sở dữ liệu mờ và xử lý truy vấn để giải quyết những hạn chế của cơ sở dữ liệu quan hệ/hướng đối tượng rõ trong việc xử lý và lưu trữ các thông tin không chắc chắn, không đầy đủ trở thành một chủ đề nghiên cứu quan trọng được nhiều người tập trung nghiên cứu và triển khai ứng dụng. Thông qua các kết quả nghiên cứu trên, việc áp dụng lĩnh vực toán học mờ vào các mô hình cơ sở dữ liệu truyền thống/hướng đối tượng, nhằm xử lý và lưu trữ các thông tin không chắc chắn, không đầy đủ là rất cần thiết.