Mở rộng cơ sở đối tượng xác suất với thuộc tính và phương thức lớp có giá trị mờ không chắc chắn

TAÏP CHÍ ÑAÏI HOÏC SAØI GOØN Soá 10 - Thaùng 6/2012<br /> <br /> <br /> MỞ RỘNG CƠ SỞ ĐỐI TƯỢNG XÁC SUẤT VỚI THUỘC TÍNH<br /> VÀ PHƯƠNG THỨC LỚP CÓ GIÁ TRỊ MỜ KHÔNG CHẮC CHẮN<br /> <br /> LÊ NGỌC HƯNG (*)<br /> NGUYỄN HOÀ (**)<br /> VÕ XUÂN BẰNG (***)<br /> <br /> TÓM TẮT<br /> Bài báo giới thiệu một mô hình cơ sở đối tượng xác suất mờ là mở rộng mô hình cơ sở<br /> đối tượng xác suất của Eiter và cộng sự với hai đặc tính chính: (1) các giá trị không chắc<br /> chắn và không chính xác của một thuộc tính lớp (class attribute) được biểu diễn bởi một<br /> khoảng phân bố xác suất trên một tập các giá trị tập mờ; (2) các phương thức lớp (class<br /> method) với các đối số có giá trị không chắc chắn và không chính xác được tích hợp một<br /> cách hình thức vào mô hình mới. Một diễn dịch xác suất của các quan hệ trên các giá trị<br /> tập mờ và một đại số các bộ ba xác suất mờ được đề nghị để tính toán xác suất của cá c<br /> quan hệ tập mờ và các giá trị của các tính chất đối tượng. Sau đó, lược đồ và thể hiện của<br /> cơ sở đối tượng xác suất mờ được nghiên cứu và định nghĩa một cách hình thức để hỗ trợ<br /> truy vấn thông tin không chắc chắn, khômg chính xác trên FPOB.<br /> Từ khoá: Cơ sở đối tượng xác suất, cơ sở đối tượng xác suất mờ, tập mờ, truy vấn,<br /> diễn dịch xác suất.<br /> <br /> ABSTRACT<br /> This article introduces a fuzzy and probabilistic object base model (FPOB) that extends<br /> the Eiter et al.’s probabilistic object base model (POB) with two key features: (1) uncertain<br /> and imprecise values of a class attribute are represented as probability distributions on a<br /> set of fuzzy set values; (2) class methods with uncertain and imprecise input and output<br /> arguments are formally integrated into the new model. A probabilistic interpretation of<br /> relations on fuzzy set values and a fuzzy probabilistic triple algebra are proposed to<br /> compute probability degrees of fuzzy set relations and values of object properties. Fuzzy-<br /> probabilistic object base schemas and instances, then, are formally researched and defined<br /> to support queries with the imprecise and uncertain information on FPOB.<br /> Keywords: Probabilistic object base, Fuzzy and probabilistic object base, fuzzy set and<br /> query.<br /> <br /> 1. GIỚI THIỆU (*) (**) (***) hướng đối tượng truyền thống không biểu<br /> Thực tế đã cho thấy hướng đối tượng diễn và xử lí được thông tin không chắc<br /> là một phương pháp hiệ u quả để mô hình chắn và không chính xác c ủa các đối tượng<br /> hoá, thiết kế và hiện thực các hệ thống. trong thực tế. Điều này đã đòi hỏi và thúc<br /> Tuy nhiên, mô hình cơ sở dữ liệu (CSDL) đẩy việc nghiên cứu và phát triển các mô<br /> hình CSDL hướng đối tượng xác suất và<br /> (*)<br /> ThS, Trường Đại học Sài Gòn mờ. Tuy nhiên cho đến nay ít có mô hình<br /> (**)<br /> TS, Trường Đại học Sài Gòn<br /> (***)<br /> ThS.GVC, Trường Đại học Giao thông Vận tải kết hợp được cả hai yếu tố không chắc<br /> (Cơ sở 2) chắn và không chính xác trên một nền tả ng<br /> MỞ RỘNG CƠ SỞ ĐỐI TƯỢNG XÁC SUẤT VỚI THUỘC TÍNH VÀ PHƯƠNG THỨC LỚP …<br /> <br /> <br /> lí thuyết chặt chẽ. Hơn nữa, thật sự không không chính xác được tích hợp một cách<br /> có mô hình nào có thể biểu diễn và xử lí hình thức vào mô hình mới .<br /> hết mọi khía cạnh không chắc chắn và Cơ sở toán học để phát triển FPOB<br /> không chính xác về thông tin trong thế giới được trình bày trong Phần 2, lược đồ và thể<br /> thực ([1], [2], [5]). Vì vậy, các mô hình hiện FPOB được giới thiệu trong Phần 3.<br /> CSDL xác suất và mờ vẫn được tiếp tục Phần 4 trình bày về truy vấn trên FPOB và<br /> nghiên cứu để đáp ứng các mục tiêu ứng cuối cùng, Phần 5 là một số kết luận và<br /> dụng khác nhau ([3], [6], [7]). hướng nghiên cứu trong tương lai.<br /> Năm 2001, Eiter và cộng sự đã giới 2. CƠ BẢN VỀ XÁC SUẤT VÀ T ẬP MỜ<br /> thiệu một mô hình cơ sở đối tượng xác suất Phần này giới thiệu cơ sở toán để xây<br /> ([4]) gọi là POB (Probabilistic Object dựng FPOB. Các chiến lược kết hợp các<br /> Base). Mô hình POB đư ợc xây dựng dựa khoảng xác suất đã được giới thiệu trong<br /> trên cơ sở toán học, nhất quán với mô hình POB. Chúng tôi đề xuất diễn dịch xác suất<br /> cơ sở dữ liệu hướng đối tượng truyền các quan hệ trên các tập mờ, các bộ ba xác<br /> thống, có khả năng biểu diễn và truy vấn suất mờ và đại số trên các bộ ba xác suất m ờ.<br /> thông tin không chắc chắn về các đối tượng 2.1. Các chiến lược kết hợp các<br /> trong thế giới thực. Tuy nhiên, thiếu sót khoảng xác suất<br /> chính của mô hình này là chưa cho phép Cho hai sự kiện e1 và e2 với các xác<br /> biểu diễn các giá trị thuộc tính không chính suất tương ứng trong các khoảng [ L1, U1]<br /> xác và các phương thức của một lớp. và [L2, U2]. Khi đó các khoảng xác suất<br /> Chúng tôi giới thiệu một mở rộng mô biểu diễn cho các sự kiện hội e1 ∧ e2, tuyển<br /> hình POB thành mô hình cơ sở đối tượng e1∨ e2, hiệu e1 ∧ ¬e2 của hai sự kiện e1 và<br /> xác suất mờ FPOB (Fuzzy Probabilistic e2 có thể được tính toán bởi các chiến lược<br /> Object Base) với hai đặc tính chính: (1) các kết hợp xác suất (probabilistic combination<br /> giá trị không chắc chắn và không chính xác strategy) như trong [4]. Bảng 2.1 là một ví<br /> của một thuộc tính lớp (class attribute) dụ về các chiến lược kết hợp xác suất,<br /> đư ợc biểu diễn bởi một khoảng phân bố trong đó ⊗, ⊕ và ⊖ tương ứng biểu thị các<br /> xác suất trên một tập các giá trị tập mờ; (2) phép toán hội, tuyển và trừ.<br /> các phương thức lớp (class method) với<br /> các đối số có giá trị không chắc chắn và<br /> Bảng 2.1. Các ví dụ về các chiến lược kết hợp xác suất<br /> Chiến lược Phép toán<br /> Bỏ qua (Ignorance) ([L1, U1] ⊗ig[L2, U2]) ≡ [max(0, L1 + L2 – 1), min(U1, U2)]<br /> ([L1, U1] ⊕ig[L2, U2]) ≡ [max(L1, L2 ), min(1, U1 + U2)]<br /> ([L1, U1] ⊖ig[L2, U2]) ≡ [max(0, L1 – U2 ), min(U1,1– L2)]<br /> Độc lập ([L1, U1] ⊗in[L2, U2]) ≡ [L1 . L2, U1 . U2]<br /> (Independence) ([L1, U1] ⊕in[L2, U2]) ≡ [L1 + L2 – (L1 . L2), U1 + U2 – (U1 . U2)]<br /> ([L1, U1] ⊖in[L2, U2]) ≡ [L1 . (1 – U2), U1 . (1– L2)]<br /> Loại trừ nhau ([L1, U1] ⊗me[L2, U2]) ≡ [0, 0]<br /> (Mutual Exclusion) ([L1, U1] ⊕me[L2, U2]) ≡ [min(1, L1 + L2), min(1, U1 + U2)]<br /> ([L1, U1] ⊖me[L2, U2]) ≡ [L1, min(U1, 1 – L2)]<br /> MỞ RỘNG CƠ SỞ ĐỐI TƯỢNG XÁC SUẤT VỚI THUỘC TÍNH VÀ PHƯƠNG THỨC LỚP …<br /> <br /> <br /> 2.2. Diễn dịch xác suất của các quan Định nghĩa 2.3.2 Cho U = {〈V, , 〉|<br /> hệ trên tập mờ V ⊆ U} là một tập các bộ ba xác suất mờ<br /> Diễn dịch xác suất các quan hệ hai khác rỗng trên tập U khác rỗng. Nếu A =<br /> ngôi trên các tập mờ (probabilistic (U, o1, …, on) là một đại số với các phép<br /> interpretation of binary relations on fuzzy toán o1, …, on trên U, thì A = (U, o1, …,<br /> sets) là cơ sở để tính toán xác suất của các on) là một đại số, được gọi là đại số các bộ<br /> quan hệ giữa các giá trị của các đối tượng ba xác suất mờ (fuzzy probabilistic triple<br /> được biểu diễn bởi các tập mờ trong algebra) trên U, với các phép toán o1, …,<br /> FPOB. Dựa trên cơ sở phép gán khối (mass on trên A được suy dẫn từ A như sau:<br /> assignment) trong [1], chúng tôi đề xuất<br /> oj(〈V1, 1, 1〉, 〈V2, 2, 2〉,… ,〈Vmj, mj,<br /> các định nghĩa diễn dịch xác suất của các<br /> quan hệ hai ngôi trên các tập mờ như sau: mj〉) = 〈V, , 〉, trong đó V = {v = oj(v1,<br /> Định nghĩa 2.2.1 Giả sử A, B là các v2,…,vmj) | vi∈Vi, i = 1,…, mj}, mj là số đối<br /> tập mờ tương ứng trên các miền U và V,  số của oj và<br /> là một quan hệ hai ngôi từ {=, ≤, 20,000 ⊗ x.time → medium)[0.3, 0.5].<br /> 2. x. θ v, trong đó x ∈ X,  là một biểu Định nghĩa 4.4 Giả sử τ = [P1: τ1,…,<br /> thức đường đi, θ là một quan hệ hai ngôi Pk: τk] là một kiểu bộ, diễn dịch<br /> (interpretation) của một biểu thức đường đi<br /> thuộc {=, ≠, ≤, 20,000)[0.7, 1.0] ∧ (x.time →<br /> Trên cơ sở các khái niệm đã được giới<br /> medium)[0.3, 1.0].<br /> thiệu, sự thoả mãn các điều kiện chọn mờ<br /> và phép chọn trong FPOB được định nghĩa Vì probS,I,o3(x.volume(x.length,<br /> bằng cách mở rộng các định nghĩa tương x.width, x.height) > 20,000) = [0.8, 1.0]<br /> MỞ RỘNG CƠ SỞ ĐỐI TƯỢNG XÁC SUẤT VỚI THUỘC TÍNH VÀ PHƯƠNG THỨC LỚP …<br /> <br /> <br /> ⊆ [0.7, 1.0] và probS,I,o3(x.time → probS,I,o⊨ φ2 nên o ∈ π2(c) vì vậy<br /> medium) = [0.36, 0.66] ⊆ [0.3, 1.0] nên probS,I2,o⊨φ1 ⇔ probS,I,o⊨ φ1. Hơn nữa, với<br /> đối tượng o3 được chọn. Không còn đối<br /> mọi c ∈ C, ta có:<br /> tượng nào khác trong I thoả điều kiện chọn<br /> đã cho. ν1,2(c) = ν2(c) | π1,2(c)<br /> Tương tự như phép chọn trong POB, = ν(c) | π2(c) | π1,2(c)<br /> phép chọn trong FPOB cũng có tính chất là = ν(c) | π1,2(c) (vì π1,2(c) ⊆ π2(c))<br /> không phụ thuộc vào thứ tự các điều kiện = ν(c) | π1∧2(c) (vì π1,2(c) = π1∧2(c)<br /> chọn. Định lí sau đây là một mở rộng của theo chứng minh trên)<br /> định lí về tính chất của phép chọn trong = ν1∧2(c) (Định nghĩa 47).<br /> POB đối với các điều kiện chọn mờ trong Từ đó hệ thức σφ1(σφ2(I)) = σφ1∧ φ2(I)<br /> FPOB. được chứng minh. Hệ thức σφ2(σφ1(I)) =<br /> Định lí 4.1 Giả sử I = (, ) là một thể<br /> σφ1∧ φ2(I) được chứng minh tương tự. Từ đó<br /> hiện FPOB trên lược đồ cơ sở đối tượng<br /> suy ra hệ thức σφ1(σφ2(I)) = σφ2(σφ1(I)) và<br /> xác suất mờ S = (C, , , me, , f). Gọi<br /> 1 và 2 là hai điều kiện chọn mờ, khi đó: do đó σφ1(σφ2(I)) = σφ2(σφ1(I)) = σφ1∧φ2(I).<br /> 5. KẾT LUẬN<br /> Trên đây, chúng tôi đã giới thiệu mô<br /> σφ1(σφ2(I)) = σφ2(σφ1(I)) = σφ1∧φ2(I) (1)<br /> hình cơ sở đối tượng xác suất mờ FPOB là<br /> mở rộng mô hình POB trong [4] với tập<br /> Với giả thiết trong phép chọn σφ1∧φ2(I) mờ và phương thức lớp đối tượng. Mô hình<br /> các điều kiện chọn mờ φ1 và φ2 là có cùng FPOB đã khắc phục được các hạn chế của<br /> một biến đối tượng. mô hình POB và cho phép không chỉ truy<br /> Chứng minh Kí hiệu I2 = (π2, ν2) = vấn thông tin không chắc chắn mà cả thông<br /> σφ2(I), I1,2 = (π1,2, ν1,2) = σφ1(σφ2(I)) và I1∧2 tin không chính xác của các đối tượng.<br /> = (π1∧2, ν1∧2) = σφ1 ∧ φ2(I). Vì φ1 ∧ φ2 ⇔ φ2 Với phép chọn được mở rộng trong<br /> FPOB, chúng tôi đã phát biểu và chứng minh<br /> ∧ φ1 (phép hội trên tập các điều kiện chọn<br /> tính không phụ thuộc vào thứ tự các điều<br /> mờ cũng như mệnh đề mờ có tính giao<br /> kiện chọn của nó như phép chọn trong POB.<br /> hoán), nên với mọi c ∈ C , ta có:<br /> Trong các bước tiếp theo, chúng tôi sẽ<br /> π1,2(c) = {o ∈ π2(c) | probS,I2,o⊨ φ1} định nghĩa các phép toán đại số khác như<br /> = {o ∈ π(c) | (probS,I,o⊨ φ2) ∧ (probS,I2,o⊨ chiếu (projection), kết (join),… và phát<br /> φ1)} triển một ngôn ngữ cho người sử dụng đầu<br /> cuối (end-user) trên FPOB, tương tự như<br /> = {o ∈ π(c) | (probS,I,o⊨ φ2) ∧ (probS,I,o⊨ OQL trong mô hình CSDL hướng đối<br /> φ1)} tượng truyền thống. Cuối cùng, chúng tôi<br /> = {o ∈ π(c) | probS,I,o⊨φ1 ∧ φ2} (Định sẽ xây dựng một hệ quản trị cho FPOB để<br /> nghĩa 4.6) biểu diễn, xử lí, và truy vấn thông tin<br /> = π1∧2(c). không chắc chắn, không chính xác trong<br /> Trong phép biến đổi trên, lưu ý rằng do thực tế.<br />  TÀI LIỆU THAM KHẢO<br /> <br /> <br /> 1. Baldwin, J.F., Lawry J.M., and Martin, T.P. (1996),A mass assignment theory of the<br /> probability of fuzzy events. Fuzzy Sets and Systems, 83 , 353-367.<br /> 2. Berzal F., Marín N., Pons O., Vila M.A. (2005), A framework to build fuzzy object-<br /> oriented capabilities over an existing database system. In Ma, Z. (Ed.): Advances in<br /> Fuzzy Object-Oriented Database: Modeling and Applications. Idea Group Publishing,<br /> 177-205.<br /> 3. Cao, T.H., and Nguyen, H. (2011), Uncertain and fuzzy object bases: a data model<br /> and. Algebraic operations. International Journal of Uncertainty, Fuzziness and<br /> Knowledge-Based Systems, 275-305.<br /> 4. Eiter T., Lu J.J., Lukasiewicz T., Subrahmanian V.S. (2001), Probabilistic object<br /> bases, ACM Transactions on database systems, 26 264-312.<br /> 5. Nguyen Cat Ho (2006), A model of relational with linguistic data of hedge algebras-<br /> based semantics. In Proceedings of the 3rd National Symposium on Research,<br /> Development and Application of Information and Communication Technology<br /> (ICTrda’06) Hanoi-Vietnam, 145-156.<br /> 6. Nguyễn Hoà và Cao Hoàng Trụ (2006), Tích hợp phương thức lớp vào mô hình cơ sở<br /> đối tượng xác suất mờ , Kỉ yếu Hội thảo Quốc gia Lần thứ 3 về Nghiên cứu, Phát triển<br /> và Ứng dụng Công nghệ Thông tin và Truyền thông (IC Trda’06) Hà Nội - Việt Nam,<br /> Nxb Khoa học và Kĩ thuật, 115 -123.<br /> 7. Nguyen, H., and Cao, T.H. (2007), Extending probabilistic object bases with<br /> uncertain applicability and imprecise values of class properties. In Proceedings of the<br /> 5th IEEE International Conference on Fuzzy Systems, London, England, 487-492.<br /> 8. Nguyễn Hoà (2008), Một mô hình cơ sở đối tượng xác suất mờ , luận án tiến sĩ, Đại<br /> học Bách khoa, Đại học Quốc gia TP.HCM.<br /> <br /> * Nhận bài ngày 15/2/2012. Sữa chữa xong 15/5/2012. Duyệt đăng 14 /6/2012.<br />