Một số phép toán quan hệ mờ và phụ thuộc hàm mờ dựa trên số mờ hình thang

TẠP CHÍ KHOA HỌC, Đại học Huế, Số 20, 2003 MỘT SỐ PHÉP TOÁN QUAN HỆ MỜ VÀ PHỤ THUỘC HÀM MỜ DỰA TRÊN SỐ MỜ HÌNH THANG Nguyễn Công Hào Trường Đại học Khoa học, Đại học Huế 1. ĐẶT VẤN ĐỀ Trong lĩnh vực cơ sở dữ liệu, một trong những yêu cầu là phản ánh thật tốt thế giới thực, giúp người quản trị dễ dàng xử lý, lưu trữ chính xác những thông tin thu nhận được. Trong thực tế, đôi khi chúng ta không thể thu nhận được các thông tin một cách đầy đủ, hoặc có những thông tin không chính xác (Inexact), không chắc chắn (Uncertain) gọi chung là các thông tin mờ. Do đó, khi người quản trị một CSDL thực tế nào đó dựa trên mô hình kinh điển, thường gặp những trường hợp sau: Tại thời điểm cần cập nhật một đối tượng nào đó vào CSDL nhưng chưa có đầy đủ thông tin về đối tượng đó, chẳng hạn biết là một cán bộ giảng dạy "thâm niên" nhưng không rõ năm vào biên chế (Giá trị hiện tại là Unknown ). Biết một cán bộ giảng dạy có "nhiều" công trình nghiên cứu khoa học, nhưng không biết cụ thể là bao nhiêu (Khái niệm mờ Vague ). Nếu giới hạn trong mô hình CSDL kinh điển thì phải đợi đầy đủ thông tin về đối tượng đó mớ cập nhật vào CSDL, hoặc nếu cứ nhập thì sẽ gây khó khăn, mất ngữ nghĩa và không nhất quán trong xử lý dữ liệu. Do đó để đáp ứng nhu cầu thực tế, chúng ta phải mở rộng mô hình CSDL kinh điển, xây dựng các phép toán quan hệ cũng như phụ thuộc dữ liệu. 2. CÁC KHÁI NIỆM CƠ BẢN Cho W=(A1, A2, ...An, m) là tập hữu hạn các thuộc tính, các miền giá trị tương ứng D(A1), D(A2),...D(An), D(m) =[0,1]. Trong đó, D(Ai) (i=1..n) có thể nhận giá trị rõ hoặc giá trị mờ. 2.1. Lược đồ quan hệ mờ Là tập hữu hạn các thuộc tính A1, A2,..An, m. Trong đó m là thuộc tính độ thuộc. 2.2. Quan hệ mờ Một quan hệ mờ fr trên lược đồ quan hệ mờ là tập con của tích Descartes D(A1)´D(A2)´...´D(An)´ D(m). Tức là fr Í D(A1)´D(A2)´...´D(An)´ D(m). 2.3. Bộ dữ liệu Một bộ dữ liệu tÎfr có dạng: (t, mfr(t)) Trong đó: mfr(t): D(A1)´D(A2)´...´D(An) à [0, 1] để cho độ thuộc của bộ t vào quan hệ fr. Do đó quan hệ fr có thể biểu diễn lại như sau: fr = ((t, mfr(t) |mfr(t)Î[0,1] và tÎr) Với rÍ D(A1)xD(A2)x..........x D(An) 2.4. Biến ngôn ngữ Theo L.A.Zadeh biến ngôn ngữ là loại biến mà miền giá trị của nó bao gồm các từ hoặc câu ở ngôn ngữ tự nhiên hoặc ngôn ngữ nhân tạo (Gọi chung là giá trị ngôn ngữ). Một cách tổng quát, biến ngôn ngữ được đặc trưng bởi bộ 6 (X, T, H, U, G, M). Trong đó: X: Tên biến ngôn ngữ, chẳng hạn như Tuổi. T: Tập các giá trị của biến ngôn ngữ X , chẳng hạn như trẻ, trung niên, già, khá trẻ.... H: Tập các gia tử, chẳng hạn như khá, hơi, rất... U: Tập cơ sở của biến X.. G: Tập các qui tắc sản sinh ra các phần tử của X. M: Tập các qui tắc ngữ nghĩa gán cho mỗi giá trị ngôn ngữ của biến X một ý nghĩa là tập mờ trên U. 3. XÂY DỰNG HÀM XẤP XỈ GIỮA 2 TẬP MỜ DỰA TRÊN SỐ MỜ HÌNH THANG Xét lược dồ quan hệ R=(A1,.....An, m) Đối với thuộc tính Ai là rõ thì D(Ai)=U(Ai) Đối với thuộc tính Ai là thuộc tính mờ thì D(Ai)=U(Ai) È LV(Ai) È P(Ai) È I(Ai) Ở đây: U(Ai): Là miền giá trị cơ sở, LV(Ai): Tập các giá trị ngôn ngữ của biến ngôn ngữ Ai, P(Ai): Tập các tập mờ biểu diễn dưới dạng số mờ hình thang, I(Ai): Tập các tập mờ biểu diễn dưới dạng số mờ dạng khoảng. Cho 2 tập mờ f1=( a1, b1, c1, d1) a1£ b1£ c1£ d1 f2=( a2, b2, c2, d2) a2£ b2£ c2£ d2 Gọi SP(f1q f2) là hàm xấp xỉ giữa 2 tập mờ f1 và f2 theo phép toán q, trong đó q = {=,,=, ¹ }. Chúng ta sẽ xây dựng hàm SP(f1q f2) sao cho khi f1 và f2 gần nhau thì SP(f1q f2) ->1 khi q là phép "=", khi f1 và f2 xa nhau thì SP(f1q f2) ->0 khi q là phép "=". Gọi Sf1 và Sf2 là biểu diễn số mờ hình thang tương ứng của 2 tập mờ f1 và f2. 3.1. Nếu q là phép "=" Trường hợp 1: Nếu Sf1 ÇSf2= Æ thì SP(f1q f2)=0 Trường hợp 2: Nếu Sf1Í Sf2 hoặc Sf2Í Sf1 thì SP(f1q f2)=1 Trường hợp 3: Nếu f1ÎP(A) và f2ÎU(A) hoặc f1ÎU(A) và f2ÎP(A), khi đó giá trị hàm SP(f1q f2) chính là giao điểm I của Sf1 và Sf2. Trường hợp 4: Nếu f1ÎP(A) và f2ÎP(A) nhưng Sf1ÇSf2¹ Æ và f1Í f2 và f2Í f1 , khi đó hàm SP được xây dựng như sau: 3.2. Nếu q là phép so sánh "¹" Ta có SP(f1¹ f2)=1-SP(f1=f2) 3.3. Nếu q là phép so sánh "³" SP(f1 ³ f2) =0 khi Sf1 Ç Sf2 = Æ và d1< a2 SP(f1 ³ f2) =1 khi a1 ³ a2, b1 ³ b2, c1 ³ c2, d1 ³ d2 và một số trường hợp như trong [2 ]. 3.4. Nếu q là phép so sánh "£" Ta có SP(f1£ f2) ó SP(f2³f1). Vì vậy chỉ cần hoán đổi 2 tập mờ f1 và f2. 3.5. Nếu q là phép so sánh "<" Ta có SP(f1<f2)=1-SP(f1³f2) 3.6. Nếu q là phép so sánh ">" Ta có SP(f1> f2) ó SP(f2<f1). Vì vậy chỉ cần hoán đổi 2 tập mờ f1 và f2. 4. CÁC PHÉP TOÁN QUAN HỆ MỜ 4.1. Phép chọn mờ (Fuzzy selection) Cho R={A1,A2,...,An, m}, fr là quan hệ mờ trên R AÎR, cÎ D(A). Phép chọn mờ Fs được định nghĩa như sau: Fs Aqc( fr )={ (t,mfr(t)) Ù SP(t[A]q c) | (t,mfr(t))Îfr và mfr(t)ÙSP (t[A]qc) ³e )} Trong đó e: là ngưỡng được chọn và eÎ (0,1], q Î{=, , £ ,,³, ¹}, Ù : Phép Min. 4.2. Phép chiếu mờ (Fuzzy projection) Cho quan hệ mờ fr={(t,mfr(t))} trên lược đồ quan hệ R, XÍR. Với mỗi bộ (t,mfr(t))Îfr, ký hiệu tx là tập các bộ (t1, mfr(t1))Îfr mà t1[X]=t[X]. Có nghĩa là tx={t1 | (t1,mfr(t1))Î fr và SP(t1[X]=t[X]) =1} Phép chiếu mờ của quan hệ fr trên X là một quan hệ mờ trên X È m được định nghĩa như sau: 4.3. Phép kết nối tự nhiên mờ (Fuzzy natural join) Cho 2 quan hệ fr1= (t1,mfr1(t1)) và fr2=(t2,mfr2(t2)) trên R1, R2, AÎR1, BÎR2, R1ÇR2=R3, R1ÈR2=R. a. Nếu R3¹Æ ta định nghĩa phép nối tự nhiên mờ như sau: FNJ º fr1 43fr2={(t, mfr1(t1)Ùmfr2(t2) ÙSP (t1[C],t2[C])) ³ e | $(t1,mfr1(t1))Îfr1 và (t2,mfr2(t2))Îfr2 mà t[A]=t1[A] và t[B]=t2[B]và t[C]=t1[C]=t2[C]} Trong đó fr1 xác định trên AC và fr2 xác định trên CB và A Ç B Ç C=Æ b. Nếu R3=Æ thì ta có phép nối tự nhiên mờ sẽ thành tích Descarts mờ. 4.4. Phép kết nối mờ q ( q Fuzzy join) Trong trường hợp q ={, £, ³, ¹} thì phép kết nối tự nhiên sẽ thành phép kết nối mờ q. Phép kết nối mờ q của 2 quan hệ mờ fr1 và fr2 trên 2 thuộc tính A và B được định nghĩa như sau: fqJ º fr143fr2 ={(t,mfr1(t1) Ù mfr2(t2) Ù SP(t1[A] q t2[B])) | t[R1]=t1, t[R2]=t2, (t1,mfr1(t1))Îfr1, (t2,mfr2(t2))Îfr2, mfr1(t1) Ù mfr2(t2) Ù SP (t1[A]q t2[B])³e} Ở đây quan hệ fqJ xác định trên R=R1ÈR2 và R1ÇR2=Æ. 5. PHỤ THUỘC HÀM MỜ 5.1. Định nghĩa phụ thuộc hàm mờ Cho lược đồ quan hệ mờ R xác định trên tập hữu hạn các thuộc tính W. X,YÍW, fr là quan hệ mờ trên R. Ta nói X xác định hàm mờ Y hay Y phụ thuộc hàm mờ vào X trong fr, ký hiệu X~>Y: Nếu với mọi bộ t1, t2 trong fr mà giá trị của chúng xấp xỉ bằng nhau trên X thì cũng xấp xỉ bằng nhau trên Y. Có nghĩa là X~>YÛ (" t1, t2Î fr) (SP(t1[X]=t2[X])»a) Þ SP(t1[Y]=t2[Y])»a (aÎ(0,1]). 5.2. Ví dụ Cho quan hệ mờ Banhang được mô tả như sau: Tenhang Ngayban Soluong Loinhuan Makhach m Máy tính 20/10/02 20 khoảng 200 K01 0.5 Máy in 15/10/01 Nhiều 300 K02 0.75 Máy chiếu 02/02/01 khoảng 30 khá nhiều K03 0.7 Máy tính 01/01/99 [12,14,16,18] khá ít K04 0.45 Máy in 03/03/98 50 rất nhiều K05 1.0 Máy quét 05/05/99 10 [10,12,14,16] K06 0.2 Máy tính 04/06/99 khá nhiều khoảng 250 K07 0.9 Trong quan hệ mờ Banhang ta có phụ thuộc hàm mờ soluong ~> Loinhuan. Trong trường hợp ứng dụng cụ thể thì người ta có thể chọn ngưỡng a Î(0,1] tùy theo từng trường hợp cụ thể. 6. KẾT LUẬN Một trong những vấn đề rất quan trọng để xây dựng các phép toán quan hệ trên cơ sở dữ liệu mờ và phụ thuộc hàm mờ là làm thế nào để so sánh giữa 2 giá trị mờ với nhau theo ngữ nghĩa nào đó. Vì vậy bài báo này đã tập trung nghiên cứu và giải quyết được một số vấn đề cơ bản sau: Hệ thống các khái niệm như lược đồ quan hệ mờ, quan hệ mờ, biến ngôn ngữ. Đề xuất cách xây dựng hàm xấp xỉ SP giữa 2 tập mờ dựa trên số mờ hình thang, đây là vấn đề rất quan trọng, chúng tôi đã mở rộng các kết quả nghiên cứu trong [2]. Xây dựng một số phép toán quan hệ trên mô hình cơ sở dữ liệu mờ. Đề xuất định nghĩa phụ thuộc hàm mờ với ngữ nghĩa mới. TÀI LIỆU THAM KHẢO Lê Tiến Vương, Nhập môn cơ sở dữ liệu, NXB khoa học kỹ thuật. Nguyễn Văn Phác, Mô hình cơ sở dữ liệu quan hệ mờ, Luận văn Thạc sỹ, Trường Đại học Khoa học Tự nhiên Hà Nội (2001). Trương Đức Hùng, Một số vấn đề về cơ sở dữ liệu với thông tin không đầy đủ và lập luận xấp xỉ trong xử lý câu hỏi. Luận án Phó Tiến sĩ, trường Đại học Bách Khoa Hà Nội (1996). Nguyễn Cát Hồ, Cơ sở dữ liệu với thông tin không đầy đủ, Bài giảng trường thu về "Hệ mờ và ứng dụng", Hà Nội (2001) Cubero JC. Vila M.A, A new definition of fuzzy functional dependency in fuzzy relational databases, International journal of intelligent System 9 (1994) 441-448 H.Thuan, L. T. Vuong, A relational databases extended by application of fuzzy set theory and linguistic variables, computer and Artifical Intelligence 8 (2) (1989) 153-168. Wei-Yi-Liu, A relational data model with fuzzy inheritance dependencies, fuzzy sets and systems 89 (1997) 205-213. P.Buckles, E.Petry, A fuzzy Representation of data for Relational databases, fuzzy sets and systems 7 (1982) 213-226. SK.De, R. Biswas and A.R.Roy, On extended fuzzy relational database model with proximity relations, fuzzy sets and systems 117 (2001) 195-201. SOME FUZZY RELATIONAL OPERATORS AND FUZZY FUNCTIONAL DEPENDENCY BASED ON TRAPEZOIDAL FUZZY NUMBER Nguyen Cong Hao College of Sciences, Hue University SUMMARY In this paper, we introduced a new approach for building fuzzy relational operators and fuzzy functional dependency. This approach is building proximity function between two fuzzy sets based on trapezoidal fuzzy number. Then, putting forward a new definition of fuzzy functional dependency with new semantic. Last, we have given examples for description about fuzzy functional dependency.