Premium
Efficient discovery of functional dependencies with degrees of satisfaction
Author(s) -
Wei Qiang,
Chen Guoqing
Publication year - 2004
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.20038
Subject(s) - functional dependency , computer science , axiom , data mining , dependency theory (database theory) , orthogonality , tuple , dependency (uml) , transitive relation , relation (database) , digraph , process (computing) , relational database , theoretical computer science , mathematics , artificial intelligence , discrete mathematics , geometry , combinatorics , operating system
Functional dependency (FD) is an important type of semantic knowledge reflecting integrity constraints in databases, and has nowadays attracted an increasing amount of research attention in data mining. Traditionally, FD is defined in the light of precise or complete data, and can hardly tolerate partial truth due to imprecise or incomplete data (such as noises, nulls, etc.) that may often exist in massive databases, or due to a very tiny insignificance of tuple differences in a huge volume of data. Based on the notion of functional dependencies with degrees of satisfaction (FDs) d , this article presents an efficient approach to discovering all satisfied (FDs) d using some important results obtained from exploration of (FDs) d properties such as extended Armstrong‐like axioms and their derivatives. In this way, many dependencies can be inferred from previously discovered ones without scanning databases, and those unsatisfied ones could be filtered out inside (rather than after) the mining process. Fuzzy relation matrix operation is used to infer transitive dependencies in the mining algorithm. Finally, the efficiency is demonstrated with data experiments. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 1089–1110, 2004.