Incremental Detection of Denial Constraint Violations

Denial constraints (DCs) are well-known to express business rules on data. They subsume other integrity constraints (ICs), such as key constraints or functional dependencies. One can use traditional DBMS or specialized algorithms to validate such dependencies on a dataset. However, no known approach exists to detect DC violations incrementally. Data typically changes over time, and recomputing the entire violation set after every update is wasteful. Alerting data practitioners of data quality issues immediately, enables them to take measures earlier and can help prevent follow-up issues.

We present Weever, the first incremental approach to detect all violations of a given set of DCs. It uses a novel index structure to process inequality predicates and a new method to plan the execution order of predicates depending on their selectivity, reducing redundant computations when handling multiple DCs. Our evaluation shows that Weever outperforms a DBMS-based baseline by up to two orders of magnitude. And in the same time that a state-of-the-art static approach takes to analyze an entire dataset, Weever processes up to 200 000 insertions.