Tài liệu Cơ sở dữ liệu mờ và ứng dụng

CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== MỤC LỤC LỜI CAM ĐOAN...........................................................................................1 LỜI CẢM ƠN.................................................................................................2 MỞ ĐẦU.........................................................................................................8 CHƢƠNG 1 TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU MỜ ................11 1.1 Các mô hình cơ sở dữ liệu mờ ........................................................... 11 1.1.1 Mô hình dựa trên lý thuyết tập mờ (mô hình tập con mờ) ..................... 11 1.1.2 Mô hình dựa trên quan hệ tƣơng tự ....................................................... 13 1.1.3 Mô hình dựa trên lý thuyết khả năng ..................................................... 15 1.2 Phụ thuộc dữ liệu trên cơ sở dữ liệu mờ ............................................ 17 1.2.1 Phụ thuộc hàm mờ ................................................................................ 17 1.2.2 Phụ thuộc đa trị mờ............................................................................... 21 1.3 Kết luận chƣơng một ......................................................................... 23 CHƢƠNG 2 CHUẨN HÓA VÀ TÁCH LƢỢC ĐỒ QUAN HỆ TRONG CƠ SỞ DỮ LIỆU MỜ .....................................................25 2.1 Phụ thuộc hàm mờ ............................................................................. 26 2.1.1 Độ phù hợp giữa các bộ ........................................................................ 27 2.1.2 Định nghĩa phụ thuộc hàm mờ .............................................................. 28 2.1.3 Các quy tắc suy diễn cho phụ thuộc hàm mờ ........................................ 31 2.2 Khóa mờ ............................................................................................ 32 2.2.1 Bao đóng bắc cầu của các phụ thuộc hàm mờ (bao đóng của tập thuộc tính đối với tập phụ thuộc hàm). .................................................................... 33 2.2.2 Tìm khóa mờ của một quan hệ .............................................................. 35 2.2.3 Thuộc tính khóa và thuộc tính không khóa............................................ 37 2.3 Các dạng chuẩn mờ ........................................................................... 37 2.3.1 Dạng chuẩn mờ một (f-1NF) ................................................................. 37 2.3.2 Dạng chuẩn mờ hai (f-2NF) .................................................................. 38 2.3.3 Dạng chuẩn mờ ba (f-3NF) ................................................................... 40 2.4 Tách lƣợc đồ quan hệ mờ .................................................................. 42 2.4.1 Phân tách thành dạng chuẩn mờ hai ...................................................... 42 Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 3 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== 2.4.2 Phân tách thành dạng chuẩn mờ ba ....................................................... 42 2.5 Dạng chuẩn mờ Boyce Codd ............................................................. 53 2.6 Kết luận chƣơng hai .......................................................................... 54 CHƢƠNG 3 MỞ RỘNG CƠ SỞ DỮ LIỆU QUAN HỆ THÀNH CƠ SỞ DỮ LIỆU MỜ DỰA TRÊN LÝ THUYẾT KHẢ NĂNG ..56 3.1 Bộ có trọng số (Weighted tuples) trong quan hệ mờ .......................... 56 3.2 Biểu diễn dữ liệu mờ bằng phân bố khả năng .................................... 57 3.3 Một số mô hình cơ sở dữ liệu mờ dựa trên lý thuyết khả năng ........... 61 3.3.1 Mô hình Prade-Testemale ..................................................................... 61 3.3.2 Mô hình Umano-Fukami....................................................................... 62 3.3.3 Mô hình Zemankova-Kandel ................................................................ 63 3.4 Các phép toán đại số quan hệ mờ ...................................................... 64 3.4.1 Phép chọn mờ ....................................................................................... 64 3.4.2 Phép chiếu mờ ...................................................................................... 65 3.4.3 Phép kết nối mờ .................................................................................... 66 3.5 Kết luận chƣơng ba ........................................................................... 67 CHƢƠNG 4 FSQL VÀ MỘT VÍ DỤ MINH HỌA ........................68 4.1 Truy vấn dữ liệu ................................................................................ 68 4.1.1 Hỏi mềm dẻo ........................................................................................ 68 4.1.2 Truy vấn mờ trong cơ sở dữ liệu quan hệ .............................................. 72 4.1.3 Hỏi mềm dẻo trong cơ sở dữ liệu quan hệ kinh điển ............................. 73 4.2 Ngôn ngữ truy vấn mờ có cấu trúc (FSQL)........................................ 74 4.2.1 Nhãn ngữ nghĩa .................................................................................... 75 4.2.2 Các phép so sánh .................................................................................. 75 4.2.3 Các hằng số mờ .................................................................................... 76 4.2.4 Các thuộc tính mờ và biểu diễn giá trị mờ ............................................. 76 4.3 Mô hình cơ sở dữ liệu quan hệ mờ cơ bản ......................................... 78 4.4 Ứng dụng FSQL trên một cơ sở dữ liệu rõ ......................................... 82 4.5 Kết luận chƣơng bốn ......................................................................... 88 KẾT LUẬN.....................................................................................89 Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 4 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== TÀI LIỆU THAM KHẢO.............................................................100 Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 5 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== DANH MỤC CÁC HÌNH VẼ VÀ BẢNG BIỂU Bảng 1-1:Quan hệ r trên lƣợc đồ EMPLOYEE ...................................................... 12 Bảng 1-2: Phép chiếu quan hệ r trên hai thuộc tính N và D .................................... 12 Hình 1-3: Bảng tổng kết các tiêu chuẩn cho các phụ thuộc hàm mờ ....................... 21 Bảng 2-1: Bảng quan hệ tƣơng tự cho thuộc tính NAME ....................................... 28 Bảng 2-2: Bảng quan hệ tƣơng tự cho thuộc tính PERFORMANCE...................... 29 Bảng 2-3: Bảng quan hệ tƣơng tự cho thuộc tính EARNING ................................. 29 Bảng 2-4: Bảng khởi tạo cho quan hệ R = (A,B,C,D,E,F) ...................................... 50 Bảng 2-5: Bảng sau khi áp dụng bƣớc ba của thuật toán 2.12 với R ...................... 51 Bảng 2-6: Bảng khởi tạo cho quan hệ R = (A,B,C,D,E,F,G) .................................. 51 Bảng 2-7: Bảng sau khi áp dụng bƣớc ba của thuật toán 2.12 vào R ..................... 52 Bảng 2-8: Bảng sau khi áp dụng bƣớc bốn của thuật toán vào R ............................ 52 Bảng 2-9: Bảng kết quả sau khi kết thúc thuật toán................................................ 53 Hình 3-1: Biểu diễn các tình huống bằng phân bố khả năng trong trƣờng hợp thông thƣờng ................................................................................................... 58 Hình 3-2: Biểu diễn các tình huống bằng phân bố khả năng trong trƣờng hợp xấu 59 Bảng 3-3: Biểu diễn thông tin trong hai mô hình Prade-Testemale và UmanoFukami .................................................................................................. 63 Bảng 3-4: Quan hệ mờ r ....................................................................................... 65 Bảng 3-5: Kết quả của phép chiếu mờ của r trên hai thuộc tính Mã phòng ban và Tuổi....................................................................................................... 66 Bảng 3-6: Quan hệ mờ r ....................................................................................... 67 Bảng 3-7: Quan hệ mờ s ....................................................................................... 67 Bảng 3-8: Kết quả phép kết nối tự nhiên giữa r và s .............................................. 67 Bảng 4-1: Mối quan hệ tuổi trung bình và lƣơng (tháng) ...................................... 71 Hình 4-2: Tuổi của John và căn cứ “Trung niên” .................................................. 72 Hình 4-3: Tuổi của John = “Trung niên”............................................................... 72 Bảng 4-4: Một số các đặc trƣng của khả năng và cấp độ cần thiết ......................... 73 Bảng 4-5: Một số phép so sánh mờ ....................................................................... 75 Bảng 4-6: Biểu diễn bên trong của thuộc tính mờ loại 2 (Cho mỗi thuộc tính mờ F) .............................................................................................................. 77 Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 6 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== Bảng 4-7: Biểu diễn bên trong của thuộc tính mờ loại 3 hoặc 4 (Cho mỗi thuộc tính mờ F) .................................................................................................... 78 Hình 4-8: Kiến trúc cơ bản của FRDB với FSQL Server ...................................... 79 Bảng 4-9: [10] Các bảng trong FMB (theo mô hình của Jose Galindo) ................. 80 Hình 4-10: [10] Các bảng trong FMB và mối quan hệ của chúng (theo mô hình của Jose Galindo)......................................................................................... 81 Hình 4-11: Định nghĩa các nhãn trên TUOI ........................................................... 83 Hình 4-12: Định nghĩa các nhãn trên LUONG ....................................................... 84 Bảng 4-13: Quan hệ tƣơng tự giữa các nhãn của thuộc tính NANGLUC ............... 84 Hình 4-14: Định nghĩa các nhãn trên MUAHANG ................................................ 85 Hình 4-15: Kết quả truy vấn mềm dẻo ................................................................... 87 Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 7 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== MỞ ĐẦU Mô hình cơ sở dữ liệu quan hệ do Codd E.F đề xuất năm 1970 đã đạt đƣợc những kết quả hoàn chỉnh về lý thuyết và ứng dụng. Tuy nhiên mô hình này hạn chế trong việc biểu diễn thông tin không đầy đủ, không chắc chắn (gọi chung là dữ liệu mờ), loại dữ liệu này đƣợc con ngƣời sử dụng thƣờng xuyên trong thực tế. Đã có nhiều cách tiếp cận và đề xuất mô hình cơ sở dữ liệu mờ, những kết quả lý thuyết đã đƣợc xây dựng trong mô hình quan hệ truyền thống cũng đƣợc kiểm chứng trên các mô hình mới với những mở rộng thích hợp. Do vậy việc tìm hiểu cơ sở dữ liệu mờ và ứng dụng vào giải quyết các bài toán thực tế là một nhu cầu cấp thiết trong thực tiễn. Một trong những cách xây dựng một cơ sở dữ liệu mờ là mở rộng cơ sở dữ liệu quan hệ kinh điển. Có thể mở rộng mô hình quan hệ để đáp ứng nhu cầu lƣu trữ và khai thác dữ liệu mờ theo hai hƣớng, đó là: mở rộng ngữ nghĩa của dữ liệu để khai thác dữ liệu rõ với yếu tố mờ và mở rộng miền trị thuộc tính để biểu diễn đƣợc dữ liệu mờ. Hƣớng mở rộng ngữ nghĩa, dữ liệu vẫn đƣợc lƣu trữ nhƣ mô hình quan hệ, dữ liệu tại các thuộc tính của các bộ vẫn là dữ liệu rõ nhƣng cho phép khai thác dữ liệu với ngữ nghĩa rộng hơn (có yếu tố mờ). Cách tiếp cận này sử dụng sử dụng lý thuyết tập mờ để mở rộng bằng cách thêm thuộc tính độ thuộc cho mỗi bộ trong quan hệ vào quan hệ. Ví dụ ta có thể truy xuất một cơ sở dữ liệu nguồn lực của một doanh nghiệp với một câu hỏi nhƣ sau: Liệt kê những ngƣời trẻ tuổi trong công ty. Thế nào là trẻ tuổi?, ta sẽ phải xây dựng cơ sở logic cho việc xử lý ngữ nghĩa mở rộng của dữ liệu nhƣ thế này và lý thuyết tập mờ và logic mờ là cơ sở để thực hiện. Hƣớng mở rộng ngữ nghĩa có thể vẫn sử dụng các hệ quản trị cơ sở dữ liệu quan hệ sẵn có trong việc lƣu trữ dữ liệu, còn những mở rộng cho việc xử lý dữ liệu đƣợc xây dựng thành các gói riêng, cài đặt thêm, nhúng vào hệ quản trị đó. Tuy nhiên cách mở rộng này chƣa cho phép lƣu trữ dữ liệu mờ nên hạn chế nhiều đến khả năng quản lý dữ liệu thực tế. Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 8 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== Hƣớng mở rộng miền trị thuộc tính là cách mở rộng tổng quát hơn, phản ánh đúng bản chất của vấn đề, nó cho phép bổ sung thêm các cú pháp trong biểu diễn dữ liệu nhằm biểu diễn đƣợc dữ liệu mờ. Với cách mở rộng này, ngoài việc đƣa vào hệ thống ký hiệu còn phải xây dựng đƣợc cơ sở logic cho việc lập luận trên các ký hiệu để xử lý, khai thác đƣợc dữ liệu. Theo hƣớng này, để mở rộng cơ sở dữ liệu kinh điển thành cơ sở dữ liệu mờ có hai cách tiếp cận tiêu biểu là mở rộng bằng cách sử dụng quan hệ tƣơng tự và mở rộng theo lý thuyết khả năng. Ở Việt Nam, việc nghiên cứu về cơ sở dữ liệu mờ lần đầu tiên đƣợc PGS.TS. Hồ Thuần và PGS.TS. Lê Tiến Vƣơng quan tâm nghiên cứu từ những năm 1985. Các tác giả đã đề xuất một cách mở rộng mô hình quan hệ bằng cách mở rộng miền trị thuộc tính, xem mỗi miền trị thuộc tính là một biến ngôn ngữ. Một số kết quả của mô hình quan hệ cũng đƣợc mở rộng trên mô hình này. Năm 1996, Trƣơng Đức Hùng tiếp tục phát triển mô hình này. Năm 2002, Hồ Cẩm Hà đã mở rộng mô hình cơ sở dữ liệu mờ bằng cách sử dụng quan hệ tƣơng tự và phát triển một số kết quả cho mô hình này. Năm 2005, Trần Thiên Thành đã mở rộng mô hình cơ sở dữ liệu mờ dựa trên lý thuyết khả năng, đƣa ra đƣợc khái niệm phụ thuộc hàm với lƣợng từ ngôn ngữ, xây dựng đƣợc công thức đánh giá độ tin cậy của các dạng luật tổng kết dữ liệu. Những nghiên cứu về cơ sở dữ liệu mờ đang tiếp tục và ngày càng phát triển mạnh mẽ trên thế giới cũng nhƣ ở trong nƣớc. Với mong muốn tìm hiểu về một hƣớng phát triển và ứng dụng nó vào thực tiễn, luận văn đề ra nhiệm vụ nhƣ sau: 1. Cách tiếp cận để mở rộng Cơ sở dữ liệu kinh điển thành cơ sở dữ liệu mờ đƣợc chọn để nghiên cứu và ứng dụng vào một bài toán cụ thể là cách tiếp cận dựa trên lý thuyết khả năng (Mô hình dựa trên lý thuyết khả năng). 2. Nghiên cứu xem trên mô hình này, cách thức xử lý thông tin không chắc chắn, mở rộng các phép toán, mở rộng ngôn ngữ truy vấn dữ liệu rõ (SQL) thành ngôn ngữ truy vấn dữ liệu mờ (FSQL). 3. Ứng dụng mô hình này vào một bài toán cụ thể. Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 9 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== Luận văn gồm phần mở đầu, 4 chƣơng, kết luận và tài liệu tham khảo. Chƣơng 1 trình bày các khái niệm cơ bản. Giới thiệu tổng quan về các mô hình cơ sở dữ liệu mờ. Chƣơng 2 trình bày cách giải quyết các vấn đề khi mở rộng cơ sở dữ liệu quan hệ thành cơ sở dữ liệu mờ: vấn đề phụ thuộc hàm mờ, khóa mờ, các dạng chuẩn mờ, tách lƣợng đồ quan hệ mờ và dạng chuẩn mờ Boyce Codd. Chƣơng 3 đi sâu về cách tiếp cận mở rộng cơ sở dữ liệu quan hệ thành cơ sở dữ liệu mờ theo lý thuyết khả năng. Các cách thức xử lý thông tin không chắc chắn, mở rộng các phép toán đại số quan hệ trên mô hình mới. Chƣơng 4 ứng dụng một hƣớng giải quyết mở rộng ngôn ngữ truy vấn dữ liệu truyền thống (SQL) thành ngôn ngữ truy vấn dữ liệu mờ (FSQL) và ứng dụng cách tiếp cận đã trình bày trong chƣơng 3 để giải quyết bài toán quản lý cửa hàng bán lẻ xăng dầu. Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 10 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== CHƢƠNG 1 TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU MỜ 1.1 Các mô hình cơ sở dữ liệu mờ Các mô hình cơ sở dữ liệu mờ cho đến hiện nay chủ yếu là các mô hình mở rộng từ mô hình cơ sở dữ liệu quan hệ kinh điển. Đã có nhiều mô hình cơ sở dữ liệu mờ đƣợc đề xuất và tựu trung lại có ba cách tiếp cận để mở rộng cơ sở dữ liệu quan hệ thành cơ sở dữ liệu mờ. 1.1.1 Mô hình dựa trên lý thuyết tập mờ (mô hình tập con mờ) Năm 1984, Mô hình này đƣợc Baldwin và Zhou đề xuất [6]. Cách tiếp cận này không mở rộng miền trị thuộc tính mà mở rộng về ngữ nghĩa của dữ liệu rõ bằng cách đƣa ra đánh giá độ thuộc   0,1 của mỗi bộ vào một quan hệ. Một cách hình thức, một quan hệ mờ trên lƣợc đồ R = {A1, A2, ..... An} các thuộc tính là một tập con mờ của tích Đề-Các: dom(A1) x dom(A2) x .....x dom(An) Về mặt biểu diễn, quan hệ mờ trong mô hình này giống nhƣ trong mô hình quan hệ nhƣng có thêm một cột µ để lƣu độ thuộc của mỗi bộ vào quan hệ. Ví dụ, xét lƣợc đồ EMPLOYEE(N,P,D,F), trong đó N (Name) là tên của nhân viên, P (Project) là tên dự án tham gia, D (Days) là số ngày tham gia, F (Fee) là số tiền thù lao đƣợc hƣởng. Miền trị của các thuộc tính D, F là các tập con mờ trên các không gian tƣơng ứng là U D = [25,60], U F= [1000,3500]. Các hàm thuộc  ND ,  PF, tƣơng ứng của các tập con mờ “số ngày ít”, “tiền thù lao cao”, đƣợc cho nhƣ sau: 1  1  d  30 / 5  , d  30  1, d  30   ND d    Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 11 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== 1  1  f  1500 / 50  , f  1500  HS  f     1, f  1500  Một quan hệ r trên lƣợc đồ EMPLOYEE thể hiện tiêu chuẩn “Tiền thù lao cao và số ngày làm việc ít” nhƣ Bảng 1.1: P(Dự án) N(Tên nhân D(Số ngày ) viên) F(Tiền thù µ lao) Smith A 25 1000 0.09 Smith B 60 3500 0.02 Smith C 45 2000 0.09 Anna A 30 1200 0.14 Anna B 50 3000 0.03 Bảng 1-1:Quan hệ r trên lược đồ EMPLOYEE Các phép tính toán quan hệ nhƣ: Phép chiếu, hợp, giao và tích Đề–Các đƣợc thực hiện nhƣ các phép toán tƣơng ứng trên các tập mờ [6]. Chẳng hạn nhƣ quan hệ r nhƣ trên khi chiếu lên tập thuộc tính N,D sẽ đƣợc quan hệ nhƣ Bảng 1.2 N(Tên nhân viên) D(Số ngày ) µ Smith 25 0.09 Smith 60 0.02 Smith 45 0.09 Anna 30 0.14 Anna 50 0.03 Bảng 1-2: Phép chiếu quan hệ r trên hai thuộc tính N và D Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 12 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== Phép so sánh giá trị trong miền trị đƣợc thực hiện qua quan hệ hai ngôi “giống nhau”(EQ) đƣợc xác định qua hàm thuộc  EQ có hai tính chất phản xạ và đối xứng. Trong lƣợc đồ quan hệ trên, các quan hệ giống nhau có thể định nghĩa trên từng miền trị nhƣ sau:  EQ (a,b) = 0, Với a  b, a,b  dom(N)  EQ (a,b) = 1/(1+  \a-b\), trong đó  = 1, Với a,b  dom(D),  = 1/10 Với a,b  dom(F) Đã có nhiều kết quả nghiên cứu về cơ sở dữ liệu mờ đã sử dụng mô hình này, nhƣ: những kết quả về phụ thuộc hàm mờ, kết nối không mất thông tin của Raju, phụ thuộc đa trị mờ của Jyothi, xây dựng ngôn ngữ hỏi mềm dẻo trên cơ sở dữ liệu mờ của Kacprzyk,.... Mô hình này tận dụng đƣợc khả năng lƣu trữ dữ liệu của các hệ quản trị cơ sở dữ liệu đã có, chỉ bổ sung những mở rộng tính toán cần thiết nên nó đƣợc ứng dụng nhiều để cài đặt cho cơ sở dữ liệu mờ trong những năm cuối của thập kỷ 80 trong thế kỷ trƣớc, tiêu biểu là các hệ OMRON, FQUERY [4]. 1.1.2 Mô hình dựa trên quan hệ tƣơng tự Vào cuối những năm 1970, Buckles và Petry bắt đầu nghiên cứu sử dụng quan hệ tƣơng tự trong mô hình quan hệ làm cơ sở cho việc xây dựng mô hình cơ sở dữ liệu mờ. Đến năm 1982, hai ông đã đề xuất mô hình cơ sở dữ liệu mờ dựa trên quan hệ tƣơng tự bằng cách mở rộng miền trị thuộc tính cho phép biểu diễn đƣợc những dữ liệu không chắc chắn [4]. Trong mô hình này, giá trị của mỗi bộ tại một thuộc tính có thể đa trị (một tập các giá trị có thể). Trên mỗi miền trị chứa dữ liệu mờ đƣợc bổ sung một quan hệ tƣơng tự để làm cơ sở đánh giá độ “gần nhau” giữa các giá trị. Quan hệ tương tự s (Similarity relationship) trên miền D là một ánh xạ từ D x D vào [0,1] thỏa mãn với mọi x, y, z  D , các luật [5]: 1. Phản xạ : sx, x   1 Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 13 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== 2.Đối xứng sx, y   s y, x  3. Max-min bắc cầu : sx, z   max yD min sx, y , s y, z  Cho x, y  D,   0,1 , ta nói x tƣơng đƣơng với y với ngƣỡng , ký hiệu x ~  y , nếu sx, y    . Quan hệ ~ là một quan hệ tƣơng đƣơng, nó chia miền D thành các lớp tƣơng đƣơng d 1, d 2 ,...d k. Một quan hệ mờ r trên các thuộc tính A1 ,A2 ,..., An là một tập con của tích Đề–Các : 2 D x 2 D ....x 2 D 1 2 n Trên mỗi miền trị D i xác định một quan hệ tƣơng tự s i , và có một ngƣỡng tƣơng tự  i  0,1, với i = 1,2,..., n Một bộ t của quan hệ mờ có dạng t = (d 1, d 2 ,...d n ), với d i ≠Ø, d i  D i , i = 1,2,..., n Về vấn đề dƣ thừa, giá trị tại mỗi thuộc tính của một bộ phận chỉ thuộc duy nhất một lớp tƣơng đƣơng với ngƣỡng cho trƣớc. Khái niệm  - dư thừa: hai bộ t = (d 1, d 2 ,...d n ) và t’ = (d’ 1, d’ 2 ,...d’ n ) đƣợc gọi là  - dư thừa, ký hiệu t  t’, nếu j = 1,2,...,n, x  d j, x’ d i’, sao cho x ~  x ' và ngƣợc lại. Trong một quan hệ có các dƣ thừa thì hợp các thành phần tƣơng ứng với nhau để tạo thành một bộ mới tƣơng đƣ ơng với hai bộ ban đầu. Hạn chế của mô hình này là sử dụng quan hệ tƣơng tự, đây là một dạng quan hệ có yêu cầu khá chặt do tính max-min bắc cầu làm hạn chế khả năng biểu diễn của những quan hệ trên thực tế. Đã có một số nghiên cứu thay quan hệ tƣơng tự bởi quan hệ gần nhau (proximity) không yêu cầu phải thỏa tính max-min bắc cầu, tiêu biểu là các nghiên cứu của Shenoi [8] mở rộng mô hình dựa trên quan hệ tƣơng tự bằng cách sử dụng quan hệ gần nhau. Tuy nhiên, để đảm bảo các kết quả trong mô hình quan hệ, các tác giả đƣa ra quan hệ tƣơng đƣơng  - gần nhau với mục đích phân hoạch miền trị mỗi Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 14 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== thuộc tính thành các lớp tƣơng đƣơng. Do các miền trị đƣợc phân hoạch thành các lớp tƣơng đƣơng theo quan hệ tƣơng đƣơng  - gần nhau và giá trị một bộ tại mỗi thuộc tính phải nằm trong một lớp tƣơng đƣơng nên các kết quả quan trọng của lý thuyết cơ sở dữ liệu quan hệ đƣợc mở rộng trên mô hình này đều đúng nhƣ: Phụ thuộc hàm mờ, các dạng chuẩn, phân tách không mất mát thông tin,... Một mở rộng khác với mục đích bỏ ràng buộc các giá trị trên mỗi thuộc tính của một bộ phải nằm trong một lớp tƣơng đƣơng đã đƣợc Hồ Cẩm Hà đề xuất nhằm mở rộng khả năng biểu diễn của mô hình này. Nhiều kết quả nghiên cứu chọn mô hình này làm cơ sở phát triển và đạt đƣợc kết quả quan trọng, tiêu biểu là những kết quả về phụ thuộc hàm mờ, phụ thuộc đa trị mờ của Sozat M.I và Yazici A. [9], đây là kết quả bƣớc đầu về nghiên cứu cấu trúc truy nhập cho mô hình của Yazici A. và Cibiceli D. 1.1.3 Mô hình dựa trên lý thuyết khả năng Mô hình này đƣợc đề xuất bởi Prade và Testemale vào năm 1983 [4], bằng cách mở rộng miền trị thuộc tính, sử dụng phân bố khả năng để biểu diễn các dữ liệu mờ. Giá trị của một n-bộ t tại thuộc tính A đƣợc biểu diễn bởi phân bố khả năng chuẩn A(t) trên miền trị mở rộng D  e. Trong đó e là phần tử bổ sung vào mỗi miền trị, đƣợc sử dụng trong trƣờng hợp thuộc tính A không áp dụng đƣợc cho bộ t. Một quan hệ mờ r trên tập thuộc tính A1 , A2 ,..., An là một tập con của tích Đề–Các: (D 1 ) x (D 2 ) x...x (D n ) với (D i ) là tập các phân bố khả năng chuẩn trên miền trị D i của thuộc tính A i , i = 1,2,...,n. Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 15 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== Sử dụng phân bố khả năng cho phép biểu diễn đƣợc nhiều loại dữ liệu: Dữ liệu rõ, dữ liệu chƣa biết, dữ liệu không có thông tin, dữ liệu với thông tin không chắc chắn: Biểu diễn dữ liệu trong các tình huống cổ điển:[Trần Thiên Thành (Luận án Tiến Sỹ)]  Biết chắc chắn lƣơng của T là 500 L(T) (e) = 0;L(T) (500) = 1; L(T) (d) = 0, d D - 500  T là một ngƣời không có lƣơng, hay thuộc tính lƣơng không áp dụng cho T: L(T) (e) =1; L(T) (d) = 0, d D  Biết chắc chắn rằng T có lƣơng nhƣng không biết là bao nhiêu (unknown). Khi đó tất cả các giá trị có khả năng bằng nhau và bằng 1 L(T) (e) =0; L(T) (d) = 1, d D Hoàn toàn không biết gì về thông tin lƣơng của T (null): L(T) (e) = 1; L(T) (d) =1, d D Biểu diễn dữ liệu không chính xác, không chắc chắn: Không biết chính xác lƣơng nhƣng chắc chắn trong khoảng từ 200 đến 300: L(T) (e) = 0; L(T) (d) = 1, nếu 200 d300; L(T) (d) = 0, nếu d < 200 hoặc d >300 Biết lƣơng của T là cao. Khi đó dùng tập mờ cao với hàm thuộc  cao để biểu diễn : L(T) (e) = 0; L(T) (d) =  cao (d), d D Ta biết những thông tin rời rạc về lƣơng của T: L(T) (e) = 0; L(T) (d i) = 1, i = 1,2,...,m: L(T) (d) = 0, d D Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 16 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== d D - (d 1, d 2 ,...d m ) 1.2 Phụ thuộc dữ liệu trên cơ sở dữ liệu mờ Trong mô hình quan hệ, phụ thuộc hàm và phụ thuộc đa trị là hai dạng phụ thuộc dữ liệu quan trọng giúp cho việc chuẩn hóa tốt các cơ sở dữ liệu. Đã có nhiều công trình tập trung nghiên cứu mở rộng hai dạng phụ thuộc này, các mở rộng chủ yếu dựa vào hai nguyên tắc chính : Mở rộng ký hiệu: nguyên tắc mở rộng này thay quan hệ bằng nhau trên dữ liệu rõ bởi quan hệ gần nhau hoặc quan hệ tƣơng tự trên dữ liệu mờ và đặt ngƣỡng để xác định độ gần nhau. Mở rộng ngữ nghĩa: nguyên tắc này dựa vào ý nghĩa của các phụ thuộc dữ liệu để xây dựng định nghĩa tƣơng ứng cho mô hình mới sao cho bảo toàn đƣợc một số kết quả quan trọng đã đƣợc xây dựng trong mô hình quan hệ . Một số quy ƣớc ký hiệu đƣợc sử dụng trong phần này   (t A, t’A) là một số thuộc 0,1 để chỉ độ gần nhau của giá trị hai bộ t và t’ tại thuộc tính A.   (tX, t’X) để chỉ độ gần nhau của giá trị hai bộ t và t’ trên tập thuộc tính X = A 1 A2 ...Ak  (t X,t’X) = (  (t A1 , t’A1 ),  (t A 2 , t’A2 ),...,  (t Ak , t’Ak )) để chỉ véc tơ độ gần nhau của giá trị hai bộ t và t’ trên tập thuộc tính X 1.2.1 Phụ thuộc hàm mờ Khái niệm phụ thuộc hàm mờ (fuzzy functional dependencies - ffd) [2] đƣợc nhiều nghiên cứu phát triển dựa trên ý nghĩa của khái niệm phụ thuộc hàm cổ điển với nhiều cách tiếp cận khác nhau. Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 17 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== Mở rộng ký hiệu: Một phụ thuộc hàm mờ X~>Y thỏa trên quan hệ r khi và chỉ khi với mọi cặp bộ t 1 , t 2  r, nếu t 1 X  t 2 X thì t 1 Y  t 2 Y. Trong đó quan hệ  dùng để chỉ sự gần nhau của hai giá trị mờ. Mở rộng ngữ nghĩa: Một cách khác, mở rộng khái niệm phụ thuộc hàm mờ trên mô hình cơ sở dữ liệu mờ là dựa vào ngữ nghĩa của phụ thuộc hàm. Với những tiếp cận theo cách này, một phụ thuộc hàm mờ X~>Y thỏa trên quan hệ r khi và chỉ khi độ gần nhau về giá trị dữ liệu của các bộ trên các tập thuộc tính X kéo theo độ gần nhau của các bộ trên tập thuộc tính Y . Phép kéo theo mờ đóng vai trò quan trọng trong cách tiếp cận này. Việc chọn toán tử kéo theo I phụ thuộc vào ngữ nghĩa của phụ thuộc hàm. Tuy nhiên, để bảo toàn một số tính chất quan trọng của phụ thuộc hàm cho các phụ thuộc hàm mờ, Chen đề xuất cách chọn toán tử kéo theo mờ I thỏa mãn các tính chất sau: a,b,c 0,1 C 1 : I(a,b) = 1 nếu a  b C 2 : I(a’,b’), với a’ = min(a,c), b’ = min(b,c) C 3 : I(a,c)  min(I(a,b),I(a,c)) Các phép toán kéo theo thƣờng đƣợc sử dụng là các phép kéo theo đƣợc đề xuất bởi: 1,  A   B 0,  A   B Rescher và Gaines:  A  B =  Godel: Dienes:  1,  A   B  B ,  A   B A  B =   A  B = max (1-  A,  B) Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 18 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== Một số khái niệm phụ thuộc hàm mờ tiêu biểu Khái niệm phụ thuộc hàm mờ của Raju [6] Đƣợc xây dựng trên mô hình tập con mờ, phụ thuộc hàm XY thỏa trên quan hệ r khi và chỉ khi với mọi t 1 ,t 2  r ta có (t 1 X, t 2 X)  (t 1 Y, t 2 Y) Đây đƣợc xem là một mở rộng tiêu biểu của khái niệm phụ thuộc hàm mờ. Khái niệm phụ thuộc hàm mờ của Chen [4] Phụ thuộc hàm mờ X   Y thỏa mãn quan hệ r khi và chỉ khi min I ( (tX , t ' X , (t Y , t ' Y ))   t ,t 'r Trong đó ngƣỡng   0,1, I là phép kéo theo của Godel. Dễ thấy khái niệm phụ thuộc hàm mờ này mở rộng hơn khái niệm của Raju. Điểm đặc biệt của khái niệm phụ thuộc hàm mờ của Chen là cho phép ngƣỡng của phụ thuộc hàm đƣợc thay đổi. Hệ tiên đề đƣợc mở rộng với tiên đề bao hàm ngƣỡng và đƣợc chứng minh là xác đáng và đầy đủ. Tuy nhiên hệ tiên đề này chỉ đúng trên mô hình dựa trên lý thuyết khả năng mà không thể mở rộng cho các mô hình khác vì khi đó tính đầy đủ của hệ t iên đề không còn đúng. Khái niệm phụ thuộc hàm mờ của Cuber [4] Xuất phát từ quan điểm xem mỗi thuộc tính, dữ liệu có độ mờ khác nhau nên đặt độ đo ngƣỡng gần nhau cho mỗi thuộc tính. Quan hệ r thỏa phụ thuộc hàm mờ X     ,       Y nếu và chỉ nếu với mọi t 1 , t 2  r, nếu  (t1 X , t 2 X    thì  (t 1  Y , t 2  Y )   Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 19 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== Trong đó ,  tƣơng ứng là véc tơ ngƣỡng của các tập thuộc tính X,Y. Có thể chứng minh đƣợc phụ thuộc hàm mờ của Cubero là mở rộng khái niệm phụ thuộc hàm mờ của Raju và Chen. Khái niệm phụ thuộc hàm mờ của Sozat và Yazici [4] Quan hệ r thỏa phụ thuộc hàm mờ X   Y nếu chỉ nếu với mọi t 1 , t 2 r,  (t1 Y , t 2 Y   min( , (t1 X , t 2 X ) Khái niệm này đƣợc các tác giả xây dựng trên mô hình dựa trên quan hệ tƣơng tự, không dùng véctơ ngƣỡng nhƣng cho phép ngƣỡng thay đổi. Cách mở rộng này không “mạnh” nhƣng đủ để hệ tiên đề của phụ thuộc hàm mờ có bổ sung tiên đề bao hàm ngƣỡng là xác đáng và đầy đủ. Một số tiêu chuẩn cho phụ thuộc hàm mờ Các tiêu chuẩn sau đƣợc tổng kết từ những nghiên cứu về phụ thuộc hàm mờ [4]. Tiêu chuẩn 1: Khái niệm phụ thuộc hàm mờ khi thu hẹp trên mô hình quan hệ thì trùng với khái niệm phụ thuộc hàm. Tiêu chuẩn 2.1: Với những cặp bộ mà độ gần nhau trên tập thuộc tính X không đủ lớn thì thỏa phụ thuộc hàm mờ X Y mà không phụ thuộc vào độ gần nhau trên tập thuộc tính Y Tiêu chuẩn 2.2: Phụ thuộc hàm mờ X Y đƣợc thỏa trên quan hệ r khi những Y – giá trị của r phải đủ gần nhau khi X- giá trị đủ gần nhau Tiêu chuẩn 3 : Dữ liệu của mỗi thuộc tính tùy vào đặc trƣng mà có độ mờ khác nhau do đó cần có ngƣỡng riêng cho từng thuộc tính. Khái niệm phụ thuộc hàm mờ phải đáp ứng đƣợc yêu cầu ngƣỡng riêng cho từng thuộc tính. Tiêu chuẩn 4: Với những phụ thuộc hàm có dùng ngƣỡng thì ngƣỡng không cố định mà thay đổi theo từng tình huống. Điều này thể hiện ở hệ tiên Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 20 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== đề của phụ thuộc hàm mờ phải có tiên đề bao hàm ngƣỡng và phải là hệ tiên đề xác đáng và đầy đủ Bảng trong hình 1.3 tổng kết các khái niệm phụ thuộc hàm mờ của các tác giả thỏa các tiêu chuẩn trên. Ký hiệu + là thỏa, - là không thỏa Phụ thuộc hàm mờ TC1 TC2.1 TC2.2 TC3 TC4 Raju + - - - - Chen + - + - + Cubero + + + + - Sozat + - - - + Hình 1-3: Bảng tổng kết các tiêu chuẩn cho các phụ thuộc hàm mờ Nhƣ vậy khái niệm phụ thuộc hàm mờ của Cubero là thỏa mãn nhiều nhất các tiêu chuẩn do sử dụng véctơ ngƣỡng. Tuy nhiên, hạn chế của mở rộng này là cố định véctơ ngƣỡng, làm hạn chế đến khả năng biểu diễn của phụ thuộc dữ liệu. 1.2.2 Phụ thuộc đa trị mờ Tƣơng tự phụ thuộc hàm, phụ thuộc đa trị cũng đƣợc nhiều tác giả nghiên cứu mở rộng trên mô hình cơ sở dữ liệu mờ. Tuy nhiên các kết quả nghiên cứu về phụ thuộc đa trị không đƣợc phong phú nhƣ phụ thuộc hàm v ì tính phức tạp của nó. Những kết quả mở rộng phụ thuộc đa trị mà đa số là mở rộng về ngữ nghĩa mà không mở rộng ký hiệu vì không đảm bảo những kết quả tƣơng tự nhƣ trong mô hình quan hệ. Một số quy ƣớc ký hiệu đƣợc sử dụng trong phần này: R là tập thuộc tính của lƣợc đồ quan hệ X,Y R Z = R –XY Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 21 CƠ SỞ DỮ LIỆU MỜ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ =========================================================== Khái niệm phụ thuộc đa trị mờ của Jyothi và Babu Dựa vào ý nghĩa của phụ thuộc đa trị, các tác giả đƣa ra khái niệm phụ thuộc đa trị mờ bằng cách thay quan hệ đồng nhất trên dữ liệu rõ bằng quan hệ gần nhau trên cơ sở dữ liệu mờ, với quan hệ gần nhau thỏa hai tính chất phản xạ và đối xứng mà không cần tính chất bắc cầu Quan hệ r thỏa phụ thuộc đa trị mờ X  Y khi và chỉ khi với mọi t1, t2r, Tồn tại t3r sao cho.  min( (t1 Y , t 3 Y ), (t 2 Z , t 3 Z )),     (t1 X , t 2 X   max  min( (t1 Y , t 3 Y ), (t 2 Z , t 3 Z )),   (t Y , t Y ,t Y ), (t Z , t Z t Z ) 3 2 1 2 3  1  với  (a,b,c)= min ( (a,b), (b,c), (a,c)) Khái niệm phụ thuộc đa trị mờ của Bhattachjee và Mazumdar Bhttacharjee và Mazumdar dựa vào ngữ nghĩa của phụ thuộc đa trị X  Y thỏa trên quan hệ r thì Y- giá trị của bộ các bộ chỉ phụ thuộc vào các X – giá trị và đƣa ra định nghĩa phụ thuộc đa trị mờ nhƣ sau: Quan hệ r thỏa phụ thuộc đa trị mờ X  Y khi và chỉ khi với mọi t r, đặt x  tX , z  tZ  , ta có Với Yr ( x)  Yr ( xz ), Yr ( x)  y : t  r , tX   x, tY   y, Yr ( x)  Yr ( xz ) khi và chỉ khi yY, (x)thì y’Yr (xz) sao cho  (y,y’)  và ngƣợc lại Khái niệm phụ thuộc hàm của Sozat và Yazici Trên mô hình cơ sở dữ liệu mờ dựa trên quan hệ tƣơng tự, Sozat và Yazici đã mở rộng khái niệm phụ thuộc đa trị mờ nhƣ sau: Quan hệ r thỏa phụ thuộc đa trị mờ X  Y khi và chỉ khi với mọi t 1 , t 2  r, tồn tại t 3 r sao cho  (t1 X , t 3 X )  min( , (t1 X ,t 2 X )),  (t1 Y , t 3 Y )  min( , (t1 X ,t 2 X )), Phạm Vũ Hoàng/K9T3/Chuyên nghành CNTT/Đại học Công nghệ/ĐHQG Hà nội 22