In cooperation with the Federal University of Technology in Brazil, we are happy that our PVLDB paper “Discovery of Approximate (and Exact) Denial Constraints” has been accepted. The research will be presented at VLDB 2020 in Tokyo. Find more information about the VLDB conference in 2020 here: www.vldb2020.org.
Authors: Eduardo H. M. Pena (Federal University of Technology, Brazil), Eduardo C. de Almeida (Federal University of Technology, Brazil), Felix Naumann (HPI)
Find short abstract below:
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 combines 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.