4.4 Article Proceedings Paper

Discovery of Approximate (and Exact) Denial Constraints

Journal

PROCEEDINGS OF THE VLDB ENDOWMENT
Volume 13, Issue 3, Pages 266-278

Publisher

ASSOC COMPUTING MACHINERY
DOI: 10.14778/3368289.3368293

Keywords

-

Ask authors/readers for more resources

Maintaining data consistency is known to be hard. Recent approaches have relied on integrity constraints to deal with the problem correct and complete constraints naturally work towards data consistency. State-of-the-art data cleaning frameworks have used the formalism known as denial constraint (DC) to handle a wide range of real-world constraints. Each DC expresses a relationship between predicates that indicate which combinations of attribute values are inconsistent. The design of DCs, however, must keep pace with the complexity of data and applications. The alternative to designing DCs by hand is automatically discovering DCs from data, which is computationally expensive due to the large search space of DCs. To tackle this challenging task, we present a novel algorithm to efficiently discover DCs: DCFINDER. The algorithm comhines data structures called position list indexes with techniques based on predicate selectivity to efficiently validate DC candidates. Because the available data often contain errors, DCFINDER is especially designed to discovering approximate DCs, i.e., DCs that may partially hold. Our experimental evaluation uses real and synthetic datasets and shows that DCFINDER outperforms all the existing approximate DC discovery algorithms.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.4
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available