Discovering Denial Constraints

Summary: Proposes Denial Constraints (DCs) as a more expressive integrity-constraint language than FDs/CFDs, with sound inference rules and a linear-time implication test. Devotes an instance-driven DC discovery algorithm and a novel scoring function to rank candidates for user validation; empirical evaluation on real and synthetic data demonstrates scalable, effective constraint discovery. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10640
Venue: VLDB
Year: 2013
Pagerank: 0.00020214701
Overall Rank: 556 | 96.14%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 71 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,489	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	4.3300131e-05
9,673	Don’t Be a Tattle-Tale: Preventing Leakages through Data Dependencies on Access Control Protected Data	2022	VLDB	4.3014213e-05
9,847	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	4.2680295e-05
9,849	Reptile: Aggregation-level Explanations for Hierarchical Data	2022	SIGMOD	4.2680295e-05
9,923	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD	4.2503475e-05
9,962	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	4.2254157e-05
10,019	Guardrail: Automated Integrity Constraint Synthesis From Noisy Data	2026	SIGMOD	4.1905499e-05
10,026	Minimum Change ≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints	2026	SIGMOD	4.1905499e-05
10,029	Outliers: The Good, the Bad and the Ugly	2026	SIGMOD	4.1905499e-05
10,522	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	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
10,730	UniClean: A Scalable Data Cleaning Solution for Mixed Errors based on Unified Cleaners and Optimized Cleaning Workflow	2025	VLDB	4.1905499e-05
10,797	FDepHunter: Harnessing Negative Examples to Expose Fakes and Reveal Ghosts	2025	VLDB	4.1905499e-05
10,859	bNDCRepair: Cleaning both Data Errors and Inaccurate Constraints on Numerical Sequential Data	2025	VLDB	4.1905499e-05
11,073	Efficient Validation of SHACL Shapes with Reasoning	2024	VLDB	4.1905499e-05
11,236	Learning and Deducing Temporal Orders	2023	VLDB	4.1905499e-05
11,513	ADESIT: Visualize the Limits of your Data in a Machine Learning Process	2021	VLDB	4.1905499e-05
11,588	T-REx: Table Repair Explanations	2020	SIGMOD	4.1905499e-05
11,685	WiClean: A System for Fixing Wikipedia Interlinks Using Revision History Patterns	2019	VLDB	4.1905499e-05
11,889	Cleaning Timestamps with Temporal Constraints	2016	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.0010863639
224	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00032743209
481	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.000221538
733	Discovering Data Quality Rules	2008	VLDB	0.00017428132
1,187	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00013432048

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,728	Semantic Integrity Constraints: Declarative Guardrails for AI-Augmented Data Processing Systems	2025	VLDB	4.2901665e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4350633e-05
2,284	Knowledge-based Integrity Constraint Validation	1986	VLDB	9.1118342e-05
3,448	Approximate Denial Constraints	2020	VLDB	7.081095e-05
4,740	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.9515736e-05
5,745	Integrity Constraint Reformulation for Efficient Validation	1987	VLDB	5.3429366e-05
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
6,470	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0439835e-05
2,484	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6737275e-05