# Approximate Denial Constraints

arXiv: https://arxiv.org/abs/2005.08540 · HTML: https://mlsanity.com/paper/2005.08540/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2020.

## Built on by (most cited first, 5 of 5)

- [Non-Invasive Fairness in Learning through the Lens of Data Drift](https://mlsanity.com/paper/2303.17566/) (2023)
- [UpLIF: An Updatable Self-Tuning Learned Index Framework](https://mlsanity.com/paper/2408.04113/) (2024)
- [DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees](https://mlsanity.com/paper/2502.05369/) (2025)
- [Quality Assessment of Tabular Data using Large Language Models and Code Generation](https://mlsanity.com/paper/2509.10572/) (2025)
- [Sig2Model: A Boosting-Driven Model for Updatable Learned Indexes](https://mlsanity.com/paper/2509.20781/) (2025)

## Abstract (arXiv)

The problem of mining integrity constraints from data has been extensively studied over the past two decades for commonly used types of constraints including the classic Functional Dependencies (FDs) and the more general Denial Constraints (DCs). In this paper, we investigate the problem of mining approximate DCs (i.e., DCs that are "almost" satisfied) from data. Considering approximate constraints allows us to discover more accurate constraints in inconsistent databases, detect rules that are generally correct but may have a few exceptions, as well as avoid overfitting and obtain more general and less contrived constraints. We introduce the algorithm ADCMiner for mining approximate DCs. An important feature of this algorithm is that it does not assume any specific definition of an approximate DC, but takes the semantics as input. Since there is more than one way to define an approximate DC and different definitions may produce very different results, we do not focus on one definition, but rather on a general family of approximation functions that satisfies some natural axioms defined in this paper and captures commonly used definitions of approximate constraints. We also show how our algorithm can be combined with sampling to return results with high accuracy while significantly reducing the running time.