Fast Approximate Denial Constraint Discovery

Summary: Two‑phase approach: build a condensed, cache‑friendly 'clue set' (parallelizable) then transform to evidence sets to discover approximate denial constraints tolerant of exceptions in dirty data. Extends evidence‑inversion for approximate DCs, yielding ~7–8× avg speedups and up to orders‑of‑magnitude gains over prior parallel methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13115
Venue: VLDB
Year: 2023
Pagerank: 4.4350633e-05
Overall Rank: 8,836 | 38.59%
DOI: 10.14778/3565816.3565828

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,748	Efficient Differential Dependency Discovery	2024	VLDB	4.2856385e-05
10,026	Minimum Change ≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints	2026	SIGMOD	4.1905499e-05
10,549	Discovering Approximate Inclusion Dependencies	2025	VLDB	4.1905499e-05
10,595	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.1905499e-05
10,687	How and Why False Denial Constraints are Discovered	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 25 of 25 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.00035692958
556	Discovering Denial Constraints	2013	VLDB	0.00020214701
890	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015542177
904	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00015425636
1,012	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014638349
2,082	Efficient Discovery of Approximate Dependencies	2018	VLDB	9.5875364e-05
2,258	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1804145e-05
2,484	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6737275e-05
3,000	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	7.7447724e-05
3,448	Approximate Denial Constraints	2020	VLDB	7.081095e-05
3,473	Data Profiling – A Tutorial	2017	SIGMOD	7.0623537e-05
3,575	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	6.9509846e-05
4,271	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	6.2943273e-05
4,403	Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database	1999	VLDB	6.2054188e-05
4,680	Scalable Discovery of Unique Column Combinations	2014	VLDB	5.9964535e-05
4,740	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.9515736e-05
5,622	Distributed implementations of dependency discovery algorithms	2019	VLDB	5.4050344e-05
6,431	Fundamentals of Order Dependencies	2012	VLDB	5.058289e-05
6,759	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	4.933198e-05
7,062	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	4.8398632e-05
7,259	Expressiveness and Complexity of Order Dependencies	2013	VLDB	4.7815192e-05
7,361	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7469673e-05
7,666	Fast Detection of Denial Constraint Violations	2022	VLDB	4.6792751e-05
8,472	DataProf: Semantic Profiling for Iterative Data Cleansing and Business Rule Acquisition	2018	SIGMOD	4.4985733e-05
8,851	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	4.4322123e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,470	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.4993203e-05
9,748	Efficient Differential Dependency Discovery	2024	VLDB	4.2856385e-05
10,549	Discovering Approximate Inclusion Dependencies	2025	VLDB	4.1905499e-05
556	Discovering Denial Constraints	2013	VLDB	0.00020214701
2,258	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1804145e-05
10,687	How and Why False Denial Constraints are Discovered	2025	VLDB	4.1905499e-05
7,666	Fast Detection of Denial Constraint Violations	2022	VLDB	4.6792751e-05
3,448	Approximate Denial Constraints	2020	VLDB	7.081095e-05
2,484	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6737275e-05
6,470	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0439835e-05