Approximate Denial Constraints

Summary: Introduces approximate denial constraints for noisy/inconsistent data, capturing generally valid rules with exceptions while reducing overfitting. ADCMiner supports arbitrary approximation functions satisfying natural axioms and combines with sampling for scalable, accurate discovery. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12260
Venue: VLDB
Year: 2020
Pagerank: 8.2594662e-05
Overall Rank: 2,685 | 81.58%
DOI: 10.14778/3401960.3401966

Incoming Non-self Citations Over Time

Authors

1. Ester Livshits (Technion)
2. Alireza Heidari (University of Waterloo)
3. Ihab F. Ilyas (University of Waterloo)
4. Benny Kimelfeld (Technion)

BibTeX Citation

@article{livshits_vldb20,
        title = {{Approximate Denial Constraints}},
        author = {Livshits, Ester and Heidari, Alireza and Ilyas, Ihab F. and Kimelfeld, Benny},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {10},
        pages = {1682--1695},
        doi = {10.14778/3401960.3401966},
        url = {https://doi.org/10.14778/3401960.3401966},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.1504635e-05
6,544	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.8461093e-05
6,755	Synthesizing Linked Data Under Cardinality and Integrity Constraints	2021	SIGMOD	5.7830386e-05
7,330	Discovering Association Rules from Big Graphs	2022	VLDB	5.6435171e-05
7,397	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	5.6256632e-05
7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB	5.5138609e-05
8,594	Exploratory Training: When Annotators Learn About Data	2023	SIGMOD	5.4053095e-05
8,844	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3588479e-05
8,914	CtxPipe: Context-aware Data Preparation Pipeline Construction for Machine Learning	2024	SIGMOD	5.3483178e-05
9,427	Discovering Top-k Rules using Subjective and Objective Criteria	2023	SIGMOD	5.271035e-05
9,437	GIDCL: A Graph-Enhanced Interpretable Data Cleaning Framework with Large Language Models	2024	SIGMOD	5.2687567e-05
9,923	Efficient Differential Dependency Discovery	2024	VLDB	5.1955087e-05
9,999	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.1814573e-05
10,111	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	5.1347137e-05
10,223	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD	5.093636e-05
10,766	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	5.093636e-05
10,786	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	5.093636e-05
10,812	Discovering Approximate Inclusion Dependencies	2025	VLDB	5.093636e-05
10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	5.093636e-05
10,928	How and Why False Denial Constraints are Discovered	2025	VLDB	5.093636e-05
10,955	DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees	2025	VLDB	5.093636e-05
11,212	Capturing More Associations by Referencing External Graphs	2024	VLDB	5.093636e-05
11,434	Learning and Deducing Temporal Orders	2023	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
376	Discovering Denial Constraints	2013	VLDB	0.00019677674
647	Discovering Data Quality Rules	2008	VLDB	0.00015334666
729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014539421
946	HoloDetect: Few-Shot Learning for Error Detection	2019	SIGMOD	0.00013054126
1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010893312
1,741	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.8755846e-05
1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.4166032e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
2	1,741	Efficient Denial Constraint Discovery with Hydra	2018	VLDB
3	533	Improving Data Quality: Consistency and Accuracy	2007	VLDB
4	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
5	4,454	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB
6	376	Discovering Denial Constraints	2013	VLDB
7	10,928	How and Why False Denial Constraints are Discovered	2025	VLDB
8	5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB
9	7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB
10	1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB