Efficient Discovery of Relaxed Functional Dependencies

Summary: First row-based algorithm to discover all valid, minimal relaxed functional dependencies (RFDs) with value-similarity and error thresholds. Extends difference-set to attribute+threshold predicates and uses efficient construction plus RHS-subsumption enumeration to share work, achieving large speedups. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13859
Venue: VLDB
Year: 2025
Pagerank: 4.1905499e-05
Overall Rank: 10,595 | 26.37%
DOI: 10.14778/3734839.3734843

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
224	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00032743209
556	Discovering Denial Constraints	2013	VLDB	0.00020214701
890	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015542177
1,047	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014442219
1,187	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00013432048
2,082	Efficient Discovery of Approximate Dependencies	2018	VLDB	9.5875364e-05
2,484	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6737275e-05
3,448	Approximate Denial Constraints	2020	VLDB	7.081095e-05
3,473	Data Profiling – A Tutorial	2017	SIGMOD	7.0623537e-05
4,129	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	6.4208557e-05
4,740	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.9515736e-05
5,622	Distributed implementations of dependency discovery algorithms	2019	VLDB	5.4050344e-05
5,626	Explaining Repaired Data with CFDs	2018	VLDB	5.4032498e-05
6,470	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0439835e-05
7,259	Expressiveness and Complexity of Order Dependencies	2013	VLDB	4.7815192e-05
7,361	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7469673e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4350633e-05
9,647	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD	4.3067693e-05
9,650	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB	4.3067693e-05
9,748	Efficient Differential Dependency Discovery	2024	VLDB	4.2856385e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,478	Functional Dependencies for Graphs	2016	SIGMOD	7.0554625e-05
2,576	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	8.509121e-05
9,650	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB	4.3067693e-05
7,120	Discovering Graph Functional Dependencies	2018	SIGMOD	4.8200122e-05
1,047	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014442219
25	Dependency Inference (Extended Abstract)	1987	VLDB	0.00083070519
9,647	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD	4.3067693e-05
7,361	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7469673e-05
890	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015542177
9,748	Efficient Differential Dependency Discovery	2024	VLDB	4.2856385e-05