How and Why False Denial Constraints are Discovered

Summary: Show SOTA denial-constraint discovery yields mostly false constraints (false rate often >95%), tracing the issue to the standard DC validity definition. Propose a statistical redefinition of DC validity that prevents false positives, recovers true constraints missed by experts, and provides curated golden DC sets. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13975
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,679 | 25.71%
DOI: 10.14778/3748191.3748209

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035728858
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
732	Discovering Data Quality Rules	2008	VLDB	0.00017465093
894	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015556428
2,077	Efficient Discovery of Approximate Dependencies	2018	VLDB	9.6001836e-05
2,253	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1937209e-05
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05
2,574	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	8.5173637e-05
3,440	Approximate Denial Constraints	2020	VLDB	7.0918817e-05
4,273	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	6.3003864e-05
4,682	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.0022412e-05
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05
7,261	Expressiveness and Complexity of Order Dependencies	2013	VLDB	4.7861106e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4393184e-05
8,850	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	4.4364648e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,273	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	6.3003864e-05
9,478	Incremental Detection of Denial Constraint Violations	2025	VLDB	4.3341665e-05
732	Discovering Data Quality Rules	2008	VLDB	0.00017465093
7,667	Fast Detection of Denial Constraint Violations	2022	VLDB	4.683767e-05
2,253	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1937209e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4393184e-05
3,440	Approximate Denial Constraints	2020	VLDB	7.0918817e-05
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05