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: 10639
Venue: VLDB
Year: 2013
Pagerank: 0.00020254908
Overall Rank: 555 | 96.15%
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,487	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	4.3341665e-05
9,673	Don’t Be a Tattle-Tale: Preventing Leakages through Data Dependencies on Access Control Protected Data	2022	VLDB	4.3055474e-05
9,847	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	4.2721228e-05
9,849	Reptile: Aggregation-level Explanations for Hierarchical Data	2022	SIGMOD	4.2721228e-05
9,924	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD	4.2544238e-05
9,963	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	4.2294678e-05
10,019	Guardrail: Automated Integrity Constraint Synthesis From Noisy Data	2026	SIGMOD	4.1945683e-05
10,026	Minimum Change ≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints	2026	SIGMOD	4.1945683e-05
10,029	Outliers: The Good, the Bad and the Ugly	2026	SIGMOD	4.1945683e-05
10,513	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	4.1945683e-05
10,587	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.1945683e-05
10,679	How and Why False Denial Constraints are Discovered	2025	VLDB	4.1945683e-05
10,723	UniClean: A Scalable Data Cleaning Solution for Mixed Errors based on Unified Cleaners and Optimized Cleaning Workflow	2025	VLDB	4.1945683e-05
10,791	FDepHunter: Harnessing Negative Examples to Expose Fakes and Reveal Ghosts	2025	VLDB	4.1945683e-05
10,855	bNDCRepair: Cleaning both Data Errors and Inaccurate Constraints on Numerical Sequential Data	2025	VLDB	4.1945683e-05
11,070	Efficient Validation of SHACL Shapes with Reasoning	2024	VLDB	4.1945683e-05
11,234	Learning and Deducing Temporal Orders	2023	VLDB	4.1945683e-05
11,509	ADESIT: Visualize the Limits of your Data in a Machine Learning Process	2021	VLDB	4.1945683e-05
11,584	T-REx: Table Repair Explanations	2020	SIGMOD	4.1945683e-05
11,680	WiClean: A System for Fixing Wikipedia Interlinks Using Revision History Patterns	2019	VLDB	4.1945683e-05
11,881	Cleaning Timestamps with Temporal Constraints	2016	VLDB	4.1945683e-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.0010864752
224	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00032746205
475	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00022303253
732	Discovering Data Quality Rules	2008	VLDB	0.00017465093
1,188	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00013441729

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,729	Semantic Integrity Constraints: Declarative Guardrails for AI-Augmented Data Processing Systems	2025	VLDB	4.2942813e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4393184e-05
2,283	Knowledge-based Integrity Constraint Validation	1986	VLDB	9.105984e-05
3,440	Approximate Denial Constraints	2020	VLDB	7.0918817e-05
4,744	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.957936e-05
5,745	Integrity Constraint Reformulation for Efficient Validation	1987	VLDB	5.3440873e-05
2,253	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1937209e-05
10,679	How and Why False Denial Constraints are Discovered	2025	VLDB	4.1945683e-05
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05