Tài liệu Nghiên cứu các phụ thuộc hàm trong 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 VIỆN CÔNG NGHỆ THÔNG TIN VŨ ĐỨC QUẢNG NGHIÊN CỨU CÁC PHỤ THUỘC HÀM TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG MỜ LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2013 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 VIỆN CÔNG NGHỆ THÔNG TIN VŨ ĐỨC QUẢNG NGHIÊN CỨU CÁC PHỤ THUỘC HÀM TRONG CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG MỜ Chuyên ngành: BẢO ĐẢM TOÁN HỌC CHO MÁY TÍNH VÀ CÁC HỆ THỐNG TÍNH TOÁN Mã số: 62.46.35.01 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TS. Đoàn Văn Ban 2. PGS.TS. Hồ Cẩm Hà HÀ NỘI - 2013 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ả Vũ Đức Quảng LỜI CÁM ƠN Luận án được hoàn thành tại Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam dưới sự hướng dẫn tận tình và nghiêm khắc của PGS.TS. Đoàn Văn Ban và PGS.TS. Hồ Cẩm Hà trong suốt thời gian tác giả theo học nghiên cứu sinh. Nhân dịp này, tác giả xin được bày tỏ lòng biết ơn chân thành và kính trọng sâu sắc đến quí Thầy, Cô. Tác giả xin chân thành cảm ơn Ban Lãnh đạo Viện Công nghệ Thông tin, Bộ phận quản lý Nghiên cứu sinh và các Phòng chức năng của Viện Công nghệ Thông tin đã 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, Ban chủ nhiệm khoa Toán – Tin và các đồng nghiệp ở trường Đại học Quảng Nam đã quan tâm, giúp đỡ mọi mặt để tác giả hoàn thành nhiệm vụ học tập. Sự quan tâm, động viên của mọi thành viên trong gia đình, đặc biệt sự chăm sóc, gánh vác phần lớn công việc gia đình của người Vợ là chỗ dựa tinh thần để tác giả tập trung vào học tập, nghiên cứu. Luận án này, là một món quà xin dâng tặng Bố, Mẹ, các anh chị em và cậu con trai yêu quí. Cuối cùng, tác giả xin bày tỏ lòng biết ơn tới những người thân, bạn bè đã động viên, giúp đỡ để 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 các ký hiệu, từ viết tắt............................................................................................ v Danh sách bảng .............................................................................................................. vi Danh sách hình vẽ ......................................................................................................... vii Mở đầu ....................................................................................................................... - 1 Chương 1: Cơ sở dữ liệu hướng đối tượng mờ ..................................................... - 6 1.1. Giới thiệu .............................................................................................................- 6 1.2. Thông tin không hoàn hảo trong mô hình hóa CSDL..........................................- 7 1.2.1. Thông tin sai lệch ............................................................................................... - 8 1.2.2. Thông tin không chính xác .................................................................................. - 8 1.2.3. Thông tin không chắc chắn.................................................................................. - 8 - 1.3. Tập mờ và phân bố khả năng ...............................................................................- 9 1.3.1. Các đặc trưng của tập mờ ...................................................................................... - 10 1.3.2. Các phép toán trên tập mờ ..................................................................................... - 11 1.3.2.1. Các phép toán tập hợp .................................................................................... - 11 1.3.2.2. Các phép toán quan hệ .................................................................................... - 11 1.3.2.3. Các phép toán logic ........................................................................................ - 16 - 1.4. Mô hình cơ sở dữ liệu hướng đối tượng mờ ..................................................... - 16 1.4.1. Đối tượng mờ ........................................................................................................ - 16 1.4.2. Lớp mờ .................................................................................................................. - 18 1.4.3. Mối quan hệ đối tượng/lớp mờ .............................................................................. - 19 1.4.4. Các phân cấp thừa kế mờ ...................................................................................... - 23 1.4.4.1. Phân cấp thừa kế trong các lớp ngoại diên ..................................................... - 24 1.4.4.2. Phân cấp thừa kế trong các lớp nội hàm ......................................................... - 24 1.4.4.3. Đa thừa kế mờ ................................................................................................ - 26 1.4.5. Mô hình lớp đối tượng mờ .................................................................................... - 26 1.4.6. Biểu diễn cơ sở dữ liệu hướng đối tượng mờ ........................................................ - 27 - 1.5. Kết luận chương 1 ............................................................................................. - 30 i Chương 2: Phụ thuộc dữ liệu trong lớp đối tượng và các dạng chuẩn của lược đồ cơ sở dữ liệu hướng đối tượng mờ ........................................................................ - 31 2.1. Phụ thuộc hàm mờ và các luật suy dẫn ............................................................. - 31 2.1.1. Sự tương tự của hai giá trị thuộc tính .................................................................... - 31 2.1.2. Phụ thuộc hàm mờ trong lớp đối tượng ................................................................. - 33 2.1.3. Tách các thuộc tính kiểu bộ theo phụ thuộc hàm mờ ............................................ - 34 2.1.4. Các luật suy dẫn trên các phụ thuộc hàm mờ ........................................................ - 35 2.1.5. Khóa của lớp đối tượng mờ ................................................................................... - 36 - 2.2. Phụ thuộc phương thức ..................................................................................... - 37 2.3. Phép tách lớp đối tượng mờ không mất thông tin ............................................ - 38 2.4. Chuẩn hóa lớp đối tượng mờ ............................................................................ - 39 2.4.1. Các dạng chuẩn đối tượng mờ ............................................................................... - 39 2.4.1.1. Dạng chuẩn đối tượng mờ 1 (1FONF) ........................................................... - 40 2.4.1.2. Dạng chuẩn đối tượng mờ 2 (2FONF) ........................................................... - 41 2.4.1.3. Dạng chuẩn đối tượng mờ 3 (3FONF) ........................................................... - 42 2.4.2. Chuẩn hóa lớp đối tượng mờ ................................................................................. - 43 2.4.2.1. Thuật toán chuẩn hóa lớp về 1FONF ............................................................. - 43 2.4.2.2. Thuật toán chuẩn hóa lớp về 2FONF ............................................................. - 46 2.4.2.3. Thuật toán chuẩn hóa lớp về 3FONF ............................................................. - 48 - 2.5. Sự tương tự của hai đối tượng mờ .................................................................... - 50 2.5.1. Sự tương tự của hai đối tượng trong cùng một lớp mờ ....................................... - 50 2.5.2. Sự tương tự của hai đối tượng mờ thuộc hai lớp khác nhau ............................... - 51 - 2.6. Truy vấn CSDL hướng đối tượng mờ ............................................................... - 52 2.6.1. Đại số kết hợp mờ.................................................................................................. - 53 2.6.1.1. Các mẫu kết hợp mờ ....................................................................................... - 53 2.6.1.2. Các phép toán kết hợp mờ .............................................................................. - 55 2.6.2. Giá trị chân lý của các mẫu kết hợp mờ ................................................................ - 57 2.6.2.1. Mối quan hệ đối tượng/lớp ............................................................................. - 57 2.6.2.2. Mối quan hệ kết nhập mờ ............................................................................... - 58 2.6.2.3. Mối quan hệ tổng quát hóa mờ ....................................................................... - 59 2.6.2.4. Mối quan hệ kết hợp mờ................................................................................. - 59 - ii 2.6.3. Ví dụ về truy vấn dữ liệu hướng đối tượng mờ ..................................................... - 61 - 2.7. Kết luận chương 2 ............................................................................................. - 62 Chương 3: Phụ thuộc hàm đối tượng mờ trong cơ sở dữ liệu hướng đối tượng mờ .................................................................................................................................. - 64 3.1. Giới thiệu .......................................................................................................... - 64 3.2. Một số khái niệm cơ bản ................................................................................... - 65 3.2.1. Các khái niệm về đồ thị ..................................................................................... - 65 3.2.2. Lược đồ cơ sở dữ liệu hướng đối tượng mờ ...................................................... - 66 3.2.3. Quan hệ mờ ....................................................................................................... - 67 3.2.4. Phép kết nối ngoài mờ đầy đủ ........................................................................... - 68 - 3.3. Phụ thuộc hàm đối tượng mờ ............................................................................ - 70 3.4. Quan hệ mờ biểu diễn một bộ phận của trạng thái s(S) .................................... - 73 3.5. Các dạng phụ thuộc hàm đối tượng mờ ............................................................ - 76 3.6. Các FOFD không chuẩn tắc và đồ thị lược đồ mờ phân nhánh ........................ - 81 3.7. Các luật suy dẫn cho các FOFD cục bộ ............................................................ - 83 3.8. Các luật suy dẫn cho các FOFD toàn cục ......................................................... - 84 3.8.1. Luật phản xạ ...................................................................................................... - 85 3.8.2. Luật tách ............................................................................................................ - 86 3.8.3. Luật tăng trưởng ................................................................................................ - 87 3.8.4. Luật hợp ............................................................................................................. - 90 3.8.5. Luật bắc cầu ....................................................................................................... - 91 3.8.6. Luật tựa bắc cầu................................................................................................. - 94 - 3.9. Kết luận chương 3 ............................................................................................. - 95 Kết luận .................................................................................................................... - 96 Danh mục các công trình của tác giả ....................................................................... - 97 Tài liệu tham khảo.................................................................................................... - 98 - iii Danh mục các thuật ngữ Chiều cao High Đại số kết hợp mờ Fuzzy association algebra Độ bao hàm ngữ nghĩa Semantic inclusion degree Đồ thị lược đối tượng mờ Fuzzy object schema Graph Đồ thị lược đồ mờ Fuzzy schema Graph Giá đỡ Support Giá trị chân lý Truth value Hạt nhân Kernel Kết hợp mờ Fuzzy association Không gian ngữ nghĩa Semantic space Lớp cha Superclass Lớp con Subclass Mẫu kết hợp mờ Fuzzy association pattern Mối quan hệ nhị nguyên Binary relationship Mối quan hệ thừa kế Inheritance relationship Mối quan hệ đối tượng/lớp Object/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 generalization relationship Phân cấp thừa kế mờ Fuzzy inheritance hierarchy Phụ thuộc hàm mờ Fuzzy functional dependency Quan hệ giống nhau Resemblance relation iv Bảng các ký hiệu, từ viết tắt CSDL (Database) Cơ sở dữ liệu 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 OODB (Object Oriented Database) Cơ sở dữ liệu hướng đối tượng FOODB (Fuzzy Object Oriented Database) Cơ sở dữ liệu hướng đối tượng mờ SQL (Structured Query Language) Ngôn ngữ truy vấn có cấu trúc NF2 (Non-First Normal Relational Database Mô hình dữ liệu quan hệ không ở Model ) 1NF FOFD (Fuzzy Object Functional Dependency) Phụ thuộc hàm đối tượng mờ UML (Unified Modeling Language) Ngôn ngữ mô hình hợp nhất FONF (Fuzzy Object Normal Form) Dạng chuẩn đối tượng mờ v Danh sách bảng Bảng 1.1. Một quan hệ giống nhau .............................................................................. 13 Bảng 3.1. Một quan hệ mờ biểu diễn các đối tượng .................................................... 68 Bảng 3.2. Các quan hệ giống nhau .............................................................................. 69 Bảng 3.3. Một quan hệ mờ được kết nối từ Rext(O3) và Rext(r2) ..................................... 71 Bảng 3.4: Một quan hệ mờ được tham chiếu bởi f ...................................................... 78 Bảng 3.5: Các quan hệ mờ được tham chiếu bởi FOFD không chuẩn tắc với đồ thị FOFD phân nhánh ........................................................................................................ 83 Bảng 3.6: Quan hệ mờ Rfo ........................................................................................... 87 Bảng 3.7: Một quan hệ mờ biểu diễn trạng thái lược đồ được tham chiếu bởi FOFD g1 ...... 90 Bảng 3.8: Một quan hệ mờ biểu diễn trạng thái lược đồ được tham chiếu bởi FOFD g2 ..... 90 vi Danh sách hình vẽ Hình 1.1. Hàm thuộc của số mờ “gần Y” .................................................................... 15 Hình 1.2. Hàm thuộc của số mờ “tối thiểu Y”. ............................................................ 16 Hình 1.3. Hàm thuộc của số mờ “tối đa Y” ................................................................. 16 Hình 1.4. Đồ thị lược đồ mờ của CSDL Nguồn nhân lực ........................................... 29 Hình 1.5. Đồ thị lược đồ đối tượng mờ của CSDL Nguồn nhân lực ........................... 30 Hình 2.1. Mối quan hệ kết hợp mờ ............................................................................. 61 Hình 3.1. Đồ thị lược đồ mờ của cơ sở dữ liệu hướng đối tượng mờ ......................... 66 Hình 3.2. Một đồ thị lược đồ mờ của CSDL hướng đối tượng mờ ............................. 70 Hình 3.3. Sự nhập nhằng của phụ thuộc hàm đối tượng mờ ...................................... 72 Hình 3.4. Một phụ thuộc hàm đối tượng mờ ............................................................... 73 Hình 3.5. Đồ thị lược đồ mờ của CSDL hướng đối tượng mờ và trạng thái lược đồ mờ phân nhánh .................................................................................................................. 83 Hình 3.6. Một đồ thị lược đồ mờ của CSDL hướng đối tượng mờ ............................. 86 Hình 3.7. Sự vi phạm tính chất toàn ánh của FOFD thu được bởi luật bắc cầu ......... 93 vii MỞ ĐẦU Các hệ thống và mô hình dữ liệu như quan hệ, mạng, phân cấp đã phát triển thành công nghệ cơ sở dữ liệu, đặc biệt là mô hình dữ liệu quan hệ do Codd E. F. đề xuất vào năm 1970. Những kết quả nghiên cứu đạt được trên mô hình này không những tạo nền tảng về lý thuyết CSDL, mà còn mang tính ứng dụng cao với hàng loạt hệ quản trị CSDL thương mại ra đời vào cuối thập niên 70 và đầu thập niên 80 như Oracle, SQL, DB2, … Tuy nhiên, chúng vẫn tồn tại một số hạn chế khi các ứng dụng đòi hỏi CSDL được thiết kế và cài đặt ở mức phức tạp hơn. Ví dụ, các CSDL thiết kế cho hệ thống để giải quyết những bài toán trong công nghiệp, các thực nhiệm khoa học, truyền thông, các hệ thống thông tin địa lý và hệ thống đa phương tiện với sự tích hợp âm thanh, hình ảnh, ... Những chương trình ứng dụng phức tạp thường có các yêu cầu và các đặc trưng khác so với các ứng dụng thương mại truyền thống như cấu trúc của các đối tượng phức tạp hơn, các giao tác có khoảng thời gian tồn tại dài hơn, các kiểu dữ liệu mới để lưu trữ các đối tượng phức tạp của thế giới thực, nhất là cần định nghĩa được các tác vụ phù hợp cho những ứng dụng xác định. Các mô hình CSDL hướng đối tượng được đề xuất để giải quyết các vấn đề phức tạp của những hệ thống ứng dụng đó. Tiếp cận hướng đối tượng tạo ra tính mềm dẻo để xử lý các yêu cầu mà không bị hạn chế bởi các kiểu dữ liệu và tậng dụng các ngôn ngữ truy vấn sẵn có trong các hệ thống CSDL truyền thống. Tuy nhiên, trong thực tế, dữ liệu của đối tượng không phải lúc nào cũng bao gồm những thông tin đầy đủ và chính xác. Vì vậy, người ta mong muốn có những mô hình CSDL cho phép biểu diễn, thao tác trên những thông tin không chắc chắn, không chính xác nhằm thể hiện được thế giới thực một cách xác thực hơn. Mô hình cơ sở dữ liệu quan hệ truyền thống và các mở rộng liên quan đến việc xử lý, biểu diễn dữ liệu không chắc chắn, không chính xác của nó vẫn không đáp ứng yêu cầu trong việc đặc tả các đối tượng phức hợp với thông tin không chắc chắn, không chính xác. Chẳng hạn, mở rộng mô hình CSDL quan hệ không ở dạng chuẩn 1 (còn gọi là mô hình dữ liệu quan hệ NF2) bởi Yazici và các cộng sự [43] cho phép biểu diễn và thao tác trên dữ liệu không chắc chắn, phức tạp trong các cơ sở dữ liệu. Các phép toán đại số quan hệ, ngôn ngữ truy vấn dữ liệu có cấu trúc tựa SQL cũng được đưa ra trong mô hình này. Mô hình dữ liệu quan hệ NF2 mở rộng có khả năng đáp ứng -1- một số yêu cầu ứng dụng phức tạp, chẳng hạn các hệ thống tự động văn phòng, các hệ thống phục hồi thông tin và các hệ thống CSDL chuyên gia. Hạn chế của mô hình dữ liệu quan hệ NF2 mở rộng liên quan đến việc biểu diễn các mối quan hệ phức hợp giữa các đối tượng và các thuộc tính, không hỗ trợ các khái niệm cơ bản của phương pháp hướng đối tượng như phân cấp lớp, thừa kế, lớp cha/lớp con. Vì vậy, để đặc tả dữ liệu không chắc chắn và các thuộc tính có giá trị phức hợp cũng như các mối quan hệ phức tạp giữa các đối tượng, các nghiên cứu gần đây đã tập trung vào việc xây dựng các mô hình cơ sở dữ liệu hướng đối tượng với thông tin không chắc chắn, không chính xác gọi chung là mô hình CSDL hướng đối tượng mờ. Hiện này, trên thế giới đã có nhiều cách tiếp cận khác nhau để giải quyết vấn đề nêu trên. Zacari và Milano (1990) [47] lần đầu tiên giới thiệu về thông tin không đầy đủ (chẳng hạn như các giá trị null) trong các CSDL hướng đối tượng, trong đó phân biệt lược đồ không đầy đủ và các đối tượng với thông tin không đầy đủ. Từ đó, việc hợp nhất thông tin không đầy đủ và không chắc chắn trong các cơ sở dữ liệu hướng đối tượng đã nhận được sự quan tâm ngày càng nhiều, trong đó tính mờ được xem xét ở cả mức thể hiện đối tượng và mức phân cấp lớp. Dựa trên quan hệ tương tự, George và các đồng nghiệp (1996) [21] sử dụng khái niệm phạm vi giá trị của thuộc tính để biểu diễn tập các giá trị cho phép của thuộc tính của lớp. Độ thuộc thành viên của đối tượng thuộc vào lớp phụ thuộc vào mức độ bao hàm của các giá trị thuộc tính của đối tượng trong phạm vi giá trị của thuộc tính trong lớp. Các phân cấp lớp mạnh hay yếu được xác định dựa trên sự tăng hay giảm đều theo độ thuộc thành viên của một lớp con vào trong các lớp cha của nó. Mô hình CSDL hướng đối tượng mờ được G. Bordogna và các cộng sự (1999) [20] đề xuất 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ư {rất thấp, thấp, trung bình, cao, rất cao}, nó có thể được kết hợp với thể hiện mối quan hệ cũng như mối quan hệ giữa một đối tượng với một lớp. Các lớp mờ và các phân cấp lớp mờ cũng được mô tả trong CSDL. Một mô hình cơ sở dữ liệu UFO (Uncertainly and Fuzziness in an Object-Oriented) được đề xuất bởi Gyseghem và de Caluwe (1998) [23] để biểu diễn thông tin không chắc chắn và mờ lần lượt theo lý thuyết tập mờ và tập mờ tổng quát. Hành vi và cấu trúc của đối tượng có thể được xác định không đầy đủ 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. Các dạng thừa kế như thừa kế bộ phận, thừa kế theo điều kiện và đa thừa -2- kế cũng được hỗ trợ trong các phân cấp mờ. Dựa trên lý thuyết khả năng, tính không rõ ràng và không chắc chắn được biểu diễn trong các phân cấp lớp bởi Dubois, Prade và Rossazza (1991) [16], trong đó, phạm vi giá trị của thuộc tính lớp con được xác định bằng cách giới hạn phạm vi giá trị của thuộc tính lớp cha, mức độ bao hàm của một lớp con vào trong một lớp cha phụ thuộc vào mức độ bao hàm giữa các phạm vi giá trị của các thuộc tính. Ở trong nước, Cao Hoàng Trụ (2001) [48] giới thiệu một mô hình hướng đối tượng mờ và không chắc chắn, trong đó mỗi tính chất lớp (một thuộc tính hoặc một phương thức) có thể chứa các tập mờ như một họ các phân bố xác suất, độ thuộc thành viên của lớp và khả năng sử dụng các tính chất lớp được xác định bởi cận trên và cận dưới của xác suất. Trên cơ sở mô hình CSDL được đề xuất, tác giả đã sử dụng ngôn ngữ lập trình logic hướng đối tượng mờ FRIL++ để xây dựng một lược đồ CSDL mờ ứng dụng. Trở ngại lớn nhất trong việc phát triển các hệ thống CSDL hướng đối tượng mờ đó là chưa có một mô hình dữ liệu chuẩn đầy đủ hay cơ sở toán học thống nhất cho việc biểu diễn và xử lý dữ liệu đối tượng mờ. Như đã đề cập ở trên, các nghiên cứu về mô hình CSDL hướng đối tượng mờ chủ yếu tập trung vào việc mở rộng mô hình dữ liệu rõ đã có theo các cách tiếp cận khác nhau và cho phép biểu diễn, thao tác trên dữ liệu mờ. Do đó, các mô hình CSDL mờ này cũng chỉ thống nhất trên một tập các khái niệm chung nhất (tập lõi) trong mô hình hạt nhân của ODMG [11, 12]. Có thể thấy rằng, các kết quả nghiên cứu trên CSDL hướng đối tượng mờ luôn được xem xét với một mô hình cụ thể, các kết quả này sẽ giải quyết cho một lớp các bài toán với một tập con các khái niệm, tính chất đặc trưng hướng đối tượng đã được cài đặt trên mô hình. Như vậy, việc chọn lựa một mô hình dữ liệu để nghiên cứu các vấn đề trong CSDL hướng đối tượng mờ là rất quan trọng. Mô hình CSDL hướng đối tượng mờ với dữ liệu được biểu diễn bởi phân bố khả năng được đề xuất bởi ZongMin Ma [51], ngoài việc đảm bảo các khái niệm, tính chất cốt lõi của mô hình CSDL hướng đối tượng rõ, nó còn giải quyết được tương đối đầy đủ tính mờ của đối tượng, lớp, tính mờ trong mối quan hệ giữa đối tượng và lớp, giữa lớp cha và lớp con. Vì vậy, chúng tôi sử dụng mô hình này để thực hiện các nghiên cứu về các phụ thuộc dữ liệu của các đối tượng mờ. Trong cơ sở dữ liệu quan hệ mờ, các công trình nghiên cứu về các phụ thuộc dữ liệu tương đối đầy đủ, có thể kể đến các kết quả của Raij K. V. S. N và Mazumdar [34], của Bhattachajee T. K và Mazumdar [9]. Dựa trên khái niệm phụ thuộc hàm mờ, -3- các nghiên cứu của nhóm tác giả Chen G. Q, Kerre E. E, và Vandenbulcke J. liên quan đến các dạng chuẩn lược đồ quan hệ mờ, thuật toán tách lược đồ quan hệ về các dạng chuẩn mờ, thuật toán tìm bao đóng, … được triển khai một cách cụ thể và khá sâu sắc [13, 14]. Tương tự như trong CSDL quan hệ, các nhà thiết kế CSDL hướng đối tượng cũng cần có kỹ thuật thiết kế dạng chuẩn để giải quyết các vấn đề tiềm ẩn liên quan đến sự dư thừa dữ liệu cũng như đảm báo tính nhất quán trong hệ thống CSDL. Từ những năm 1980 đến nay đã có nhiều tiếp cận khác nhau trong việc chuẩn hóa các lớp đối tượng trong các lược đồ CSDL hướng đối tượng rõ, các dạng chuẩn đối tượng được đề xuất dựa trên phụ thuộc hàm giữa các thuộc tính trong lớp với các dạng chuẩn tương tự như các dạng chuẩn trong CSDL quan hệ [7, 8, 24, 42] hoặc được chuẩn hóa dựa trên các ràng buộc trong lược đồ CSDL như ràng buộc phụ thuộc đường dẫn, phụ thuộc cục bộ, phụ thuộc toàn cục [41]. Có thể thấy, phụ thuộc dữ liệu là nền tảng lý thuyết để xác định các dạng chuẩn của lược đồ CSDL nhằm hạn chế đến mức thấp nhất sự dư thừa dữ liệu, nguyên nhân chính phá vỡ tính toàn vẹn dữ liệu trong các hệ thống CSDL. Một cách tự nhiên, chúng ta cũng cần có những nghiên cứu sâu sắc về phụ thuộc dữ liệu trong CSDL hướng đối tượng mờ nhằm hỗ trợ cho việc thiết kế các CSDL ứng dụng cũng như đảm bảo tính toàn vẹn dữ liệu trong việc cập nhật dữ liệu. Mục tiêu của luận án là nghiên cứu các phụ thuộc dữ liệu trong CSDL hướng đối tượng mờ. Các vấn đề liên quan đến mục tiêu nghiên cứu được chúng tôi trình bày trong luận án bao gồm: 1. Nghiên cứu sự tương tự ngữ nghĩa (thông tin) giữa hai dữ liệu mờ với nhiều kiểu dữ liệu khác nhau được cung cấp bởi mô hình CSDL hướng đối tượng. Tiếp theo, nghiên cứu các dạng phụ thuộc dữ liệu trong CSDL hướng đối tượng với dữ liệu mờ được biểu diễn theo phân bố khả năng, cụ thể đó là các phụ thuộc dữ liệu giữa các thuộc tính trong một lớp đối tượng và các phụ thuộc dữ liệu giữa các đối tượng trong lược đồ cơ sở dữ liệu hướng đối tượng mờ. 2. Nghiên cứu, đề xuất các dạng chuẩn đối tượng mờ và các giải thuật chuẩn hóa lớp đối tượng về các dạng chuẩn để giải quyết các dị thường dữ liệu khi cập nhập dữ liệu, nhằm đảm bảo tính toàn vẹn dữ liệu trong CSDL hướng đối tượng mờ. -4- 3. Nghiên cứu đề xuất phương thức tính giá trị chân lý của các mẫu kết hợp mờ trong đại số kết hợp mờ. Từ đó, đánh giá độ tin cậy của kết quả truy vấn trên CSDL hướng đối tượng mờ theo đại số kết hợp mờ. Để thực hiện được các mục tiêu trên, luận án được tổ chức như sau: Phần mở đầu, ba chương và phần kết luận. Chương 1 trình bày khái quát về cơ sở dữ liệu hướng đối tượng mờ. Nội dung cụ thể của chương này gồm: các khái niệm, các phép toán cơ bản của tập mờ, phân bố khả năng và phương thức tính độ tương tự ngữ nghĩa của hai giá trị mờ. Quan trọng hơn, 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 dữ liệu mờ được biểu diễn bởi phân bố khả năng, trong đó đề cập đến 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ờ. Phần cuối của chương giới thiệu hai cách biểu diễn lược đồ cơ sở dữ liệu hướng đối tượng mờ theo đồ thị lược đồ mờ và đồ thị lược đồ đối tượng mờ. Chương 2 giới thiệu các nghiên cứu về phụ thuộc dữ liệu trong lớp đối tượng mờ. Dựa vào độ đo độ tương tự ngữ nghĩa giữa hai giá trị mờ mở rộng trên quan hệ giống nhau để xác định mức độ tương tự ngữ nghĩa giữa hai giá trị thuộc tính của hai đối tượng với các kiểu dữ liệu khác nhau và định nghĩa khái niệm phụ thuộc hàm cho các thuộc tính của lớp, các dạng chuẩn đối tượng mờ, xây dựng thuật toán chuẩn hóa lớp đối tượng để đưa về các dạng chuẩn lớp đối tượng. Phụ thuộc dữ liệu trong CSDL hướng đối tượng mờ còn được thể hiện qua mức độ kết hợp giữa các đối tượng trong cơ sở dữ liệu. Trong chương này, chúng tôi trình bày một phương pháp xác định giá trị chân lý của các kết hợp giữa các đối tượng trong cơ sở dữ liệu. Chương 3 nghiên cứu về phụ thuộc hàm đối tượng xác định các ràng buộc giữa các thuộc tính và các kiểu đối tượng trong một cơ sở dữ liệu hướng đối tượng mờ. Chúng được xem như một trong các công cụ để nhận biết đối tượng trong cơ sở dữ liệu hướng đối tượng mờ, hỗ trợ cho việc truy vấn dữ liệu và kiểm tra tính toàn vẹn dữ liệu trong các CSDL ứng dụng. Nội dung cụ thể bao gồm: khái niệm phụ thuộc hàm đối tượng mờ, các dạng phụ thuộc hàm đối tượng khác nhau trong một trạng thái lược đồ cơ sở dữ liệu và các luật suy dẫn cho phụ thuộc hàm đối tượng mờ. -5- Chương 1 CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG MỜ 1.1. Giới thiệu Trong những năm gần đây, việc nghiên cứu, ứng dụng cơ sở dữ liệu hướng đối tượng mờ để đặc tả các thực thể phức tạp trong thế giới thực cũng như 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 mô tả và xử lý 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 trong một số lĩnh vực của khoa học máy tính [20]. Tiếp cận hướng đối tượng mờ trong thiết kế các hệ thống phần mềm đã nhận được một sự chú ý đáng kể, đặc biệt là trong lĩnh vực cơ sở dữ liệu. Một số 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 đã được đề xuất: - Mô hình CSDL hướng đối tượng mờ được đề xuất bởi M. Umano và các cộng sự [32], trong đó giá trị của các 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. - 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ừ đó định nghĩa được một thể hiện tự nhiên của đối tượng. 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. - Mô hình CSDL hướng đối tượng mờ được đưa ra bởi G. Bordogna và các cộng sự [19] 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, rất thấp, thấp, 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ờ. - 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 [21]. Độ thuộc thành viên của đối tượng thuộc vào một lớp được tính -6- dựa trên mức độ bao hàm các giá trị thuộc tính của đối tượng vào 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ó. - 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 [16]. Cũng dựa trên phân bố khả năng, trong [51] 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ột mô hình dữ liệu tổng quát và các phép toán cho CSDL hướng đối tượng mờ đã được phát triển. Việc lựa chọn một mô hình CSDL hướng đối tượng mờ mà có khả năng đặt tả được các đối tượng chứa nhiều loại thông tin mờ khác nhau cũng như các mối quan hệ (mờ hay rõ) giữa chúng là công việc cần thiết để thực hiện các nghiên cứu liên quan đến các phụ thuộc dữ liệu và mở rộng các kết quả trên CSDL hướng đối tượng mờ. Trong phần sau, chúng tôi giới thiệu một mô hình CSDL hướng đối tượng mờ với dữ liệu được biểu diện bởi phân bố khả năng được đề xuất bởi ZongMin Ma [51], mô hình này cho phép ta thiết kế được một lược đồ CSDL biểu diễn được một cách đầy đủ các thể hiện mờ của các đối tượng và các mối quan hệ mờ trong thế giới thực. Vì vậy, nó được chọn làm mô hình cơ sở để tiến hành các nghiên cứu được đặt ra. Ngoài ra, việc sử dụng phân bố khả năng cho phép ta biểu diễn một cách linh hoạt nhiều loại dữ liệu như: dữ liệu rõ, dữ liệu chưa biết, dữ liệu không có thông tin, dữ liệu không chắc chắn. 1.2. Thông tin không hoàn hảo trong mô hình hóa CSDL Một trong những lĩnh vực nghiên cứu chủ yếu trong cơ sở dữ liệu là tiếp tục phát triển các kết quả đã đạt được trong các mô hình CSDL truyền thống với một tập các khái niệm có ngữ nghĩa mở rộng. Một trong các yêu cầu không được giải quyết đầy đủ bởi các mô hình truyền thống, đó là việc biểu diễn và xử lý thông tin không chính xác và không chắc chắn. Các mô hình truyền thống giả định rằng mô hình cơ sở dữ liệu phản ánh một cách chính xác thế giới thực, dữ liệu được lưu trữ là được xác định, chính xác và đầy đủ. Tuy nhiên, trong thực tế cuộc sống, nhiều khi các giả định này -7- không được thỏa đáng. Vì vậy, trong những năm gần đây, các mô hình dữ liệu khác nhau được đề xuất để giải quyết các loại đặc trưng của dữ liệu bởi lý thuyết tập mờ. Trong các hệ thống CSDL, ta quan tâm tới ba loại thông tin không hoàn hảo sau: thông tin sai lệch, thông tin không chính xác, thông tin không chắc chắn. 1.2.1. Thông tin sai lệch Thông tin sai lệch là loại thông tin không hoàn hảo đơn giản nhất. Thông tin của cơ sở dữ liệu là sai lệch khi nó khác với “thông tin thực” (true information). Mọi sai số lớn hay nhỏ của thông tin đều làm tổn hại đến tính toàn vẹn của CSDL và không dung thứ được. Một loại thông tin sai lệch quan trọng là sự không nhất quán. Đôi khi cùng một khía cạnh của thế giới thực được biểu diễn nhiều lần trong cùng một CSDL hay trong nhiều CSDL khác nhau. Khi các biểu diễn thông tin xung đột nhau, không thể hòa hợp được thì thông tin đó là không nhất quán. Trong việc tích hợp thông tin từ nhiều CSDL khác nhau, các vấn đề về sự không nhất quán của thông tin phải được quan tâm một cách đầy đủ. 1.2.2. Thông tin không chính xác Thông tin trong CSDL là không chính xác khi nó biểu diễn một tập các giá trị có thể, và giá trị thực là một phần tử của tập đó. Như vậy, thông tin không chính xác không phải là thông tin sai lệch và không làm phương hại tới tính toàn vẹn của CSDL. Sau đây là một số thông tin không chính xác đặc trưng: - Thông tin dạng tuyển, chẳng hạn tuổi của Nam hoặc là 35 hoặc là 36. - Thông tin âm, chẳng hạn tuổi của Nam không phải là 30. - Thông tin khoảng/miền, chẳng hạn tuổi của Nam nằm trong khoảng từ 35 đến 40 hoặc tuổi của Nam lớn hơn 35. - Thông tin với các cận, sai số, chẳng hạn tuổi của Nam là 30 ± 1. 1.2.3. Thông tin không chắc chắn Tri thức của chúng ta về thế giới thực (chính xác hoặc không chính xác), đôi khi không thể được phát biểu với một mức độ chân lý tuyệt đối, và đòi hỏi ta phải xác định giá trị chân lý về thông tin được phát biểu. Thông tin với độ chắc chắn nhất định không phải là thông tin sai lệch và không làm phương hại tới tính nhất quán của cơ sở dữ liệu. Trong phát biểu “tuổi của Nam hoặc là 35 hoặc là 36” thể hiện tính không chính xác trong khi phát biểu “tuổi của Nam có khả năng là 35” lại thể hiện tính không chắc chắn. -8- Đôi khi, một giá trị chính xác có thể kéo theo sự kém chắc chắn, nhưng chừng nào giá trị đó được thay thế bằng các giá trị càng dần kém chính xác thì độ chắc chắn sẽ tăng dần và cuối cùng đạt cực đại với một giá trị có độ “chính xác cực tiểu” (một giá trị null chẳng hạn). 1.3. Tập mờ và phân bố khả năng Cho U là một tập hợp và F là một tập con của U. Một phần từ x của U có thuộc F hay không, có thể mô tả bởi một hàm thuộc m F : ì1 Nếu x Î F m F (x ) = í î0 Nếu x Ï F Trong tập con mờ, hàm thuộc của một phần tử nào đó của F không chỉ nhận giá trị trong {0, 1} mà có thể nhận giá trị trong khoảng [0, 1]. Định nghĩa 1.1 [45]: Cho U là một vũ trụ các đối tượng (sau đây gọi tắt là vũ trụ), một tập mờ F trên U xác định bởi hàm thuộc m F : U ® [0, 1] , gán cho mỗi phần tử x của U một độ thuộc m F (x) để chỉ độ thuộc của x vào tập mờ F. Tập mờ F được biểu diễn dưới dạng: F = {m F ( x1 ) / x1 , m F ( x 2 ) / x 2 ,..., m F ( x n ) / x n } Định nghĩa 1.2 [45]: Tập mờ F được gọi là chuẩn nếu tồn tại ít nhất một phần tử x ÎU sao cho m F ( x) = 1. Định nghĩa 1.3 [45]: Tập mờ F của vũ trụ U là lồi nếu và chỉ nếu " x1, x2 Î U và l Î[0, 1] sao cho mF(lx1 + (1 - l)x2) ³ min(mF(x1), mF(x2)). Định nghĩa 1.4 [49]: Một tập mờ F lồi và chuẩn của vũ trụ U được gọi là một số mờ. Một giá trị mờ xác định trên U có thể được đặc tả bởi một tập mờ F trong U với một hàm thuộc m F : U ® [0, 1] . Ví dụ 1.1: Cho U là tập các tiền lương 2.0 triệu đồng, 2.5 triệu đồng, 4.0 triệu đồng, 3.5 triệu đồng và 5.0 triệu đồng. Một giá trị mờ tiền lương “cao” có thể được mô tả bởi tập mờ F là tập hợp các tiền lương “cao” như sau: F = {0.5/2.0 triệu đồng, 0.6/ 2.5 triệu đồng, 0.8/4.0 triệu đồng, 0.7/3.5 triệu đồng, 1.0/5.0 triệu đồng} Trong đó, mF(2.0 triệu đồng) = 0.5, mF(2.5 triệu đồng) = 0.6, mF(3.5 triệu đồng) = 0.7, mF(4.0 triệu đồng) = 0.8, mF(5.0 triệu đồng) = 1. Khi mF(xi) được xem như là độ đo khả năng mà một biến X nhận giá trị xi, ở đây, -9-