Bài giảng Cơ sở dữ liệu nâng cao - Nguyễn Văn Định

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.

pdf152 trang | Chia sẻ: Thục Anh | Ngày: 11/05/2022 | Lượt xem: 574 | Lượt tải: 0download
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), uU} 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 | uU | 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 | uU | 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 AB(u) và xác định như sau:  u U, AB(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, AB(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, AB (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:

  • pdfbai_giang_co_so_du_lieu_nang_cao_nguyen_van_dinh.pdf
Tài liệu liên quan