Effective Pruning for the Discovery of Conditional Functional Dependencies

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...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2013-03, Vol.56 (3), p.378-392
Main Authors: Li, Jiuyong, Liu, Jixue, Toivonen, Hannu, Yong, Jianming
Format: Article
Language:English
Subjects:
Algorithms
Computational fluid dynamics
Computer science
Data integrity
Maintenance
Mathematical models
Pruning
Repairing
Searching
Semantics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. [PUBLICATION ABSTRACT]
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/bxs082