Efficient Denial Constraint Discovery with Hydra

Summary: Hydra automatically discovers all valid denial constraints, unifying diverse integrity constraints and business rules. Its novel algorithm reduces tuple-scaling from quadratic to empirically linear, yielding orders-of-magnitude speedups over prior DC discovery methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11933
Venue: VLDB
Year: 2018
Pagerank: 9.8755846e-05
Overall Rank: 1,741 | 88.06%
DOI: 10.14778/3157794.3157800

Incoming Non-self Citations Over Time

Authors

1. Tobias Bleifuß (Hasso Plattner Institute)
2. Sebastian Kruse (Hasso Plattner Institute)
3. Felix Naumann (Hasso Plattner Institute)

BibTeX Citation

@article{bleifu_vldb18,
        title = {{Efficient Denial Constraint Discovery with Hydra}},
        author = {Bleifuß, Tobias and Kruse, Sebastian and Naumann, Felix},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {3},
        pages = {311--323},
        doi = {10.14778/3157794.3157800},
        url = {https://doi.org/10.14778/3157794.3157800},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 30 of 30 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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,412	Kamino: Constraint-Aware Differentially Private Data Synthesis	2021	VLDB	7.4344343e-05
3,580	Automatic Data Repair: Are We Ready to Deploy?	2024	VLDB	7.2888516e-05
5,052	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.3846183e-05
5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.1504635e-05
6,544	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.8461093e-05
6,720	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.794237e-05
7,330	Discovering Association Rules from Big Graphs	2022	VLDB	5.6435171e-05
7,396	Fast Detection of Denial Constraint Violations	2022	VLDB	5.6257228e-05
7,397	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	5.6256632e-05
7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB	5.5138609e-05
8,185	BugDoc: Algorithms to Debug Computational Processes	2020	SIGMOD	5.4707797e-05
8,686	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	5.3849387e-05
8,844	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3588479e-05
8,914	CtxPipe: Context-aware Data Preparation Pipeline Construction for Machine Learning	2024	SIGMOD	5.3483178e-05
9,427	Discovering Top-k Rules using Subjective and Objective Criteria	2023	SIGMOD	5.271035e-05
9,437	GIDCL: A Graph-Enhanced Interpretable Data Cleaning Framework with Large Language Models	2024	SIGMOD	5.2687567e-05
9,623	Incremental Detection of Denial Constraint Violations	2025	VLDB	5.2434488e-05
9,627	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.2434488e-05
9,923	Efficient Differential Dependency Discovery	2024	VLDB	5.1955087e-05
9,999	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.1814573e-05
10,111	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	5.1347137e-05
10,223	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD	5.093636e-05
10,766	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	5.093636e-05
10,786	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	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,212	Capturing More Associations by Referencing External Graphs	2024	VLDB	5.093636e-05
11,434	Learning and Deducing Temporal Orders	2023	VLDB	5.093636e-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
376	Discovering Denial Constraints	2013	VLDB	0.00019677674
618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015711835
729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014539421
800	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013911223
1,374	Data Profiling with Metanome	2015	VLDB	0.00010986078
2,269	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.8328424e-05
3,295	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	7.5477715e-05
4,183	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.8467773e-05
4,454	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.6929626e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
2	2,685	Approximate Denial Constraints	2020	VLDB
3	7,396	Fast Detection of Denial Constraint Violations	2022	VLDB
4	8,686	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB
5	9,623	Incremental Detection of Denial Constraint Violations	2025	VLDB
6	10,223	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD
7	7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB
8	376	Discovering Denial Constraints	2013	VLDB
9	1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB
10	5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB