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: h0b38014634e137fc
Venue: VLDB
Year: 2025
Pagerank: 4.9793485e-05
Overall Rank: 11,319 | 23.90%
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 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,439	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD	4.9793485e-05
10,771	Discovering Approximate Denial Constraints in Large Databases	2026	VLDB	4.9793485e-05
11,006	LIMA: Denial Constraint Discovery in Large Dynamic Databases	2026	VLDB	4.9793485e-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
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033690989
350	Discovering Denial Constraints	2013	VLDB	0.00020253521
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015699254
649	Discovering Data Quality Rules	2008	VLDB	0.00015149865
1,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010517437
1,619	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	0.00010055625
1,971	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2873596e-05
2,125	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	9.0033119e-05
2,443	Approximate Denial Constraints	2020	VLDB	8.4586656e-05
3,360	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.3767115e-05
4,067	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.8216078e-05
4,226	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.7183259e-05
5,280	Fast Approximate Denial Constraint Discovery	2023	VLDB	6.1992888e-05
6,424	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7895404e-05
8,203	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3786539e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	649	Discovering Data Quality Rules	2008	VLDB
2	10,439	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD
3	7,471	Fast Detection of Denial Constraint Violations	2022	VLDB
4	1,619	Efficient Denial Constraint Discovery with Hydra	2018	VLDB
5	5,280	Fast Approximate Denial Constraint Discovery	2023	VLDB
6	2,443	Approximate Denial Constraints	2020	VLDB
7	10,771	Discovering Approximate Denial Constraints in Large Databases	2026	VLDB
8	4,067	Fast Algorithms for Denial Constraint Discovery	2023	VLDB
9	350	Discovering Denial Constraints	2013	VLDB
10	1,971	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB