Effective pruning for the discovery of conditional functional dependencies
Article
Article Title | Effective pruning for the discovery of conditional functional dependencies |
---|---|
ERA Journal ID | 17794 |
Article Category | Article |
Authors | Li, Jiuyong (Author), Liu, Jixue (Author), Toivonen, Hannu (Author) and Yong, Jianming (Author) |
Journal Title | The Computer Journal |
Journal Citation | 56 (3), pp. 378-392 |
Number of Pages | 15 |
Year | 2013 |
Place of Publication | Oxford, United Kingdom |
ISSN | 0010-4620 |
1460-2067 | |
Digital Object Identifier (DOI) | https://doi.org/10.1093/comjnl/bxs082 |
Web Address (URL) | http://comjnl.oxfordjournals.org/content/56/3/378 |
Abstract | Conditional functional dependencies (CFDs) have been proposed as a new type of semantic rules extended from traditional functional dependencies. They have shown great potential for detecting and repairing inconsistent data. Constant CFDs are 100% confidence association rules. The theoretical search space for the minimal set of CFDs is the set of minimal generators and their closures in data. This search space has been used in the currently most efficient constant CFD discovery algorithm. In this paper, we propose pruning criteria to further prune the theoretic search space, and design a fast algorithm for constant CFD discovery. We evaluate the proposed algorithm on a number of media to large real-world data sets. The proposed algorithm is faster than the currently most efficient constant CFD discovery algorithm, and has linear time performance in the size of a data set. |
Keywords | functional dependencies; conditional functional dependencies; association rules; closed patterns |
ANZSRC Field of Research 2020 | 460908. Information systems organisation and management |
460599. Data management and data science not elsewhere classified | |
490407. Mathematical logic, set theory, lattices and universal algebra | |
Public Notes | Copyright of Computer Journal is the property of Oxford University Press and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. |
Byline Affiliations | University of South Australia |
University of Helsinki, Finland | |
School of Information Systems | |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q18w5/effective-pruning-for-the-discovery-of-conditional-functional-dependencies
1961
total views9
total downloads2
views this month0
downloads this month