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: 13322
Venue: VLDB
Year: 2023
Pagerank: 5.0488285e-05
Overall Rank: 6,477 | 54.95%
DOI: 10.14778/3574245.3574254

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,472	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.5036378e-05
9,749	Efficient Differential Dependency Discovery	2024	VLDB	4.2897489e-05
10,081	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD	4.1945683e-05
10,587	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.1945683e-05
10,676	Meaningful Data Erasure in the Presence of Dependencies	2025	VLDB	4.1945683e-05
10,679	How and Why False Denial Constraints are Discovered	2025	VLDB	4.1945683e-05
11,010	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	4.1945683e-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
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035728858
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
1,312	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012652548
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
3,440	Approximate Denial Constraints	2020	VLDB	7.0918817e-05
3,818	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	6.7300958e-05
4,273	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	6.3003864e-05
5,315	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	5.5723424e-05
6,546	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.0185588e-05
7,667	Fast Detection of Denial Constraint Violations	2022	VLDB	4.683767e-05
8,145	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5761263e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,690	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	4.9621556e-05
9,478	Incremental Detection of Denial Constraint Violations	2025	VLDB	4.3341665e-05
3,440	Approximate Denial Constraints	2020	VLDB	7.0918817e-05
10,679	How and Why False Denial Constraints are Discovered	2025	VLDB	4.1945683e-05
8,472	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.5036378e-05
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
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
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05