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ạ : sx, 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 sx, y s y, x
3. Max-min bắc cầu : sx, z max yD min sx, 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 sx, 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 d300; 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.
(tX, 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 XY 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 ( (tX , 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,
t2r, Tồn tại t3r 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 tX , z tZ , ta có
Với
Yr ( x) Yr ( xz ),
Yr ( x) y : t r , tX x, tY y, Yr ( x) Yr ( xz ) khi
và chỉ
khi
yY, (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
- Xem thêm -