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ở dữ liệu hướng đối tượng mờ

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:138

Thêm vào BST

Báo xấu

35
lượt xem 7
download

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

Mục tiêu của luận án là đề xuất đại số đối tượng mờ mới, quy trình và phương pháp xử lý, tối ưu hóa truy vấn dựa trên đại số đã đề xuất kết hợp với các giải pháp như phép biến đổi tương đương và giải thuật Heuristic. Bên cạnh đó, luận án cũng đề xuất các bước tiền xử lý như so sánh tính tương tự của hai đối tượng mờ và thuật toán gom cụm EMC (Expectation-Maximization-Coefficient). 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ĩ ngành Máy tính: 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ờ

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. GS.TS. Đoàn Văn Ban 2. TS. 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ẽ .......................................................................................................8 MỞ ĐẦU ...................................................................................................................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Ờ .......................................................15 1.1 Giới thiệu bài toán ...........................................................................................15 1.2 Các nghiên cứu liên quan ................................................................................16 1.2.1 Các mô hình CSDL HĐT mờ ..................................................................16 1.2.2 Tiền xử lý dữ liệu (đối sánh và gom cụm) cho mô hình CSDL HĐT mờ ..........................................................................................................................18 1.2.3 Xử lý và tối ưu hóa truy vấn mờ .............................................................18 1.3 Các vấn đề nghiên cứu và giải pháp................................................................19 1.3.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ờ ..........................................................................................................................19 1.3.2 Mô hình hóa UML của dữ liệu mờ ..........................................................21 1.3.3 Lớp mờ ....................................................................................................22 1.3.4 Giá trị thuộc tính mờ ...............................................................................25 1.3.5 Biểu diễn các giá trị thuộc tính mơ hồ cho đối tượng mờ .......................26 1.3.6 Quan hệ tổng quát hóa mờ.......................................................................29 1.3.7 Quan hệ kết tập mờ..................................................................................34 1.3.8 Quan hệ kết hợp mờ ................................................................................37 1.3.9 Quan hệ phụ thuộc mờ ............................................................................40 1.3.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ờ ..........................................................................................................42 1.3.10.1 Mô hình cơ sở dữ liệu hướng đối tượng mờ (FOODB) ..................42
2 1.3.10.2 Chuyển đổi biểu đồ lớp UML mờ ...................................................43 1.3.10.3 Chuyển đổi các lớp..........................................................................43 1.3.10.4 Chuyển đổi quan hệ kết tập .............................................................46 1.3.10.5 Chuyển đổi quan hệ kết hợp............................................................47 1.3.10.6 Chuyển đổi các quan hệ phụ thuộc .................................................49 1.3.11 Truy vấn mờ FOQL ...............................................................................50 1.4 Giải pháp cho bài toán.....................................................................................50 1.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 ..................................................................53 2.1 Xử lý truy vấn mờ dựa vào độ đo tương tự .....................................................53 2.1.1 So sánh tính tương tự của hai đối tượng mờ ...........................................53 2.1.1.1 Độ đo tương tự và phi tương tự.........................................................54 2.1.1.2 Độ đo ngữ nghĩa của dữ liệu mờ .......................................................55 2.1.1.3 So sánh hai đối tượng dựa vào độ đo tương tự mờ ...........................56 2.1.2 Thuật toán xử lý truy vấn dựa vào độ đo tương tự ..................................68 2.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ờ ..75 2.2.1 Phương pháp gom cụm dữ liệu bằng thuật toán EM ...............................75 2.2.1.1 Mô hình Gaussian Mixture Model ....................................................75 2.2.1.2 Thuật toán EM...................................................................................76 2.2.1.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 ......................................................................................................79 2.2.1.4 Đánh giá thuật toán EMC dựa trên Log Likelihood .........................85 2.2.1.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 ...............................................................................................85 2.2.2 Phân các khoảng mờ ................................................................................87 2.2.2.1 Xác định tâm .....................................................................................87
3 2.2.2.2 Xác định các khoảng .........................................................................88 2.2.3 Xử lý truy vấn dựa trên các khoảng mở ..................................................89 2.2.4 Thuật toán xử lý truy vấn trên các cụm ...................................................93 2.3 Xử lý truy vấn dựa vào đại số gia tử ...............................................................94 2.4 Đánh giá thực nghiệm .....................................................................................95 2.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Ờ .....................................................................................98 3.1 Các phép toán đại số trong cơ sở dữ liệu hướng đối tượng mờ ......................99 3.1.1 Đại số đối tượng ......................................................................................99 3.1.2 Đại kết hợp mờ ........................................................................................99 3.1.3 Mô hình đại số kết hợp các đối tượng mờ ...............................................99 3.1.4 Các phép toán đại số kết hợp mờ ..........................................................100 3.1.4.1 Tích mờ × .......................................................................................102 3.1.4.2 Kết nối mờ ⋈ ..................................................................................102 3.1.4.3 Phép hợp mờ ∪ ................................................................................103 3.1.4.4 Phép trừ mờ ≃ .................................................................................103 3.1.4.5 Phép giao mờ ∩ ...............................................................................104 3.1.4.6 Phép chia mờ ÷ ...............................................................................104 3.1.5 Các phép toán mở rộng..........................................................................105 3.1.5.1 Phép chiếu mờ 𝜫 .............................................................................105 3.1.5.2 Phép chọn mờ ..................................................................................105 3.2 Ngôn ngữ truy vấn mờ FOQL .......................................................................106 3.2.1 Truy vấn mờ FOQL ...............................................................................106 3.2.2 Mô hình lớp mờ .....................................................................................106 3.2.3 Cấu trúc câu truy vấn mờ ......................................................................108
4 3.2.4 Phương pháp xử lý truy vấn mờ ............................................................108 3.2.4.1 Các bước của phương pháp .............................................................108 3.2.4.2 Quy trình xử lý truy vấn mờ ...........................................................110 3.2.4.3 Cây truy vấn và đồ thị truy vấn .......................................................110 3.3 Tối ưu hóa truy vấn mờ .................................................................................114 3.3.1 Các phép biến đổi tương đương ............................................................114 3.3.1.1 Tối ưu hóa kế hoạch thực thi truy vấn ............................................116 3.3.1.2 Không gian tìm kiếm và các luật chuyển đổi ..................................117 3.3.1.3 Thuật toán tối ưu hóa truy vấn mờ ..................................................117 3.3.1.4 Đánh giá thực nghiệm .....................................................................121 3.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ờ.......................................74 Bảng 2.2: Danh sách dữ liệu phòng từ kết quả truy vân của trường hợp 1 ..............74 Bảng 2.3. Danh sách dữ liệu phòng từ kết quả truy vân của trường hợp 2...............75 Bảng 2.4: Bảng dữ liệu của các đối tượng về "Điểm Toán" .....................................83 Bảng 2.5: Kết quả phân cụm của thuật toán EMC ....................................................84 Bảng 2.6: Bảng kết quả thống kê dữ liệu ..................................................................86 Bảng 2.7: Xác định khoảng mờ của thuộc tính định lượng "Điểm toán" .................89 Bảng 2.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 ..............................................................................................................90 Bảng 2.9: Các giá trị khoảng mờ của thuộc tính Điểm Toán....................................92 Bảng 2.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. .............................................................................................................92 Bảng 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" .....................................................................................................................93 Bảng 2.12: Thời gian thực thi của thuật toán ............................................................95 Bảng 2.13: Sử dụng bộ nhớ trong các thuật toán ......................................................96
8 Danh sách hình vẽ Hình 1.1. Biểu diễn dữ liệu mờ tuổi ..........................................................................20 Hình 1.2. Lớp mờ ......................................................................................................25 Hình 1.3. Quan hệ tổng quát mờ ...............................................................................34 Hình 1.4.Mối quan hệ kết tập mờ..............................................................................37 Hình 1.5.Mối quan hệ kết hợp mờ ............................................................................39 Hình 1.6. Mối quan hệ phụ thuộc mờ .......................................................................41 Hình 1.7.Mô hình dữ liệu UML mờ ..........................................................................41 Hình 1.8.Chuyển đổi các lớp trong UML mờ sang lược đồ cơ sở dữ liệu hướng đối tượng mờ. ..................................................................................................................45 Hình 1.9.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ờ .............................................................................................................46 Hình 1.10.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ờ .............................................................................................................47 Hình 1.11.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ờ. ............................................................................................................49 Hình 2.1.Nghiên cứu điển hình về so sánh các đối tượng mờ ..................................57 Hình 2.2. Tính toán sự giống nhau giữa hai đối tượng mờ 𝑜1 và 𝑜2 .......................60 Hình 2.3. Trường hợp I (a) so sánh hai phòng ..........................................................61 Hình 2.4.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) ........................................................................62 Hình 2.5: Trường hợp I (b) So sánh phòng ...............................................................63 Hình 2.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) .................................................................................64 Hình 2.7: Trường hợp II Các phòng được mô tả bởi các thuộc tính rõ và mờ. ........64 Hình 2.8: Đồ thị biểu diễn một vòng lặp của thuật toán EM. ...................................78 Hình 2.9: Các khoảng mờ .........................................................................................88 Hình 2.10: Thời gian thực thi trong thuật toán .........................................................95 Hình 2.11: Đánh giá việc sử dụng bộ nhớ cho các bộ dữ liệu khác nhau .................96 Hình 3.1: Phương pháp xử lý truy vấn hướng đối tượng mờ ..................................108 Hình 3.2: Cây truy vấn ............................................................................................111
9 Hình 3.3: Đồ thị truy vấn ........................................................................................111 Hình 3.4: Đồ thị lược đồ phân cấp lớp mờ .............................................................111 Hình 3.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. ....................................................113 Hình 3.6: Các cây xử lý truy vấn tương đương .......................................................117 Hình 3.7: Cây đại số đối tượng tối ưu hóa truy vấn mờ.........................................120 Hình 3.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. Một số đề xuất và triển khai toán học mờ đẫ được áp dụng hiệu quả trên các hệ thống quản lý cơ sở dữ liệu nói chung như [12] - [15] và như vậy mô hình cơ sở dữ liệu hướng đối tượng mờ đã được đề xuất trên cơ sở áp dụng toán học mờ [16] - [21]. Mô hình cơ sở dữ liệu hướng đối tượng mờ là một mô hình cơ sở dữ liệu hướng đối tượng mở rộng, trong đó các giá trị thuộc tính của các đối tượng có thể được biểu
11 diễn bằng các tập mờ. Do đó, các lớp, các mối quan hệ lớp đối tượng và các mối quan hệ lớp với lớp có thể cũng mờ. Một số nghiên cứu liên quan về mô hình cơ sở dữ liệu hướng đối tượng mờ đã đề xuất như:  Các mô hình CSDL HĐT mờ: Mô hình cơ sở dữ liệu hướng đối tượng mờ đã được đề xuất bởi M.Umano và các cộng sự [22], trong đó giá trị của thuộc tính đối tượng là các giá trị mờ với một hệ số chắc chắn, và một ngôn ngữ thao tác dữ liệu trên mô hình này là SQL. Mô hình với thông tin không chắc chắn được đề xuất bởi Gyseghem và Caluwe [23], đặc tả tính mờ và không chắc chắn bằng cách sử dụng lần lượt các tập mờ và phân bố khả năng. Mô hình mở rộng dựa trên đồ thị do G. Bordogna và các cộng sự [16], [21]. Mô hình dựa trên quan hệ tương tự, phạm vi của các giá trị thuộc tính được sử dụng để biểu diễn tập các giá trị cho phép của một thuộc tính trong một lớp được trình bày trong [24]. Mô hình dựa vào lý thuyết khả năng, tính mơ hồ được biểu diễn trong phân cấp lớp, mức độ bao hàm của lớp con trong lớp cha được xác định dựa trên mức độ bao hàm các miền mờ của các thuộc tính của lớp cha đối với các miền mờ của các thuộc tính của lớp con [25]. Cũng dựa trên phân bố khả năng, trong [26] một số khái niệm chính trong CSDL hướng đối tượng chẳng hạn đối tượng, các mối quan hệ đối tượng/lớp, lớp con/lớp cha và đa thừa kế được đưa ra trong môi trường thông tin mờ. Mô hình dựa trên lý thuyết xác suất đầu tiên được nhóm tác giả Kornatzky và Shimony đề xuất năm 1994 [27]. Trong mô hình này, lớp được định nghĩa như một tập các thuộc tính mà giá trị của chúng có thể kết hợp với một phân bố xác suất. Lược đồ được định nghĩa như một tập các lớp có phân cấp kết hợp với xác suất có điều kiện để một đối tượng của một lớp thuộc về lớp con của nó. Bên cạnh đó một mô hình mới về xác suất đã được B. Ding và các cộng sự đề xuất [28] nhằm mô tả một diễn dịch xác suất của các quan hệ trên các giá trị tập mờ và một đại số cho các bộ ba xác suất mờ được nghiên cứu và định nghĩa một cách hình thức.  Tiền xử lý dữ liệu (đối sánh và gom cụm) cho mô hình CSDL HĐT mờ: Thuật toán GNP phân cụm cơ sở dữ liệu được đề xuất [29]. GNP tạo các cụm dựa trên phân loại mẫu, trong đó nhãn cụm được gán cho mỗi đối tượng được biểu diễn bằng một tập hợp các đặc trưng mờ. Việc tối ưu hóa các cụm được thực
12 hiện để các đối tượng có độ tương tự cao được đưa vào cùng một cụm. L. Yan và các cộng sự [30] phân biệt các thực thể trong cơ sở dữ liệu hướng đối tượng mờ dựa trên thước đo ngữ nghĩa của dữ liệu mờ, để so sánh một cách tổng quát hơn các đối tượng và lớp với kiểu dữ liệu mờ. Phương pháp này cũng có thể được sử dụng trong cơ sở dữ liệu mờ hoặc thậm chí mô hình cơ sở dữ liệu quan hệ cổ điển. Đề xuất mới của M. C. Mouna và các cộng sự [31] về phương pháp tính toán tính tương tự để so sánh hai đối tượng mờ thông qua các thuộc tính mờ bằng cách sử dụng độ đo khoảng cách Euclide. A. Mhedhbi và S. Salihoglu [4] phát triển phép đo độ tương tự dựa trên mô hình đối sánh Tversky và áp dụng nó trên các tập mờ bằng cách sử dụng lý thuyết tập mờ và các phép toán của chúng. Mô hình này cung cấp một phương pháp so sánh các đối tượng có nội dung mơ hồ / mờ.  Xử lý và tối ưu hóa truy vấn: X. Hu và các cộng sự phát triển [32] mô hình dữ liệu hướng đối tượng mờ mới (F-model) và định nghĩa đại số kết hợp mờ mở rộng (FA-algebra), dựa trên các kết hợp mờ, truy vấn mờ được đề xuất nhằm xử lý các giá trị mờ. Các phép toán lý thuyết tập hợp, cụ thể là phép hợp, phép giao và phép hiệu dựa trên trên cấu trúc lớp. Các phép toán được thiết lập dựa trên thành viên của lớp tương ứng chứa các đối tượng mờ được phát triển bằng cách sử dụng giá trị chân lý của đối tượng và nhận dạng đối tượng nhằm giúp cho truy vấn xác định các đối tượng có giá trị mờ. Đề xuất [33] tối ưu hóa truy vấn dựa vào biểu thức đường dẫn và cách viết lại câu truy vấn. Tuy nhiên, trong các mô hình đề xuất trên còn thiếu định nghĩa chính thức một thiết kế kiến trúc, định nghĩa về các phép toán đại số đối tượng mờ và ngôn ngữ truy vấn. Do đó cần có một đề xuất mới nhằm đảm bảo tính hệ thống cho mô hình cơ sở dữ liệu hướng đối tượng mờ hoạt động hiệu quả hơn. Mục tiêu của luận án là đề xuất đại số đối tượng mờ mới, quy trình và phương pháp xử lý, tối ưu hóa truy vấn dựa trên đại số đã đề xuất kết hợp với các giải pháp như phép biến đổi tương đương và giải thuật Heuristic. Bên cạnh đó, luận án cũng đề xuất các bước tiền xử lý như so sánh tính tương tự của hai đối tượng mờ và thuật toán gom cụm EMC (Expectation-Maximization-Coefficient). Các vấn đề liên quan đến mục tiêu nghiên cứu được trình bày trong luận án bao gồm.
13 1. Nhằm tăng tính hiệu quả cho quá trình xử lý truy vấn dữ liệu có các đại diện thông tin là mờ, luận án đề xuất phương pháp gom cụm và so sánh tính tương tự giữa hai đối tượng một cách tổng quát nhất, cụ thể hơn để so sánh tính tương tự giữa hai đối tượng luận án đã sử dụng các kỹ thuật khác nhau đó là: tính độ đo ngữ nghĩa, độ đo Euclidean. Bằng các kỹ thuật như vậy, tác giả thực hiện so sánh hai đối tượng trong các trường hợp như: hai đối tượng có cùng thể hiện hoặc không cùng thể hiện của một lớp, hai đối tượng có giá trị thuộc tính là mờ hoặc rõ hay cả hai đối tượng rõ/mờ. Bên cạnh đó, luận án đề xuất thuật toán phân cụm EMC được cải tiến dựa trên thuật toán Expectation Maximization (EM) bằng cách bổ sung bước (C) vào thuật toán để tăng độ mềm dẻo và giảm tối ưu hóa cục bộ và tăng tối ưu hóa toàn cục trong quá trình phân cụm. Luận án cũng đánh giá tính hiệu quả của thuật toán phân cụm EMC bằng phương pháp đánh giá sự khác biệt giữa các nhóm đã đề xuất. Nhằm đảm bảo cho hệ thống thực hiện câu truy vấn linh hoạt và tự nhiên hơn, luận án đề xuất phương pháp phân các khoảng mờ dựa trên kết quả của thuật toán gom cụm EMC. 2. Thông qua các đề xuất đối sánh và gom cụm dữ liệu, luận án đề xuất các thuật toán xử lý truy vấn mờ mới như: Thuật toán xử lý truy vấn đơn, đa điều kiện mờ FQSIMSC (Fuzzy Query Sim Single Condition) và FQSIMMC (Fuzzy Query Sim Multi-Condition) sử dụng đại lượng tính toán độ đo tương tự của SIM để trích rút các đối tượng mờ, hay như thuật toán xử lý truy vấn mờ FQSEM (Fuzzy Query SEM) sử dụng đại lượng tính toán SEM để trích rút dữ liệu có dạng phân bố khả năng. Hơn nữa, luận án cũng đã đề xuất thuật toán xử lý truy vấn trên các khoảng mờ FQINTERVAL (Fuzzy Query Interval), nhằm giúp người dùng thực hiện trích lọc dữ liệu tự nhiên hơn. 3. Đề xuất đại số kết hợp mờ mới. Trong đó luận án định nghĩa các phép toán kết hợp mờ như (Phép chọn mờ, phép nối mờ, phép chiếu mờ, phép chia mờ, phép trừ mờ, phép hợp mờ và phép giao mờ làm cơ sở cho việc xây dựng đại số truy vấn mờ cho mô hình cơ sở dữ liệu hướng đối tượng mờ. 4. Luận án đề xuất kiến trúc xử lý và tối ưu hóa truy vấn mờ. Cụ thể, luận án phát triển thuật toán heuristic tối ưu hóa đại số đối tượng mờ dựa trên các
14 quy tắc của phép biến đổi tương đương. Phân tích trên một số thử nghiệm sử dụng thuật toán đề xuất cho thấy hiệu suất xử lý truy vấn tốt hơn, điều này chứng tỏ sự nâng cao hiệu quả của phương pháp đã đề xuất. Để thực hiện được các mục tiêu trên, luận án được tổ chức như sau: Ngoài phần mở đầu, kết luận và tài liệu tham khảo, luận án được chia thành 3 chương, trong đó: Chương thứ nhất trình bày khái quát về cơ sở dữ liệu hướng đối tượng mờ. Nội dung của chương này bao gồm: các khái niệm, các phép toán cơ bản của lý thuyết tập mờ. Trong chương này trình bày cụ thể mô hình cơ sở dữ liệu hướng đối tượng với các khái niệm về đối tượng mờ, lớp mờ, phân cấp thừa kế mờ và mô hình lớp mờ và các quan hệ mờ. Chương thứ hai giới thiệu các thuật toán xử lý truy vấn mờ mới dựa vào các tính toán đối sánh và gom cụm dữ liệu. Để so sánh tính tương tự giữa các đối tượng nếu chúng đảm bảo một trong hai yếu tố: thứ nhất hai đối tượng được gọi là tương tự nếu chúng có cùng thể hiện của một lớp các đối tượng, yếu tố thứ hai là hai đối tượng được gọi là tương tự nếu giá trị một trong các thuộc tính của lớp này có ngữ nghĩa tương tự với giá trị thuộc tính của lớp kia. Một đề xuất quan trọng trong chương này là đề xuất thuật toán gom cụm dữ liệu EMC được cải tiến từ thuật toán gom cụm dữ liệu cực đại hóa kỳ vọng (EM). Các kết quả đánh giá thuật toán cho thấy tính hiệu quả cũng như tính mềm dẻo với số cụm được tùy biến tùy thuộc vào từng ứng dụng cụ thể sẽ có số cụm được phân khác nhau. Thuật toán gom cụm EMC tăng tính hiệu quả cho việc xử lý và trích rút dữ liệu cho câu truy vấn trên các cụm đó. Chương thứ ba giới thiệu các phép toán đại số đối tượng mới như (phép chiếu mờ, giao mờ, hợp mờ, chọn mờ, trừ mờ, tích đề các mờ, nối mờ) và các phép biến đổi tương đương mờ. Một chủ đề không thể thiếu đối với mọi hệ quản trị cơ sở dữ liệu đó là tối ưu hóa truy vấn bằng phương pháp Heuristic.
15 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.1 Giới thiệu bài toán Hệ thống thông tin đã cách mạng hóa cách thức lưu trữ và xử lý thông tin đa dạng, phức tạp. Kết quả là, khối lượng thông tin đã tăng lên đáng kể dẫn đến quá tải thông tin. Do đó, việc phân tích lượng lớn dữ liệu có sẵn và đưa ra các quyết định quản lý phù hợp trở nên khó khăn. Trong thực tế, hệ thống thông tin chủ yếu sử dụng CSDL quan hệ [12], [14], [34] - [38], hoặc CSDL hướng đối tượng [39] - [42] để lưu trữ các tập hợp dữ liệu này. 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. Một vấn đề khác, sử dụng mô hình quan hệ, hướng đối tượng đang gặp phải nhiều hạn chế của việc mô tả và xử lý các thông tin không chắc chắn, không đầy đủ, theo đó là một quy trình truy vấn không phù hợp cho việc ra quyết định. 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 tự nhiên. Tuy nhiên, nhiều ứng dụng trong thế giới thực luôn 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 nhà khoa học tập trung nghiên cứu [2], [17], [30], [43] - [68]. Hơn nữa, cuộc cách mạng công nghiệp lần thứ tư, hay còn gọi là “Công nghiệp 4.0” (I4.0) được giới thiệu bởi Hamburg 2013 [102], đang được thực hiện trong những năm gần đây và tiếp theo dự kiến sẽ thay đổi sâu sắc các quy trình sản xuất và chế tạo trong tương lai, dẫn đến các nhà máy thông minh và môi trường công nghiệp được nối mạng sẽ được hưởng lợi từ các nguyên tắc thiết kế của công nghệ này: khả năng tương tác, ảo hóa, phân quyền, điều khiển và giao tiếp phân tán, khả năng thời gian thực, định hướng dịch vụ, bảo trì nhanh chóng và dễ dàng chi phí thấp [103]. Về công nghệ hiện đại, Công nghiệp 4.0 gắn liền với việc ứng dụng và xử lý dữ liệu thông minh trong các lĩnh vực: hệ thống thần kinh nhân tạo, Internet công nghiệp, giải pháp đám mây và dịch vụ phi tập trung, cũng như xử lý và khai thác dữ liệu lớn. Các công trình của Klaus-Dieter Thoben, Stefan Wiesner và Thorsten Wuest [104], Robert
16 Lawrence Wichmann, Boris Eisenbart và Kilian Gericke [105] dành cho những nghiên cứu này về công nghệ xử lý dữ liệu lớn theo thời gian thực. Bên cạnh đó, các dịch vụ tư vấn trực tuyến cũng đã xuất hiện trên các ứng dụng web thông qua công cụ tư vấn tự động chatbot [106], [107] bằng cách ứng dụng trí tuệ nhân tạo và dữ liệu đám mây nhằm cung cấp thông tin cho khách hàng. Hay như, robot có thể giao tiếp với con người bằng ngôn ngữ tự nhiên [108]. Qua đó ta có thể nhận thấy rằng tiền xử lý dữ liệu là một bước rất quan trọng trong việc giải quyết xử lý truy vấn CSDL và như vậy cơ sở dữ liệu hướng đối tượng mờ cũng cần có các bước tiền xử lý dữ liệu như vậy. Trong luận án này, tác giả tập trung nghiên cứu, phát triển các phương pháp xử lý truy vấn, các phép toán đại số đối tượng mờ, ngôn ngữ truy vấn mờ và các thuật toán tiền xử lý dữ liệu. Nhằm đảm bảo cho hệ thống CSDL HĐT mờ hoàn thiện hơn trong các cơ chế vận hành, xử lý dữ liệu mờ. 1.2 Các nghiên cứu liên quan Trong những năm qua đã có nhiều nghiên cứu liên quan về mô hình cơ sở dữ liệu hướng đối tượng mờ theo các cách tiếp cận khác nhau và các kết quả đạt được trên các mô hình này là: 1.2.1 Các mô hình CSDL HĐT mờ 1) Mô hình cơ sở dữ liệu hướng đối tượng mờ đã được đề xuất bởi M.Umano và các cộng sự [22], trong đó giá trị của thuộc tính đối tượng là các giá trị mờ với một hệ số chắc chắn, và một ngôn ngữ thao tác dữ liệu trên mô hình này là SQL. 2) Mô hình CSDL hướng đối tượng mờ và không chắc chắn được đề xuất bởi Gyseghem và Caluwe [23], đặc tả tính mờ và không chắc chắn bằng cách sử dụng lần lượt các tập mờ và phân bố khả năng. Hành vi và cấu trúc của đối tượng có thể được định nghĩa không đầy đủ, từ đó cho phép đặc tả được các thể hiện của các đối tượng một cách tự nhiên như trong thế giới thực. Thừa kế bộ phận, thừa kế có điều kiện và đa thừa kế cũng được giới thiệu trong mô hình này. 3) Mô hình CSDL hướng đối tượng mờ được đề xuất bởi G. Bordogna và các cộng sự [16], [21] bằng cách mở rộng mô hình đối tượng dựa trên đồ thị. Mức độ mờ được biểu diễn bởi các từ chỉ mức độ, chẳng hạn như {không,
17 rất lưu loát, lưu loát, trung bình, cao, rất cao, hoàn toàn}, kết hợp với thể hiện mối quan hệ giữa các đối tượng với một lớp. Các khái niệm lớp mờ, phân cấp lớp mờ và các phép toán được định nghĩa dựa trên đồ thị để chọn, duyệt CSDL hướng đối tượng mờ được sử dụng để biểu diễn và xử lý các thông tin mờ. 4) Dựa trên quan hệ tương tự, phạm vi của các giá trị thuộc tính được sử dụng để biểu diễn tập các giá trị cho phép của một thuộc tính trong một lớp được trình bày trong [24] . Độ thuộc thành viên của đối tượng thuộc vào một lớp được tính dựa trên mức độ bao hàm các giá trị thuộc tính của đối tượng và trong các phạm vi giá trị thuộc tính của lớp. Phân cấp lớp mạnh hay yếu được xác định dựa vào sự tăng đều hay giảm đều theo độ thuộc thành viên của một lớp con vào trong lớp cha của nó. 5) Dựa vào lý thuyết khả năng, tính mơ hồ được biểu diễn trong phân cấp lớp, các miền mờ của các thuộc tính lớp con được xác định bằng cách thu hẹp miền của các thuộc tính của lớp cha, mức độ bao hàm của lớp con trong lớp cha được xác định dựa trên mức độ bao hàm các miền mờ của các thuộc tính của lớp cha đối với các miền mờ của các thuộc tính của lớp con [25]. Cũng dựa trên phân bố khả năng, trong [26] một số khái niệm chính trong CSDL hướng đối tượng chẳng hạn đối tượng, các mối quan hệ đối tượng/lớp, lớp con/lớp cha và đa thừa kế được đưa ra trong môi trường thông tin mờ. 6) Mô hình dựa trên lý thuyết xác suất đầu tiên do nhóm tác giả Kornatzky và Shimony đề xuất năm 1994 [27]. Trong mô hình này, lớp được định nghĩa như một tập các thuộc tính mà giá trị của chúng có thể kết hợp với một phân bố xác suất. Lược đồ được định nghĩa như một tập các lớp có phân cấp kết hợp với xác suất có điều kiện để một đối tượng của một lớp thuộc về lớp con của nó. Các tác giả cũng đã phát triển một ngôn ngữ truy vấn để thao tác chọn các đối tượng thỏa một xác suất được kết hợp với các truy vấn. Bên cạnh đó một mô hình mới về xác suất đã được đề xuất [28] nhằm mô tả một diễn dịch xác suất của các quan hệ trên các giá trị tập mờ và một đại số cho các bộ ba xác suất mờ được nghiên cứu và định nghĩa một cách hình thức.
18 1.2.2 Tiền xử lý dữ liệu (đối sánh và gom cụm) cho mô hình CSDL HĐT mờ 1) Thuật toán phân cụm cơ sở dữ liệu sử dụng lập trình mạng di truyền (GNP) [29] tách được các cụm đối tượng dựa trên phân loại mẫu, trong đó nhãn cụm gán cho mỗi đối tượng được biểu diễn bằng một tập hợp các đặc trưng mờ. GNP là một trong những thuật toán tiến hóa và khám phá các quy tắc mờ từ cơ sở dữ liệu hướng đối tượng mờ. Việc tối ưu hóa các cụm được thực hiện để các đối tượng có độ tương tự cao được đưa vào cùng một cụm. 2) Nhằm mục đích phân biệt các đối tượng trong cơ sở dữ liệu hướng đối tượng mờ, L. Yan và Z. M. Ma [30] sử dụng độ đo ngữ nghĩa của dữ liệu mờ, để so sánh một cách tổng quát hơn các đối tượng và lớp với kiểu dữ liệu mờ. 3) Một trong những vấn đề quan trọng nhất trong cơ sở dữ liệu mờ là làm thế nào để quản lý sự xuất hiện của sự mơ hồ, không chính xác và không chắc chắn. Các phương pháp đánh giá tính tương tự là cần thiết để tìm các đối tượng gần với các đối tượng mờ đã cho khác hoặc được sử dụng trong một truy vấn mơ hồ của người dùng. Các phương pháp như vậy cũng có thể được sử dụng trong cơ sở dữ liệu mờ hoặc thậm chí mô hình cơ sở dữ liệu quan hệ cổ điển. Y. Bashon và các cộng sự [31] đề xuất phương pháp tính toán tính tương tự để so sánh hai đối tượng mờ thông qua các thuộc tính mờ bằng cách sử dụng độ đo khoảng cách Euclide. So sánh được thực hiện cho hai trường hợp: cả hai thuộc tính là mờ hoặc một thuộc tính rõ với một thuộc tính mờ. 4) Y. Bashon và các cộng sự [4] phát triển phép đo độ tương tự dựa trên mô hình đối sánh Tversky và áp dụng nó trên các tập mờ bằng cách sử dụng lý thuyết tập mờ và các phép toán của chúng. Mô hình này cung cấp một phương pháp so sánh các đối tượng có nội dung mơ hồ / mờ. 1.2.3 Xử lý và tối ưu hóa truy vấn mờ 1) S. Na và S. Park [32] đề xuất mô hình dữ liệu hướng đối tượng mờ mới (F- model) và định nghĩa đại số kết hợp mờ mở rộng (FA-algebra). F-model hỗ trợ các lớp mờ và liên kết mờ giữa các đối tượng mờ. Bằng đại số FA