Fast Algorithms for Denial Constraint Discovery

Summary: Suite of fast DC-discovery algorithms that accelerate the expensive intermediate construction using a parallel pipeline, custom data representations, and indexes. For enumeration they use inverted indexes, pruning, parallel search and hybridization with prior methods, yielding up to an order-of-magnitude speedups. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13510
Venue: VLDB
Year: 2023
Pagerank: 6.1504635e-05
Overall Rank: 5,611 | 61.51%
DOI: 10.14778/3574245.3574254

Incoming Non-self Citations Over Time

Authors

1. Eduardo H. M. Pena (Federal University of Technology)
2. Fabio Porto (National Laboratory for Scientific Computing)
3. Felix Naumann (Hasso Plattner Institute; University of Potsdam)

BibTeX Citation

@article{pena_vldb23,
        title = {{Fast Algorithms for Denial Constraint Discovery}},
        author = {Pena, Eduardo H. M. and Porto, Fabio and Naumann, Felix},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {4},
        pages = {684--696},
        doi = {10.14778/3574245.3574254},
        url = {https://doi.org/10.14778/3574245.3574254},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,686	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	5.3849387e-05
9,923	Efficient Differential Dependency Discovery	2024	VLDB	5.1955087e-05
10,223	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD	5.093636e-05
10,372	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD	5.093636e-05
10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	5.093636e-05
10,925	Meaningful Data Erasure in the Presence of Dependencies	2025	VLDB	5.093636e-05
10,928	How and Why False Denial Constraints are Discovered	2025	VLDB	5.093636e-05
11,221	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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
964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012934147
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,685	Approximate Denial Constraints	2020	VLDB	8.2594662e-05
3,361	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.4872032e-05
3,609	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	7.2602055e-05
4,782	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.5115802e-05
6,544	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.8461093e-05
7,396	Fast Detection of Denial Constraint Violations	2022	VLDB	5.6257228e-05
8,133	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.4813895e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,623	Incremental Detection of Denial Constraint Violations	2025	VLDB
2	2,685	Approximate Denial Constraints	2020	VLDB
3	10,928	How and Why False Denial Constraints are Discovered	2025	VLDB
4	8,686	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB
5	376	Discovering Denial Constraints	2013	VLDB
6	7,396	Fast Detection of Denial Constraint Violations	2022	VLDB
7	10,223	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD
8	1,741	Efficient Denial Constraint Discovery with Hydra	2018	VLDB
9	7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB
10	1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB