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: 10827
Venue: VLDB
Year: 2013
Pagerank: 0.00019677674
Overall Rank: 376 | 97.43%
DOI: 10.14778/2536258.2536262

Incoming Non-self Citations Over Time

Authors

1. Xu Chu (University of Waterloo)
2. Ihab F. Ilyas (Qatar Computing Research Institute)
3. Paolo Papotti (Qatar Computing Research Institute)

BibTeX Citation

@article{chu_vldb13,
        title = {{Discovering Denial Constraints}},
        author = {Chu, Xu and Ilyas, Ihab F. and Papotti, Paolo},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {13},
        pages = {1498--1509},
        doi = {10.14778/2536258.2536262},
        url = {https://doi.org/10.14778/2536258.2536262},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 73 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,627	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.2434488e-05
9,838	Don’t Be a Tattle-Tale: Preventing Leakages through Data Dependencies on Access Control Protected Data	2022	VLDB	5.2103651e-05
9,999	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.1814573e-05
10,001	Reptile: Aggregation-level Explanations for Hierarchical Data	2022	SIGMOD	5.1814573e-05
10,065	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD	5.1648805e-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,282	Prism: Private Relational Data Synthesis with Language Models	2026	SIGMOD	5.093636e-05
10,317	Guardrail: Automated Integrity Constraint Synthesis From Noisy Data	2026	SIGMOD	5.093636e-05
10,322	Minimum Change ≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints	2026	SIGMOD	5.093636e-05
10,324	Outliers: The Good, the Bad and the Ugly	2026	SIGMOD	5.093636e-05
10,786	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	5.093636e-05
10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	5.093636e-05
10,928	How and Why False Denial Constraints are Discovered	2025	VLDB	5.093636e-05
10,966	UniClean: A Scalable Data Cleaning Solution for Mixed Errors based on Unified Cleaners and Optimized Cleaning Workflow	2025	VLDB	5.093636e-05
11,020	FDepHunter: Harnessing Negative Examples to Expose Fakes and Reveal Ghosts	2025	VLDB	5.093636e-05
11,079	bNDCRepair: Cleaning both Data Errors and Inaccurate Constraints on Numerical Sequential Data	2025	VLDB	5.093636e-05
11,276	Efficient Validation of SHACL Shapes with Reasoning	2024	VLDB	5.093636e-05
11,434	Learning and Deducing Temporal Orders	2023	VLDB	5.093636e-05
11,707	ADESIT: Visualize the Limits of your Data in a Machine Learning Process	2021	VLDB	5.093636e-05
11,780	T-REx: Table Repair Explanations	2020	SIGMOD	5.093636e-05
11,875	WiClean: A System for Fixing Wikipedia Interlinks Using Revision History Patterns	2019	VLDB	5.093636e-05
12,081	Cleaning Timestamps with Temporal Constraints	2016	VLDB	5.093636e-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.0006567919
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
647	Discovering Data Quality Rules	2008	VLDB	0.00015334666
1,033	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012529852

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,841	Semantic Integrity Constraints: Declarative Guardrails for AI-Augmented Data Processing Systems	2025	VLDB
2	7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB
3	2,591	Knowledge-based Integrity Constraint Validation	1986	VLDB
4	2,685	Approximate Denial Constraints	2020	VLDB
5	4,454	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB
6	6,142	Integrity Constraint Reformulation for Efficient Validation	1987	VLDB
7	1,741	Efficient Denial Constraint Discovery with Hydra	2018	VLDB
8	10,928	How and Why False Denial Constraints are Discovered	2025	VLDB
9	5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB
10	1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB