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.00010517437
Overall Rank: 1,488 | 90.00%
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,191	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011590153
1,971	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2873596e-05
2,238	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7751619e-05
2,583	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	8.2589758e-05
3,193	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.5505481e-05
3,778	Optimizing Video Analytics with Declarative Model Relationships	2023	VLDB	7.0259119e-05
4,287	VIVA: An End-to-End System for Interactive Video Analytics	2022	CIDR	6.6869736e-05
5,280	Fast Approximate Denial Constraint Discovery	2023	VLDB	6.1992888e-05
5,854	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.9708829e-05
6,589	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	5.7427998e-05
6,855	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.6642528e-05
7,287	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.5658087e-05
7,505	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	5.5074181e-05
8,263	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	5.3657304e-05
9,107	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB	5.2283159e-05
9,608	Discovering Top-k Rules using Subjective and Objective Criteria	2023	SIGMOD	5.1527671e-05
9,967	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.1038322e-05
10,058	Discovering Approximate Inclusion Dependencies	2025	VLDB	5.0875952e-05
10,106	Efficient Differential Dependency Discovery	2024	VLDB	5.0789354e-05
10,186	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0651993e-05
10,339	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	5.0195045e-05
10,494	Prism: Private Relational Data Synthesis with Language Models	2026	SIGMOD	4.9793485e-05
10,794	Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies	2026	VLDB	4.9793485e-05
11,188	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.9793485e-05
11,254	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.9793485e-05
11,319	How and Why False Denial Constraints are Discovered	2025	VLDB	4.9793485e-05
11,570	SplitDF: Splitting Dataframes for Memory-Efficient Data Analysis	2024	VLDB	4.9793485e-05
12,077	AUDITOR: A System Designed for Automatic Discovery of Complex Integrity Constraints in Relational Databases	2020	SIGMOD	4.9793485e-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.00061066921
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027837289
164	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00027412227
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015699254
727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014443394
767	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014114806
1,348	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.0001094733
1,395	Data Profiling with Metanome	2015	VLDB	0.00010794808
2,291	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6872323e-05
2,423	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.4877894e-05
3,422	UGuide – User-Guided Discovery of FD-Detectable Errors	2017	SIGMOD	7.3138834e-05
4,226	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.7183259e-05
4,342	Possible and Certain SQL Keys	2015	VLDB	6.6510065e-05

Semantically Similar Papers

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