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.00010513265
Overall Rank: 1,488 | 90.01%
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,188	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011598149
1,972	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2829634e-05
2,237	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7738349e-05
2,583	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	8.2589842e-05
3,194	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.5469742e-05
3,780	Optimizing Video Analytics with Declarative Model Relationships	2023	VLDB	7.0225859e-05
4,273	VIVA: An End-to-End System for Interactive Video Analytics	2022	CIDR	6.6895276e-05
5,283	Fast Approximate Denial Constraint Discovery	2023	VLDB	6.1963542e-05
5,842	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.971167e-05
6,591	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	5.7400812e-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,510	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	5.504811e-05
8,269	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	5.3631903e-05
9,087	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB	5.2258409e-05
9,616	Discovering Top-k Rules using Subjective and Objective Criteria	2023	SIGMOD	5.1503279e-05
9,973	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.1014161e-05
10,063	Discovering Approximate Inclusion Dependencies	2025	VLDB	5.0851868e-05
10,110	Efficient Differential Dependency Discovery	2024	VLDB	5.0765311e-05
10,189	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0628015e-05
10,346	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	5.0171283e-05
10,505	Prism: Private Relational Data Synthesis with Language Models	2026	SIGMOD	4.9769913e-05
10,804	Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies	2026	VLDB	4.9769913e-05
11,197	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	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
11,576	SplitDF: Splitting Dataframes for Memory-Efficient Data Analysis	2024	VLDB	4.9769913e-05
12,083	AUDITOR: A System Designed for Automatic Discovery of Complex Integrity Constraints in Relational Databases	2020	SIGMOD	4.9769913e-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.00061067652
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027827605
164	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.000273994
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015692059
728	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014436728
767	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014108234
1,348	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00010942213
1,394	Data Profiling with Metanome	2015	VLDB	0.00010791559
2,294	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6831732e-05
2,424	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.483813e-05
3,421	UGuide – User-Guided Discovery of FD-Detectable Errors	2017	SIGMOD	7.3120636e-05
4,226	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.7151469e-05
4,342	Possible and Certain SQL Keys	2015	VLDB	6.6478954e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	650	Discovering Data Quality Rules	2008	VLDB
2	10,110	Efficient Differential Dependency Discovery	2024	VLDB
3	9,964	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD
4	8,861	Workload-driven, Lazy Discovery of Data Dependencies for Query Optimization	2022	CIDR
5	11,262	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
6	10,063	Discovering Approximate Inclusion Dependencies	2025	VLDB
7	7,289	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
8	12,052	Making DBMSes Dependency-Aware	2020	CIDR
9	728	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
10	603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD