Chương 1
TỔNG QUAN VỀ CSDL PHÂN TÁN
Chương này, đề cập đến một số khái niệm và kết quả cơ bản liên quan đến việc thiết kế
một CSDL phân tán.
1.1. CẤU TRÚC CỦA HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN
Dữ liệu là một thành phần không thể thiếu trong các ứng dụng công nghệ
thông tin. Quá trình phát triển của CNTT cũng kéo theo quá trình phát triển của công nghệ
CSDL.
1.1.1. Sự phát triển của công nghệ CSDL
Công nghệ lưu trữ và xử lý dữ liệu cho đến nay đã trải qua các giai đoạn phát triển chính
như sau:
- Xử lý tệp truyền thống: Trong mô hình này, dữ liệu lưu trữ thành các tệp riêng rẽ, được
mô tả và gắn kết với từng chương trình ứng dụng.
Hình 1.1. Sơ đồ xử lý tệp truyền thống
Cách xử lý này sẽ phát sinh vấn đề dư thừa dữ liệu và các dị thường trong cập nhật. Chẳng
hạn, có thể có 2 chương trình ứng dụng với 2 tệp dữ liệu riêng, nhưng mỗi tệp dữ liệu này lại có
những thông tin giống nhau, vì vậy tạo nên sự dư thừa dữ liệu, gây lãng phí cho lưu trữ và quản lý.
Nguy hại hơn là khi cập nhật thay đổi thông tin về một thực thể trong tệp dữ liệu này thì cũng phải
thay đổi trong tệp kia với đối tượng đó. Điều này rất khó thực hiện triệt để khi có nhiều tệp dữ liệu
có chứa các thông tin trùng lặp, và sẽ gây ra các dị thường trong cập nhật (thông tin không nhất
quán, thông tin mâu thuẫn.).
- Xử lý CSDL (Database-DB): Để khắc phục các nhược điểm của mô hình xử lý tệp, dữ
liệu của các ứng dụng được lưu trữ tập trung, được mô tả và xử lý thống nhất cho mọi chương
trình ứng dụng. Các dữ liệu tập trung lại thành một CSDL, được xử lý theo cách thống nhất cho
tất cả các ứng dụng có liên quan.
Như vậy vấn đề tập trung dữ liệu là mấu chốt của xử lý CSDL. Công nghệ CSDL là một
bước tiến lớn của công nghệ xử lý dữ liệu. Rõ ràng là nhờ sự tập trung dữ liệu, CSDL đã khắc
phục được sự dư thừa dữ liệu, hạn chế các dị thường trong cập nhật.
152 trang |
Chia sẻ: Thục Anh | Ngày: 11/05/2022 | Lượt xem: 563 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Cơ sở dữ liệu nâng cao - Nguyễn Văn Định, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
tin mơ hồ như vậy. Một CSDL
như vậy được gọi là CSDL với thông tin không hoàn hảo.
Giải pháp thứ hai rõ ràng là tốt hơn, vì có thể mở rộng các ứng dụng của CSDL trên cơ sở
cho phép biểu diễn và xử lý các thông tin không hoàn hảo.
6.1.2. Thông tin không hoàn hảo
Trong những năm gần đây, để đáp ứng các yêu cầu của những ứng dụng cơ sở dữ liệu
không truyền thống, bao gồm CAD/CAM, các hệ thống tự động hóa văn phòng, những thiết kế
kỹ thuật, nhiều loại thông tin không hoàn hảo khác nhau đã được đưa vào CSDL quan hệ.
Các mô hình CSDL quan tâm tới năm loại thông tin không hoàn hảo dưới đây:
- Thông tin không nhất quán (inconsistent information): Đây là loại thông tin sai lệch,
trong đó 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 những CSDL khác nhau, khi các biểu diễn đó là đối lập quyết liệt không thể hòa hợp
được. Thông tin không nhất quán có thể ảnh hưởng đến tính toàn vẹn của một CSDL, chẳng hạn
có thể phá vỡ một phụ thuộc dữ liệu nào đó. Thông tin không nhất quán thường xuất hiện khi
tích hợp thông tin từ nhiều CSDL.
- Thông tin không chính xác (imprecise information): Là thông tin được ký hiệu bởi một
tập các giá trị có thể, và giá trị thực của thông tin là một phần tử của tập đó. Như vậy thông tin
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 112
không chính xác không phải là thông tin không nhất quán, nó không làm phương hại tới tính toàn
vẹn của CSDL. Chẳng hạn những thông tin sau đây là không chính xác:
Thông tin tuyển: tuổi của Nam hoặc là 35 hoặc là 36.
Thông tin âm: Tuổi của Nam không phải 30.
Thông tin khoảng miền: Tuổi của Nam giữa 35 và 40, hay tuổi của Nam lớn hơn 32.
Thông tin với sai số: Tuổi của Nam là 35 1.
Các giá trị null được hiểu là thông tin không chính xác, trong đó tập các giá trị có thể là
toàn bộ miền trị hợp lệ,...
- Thông tin mơ hồ (vague information): Có thể thấy thông tin không chính xác và thông
tin mơ hồ là có mối liên hệ tới nội dung của giá trị thuộc tính, có nghĩa là một sự lựa chọn phải
được thực hiện trên một vùng đã cho của miền trị, nhưng ta không thực sự biết chính xác giá trị
nào được chọn. Chẳng hạn, các phát biểu: “Tuổi của Nam là trẻ”, hay “Căn hộ tương đối rộng và
gần bãi biển” là chứa đựng các thông tin mơ hồ, vì ta không biết tuổi của Nam “trẻ” là bao
nhiêu, hay “tương đối rộng” là diện tích bao nhiêu, hay “gần” là khoảng cách bao nhiêu... Thông
tin mơ hồ có thể hiểu là sự biểu diễn của giá trị của các biến ngôn ngữ.
- Thông tin không chắc chắn (uncertaint information): Là loại thông tin không được phát
biểu với niềm tin tuyệt đối và đòi hỏi phải đưa ra niềm tin (mức độ chắc chắn) về thông tin được
phát biểu. Chẳng hạn, với phát biểu: “tuổi của nam là 35 hoặc 36” thể hiện tính không chính xác,
thì 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.
Chú ý rằng, đôi khi một giá trị chính xác lại kéo theo sự kém chắc chắn, một giá trị càng kém
chính xác thì độ chắc chắn sẽ tăng dần, cuối cùng đạt cực đại với một giá trị có độ chính xác cực
tiểu (chẳng hạn giá trị null). Với phát biểu trên về tuổi của Nam là 35 (chính xác), thì độ chắc chắn
là thấp (chỉ là “có khả năng”), còn phát biểu: “chắc chắn tuổi của Nam từ 25 đến 50”, thông tin này
có niềm tin tuyệt đối, độ chắc chắn cao nhất, nhưng độ chính xác lại rất thấp. Thông tin không chắc
chắn cũng không phải là thông tin không nhất quán, và không làm phương hại tới tính vẹn toàn của
CSDL.
- Thông tin nhập nhằng (ambiguos information): Là loại thông tin còn thiếu một số yếu tố
về ngữ nghĩa, ngữ cảnh, do đó có thể dẫn tới nhiều cách hiểu và giải thích khác nhau. Chẳng hạn
nói rằng lương của Bill là 50.000 USD, là một thông tin nhập nhằng, vì không biết lương đó là
tính theo tuần, theo tháng hay theo năm?.
Như vậy, từ các yêu cầu của thế giới thực, cần đặt ra vấn đề mở rộng mô hình CSDL quan
hệ để cho phép biểu diễn và xử lý những thông tin không hoàn hảo, những thông tin như vậy đều
có tính chất chung là không rõ ràng, được gọi chung là các dữ liệu mờ (Fuzzy Data). Có hai cách
mở rộng mô hình quan hệ để đáp ứng các yêu cầu về biểu diễn, xử lý và khai thác dữ liệu mờ, đó
là: mở rộng ngữ nghĩa của dữ liệu để khai thác dữ liệu rõ với các yếu tố mờ và mở rộng miền trị
thuộc tính để biểu diễn được dữ liệu mờ.
6.1.3. Hai cách mở rộng mô hình cơ sở dữ liệu quan hệ
- Mở rộng ngữ nghĩa dữ liệu
Với cách mở rộng ngữ nghĩa, dữ liệu vẫn được lưu trữ như mô hình dữ liệu quan hệ truyền
thống (là các “CSDL rõ”), tức là dữ liệu tại mỗi bộ tại các thuộc tính là dữ liệu rõ nhưng cho
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 113
phép khai thác dữ liệu với ngữ nghĩa rộng hơn. Chẳng hạn ta có thể hỏi dữ liệu với tiêu chuẩn
không rõ ràng như: “cho biết những nhân viên có lương khá cao trong công ty”. Cách mở rộng
này tất yếu 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ư việc ta
phải mô hình hóa những khái niệm mờ như “cao”, “thấp”, cách gắn giá trị chân lý cho những
phép so sánh như “xấp xỉ nhau”, “gần nhau”, “tương đương”,
Lý thuyết tập mờ và logic mờ là cơ sở cho việc mở rộng theo cách này. Điểm tiện lợi của
cách mở rộng này là có thể sử dụng được các hệ quản trị CSDL của mô hình quan hệ để quản lý
dữ liệu, những mở rộng cho việc xử lý dữ liệu được cài đặt thành một mô đun độc lập. Các ứng
dụng của cơ sở dữ liệu mờ cho đến hiện nay thường làm theo cách này bởi vì CSDL quan hệ
được sử dụng rất rộng rãi trong hầu hết các hệ thống thông tin và trở nên quen thuộc với người
dùng cũng như những người quản trị hệ thống. Hơn nữa, nó không làm thay đổi cấu trúc của hệ
thống cũng như không yêu cầu người dùng phải học thêm một ngôn ngữ hoàn toàn mới.
- Mở rộng miền trị thuộc tính
Đây là cách mở rộng tổng quát hơn so với cách mở rộng ngữ nghĩa. Cách mở rộng này bổ
sung những cú pháp cho phép biểu diễn được nhiều dạng dữ liệu mờ. Nhiều nhà nghiên cứu mở
rộng theo cách này từ những năm 1970 và cho đến nay vẫn tiếp tục phát triển. Nhiều công cụ
toán học được sử dụng để mở rộng khả năng biểu diễn dữ liệu như: lý thuyết tập mờ, biến ngôn
ngữ, lý thuyết khả năng, lý thuyết xác suất Với cách mở rộng này, bên cạnh bổ sung cú pháp
biểu diễn còn phải giải quyết cả vấn đề ngữ nghĩa của các ký hiệu mới, những cơ sở tính toán,
logic hỗ trợ cho việc xử lý dữ liệu với các ký pháp mở rộng. Do đó cách mở rộng này yêu cầu
người dùng phải học về một cơ sở dữ liệu mới là cơ sở dữ liệu mờ cùng với các hệ quản trị cho
cơ sở dữ liệu mờ.
6.1.4. Ứng dụng lý thuyết tập mờ để mở rộng mô hình cơ sở dữ liệu quan hệ
Mô hình quan hệ do Codd E.F. đề xuất năm 1970 đã đáp ứng được nhu cầu lưu trữ và xử lý
dữ liệu của con người trong một thời gian dài. Tuy nhiên, mô hình này đòi hỏi các thông tin lưu
trữ và xử lý phải là chính xác và hoàn hảo, trong khi các ứng dụng của thế giới thực, thông tin
thường là không hoàn hảo. Như vậy đặt ra vấn đề cần xây dựng một mô hình CSDL mới để lưu
trữ và thao tác với các thông tin không hoàn hảo.
Ta có thể định nghĩa tổng quát cho một mô hình CSDL mờ như sau:
Định nghĩa 6.1: Mô hình CSDL mờ là một mô hình dữ liệu cho phép biểu diễn, thao tác và
xử lý các thông tin không hoàn hảo và không đầy đủ bằng cách mở rộng ngữ nghĩa dữ liệu hoặc
mở rộng miền trị thuộc tính.
Như vậy, một CSDL mà trong đó có chứa một yếu tố liên quan đến các thông tin không
hoàn hảo (các thông tin mờ) thì được gọi là CSDL mờ. Nếu chúng ta chỉ xem xét các mô hình
CSDL quan hệ, biểu diễn bởi tập các bảng thì một cách trực quan có thể thấy nếu một CSDL quan
hệ có chứa ít nhất một bảng có yếu tố mờ thì đó là một CSDL mờ.
Dựa trên các tiếp cận theo logic mờ, người ta đề xuất nhiều phương pháp để lưu trữ và xử
lý thông tin không hoàn hảo dựa trên cơ sở của lý thuyết tập mờ, lý thuyết khả năng và quan hệ
tương tự. Với mỗi cách tiếp cận, có thể xây dựng được các mô hình CSDL quan hệ mờ khác
nhau. Trong giáo trình này, chúng ta giới thiệu một số mô hình CSDL mờ chủ yếu, đó là các mô
hình CSDL quan hệ mờ dựa trên tập con mờ, mô hình CSDL quan hệ mờ dựa trên quan hệ tương
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 114
tự, mô hình CSDL quan hệ mờ dựa trên phân bố khả năng cùng với các vấn đề liên quan đến việc
thiết kế và chuẩn hóa các CSDL mờ.
6.2. CÁC KHÁI NIỆM CƠ SỞ CỦA LÝ THUYẾT TẬP MỜ
6.2.1. Khái niệm tập hợp mờ
Khái niệm ‘Tập hợp mờ’ (Fuzzy Set) được đề xuất bởi Zadez [11] từ năm 1965, là mở rộng
của khái niệm tập hợp cổ điển, nhằm đáp ứng nhu cầu biểu diễn những tri thức không chính xác.
Trong lý thuyết tập hợp cổ điển (tập hợp rõ-crisp set), quan hệ thành viên của các phần tử đối với
một tập hợp được đánh giá theo kiểu nhị phân một cách rõ ràng: mỗi phần tử u của vũ trụ tham
chiếu U chỉ có thể là chắc chắn thuộc tập A hoặc chắc chắn không thuộc tập A. Như vậy, để xem
một phần tử có là là thành viên của tập A hay không, ta gán cho phần tử đó giá trị 1 nếu phần tử
đó chắc chắn thuộc A, và giá trị 0 nếu nó không thuộc về tập hợp A, tức là ta có thể xây dựng
một hàm thành viên (hay hàm thuộc) để đánh giá một phần tử có thuộc tập A hay không:
1 if u
,
0
A
A
u U u
if u A
Rõ ràng, hàm thành viên A sẽ xác định các phần tử thuộc về tập rõ A chỉ nhận giá trị 0
hoặc 1. Như vậy với tập rõ A thì A: U { 0, 1}.
Ngược lại, lý thuyết tập mờ cho phép đánh giá nhiều mức độ khác nhau về khả năng một
phần tử có thể thuộc về một tập mờ A. Ta cũng dùng một hàm thành viên A để xác định các
mức độ mà một phần tử u thuộc về tập mờ A, hàm này nhận mọi giá trị từ 0 đến 1, tức là: u
U, 0 A(u) 1. Như vậy, với tập mờ A thì A: U [0, 1].
Chẳng hạn, xét vũ trụ tham chiếu là các nhân viên trong một công ty, gọi A là tập ‘những
người có mức lương từ 6 triệu đến 8 triệu đồng, thì A là một ‘tập rõ’, gồm tất cả những người có
mức lương S, mà 6.000.000 S 8.000.000. Rõ ràng ai có lương 5.990.000đ hay 8.010.000đ là
không thuộc tập A. Nếu ta coi mức lương từ 6.000.000 trở lên là mức ‘thu nhập cao’, thì cả
những người có mức lương thấp hơn 6.000.000 vài chục ngàn đến vài trăm ngàn đồng vẫn có thể
được xem là thuộc tập hợp ‘những người có thu nhập cao’. Nếu gọi B là tập: ‘những người có
thu nhập cao’ thì B là tập mờ, mỗi phần tử của vũ trụ tham chiếu đều được gán một giá trị chỉ
mức độ mà phần tử đó thuộc về tập mờ này. Chẳng hạn một nhân viên có mức lương 6.800.000
có độ thuộc vào tập B này là bằng 1 (chắc chắn là người có thu nhập cao), nhưng một người có
mức lương 2.000.000 thì có thể coi là thành viên của tập này với độ thuộc rất thấp, độ thuộc sẽ
tăng dần với những người có mức lương càng cao. Những người có thu nhập dưới 1.000.000 đ
thì không thể xem là có thu nhập cao, chắc chắn không thể thuộc tập B (mức độ là thành viên là
bằng 0).
Ta có định nghĩa hình thức cho một tập con mờ trên một vũ trụ tham chiếu U (là tập hợp
tất cả các phần tử xem xét, còn gọi là ‘tập nền’) như sau:
Định nghĩa 6.2: Tập con mờ A trên tập nền U xác định bởi hàm thuộc A: U [0, 1] gán
cho mỗi phần tử u của U, một giá trị A(u), với 0 ≤ A(u) ≤1, để chỉ mức độ mà phần tử u thuộc
về tập mờ A và được xác định:
, 1,2,...,
A i
i
i
u
A u U i n
u
Có thể dùng ký hiệu: , i A i iA u u u U
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 115
hoặc:
1 2
1 2
... A A A n
n
u u u
A
u u u
và chú ý rằng các dấu ‘+’ và ký hiệu phân số trong biểu diễn trên chỉ là một cách ký hiệu cho
mỗi phần tử ui (ở mẫu số) và mức độ thuộc về A của các phần tử đó (ở tử số) chứ không liên quan
gì đến các phép toán.
Nếu hàm A(u) cho kết quả 0 đối với phần tử u U thì phần tử đó không có trong tập mờ
A, kết quả 1 thì phần tử đó hoàn toàn thuộc tập đã cho. Các giá trị trong khoảng mở từ 0 đến 1
đặc trưng cho các phần tử mờ, tức là mức độ là thành viên của phần tử đó đối với tập hợp dã cho.
Trường hợp đặc biệt khi A: U {0, 1}, tức là hàm A(u) chỉ lấy giá trị bằng 0 hay 1, thì
tập con mờ A là một tập con cổ điển của U. Như vậy, tập con cổ điển (tập rõ) là một trường hợp
riêng của tập con mờ.
Thí dụ 6.1. Xét tập U gồm 8 căn hộ được ký hiệu là u1, u2, u3, u4, u5, u6, u7 và u8, mỗi căn
hộ có số phòng tương ứng là 1, 2,, 8 phòng. Gọi A là tập hợp gồm các căn hộ “rộng”, B là tập
hợp gồm các căn hộ “thích hợp cho 4 người”. Ta xây dựng hàm thuộc cho các tập mờ A và B
như sau:
A : A(u3) = 0,4; A(u4) = 0,5; A(u5) = 0,6; A(u6) = 0,8; A(u7) = 0,9; A(u8) = 1,0
B : B(u3) = 0,4; B(u4) = 1,0; B(u5) = 0,7; B(u6) = 0,5;
đối với các phần tử khác, các giá trị của hàm thuộc là bằng 0.
Như vậy có thể biểu diễn các tập mờ trên như sau:
A = {0,4/u3; 0,5/u4; 0,6/u5; 0,8/u6; 0,9/u7; 1,0/u8}
B = {0,4/u3; 1,0/u4; 0,7/u5; 0,5/u6},
Từ nay về sau, để cho gọn ta có thể dùng “Tập mờ” thay cho “Tập con mờ” mà không gây
ra sai sót và hiểu lầm nào.
6.2.2. Các đặc trưng của tập mờ
Các đặc trưng của một tập mờ A trên U, là những thông tin để mô tả về các phần tử liên
quan đến tập mờ A, những đặc trưng này còn chỉ rõ sự khác biệt của tập mờ A, so với những tập
con cổ điển khác của U.
Định nghĩa 6.3: Cho tập mờ A trên vũ trụ tham chiếu U, các đặc trưng cơ bản của tập mờ
A được định nghĩa và xác định như sau:
(1) Giá đỡ của tập mờ A (Support) là tập các phần tử có giá trị hàm thuộc lớn hơn 0 trong
tập mờ A, được ký hiệu và xác định như sau:
supp(A) = {u | u U | A(u) > 0}
(2) Chiều cao của tập mờ A là giá trị lớn nhất mà hàm thuộc có thể lấy trong tập mờ A,
được ký hiệu và xác định như sau:
h(A) = Asup{ ( ), }u u U
- Chú ý rằng nếu U là tập rời rạc thì h(A) = max{A(u), uU}
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 116
- Tập mờ A gọi là chuẩn hóa nếu chiều cao của nó h(A) = 1
Như vậy, tập mờ A trên U được gọi là chuẩn hóa, nếu chắc chắn có ít nhất 1 phần tử của U
là thật sự thuộc A.
(3) Hạt nhân của tập mờ A là tập các phần tử có giá trị hàm thuộc bằng 1, được ký hiệu và
xác định như sau:
ker(i) = {u | uU | A(u) = 1}
Như vậy, tập mờ A có hạt nhân khác rỗng khi và chỉ khi A là tập mờ chuẩn hóa.
(4). Lực lượng của tập mờ A được ký hiệu và xác định như sau:
A
u U
A u
Chú ý rằng nếu A là tập rõ thì A(u) = 1 với mọi u thuộc A, tổng trên bằng số phần tử của
A, định nghĩa này là mở rộng của định nghĩa lực lượng của tập hợp cổ điển cho một tập rời rạc.
(5) - nhát cắt của tập mờ A (hay tập mức của A) là tập các phần tử có giá trị hàm
thuộc lớn hơn hoặc bằng , với [0, 1], được ký hiệu và định nghĩa như sau:
A = {u | uU | A(u) }
Chú ý rằng - nhát cắt của tập mờ A là 1 tập “rõ”, các phần tử của A hoàn toàn được xác
định.
Thí dụ 6.2. Xét tập mờ A là các căn hộ rộng, trong thí dụ 6.1:
A = {0,4/u3; 0,5/u4; 0,6/u5; 0,8/u6; 0,9/u7; 1,0/u8}
Khi đó: Giá đỡ, hạt nhân, chiều cao, tập mức của tập mờ A được xác định
như sau:
supp(A) = {u3, u4, u5, u6, u7, u8}
ker(A) = {u8}
h(A) = 1.0
A là tập mờ chuẩn hóa, do có h(A) = 1.
Một số nhát cắt mức = 0,5 của tập mờ A:
A0,5 = {u4, u5, u6, u7, u8};
A0,9 = {u7, u8}
6.2.3. Các phép toán trên tập mờ
Tương tự như lý thuyết tập hợp, trên các tập mờ cũng định nghĩa các khái niệm bằng nhau,
bao hàm nhau và một số phép toán như: phép hợp, phép giao, tích Đề các (Descartes) của 2 tập
mờ, là sự mở rộng các phép toán tương ứng trong lý thuyết tập hợp cổ điển.
a. So sánh các tập mờ
Cho A và B là hai tập con mờ trên vũ trụ tham chiếu U với hàm thuộc tương ứng là A và
B, để so sánh các tập con mờ A, B ta xem xét các hàm thuộc của nó. Ta có:
- Hai tập mờ A và B là bằng nhau: ký hiệu A = B, nếu u U thì A(u) = B(u)
- Tập mờ A chứa trong tập mờ B: ký hiệu A B, nếu u U thì A(u) B (u).
- Tập rỗng có thể xem là tập mờ A, với hàm thuộc A(u) = 0, u U
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 117
Từ các khái niệm trên, ta thấy hai tập mờ là bằng nhau, khi mọi phần tử của tập này cũng
thuộc tập kia (với cùng độ thuộc) và ngược lại. Điều này hoàn toàn tương tự khái niệm bằng
nhau của hai tập hợp cổ điển. Ngoài ra, tập mờ A là tập con của tập mờ B nếu một phần tử bất kỳ
thuộc A thì cũng thuộc B (với độ thuộc không thấp hơn độ thuộc của phần tử đó trong A), điều
này cũng tương tự như đối với các tập hợp cổ điển.
b. Phép hợp 2 tập mờ
Định nghĩa 6.4: Hợp của hai tập mờ A và B trên U, ký hiệu A B, là một tập mờ trên U
với hàm thuộc được ký hiệu AB(u) và xác định như sau:
u U, AB(u) = max{A(u), B (u)}
Đồ thị hàm thuộc của hợp mờ A, B và tập mờ A B được cho trong hình sau:
Hình 6.1. Hợp của hai tập mờ A và B
c. Phép giao 2 tập mờ
Định nghĩa 6.5: Giao của hai tập mờ A và B trên U, ký hiệu A B, là một tập mờ trên U
với hàm thuộc được ký hiệu A B(u) và được xác định như sau:
u U, AB(u) = min{A(u), B(u)}
Đồ thị hàm thuộc của hợp mờ A, B và tập mờ A B được cho trong hình sau:
Hình 6.2. Giao của hai tập mờ A và B
d. Một số tính chất của phép hợp và phép giao các tập mờ:
Các tính chất giao hoán, kết hợp và phân bố của phép hợp và phép giao trong lý thuyết tập
hợp cổ điển vẫn đúng đối với phép hợp, phép giao của các tập con mờ. Tức là nếu A, B, C là các
tập con mờ trên vũ trụ tham chiếu U, ta có các công thức sau:
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 118
- Tính chất giao hoán:
A B = B A
A B = B A
- Tính chất kết hợp:
(A B) C = A (B C)
(A B) C = A (B C)
- Tính chất phân bố:
A (B C) = (A B) (A C)
A (B C) = (A B) (A C)
Nói chung, những công thức của tập hợp cổ điển chỉ liên quan đến phép hợp và phép giao,
thì cũng đúng đối với các tập con mờ, chẳng hạn: A B A A B, A U = A, A U = U
và vv
e. Phần bù của một tập mờ
Trong tập hợp cổ điển, phần bù của một tập hợp chứa những phần tử không thuộc tập đó
(trên cùng tập vũ trụ tham chiếu). Đối với tập con mờ A trên U, phần bù của A, ký hiệu là A ,
chứa những phần tử với độ thuộc càng cao nếu độ thuộc của phần tử này vào A càng nhỏ. Nói
cách khác, một phần tử càng ít có khả năng thuộc vào tập mờ A thì càng có nhiều khả năng thuộc
vào phần bù A , như vậy A cũng là một tập con mờ trên U và được định nghĩa như sau:
Định nghĩa 6.6: Phần bù của tập mờ A, ký hiệu A là một tập con mờ trên U với hàm
thuộc được ký hiệu
A
(u) và xác định như sau:
u U,
A
(u) = 1- A(u)
Đồ thị hàm thuộc của tâp mờ A và tập mờ A như sau:
Hình 6.3. Phần bù của tập mờ A
g. Một số tính chất của phép lấy phần bù các tập mờ:
Đối với các tập con cổ điển trên tập vũ trụ U, ta luôn có A A = và A A = U, nhưng
đối với các tập mờ thì hai tính chất này nói chung không đúng, tức là nếu A là phần bù của tập
mờ A trên U thì:
A A , và
A A U.
Đây là điểm khác nhau quan trọng giữa các tập con cổ điển và các tập con mờ.
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 119
Các tính chất khác đối với phần bù của tập con cổ điển vẫn đúng cho các tập con mờ, tức là
nếu A, B là các tập con mờ trên U thì ta có:
- Một số tính chất về phần bù (phủ định):
A A ; U = Ø ; Ø = U
- Các công thức đối ngẫu (công thức De Morgan):
A B A B
A B A B
Thí dụ 6.3. Trở lại các tập mờ A, B trong thí dụ 6.1, với các tập con mờ A, B
như sau:
A là tập hợp các căn hộ “rộng”. A = {0,4/u3; 0,5/u4; 0,6/u5; 0,8/u6; 0,9/u7; 1,0/u8}
B là tập hợp các căn hộ “thích hợp cho 4 người”. B = {0,4/u3; 1,0/u4; 0,7/u5; 0,5/u6}
Khi đó ta có:
- A B = {Các căn hộ thích hợp cho 4 người “hoặc” rộng}
= {0,4/u3; 1,0/u4; 0,7/u5; 0,8/u6; 0,9/u7; 1,0/u8}
- A B = {Các căn hộ thích hợp cho 4 người “và” rộng}
= {0,4/u3; 0,5/u4; 0,6/u5; 0,5/u6}
- A = {Các căn hộ không rộng}
= {0,6/u3; 0,5/u4; 0,4/u5;0,2/u6; 0,1/u7}
- A A = {0,4/u3 ; 0,5/u4 ; 0,4/u5 ; 0,2/u6 ; 0,1/u7}
h. Tích Đề các (Descartes) của tập mờ
Trước hết ta định nghĩa tích Đề các của 2 tập con mờ A và B trên các vũ trụ tham chiếu
tương ứng U và V, giả sử U và V là độc lập với nhau.
Định nghĩa 6.7: Cho A và B là hai tập con mờ có các hàm thuộc A và B trên các vũ trụ
tham chiếu tương ứng U và V, khi đó tích Đề các của A và B là một tập con mờ ký hiệu là A B
trên vũ trụ tham chiếu U V, với hàm thuộc là A B được xác định
như sau:
(u,v) U V, AB (u,v) = min{A(u), B(v)}
Tương tự như trong lý thuyết tập hợp cổ điển, ta có thể mở rộng định nghĩa tích Đề các cho
k tập mờ trên các vũ trụ tham chiếu độc lập:
Định nghĩa 6.8: Tích Đề các của k tập mờ A1, A2,..., Ak trên các vũ trụ tham chiếu U1,
U2,.., Uk là một tập con mờ ký hiệu là A1 A2 ... Ak trên vũ trụ tham chiếu U1 U2 ... Uk,
với hàm thuộc là A1 A2 Ak được xác định như sau:
A1 A2 × Ak (u) = min{A1(u1), A2(u2),..., Ak(uk)},
u = (u1, u2,, uk) U1 U2 ... Uk.
Các khái niệm về tích Đề các của các tập con mờ là cơ sở để nghiên cứu các quan hệ mờ
trong các phần sau.
6.3. CÁC QUAN HỆ MỜ
6.3.1. Định nghĩa quan hệ mờ
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 120
Chúng ta bắt đầu xem xét trường hợp đơn giản nhất của các quan hệ mờ, đó là quan hệ mờ
giữa 2 phần tử của vũ trụ tham chiếu U nào đó (U còn được gọi là tập nền).
Đây cũng là trường hợp có nhiều ứng dụng nhất của các quan hệ mờ, đó là các quan hệ mờ
hai ngôi trên cùng một tập nền. Trong Giáo trình này, ta cũng chủ yếu xét các quan hệ mờ hai
ngôi trên cùng một tập nền, việc mở rộng định nghĩa cho các quan hệ mờ trên nhiều tập nền là
không khó khăn.
Đối với các quan hệ cổ điển R (quan hệ “rõ”) thì với 2 phần tử a, b U, chúng hoặc là có
quan hệ với nhau (khi đó ta viết aRb), hoặc là không có quan hệ với nhau (ta viết aRb). Ta có
thể gán giá trị cho cặp (a, b) là bằng 1 nếu a và b có quan hệ với nhau, và gán giá trị 0 trong
trường hợp trái lại. Như vậy hàm hai biến:
a, b U, fR(a, b) =
1
0
if aRb
if aRb
lấy giá trị trong tập {0, 1} sẽ xác định được tất cả những
cặp (a, b) U U có quan hệ với nhau theo quan hệ R nào đó, những cặp phần tử như vậy tạo
nên một tập con của tích Đề các U U, và được gọi là một quan hệ hai ngôi (rõ) trên tập hợp U.
Với các quan hệ mờ, thì mỗi cặp phần tử a, b U có thể có mối liên hệ không chỉ ở mức độ 0
hoặc 1, mà có thể có nhiều mức độ giữa 0 và 1. Như vậy, nếu ta dùng một hàm fR(a, b) lấy mọi
giá trị trong miền [0, 1] thì sẽ xác định được nhiều cấp độ quan hệ giữa hai phần tử bất kỳ a, b
U, tức là xác định được quan hệ mờ 2 ngôi trên U, quan hệ này sẽ là một tập con mờ của tích Đề
các U U. Ta có định nghĩa sau:
Định nghĩa 6.9: Một quan hệ mờ R trên tập tham chiếu U, ký hiệu là R(U), (hay RU) là một
tập con mờ của tích Đề các U U, xác định bởi hàm thuộc fR: U U [0, 1].
Nếu hai phần tử a, b U có liên hệ theo quan hệ R với mức độ , thì ta viết fR(a, b) = , (
chỉ mức độ quan hệ nhiều hay ít giữa hai phần tử a và b, với 0 < < 1)
Nếu tập U là hữu hạn: U = {u1, u2,..., un} thì quan hệ mờ hai ngôi trên U có thể được biểu
diễn bằng một ma trận vuông cấp n, (hoặc cho bởi bảng n hàng, n cột) mà phần tử ij nằm trên
hàng i và cột j là mức độ quan hệ của cặp phần tử ui, uj trong U, tức là ij = fR(ui, uj).
Ma trận của quan hệ mờ R được ký hiệu và xác định như sau:
M(R) = (ij)n × n ; với ij = fR(ui, uj), (i = 1, 2,..., n; j = 1, 2,..., n)
Việc cho một quan hệ mờ 2 ngôi R trên U tương đương với việc cho một ma
trận M(R).
Thí dụ 6.4. Cho tập 3 sinh viên: {Hùng, Liên, Dung}, ký hiệu ngắn gọn: U = {H, L, D}.
Cho R là một quan hệ mờ hai ngôi trên U, là mức độ tin cậy của sinh vên này đối với sinh viên
kia. Quan hệ R (mức độ “tin cậy” lẫn nhau) giữa các sinh viên cho trong bảng dưới đây:
Bảng 6.1. Quan hệ “tin cậy” giữa các sinh viên
R H L D
H 1 0,9 0,3
L 0,9 1 0,1
D 0,5 0,1 1
Ta có thể cho quan hệ mờ R bằng ma trận M(R) = (aij) với aij là mức độ tin cậy của sinh
viên thứ i với sinh viên thứ j, với i, j = 1, 2, 3.
Bài giảng “Cơ sở dữ liệu nâng cao” | nvdinh@vnua.edu.vn 121
1 0,9 0,3
M R 0,9 1 0,1
0,5 0,1 1
Tức là ta có các mức độ tin cậy giữa các cặp SV như sau:
fR(H, L) = fR(L, H) = 0,9;
fR(L, D) = fR(D, L) = 0,1;
fR(H, D) = 0,3; fR(D, H) = 0,5;
fR(H, H) = fR(L, L) = fR(D, D) = 1,
Nếu biểu diễn quan hệ trên dưới dạng tập con mờ ta có:
R(U) ={0,9/(H, L), 0,9/(L, H), 0,1/(L, D), 0,1/(D, L), 0,3/(H, D), 0,5/(D, H), 1,0/(H, H), 1,0/(L, L),
1,0/(D, D)}
Mở rộng định nghĩa quan hệ mờ trên nhiều tập tham chiếu U1, U2,, Uk như sau:
Định nghĩa 6.10: Một quan hệ mờ k ngôi R trên k tập tham chiếu U1, U2, ,Uk, ký hiệu là
R(U), là một tập con mờ của tích Đề các U = U1 U2 Uk với hàm thuộc:
fR: U1 U2 Uk [0, 1]
Trong định nghĩa trên, khi các tập tham chiếu U1= U2 == Uk = U thì ta có quan hệ mờ k
ngôi trên U, đó là tập con mờ của tích Đề các U U U (ký hiệu là Un), xác định bởi hàm
thuộc fR:
Các file đính kèm theo tài liệu này:
- bai_giang_co_so_du_lieu_nang_cao_nguyen_van_dinh.pdf