Fast Approximate Denial Constraint Discovery

Summary: Two‑phase approach: build a condensed, cache‑friendly 'clue set' (parallelizable) then transform to evidence sets to discover approximate denial constraints tolerant of exceptions in dirty data. Extends evidence‑inversion for approximate DCs, yielding ~7–8× avg speedups and up to orders‑of‑magnitude gains over prior parallel methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hc190a44f0820c3a5
Venue: VLDB
Year: 2023
Pagerank: 6.1963542e-05
Overall Rank: 5,283 | 64.50%
DOI: 10.14778/3565816.3565828
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Renjie Xiao (Fudan University)
2. Zijing Tan (Fudan University)
3. Haojin Wang (Fudan University)
4. Shuai Ma (Beihang University)

BibTeX Citation

@article{xiao_vldb23,
        title = {{Fast Approximate Denial Constraint Discovery}},
        author = {Xiao, Renjie and Tan, Zijing and Wang, Haojin and Ma, Shuai},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {2},
        pages = {269--281},
        doi = {10.14778/3565816.3565828},
        url = {https://doi.org/10.14778/3565816.3565828},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,063	Discovering Approximate Inclusion Dependencies	2025	VLDB	5.0851868e-05
10,110	Efficient Differential Dependency Discovery	2024	VLDB	5.0765311e-05
10,451	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD	4.9769913e-05
10,540	Minimum Change ≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints	2026	SIGMOD	4.9769913e-05
10,781	Discovering Approximate Denial Constraints in Large Databases	2026	VLDB	4.9769913e-05
11,015	LIMA: Denial Constraint Discovery in Large Dynamic Databases	2026	VLDB	4.9769913e-05
11,262	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.9769913e-05
11,327	How and Why False Denial Constraints are Discovered	2025	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 25 of 25 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033676943
350	Discovering Denial Constraints	2013	VLDB	0.00020244085
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015692059
697	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014687805
725	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00014471289
1,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010513265
1,620	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	0.00010050865
1,972	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2829634e-05
2,424	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.483813e-05
2,445	Approximate Denial Constraints	2020	VLDB	8.4546614e-05
3,296	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	7.444648e-05
3,360	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.3732195e-05
3,419	Data Profiling – A Tutorial	2017	SIGMOD	7.3175997e-05
3,958	Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database	1999	VLDB	6.8960375e-05
4,226	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.7151469e-05
4,467	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.5842379e-05
5,133	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.2573449e-05
6,173	Fundamentals of Order Dependencies	2012	VLDB	5.8595496e-05
6,427	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7867997e-05
6,734	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	5.6919385e-05
6,860	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.6615714e-05
7,289	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.5631739e-05
7,476	Fast Detection of Denial Constraint Violations	2022	VLDB	5.5150385e-05
8,211	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3761077e-05
8,513	DataProf: Semantic Profiling for Iterative Data Cleansing and Business Rule Acquisition	2018	SIGMOD	5.3244694e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,063	Discovering Approximate Inclusion Dependencies	2025	VLDB
2	350	Discovering Denial Constraints	2013	VLDB
3	1,620	Efficient Denial Constraint Discovery with Hydra	2018	VLDB
4	11,327	How and Why False Denial Constraints are Discovered	2025	VLDB
5	7,476	Fast Detection of Denial Constraint Violations	2022	VLDB
6	10,781	Discovering Approximate Denial Constraints in Large Databases	2026	VLDB
7	10,451	Discovery of Denial Constraints with Hardware Acceleration	2026	SIGMOD
8	2,445	Approximate Denial Constraints	2020	VLDB
9	1,972	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB
10	4,070	Fast Algorithms for Denial Constraint Discovery	2023	VLDB