Dynamic Discovery of Fuzzy Functional Dependencies Using Partitions

Introduction

A functional dependency describes the relationship between attributes in a database relation. It states that the value of an attribute is uniquely determined by the values of some other attributes. It serves as a constraint between the attributes and is being used in the normalization process of relational database design. Therefore the discovery of functional dependencies from databases has been identified as an important technique for analyzing attribute semantics and redesign of relational schemas. It has received considerable research interest in recent years. For examples, from a database of chemical compounds, it is valuable to discover compounds that are functionally dependent on a certain structure attribute (Huhtala, Karkkainen, Porkka, & Toivonen, 1998). In addition, as a kind of data dependency, a large dataset can be losslessly decomposed into a set of smaller datasets using the discovered functional dependencies.

To find all functional dependencies from a given database relation r, we need to search for all possible dependencies and test their validity. There are essentially two approaches for searching for all possible functional dependencies: top-down searching and bottom-up searching. The top-down approach starts with the set of trivial functional dependencies and adds those functional dependencies that are satisfied by r. It can be further classified into depth-first search and level-wise (breadth-first) search. The dependencies discovery techniques proposed in Bell et al. (1995), Huhtala et al. (1998), Mannila et al. (1997), Yao et al. (2002) are top-down approach. The bottom-up approach starts with the set of all possible functional dependencies and removes those functional dependencies that are contradicted by r. The discovery techniques proposed in Flach, (1990), Flach & Savnik (1999), Mannila et al. (1997) are bottom-up approach. To test the validity of a given dependency, pair wise comparison method between any two tuples, decision-tree method and a tuple-partition method have been proposed. However, current data mining techniques of determining functional dependencies deal only with crisp databases. Although various forms of fuzzy functional dependencies have been proposed for fuzzy databases, they emphasized conceptual viewpoints, and few mining algorithms are given.

To extend functional dependency, there are many approximate dependencies proposed and defined on the crisp relational data model. For example, Haux and Eckert (1985) have extended functional dependency to probabilistic dependency. Saharia and Barron (1995) have extended functional dependency to cluster dependency. To extend functional dependency to fuzzy databases, there are different forms of fuzzy functional dependency on various types of fuzzy relational data models. For example, Raju and Majumdar (1988), Bosc et al. (1997), Chen (Chen, 1998), have defined various forms of fuzzy functional dependencies on the possibility-based fuzzy relational data model. For the similarity-based fuzzy relational data model Buckles et al. (1982), Sachar (1985), and Yazici et al. (1999) have defined a fuzzy functional dependency based on conformance. Wang et al. (2001) proposed a form of fuzzy functional dependency based on equivalence classes induced by level values on given similarity relations. Belohlavek et al. (2006) proposed a fuzzy functional dependency using fuzzy predicate logic on ranked database relations over domains with similarities. For equivalence-class-based fuzzy relational data model, Shenoi et al. (1990) defined a fuzzy functional dependency based on redundancy. These fuzzy functional dependencies are basically intended to preserve the functionality of classical functional dependency on the new fuzzy relational data models so that semantics between fuzzy attributes can be captured.