Efficient Denial Constraint Discovery with Hydra

Summary: Hydra introduces an efficient denial-constraint (DC) discovery algorithm that scales linearly with dataset size, overcoming prior quadratic runtimes. By dramatically reducing search cost, Hydra delivers orders-of-magnitude speedups and finds all valid DCs in seconds on large databases. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11745
Venue: VLDB
Year: 2018
Pagerank: 9.1937209e-05
Overall Rank: 2,253 | 84.33%
DOI: 10.14778/3157794.3157800

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 29 of 29 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05
3,396	Automatic Data Repair: Are We Ready to Deploy?	2024	VLDB	7.1455126e-05
3,440	Approximate Denial Constraints	2020	VLDB	7.0918817e-05
3,831	Kamino: Constraint-Aware Differentially Private Data Synthesis	2021	VLDB	6.7181688e-05
5,613	Distributed implementations of dependency discovery algorithms	2019	VLDB	5.4102298e-05
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05
6,546	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.0185588e-05
6,756	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	4.9379361e-05
7,202	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	4.8023314e-05
7,287	Discovering Association Rules from Big Graphs	2022	VLDB	4.7762276e-05
7,667	Fast Detection of Denial Constraint Violations	2022	VLDB	4.683767e-05
8,341	BugDoc: Algorithms to Debug Computational Processes	2020	SIGMOD	4.5433282e-05
8,472	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.5036378e-05
8,743	CtxPipe: Context-aware Data Preparation Pipeline Construction for Machine Learning	2024	SIGMOD	4.456315e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4393184e-05
8,850	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	4.4364648e-05
9,348	GIDCL: A Graph-Enhanced Interpretable Data Cleaning Framework with Large Language Models	2024	SIGMOD	4.3526427e-05
9,355	Discovering Top-k Rules using Subjective and Objective Criteria	2023	SIGMOD	4.3514328e-05
9,478	Incremental Detection of Denial Constraint Violations	2025	VLDB	4.3341665e-05
9,487	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	4.3341665e-05
9,749	Efficient Differential Dependency Discovery	2024	VLDB	4.2897489e-05
9,847	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	4.2721228e-05
9,963	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	4.2294678e-05
10,489	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.1945683e-05
10,513	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	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,001	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.1945683e-05
11,234	Learning and Deducing Temporal Orders	2023	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
894	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015556428
1,047	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014459715
1,197	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013390321
1,625	Data Profiling with Metanome	2015	VLDB	0.00011094926
2,549	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.5641554e-05
3,571	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	6.9580858e-05
4,682	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.0022412e-05
4,744	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.957936e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,679	How and Why False Denial Constraints are Discovered	2025	VLDB	4.1945683e-05
894	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015556428
3,440	Approximate Denial Constraints	2020	VLDB	7.0918817e-05
7,667	Fast Detection of Denial Constraint Violations	2022	VLDB	4.683767e-05
8,472	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.5036378e-05
9,478	Incremental Detection of Denial Constraint Violations	2025	VLDB	4.3341665e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4393184e-05
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05