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: 11969
Venue: VLDB
Year: 2018
Pagerank: 0.00010561098
Overall Rank: 1,500 | 89.72%
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 27 of 27 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,174	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011817414
1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.4166032e-05
2,213	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.9410226e-05
2,620	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	8.3363963e-05
3,441	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.4138323e-05
4,007	Optimizing Video Analytics with Declarative Model Relationships	2023	VLDB	6.9632395e-05
4,256	VIVA: An End-to-End System for Interactive Video Analytics	2022	CIDR	6.8018439e-05
6,042	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.9970052e-05
6,720	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.794237e-05
6,929	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	5.7369354e-05
7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.6776392e-05
7,397	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	5.6256632e-05
7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB	5.5138609e-05
8,137	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	5.4809275e-05
9,427	Discovering Top-k Rules using Subjective and Objective Criteria	2023	SIGMOD	5.271035e-05
9,783	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB	5.2209769e-05
9,923	Efficient Differential Dependency Discovery	2024	VLDB	5.1955087e-05
9,999	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.1814573e-05
10,111	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	5.1347137e-05
10,282	Prism: Private Relational Data Synthesis with Language Models	2026	SIGMOD	5.093636e-05
10,766	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	5.093636e-05
10,812	Discovering Approximate Inclusion Dependencies	2025	VLDB	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
11,235	SplitDF: Splitting Dataframes for Memory-Efficient Data Analysis	2024	VLDB	5.093636e-05
11,688	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.093636e-05
11,775	AUDITOR: A System Designed for Automatic Discovery of Complex Integrity Constraints in Relational Databases	2020	SIGMOD	5.093636e-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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
161	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00027981772
618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015711835
729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014539421
800	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013911223
1,332	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00011129529
1,374	Data Profiling with Metanome	2015	VLDB	0.00010986078
2,269	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.8328424e-05
2,398	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.631172e-05
3,380	UGuide – User-Guided Discovery of FD-Detectable Errors	2017	SIGMOD	7.457539e-05
4,183	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.8467773e-05
4,303	Possible and Certain SQL Keys	2015	VLDB	6.7711902e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	647	Discovering Data Quality Rules	2008	VLDB
2	9,923	Efficient Differential Dependency Discovery	2024	VLDB
3	9,780	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD
4	8,684	Workload-driven, Lazy Discovery of Data Dependencies for Query Optimization	2022	CIDR
5	10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
6	10,812	Discovering Approximate Inclusion Dependencies	2025	VLDB
7	7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
8	11,743	Making DBMSes Dependency-Aware	2020	CIDR
9	729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
10	618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD