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: 14163
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,928 | 25.03%
DOI: 10.14778/3748191.3748209

Incoming Non-self Citations Over Time

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

Authors

1. Albert Martin (Universitat Politècnica de Catalunya)
2. Eduardo C. de Almeida (Federal University of Parana)
3. Oscar Romero (Universitat Politècnica de Catalunya)
4. Anna Queralt (Universitat Politècnica de Catalunya)

BibTeX Citation

@article{martin_vldb25,
        title = {{How and Why False Denial Constraints are Discovered}},
        author = {Martin, Albert and de Almeida, Eduardo C. and Romero, Oscar and Queralt, Anna},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {10},
        pages = {3477--3489},
        doi = {10.14778/3748191.3748209},
        url = {https://doi.org/10.14778/3748191.3748209},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,223	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD	5.093636e-05

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
112	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00032801121
376	Discovering Denial Constraints	2013	VLDB	0.00019677674
618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015711835
647	Discovering Data Quality Rules	2008	VLDB	0.00015334666
1,500	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010561098
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
2,123	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	9.1372798e-05
2,685	Approximate Denial Constraints	2020	VLDB	8.2594662e-05
3,361	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.4872032e-05
4,183	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.8467773e-05
5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.1504635e-05
6,930	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7367175e-05
7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB	5.5138609e-05
8,844	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3588479e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,623	Incremental Detection of Denial Constraint Violations	2025	VLDB
2	647	Discovering Data Quality Rules	2008	VLDB
3	10,223	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD
4	7,396	Fast Detection of Denial Constraint Violations	2022	VLDB
5	1,741	Efficient Denial Constraint Discovery with Hydra	2018	VLDB
6	7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB
7	2,685	Approximate Denial Constraints	2020	VLDB
8	5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB
9	376	Discovering Denial Constraints	2013	VLDB
10	1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB