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: 11746
Venue: VLDB
Year: 2018
Pagerank: 9.8500378e-05
Overall Rank: 1,782 | 87.62%
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
1,919	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.5736185e-05
2,757	Approximate Denial Constraints	2020	VLDB	8.2236644e-05
3,428	Kamino: Constraint-Aware Differentially Private Data Synthesis	2021	VLDB	7.499038e-05
3,533	Automatic Data Repair: Are We Ready to Deploy?	2024	VLDB	7.3965413e-05
4,987	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.4805516e-05
5,974	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.084153e-05
6,341	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.9698241e-05
6,609	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.8839764e-05
7,206	Discovering Association Rules from Big Graphs	2022	VLDB	5.7309223e-05
7,221	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	5.7238672e-05
7,287	Fast Detection of Denial Constraint Violations	2022	VLDB	5.7098267e-05
8,056	BugDoc: Algorithms to Debug Computational Processes	2020	SIGMOD	5.5554158e-05
8,583	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	5.468339e-05
8,717	Fast Approximate Denial Constraint Discovery	2023	VLDB	5.441927e-05
8,737	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.4388186e-05
8,781	CtxPipe: Context-aware Data Preparation Pipeline Construction for Machine Learning	2024	SIGMOD	5.4311509e-05
9,289	Discovering Top-k Rules using Subjective and Objective Criteria	2023	SIGMOD	5.3527456e-05
9,300	GIDCL: A Graph-Enhanced Interpretable Data Cleaning Framework with Large Language Models	2024	SIGMOD	5.3503577e-05
9,474	Incremental Detection of Denial Constraint Violations	2025	VLDB	5.3246578e-05
9,483	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.3246578e-05
9,736	Efficient Differential Dependency Discovery	2024	VLDB	5.2802856e-05
9,845	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.2617062e-05
9,962	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	5.2142386e-05
10,499	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	5.1725247e-05
10,522	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	5.1725247e-05
10,684	Meaningful Data Erasure in the Presence of Dependencies	2025	VLDB	5.1725247e-05
10,687	How and Why False Denial Constraints are Discovered	2025	VLDB	5.1725247e-05
11,004	Capturing More Associations by Referencing External Graphs	2024	VLDB	5.1725247e-05
11,236	Learning and Deducing Temporal Orders	2023	VLDB	5.1725247e-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
378	Discovering Denial Constraints	2013	VLDB	0.00019731608
668	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015281911
738	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014557138
896	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013398659
1,415	Data Profiling with Metanome	2015	VLDB	0.00010941889
2,244	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.9465445e-05
3,303	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	7.6069876e-05
4,110	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.9575204e-05
4,404	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.7827135e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,687	How and Why False Denial Constraints are Discovered	2025	VLDB	5.1725247e-05
668	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015281911
2,757	Approximate Denial Constraints	2020	VLDB	8.2236644e-05
7,287	Fast Detection of Denial Constraint Violations	2022	VLDB	5.7098267e-05
8,583	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	5.468339e-05
9,474	Incremental Detection of Denial Constraint Violations	2025	VLDB	5.3246578e-05
8,717	Fast Approximate Denial Constraint Discovery	2023	VLDB	5.441927e-05
378	Discovering Denial Constraints	2013	VLDB	0.00019731608
1,919	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.5736185e-05
5,974	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.084153e-05