Efficient Discovery of Approximate Dependencies

Summary: Efficient discovery of approximate FDs and approximate UCCs. Pyro combines separate-and-conquer search with sampling-guided verification to quickly propose and validate candidates; scales to large datasets with minimal memory, outperforming prior methods by up to 33×. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h10ff48b42a992c6c
Venue: VLDB
Year: 2018
Pagerank: 0.0001047928
Overall Rank: 1,490 | 90.02%
DOI: 10.14778/3192965.3192968

Incoming Non-self Citations Over Time

Authors

1. Sebastian Kruse (Hasso Plattner Institute)
2. Felix Naumann (Hasso Plattner Institute)

BibTeX Citation

@article{kruse_vldb18,
        title = {{Efficient Discovery of Approximate Dependencies}},
        author = {Kruse, Sebastian and Naumann, Felix},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {7},
        pages = {759--772},
        doi = {10.14778/3192965.3192968},
        url = {https://doi.org/10.14778/3192965.3192968},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,190	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011564169
1,980	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2527187e-05
2,249	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7479608e-05
2,584	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	8.2435322e-05
3,205	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.5221127e-05
3,782	Optimizing Video Analytics with Declarative Model Relationships	2023	VLDB	7.0029633e-05
4,284	VIVA: An End-to-End System for Interactive Video Analytics	2022	CIDR	6.6710929e-05
5,303	Fast Approximate Denial Constraint Discovery	2023	VLDB	6.1758652e-05
5,856	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.9514226e-05
6,600	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	5.721104e-05
6,877	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.6429454e-05
7,307	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.5447786e-05
7,518	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	5.4894144e-05
8,285	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	5.3454563e-05
9,094	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB	5.208561e-05
9,645	Discovering Top-k Rules using Subjective and Objective Criteria	2023	SIGMOD	5.1332977e-05
10,004	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.0845476e-05
10,096	Discovering Approximate Inclusion Dependencies	2025	VLDB	5.068372e-05
10,146	Efficient Differential Dependency Discovery	2024	VLDB	5.0597449e-05
10,223	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0460607e-05
10,373	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	5.0005386e-05
10,571	Prism: Private Relational Data Synthesis with Language Models	2026	SIGMOD	4.9605343e-05
10,865	Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies	2026	VLDB	4.9605343e-05
11,256	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.9605343e-05
11,318	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.9605343e-05
11,381	How and Why False Denial Constraints are Discovered	2025	VLDB	4.9605343e-05
11,625	SplitDF: Splitting Dataframes for Memory-Efficient Data Analysis	2024	VLDB	4.9605343e-05
12,127	AUDITOR: A System Designed for Automatic Discovery of Complex Integrity Constraints in Relational Databases	2020	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027775994
165	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00027323925
602	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015670535
727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014426954
769	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014091996
1,354	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00010912271
1,399	Data Profiling with Metanome	2015	VLDB	0.0001076306
2,305	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6550507e-05
2,429	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.4657925e-05
3,432	UGuide – User-Guided Discovery of FD-Detectable Errors	2017	SIGMOD	7.288198e-05
4,245	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.6958006e-05
4,361	Possible and Certain SQL Keys	2015	VLDB	6.6271978e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	653	Discovering Data Quality Rules	2008	VLDB
2	10,146	Efficient Differential Dependency Discovery	2024	VLDB
3	9,997	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD
4	8,873	Workload-driven, Lazy Discovery of Data Dependencies for Query Optimization	2022	CIDR
5	11,318	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
6	10,096	Discovering Approximate Inclusion Dependencies	2025	VLDB
7	7,307	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
8	12,096	Making DBMSes Dependency-Aware	2020	CIDR
9	727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
10	602	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD