Fuzzy function dependencies in fuzzy object-oriented databases

JOURNAL OF SCIENCE OF HNUE Natural Sci., 2011, Vol. 56, No. 7, pp. 23-31 FUZZY FUNCTION DEPENDENCIES IN FUZZY OBJECT-ORIENTED DATABASES Ho Cam Ha(∗) Hanoi National University of Education Vu Duc Quang Quang Nam University (∗)E-mail: hahc@hnue.edu.vn Abstract. This paper concerns to fuzzy dependencies of attributes on fuzzy object class. Base on the possibility distribution approach, we proposes the formal definition of fuzzy functional and multivalued dependencies on object class. The dependencies in this study allows a sound and complete set of inference rules. Keywords: object-oriented database, fuzzy dependencies, fuzzy ob- ject, possibility distribution 1. Introduction Not all the elements (data) that occur in the real world are fully known or defined in a perfect way. Classical relational database models and its extension of imprecision and uncertainty do not satisfy the need of modelling complex objects with imprecision and uncertainty. So many researchers have concentrated on the development of object-oriented database models to deal with uncertain data [9]. The fuzzy object-oriented approach have recently received increasing attention. Integrity constraints play a crucial role as in traditional databases, and also in fuzzy object- orientation. These constraints are used to define the semantics and guidelines for database design. Based on the possibility distribution approach and resemblance relationship we introduce a measurement of semantic equivalence of fuzzy data. In this paper, we propose formal definitions of dependencies in the fuzzy class. The formal definition fuzzy functional and multivalued dependencies in this study allows a sound and complete set of inference rules. It is also shown that, such extended dependencies, the classical dependency is a special case. 23 Ho Cam Ha and Vu Duc Quang The remainder of the paper is organized as follows: In the next section we recall basic notions from fuzzy set and resemblance relationships. Then we define fuzzy functional dependency, fuzzy multi-valued dependency on object class. These formal definitions of dependencies allows a sound and complete set of inference rules. Finally, we present some concluding remarks. 2. Content 2.1. Representations Fuzzy set and Possibility Distribution As pointed out [10], fuzzy data is originally described as fuzzy set. Let U be a universe of discourse, a fuzzy set F is defined in U by a membership function. The membership function µF : U → [0, 1] assigns to each element u of U a number, in the close interval [0,1], that characterizes the degree of membership of u in F . A fuzzy set F can be written as: F = {µF (u1)/u1, µF (u2)/u2, ..., µF (un)/un} (U is a finite set) or F = ∫ u∈U µF (u) u (U is a infinite set). When µF (u) is viewed to be a measure of the possibility that a variable X has the value u in this approach, where X takes values in U , a fuzzy value is described by a possibility distribution πX . πX = {πX(u1)/u1, πX(u2)/u2, ..., πX(un)/un}, where πX(ui), ui ∈ U denotes the possibility that ui is true. Let πX , F be the possibility distribution representation and the fuzzy set representation for a fuzzy value, respectively. It is apparent that πX = F is true. 2.2. Semantic relationship between fuzzy data Let U = u1, u2, , un be the universe of discourse, A is a variable, a fuzzy data of A on U based on possibility distribution is denoted as follows: πA = {πA(u1)/u1, πA(u2)/u2, ..., πA(un)/un}, ui ∈ U, πA(ui) ∈ [0, 1]. Definition 2.1 (11). For fuzzy data, its semantics correspond to an area in space (U× [0, 1]), where the universe of discourse is its X-axis and possibility is its Y -axis. The semantics of a fuzzy data πA expressed by possibility distribution corre- sponds to an area in space, the so called semantic space, denoted by SS(πA) (see Figure 1). The semantic relationship between two fuzzy data can be described by the relationship between their semantic spaces. Let SS(πA) and SS(πB) be semantic 24 Fuzzy function dependencies in fuzzy object-oriented databases Figure 1. Semantic space of fuzzy data. spaces of two fuzzy data πA and πB, respectively. If SS(πA) ⊇ SS(πB), πA seman- tically includes πB or πB is semantically included by πA. If SS(πA) ⊇ SS(πB) and SS(πA) ⊆ SS(πB), πA, πB are semantically equivalent to each other. We employ semantic inclusion degree to measure the semantic relationship of fuzzy data. Definition 2.2 (11). Let πA and πB be two fuzzy data, and their semantic spaces be SS(πA) and SS(πB), respectively. Let SID (πA, πB) denotes the degree that πA semantically includes πB. Then SID(πA, πB) = (SS(πA) ∩ SS(πB))/SS(πB). For two fuzzy data πA and πB, the meaning of SID(πA, πB) is the percentage of the semantic space of πB which is wholly included in the semantic space of πA. Definition 2.3 (11). Let πA and πB be two fuzzy data, SE(πA, πB) denote the degree that πA and πB are equivalent to each other, then SE(πA, πB) = min(SID(πA, πB), SID(πB, πA)). 2.3. Evaluation of Semantic Measures Definition 2.4 (11). Let U = {u1, u2, , un} be the universe of discourse. Let πA v πB be two fuzzy datas on U based on possibility distribution and πA(ui), ui ∈ U denote the possibility that ui is true. SID(πA, πA) is then defined SID(πA, πB) = n∑ i=1 min ui∈U (πB(ui), πA(ui))/ n∑ i=1 πB(ui). Definition 2.5 (11). Let U = u1, u2, , un be the universe of discourse. Let πA v πB be two fuzzy data on U based on possibility distribution and πA(ui), ui ∈ U denote 25 Ho Cam Ha and Vu Duc Quang the possibility that ui is true. Let Res be a resemblance relation on domain U , α for 0 ≤ α ≤ 1 be a threshold corresponding to Res. SIDα(πA, πB) is then defined by SIDα(πA, πB) = n∑ i=1 min ui,uj∈U ;Res(ui,uj)≥α (πB(ui), πA(uj))/ n∑ i=1 πB(ui). In there, resemblance relationship Res on domain U is mapping U×U → [0, 1] which satisfies two terms as follows: (1) ∀u ∈ U,Res(u, u) = 1; (2) ∀ui, uj ∈ U,Res(ui, uj) = Res(uj, ui). 2.4. Fuzzy functional dependencies and fuzzy multi-valued dependencies Assumption: OID is a set of object-identities. C is a set of classes. A is a set of names of attributes. nil is used to denote a special constant, that presents uncertainty value. dom includes all crisp atom values and fuzzy values. Fuzzy Object: A fuzzy object is a pair of (id, v), in there, id is the object identifier taken from the OID, v is a fuzzy (or clearly) value on the OID. The OID values is signed as val(OID) and defined as follows [1]: (a) an element of dom, an element of IOD and the nil values on OID (b) if v1, v2, , vn are values and A1, A2, ..., An are names of attributes, the tuple value is (A1 : v1, A2 : v2, ..., An : vn) and the set value is {v1, v2, , vn} on OID. Fuzzy class [11]: The objects having the same properties are gathered into classes. A class is fuzzy because of the following several reasons. First, some objects are fuzzy ones, which have similar properties. A class defined by these objects may be fuzzy. These objects belong to the class with membership degree of [0,1]. Second, when a class is defined, the domain of an attribute may be fuzzy and a fuzzy class is formed. Third, the subclass produced by a fuzzy class by means of specialization and the superclass produced by some classes (in which there is at least one class which is fuzzy) by means of generalization are also fuzzy. Types(C) is defined as follows: (1) Base type: integer, string, bool, float and the fuzzy type is generated base on the base types. 26 Fuzzy function dependencies in fuzzy object-oriented databases (2) Class name in C is fuzzy (clearly) type object type. (3) If T is a fuzzy type, set(T) is fuzzy (clearly) set type. (4) If T1, T2, , Tn are types and A1, A2, ..., An are names of attributes in A, the tuple type is (A1 : T1, A2 : T2, ..., An : Tn). 2.4.1. Fuzzy Functional Dependencies Definition 2.6. Let c be a class. Suppose that U is set of attributes of c and X, Y ⊆ U . A fuzzy functional dependency X fc−→ Y is said to hold in class c if for every pairs of objects O1, O2 of class c, we have SE(O1.X,O2.X) ≤ SE(O1.Y, O2.Y ). Note that: The equivalent measurement of semantics is defined as follows: (i) If X = A1, A2, ..., Ak, then SE(O1.X,O2.X) =min(SE(O1.A1, O2.A1), SE(O1.A2, O2.A2), ..., SE(O1.Ak, O2.Ak)). (ii) If Ai refers to class ci(Ui), type of Ai is object type, then SE(O1.X,O2.X) = 1 when O1.X ≡ O2.X , E(O1.Ai, O2.Ai) = SE(O1.Ai.Ui, O2.Ai.Ui); otherwise. (iii) If type of Ai is set type, O1.Ai = {s1, s2, s3, ..., si, ..., sn}, O2.A = {s1, s2, s3, ..., si, ..., sm}, then SE(O1.Ai, O2.Ai) = min(min(maxi(SID(sj, si) i=1..n,j=1..m ),min(maxj(SID(si, sj) j=1..m,i=1..n )). (iv) If type of A is tuple type, O1.Ai = (v1, v2, v3, ..., vi, ..., vn), O2.Ai = {w1, w2, w3, ..., wj, ..., wn}, then SE(O1.Ai, O2.Ai) = min(SE(vi, wj i,j=1..n )). The equivalent measurement of semantic on Y and on X is defined similarly. Example 1: Given c(U), where c is class c and U is set of attributes of c.X, Y ⊆ U , Res(X) and Res(Y ) are similarity related on X and Y , with α1 = 0.9, α2 = 0.95 are threshold of Res(X) and Res(Y ) respectively. Res(X) a b c d e a 1.0 0.2 0.3 0.2 0.4 b 1.0 0.92 0.4 0.1 c 1.0 0.1 0.3 d 1.0 0.2 e 1.0 Res(Y) f g h i j f 1.0 0.3 0.2 0.96 0.2 g 1.0 0.4 0.2 0.3 h 1.0 0.3 0.1 i 1.0 0.4 j 1.0 27 Ho Cam Ha and Vu Duc Quang Instances of object class is shown as follows: Id X Y ... Id1 {0.7/a, 0.4/b, 0.5/d} {0.9/f, 0.6/g, 1.0/h} ... Id2 {0.5/a, 0.4/c, 0.8/d} {0.6/g, 0.9/h, 0.9/i} ... Id3 {0.3/d, 0.8/e} {0.6/h, 0.4/i, 0.1/j} ... For every objects O1, O2 of c, we have: SE(O1.X,O2.X) = min(SID(O1.X,O2.X), SID(O2.X,O1.X)) = min(0.824, 0.875) = 0.824 v SE(O1.Y, O2.Y ) = min(SID(O1.Y, O2.Y ), SID(O2.Y, O1.Y )) = min(1.0, 0.96) = 0.96, It is easy to realize that SE(O1.Y, O2.Y ) > SE(O1.X,O2.X) from the definition of fuzzy functional dependency X fc−→ Y . Lemma 2.1. Let c(U) is a class with set of attributes U . Suppose X ⊆ U,A ∈ U . If X fc−→ A holds and A: tuple(A1 : T1, A2 : T2, ..., Ak : Tk) then X fc−→ Ai, i = 1, 2, ..., k. Proof. X fc−→ A implies that SE(O1.A, O2.A) ≥ SE(O1.X,O2.X), for every O1, O2 in fuzzy object class. A1, A2, ..., Ak takes the place of A, so that SE(O1.A, O2.A) = min(SE(O1.Ai, O2.Ai)), i = 1..k. Obviously SE(O1.Ai, O2.Ai) ≥ SE(O1.X,O2.X), i = 1..k. Thus, according to definition of fuzzy functional dependency, we have X fc−→ Ai, i = 1, 2, ..., k. Theorem 2.1. The functional dependency in relational database is a special case of the fuzzy functional dependency in object oriented database (given above). Proof. Suppose X → Y holds in relation r(U), X, Y ⊆ U . It means: for every pairs of tuple t1, t2 ∈ r, if t1[X ] = t2[X ] then t1[Y ] = t2[Y ]. If consider U as the set of attributes of class c, for every pairs object of c(O1, O2), we have SE(O1.X,O2.X) = 1, SE(O1.Y, O2.Y ) = 1. Thus, SE(O1.Y, O2.Y ) > SE(O1.X,O2.Y ) > 1. It means X fc−→ Y holds. 2.4.2. Decomposing tuple type attribute to fuzzy function dependencies The group of some attributes in a class into the other one which has tuple type. This can lead to binding semantics or fuzzy functional dependencies between attributes are not preserved. In this case, we need to decompose these attributes to preserve the semantic constraints. 28 Fuzzy function dependencies in fuzzy object-oriented databases Suppose A∗: tuple(Xi : Ti), i = 1, 2, 3, ..., k(k > 1). If Xi takes the place of A∗ and X fc−→ Y holds, where X = k∪ i=1 X ′i, X ′ i ⊆ Xi, then A∗ can be decomposed into attributes as follows: Bi : tuple(Xi\X ′i : TXi\X′i), i = 1, 2, 3, ..., k − 1. Bk : tuple(Xk\X ′k\Y : TXk\X′k\Y ), i = 1, 2, 3, ..., k − 1. Ci : tuple(X ′ i : TX′i), i = 1, 2, 3, ..., k. D : tuple(Y : TY ). 2.4.3. Fuzzy Multi-valued Dependencies Definition 2.7. Let c be a class. Suppose that U is set of attributes of c. Suppose also X, Y ⊆ U , Z = U\XY . A fuzzy multivalued dependency X fc→→Y is said to be held in class c if whenever O1, O2 are two objects of class c, contains object O3 so that SE(O3.X,O1.X) > SE(O1.X,O2.X) and SE(O3.Y, O1.Y ) > SE(O1.X,O2.X), SE(O3.Z, O2.Z) > SE(O1.X,O2.X) Example 2: Given class c(U), X, Y ⊆ U,Z = U\XY . Res(X), Res(Y ) and Res(Z) are three similarity relations of X , Y and Z respectively, as in Example 1. α1 = 0.9, α2 = 0.95, α3 = 0.90 are three thresholds of Res(X) and Res(Y ), Res(Z) respectively. Instances of object class is shown as follows: Id X Y Z O1 Id1 {0.4/a, 0.6/b, 0.7/d} {0.6/g, 0.9/h, 0.8/i} {0.5/a, 0.7/c, 0.4/e} O2 Id2 {0.4/c, 0.5/d, 0.2/e} {0.3/h, 0.6/i, 1.0/j} {0.2/b, 0.5/c, 0.9/e, 0.8/f} O3 Id3 {0.4/a, 0.5/b, 0.6/d} {0.6/g, 0.7/h, 0.8/f} {0.6/d, 1.0/e, 0.7/f} SE(O1.X,O2.X) = min(SID(O1.X,O2.X), SID(O2.X,O1.X)) = min(0.818, 0.529) = 0.529 SE(O1.X,O3.X) = min(SID(O1.X,O3.X), SID(O3.X,O1.X)) = min(1.0, 0.882) = 0.882 > SE(O1.X,O2.X) SE(O1.Y, O3.Y ) = min(SID(O1.Y, O3.Y ), SID(O3.Y, O1.Y )) = min(1.0, 0.913) = 0.913 > SE(O1.X,O2.X) SE(O2.Z, O3.Z) = min(SID(O2.Z, O3.Z), SID(O3.Z, O2.Z)) = min(0.913, 0.875) = 0.875 > SE(O1.X,O2.X) 29 Ho Cam Ha and Vu Duc Quang Thus, according to the definition of fuzzy multivalued dependency, X fc→→Y holds in fuzzy object class c. Theorem 2.2. The multi-valued dependency in relational database is the special case of the fuzzy multivalued dependency in object oriented database (as given above). Proof. Suppose X →→ Y holds in relation r(U). It means ∀t1, t2, t1[X ] = t2[X ], ∃t3 such that t3[X ] = t1[X ], t3[Y ] = t1[Y ], t3[Z] = t2[Z], where Z = U −XY . Consider U be as the set of attributes of class c. For every pair of objects of c(O1, O3), exits object O3 ∈ c we have SE(O3.X,O1.X) = SE(O3.Y, O1.Y ) = 1, SE(O3.Z, O2.Z) = SE(O1.X,O2.X) = 1. Obviously, SE(O3.X,O1.X) > SE(O1.X,O2.X) > 1, SE(O3.Y, O1.Y ) > SE(O1.X,O2.X) > 1 and SE(O3.Z, O2.Z) > SE(O1.X,O2.X) > 1. Thus, X fc→→Y holds. 2.4.4. The inference rules of fuzzy dependencies The inference rules of fuzzy functional dependencies: Rule 1: Reflexivity. If X ⊇ Y then X fc→Y Rule 2: Augmentation. If X fc→Y then XZ fc→Y Z Rule 3: Transitivity. If X fc→ Y and Y fc→Z then X fc→Z Rule 4: Union. If X fc→Y , X fc→Z then X fc→Y Z Rule 5: Pseudo transitivity. If X fc→Y , Y W fc→Z then XW fc→Z Rule 6: Decomposition. If X fc→Y , Z ⊆ Y thenX fc→Z The inference rules of fuzzy multivalued dependencies: Rule 7: Reflexivity. If Y ⊆ X then X fc→→Y Rule 8: Complementation. If X fc→→Y then X fc→→U −XY Rule 9: Augmentation. If X fc→→Y and Z ⊆ W then XW fc→→Y Z Rule 10: Transitivity. If X fc→→Y and Y fc→→Z then X fc→→Z − Y Rule 11: Union. If X fc→→Y and X fc→→Z then X fc→→ZY Rule 12: Pseudo transitivity. If X fc→→Y and Y W fc→→Z then XW fc→→Z − Y W Rule 13: If X fc→→Y and X fc→→Z then X fc→→Z ∩ Y . Rule 14: If X fc→→Y and X fc→→Z then X fc→→Y −Z and X fc→→Z−Y . 30 Fuzzy function dependencies in fuzzy object-oriented databases Theorem 2.3. The inference rules (rule 1- rule 14) in fuzzy class are sound and complete. We suppose that procedure of proof for the soundness and completeness of above inference rules is similar to the case of fuzzy relational database [7, 11]. 3. Conclusion When we design an object-oriented database schema, we need to eliminate data redundancy. The reason is that as a consequence of the redundancy, the integrity constraints are broken. It is the same in classical database, the fuzzy dependencies are conceptually meaningful, which are integrity constrains in fuzzy object-oriented database design. This paper describes an on going work. In order to continue, we have already begun some studies of normalization in OODB design. REFERENCES [1] A. Cami, 1998. Advanced BDMS. ACCT 5524. [2] B.Bouchon-Meunier, Ho Thuan, Dang Thanh Ha, 2007. Fuzzy logic and Appli- cations (in Vietnamese). Vietnam National University, Hanoi. [3] Catriel Beeri, Ronald Fagin, and John H. Howard, 1997. A complete axiomatiza- tion for functional and multivalued dependencies in database relations. Proceed- ings of ACM SIGMOD, pp. 47-63. [4] Gloria Bordogna, Gabriella Pasi, 2000. Recent Issuse on Fuzzy Databases. Physica-Verlag Heidelberg New York. [5] Nguyen Kim Anh, 2003. Standardizing object-oriented database (in Vietnamese). Journal of computer science and cybernetics, pp. 125-130. [6] P. J. Pratt and J. J. Adamski, 1994. Database Systems Management and Design (3rd edition). Boyd & Fraser Publishing Company, Danvers, MA, pp. 597-598. [7] Sozat M I, Yazici A, 2001. A complete axiomatization for fuzzy functional and multivalued dependencies in fuzzy database relations. Fuzzy Sets and Systems, pp.161-183. [8] Tarek Sobh, 2008. Advances in Computer and Information Sciences and Engi- neering. Springer, NewYork, pp. 300-304. [9] Z. M. Ma, 2004. Advances in Fuzzy Object-Oriented Databases: Modeling and Applications. Idea Group Publishing. [10] Zadeh, L. A., 1965. Fuzzy sets, Information & Control, pp. 338-353. [11] Zongmin Ma, 2005. Fuzzy Database Modeling with XLM. Springer, NewYork. 31