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: 13858
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,587 | 26.35%
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.00032746205
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
894	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015556428
1,047	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014459715
1,188	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00013441729
2,077	Efficient Discovery of Approximate Dependencies	2018	VLDB	9.6001836e-05
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05
3,440	Approximate Denial Constraints	2020	VLDB	7.0918817e-05
3,467	Data Profiling – A Tutorial	2017	SIGMOD	7.069081e-05
4,127	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	6.4310458e-05
4,744	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.957936e-05
5,613	Distributed implementations of dependency discovery algorithms	2019	VLDB	5.4102298e-05
5,618	Explaining Repaired Data with CFDs	2018	VLDB	5.4079415e-05
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05
7,261	Expressiveness and Complexity of Order Dependencies	2013	VLDB	4.7861106e-05
7,366	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7515248e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4393184e-05
9,646	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD	4.3109001e-05
9,649	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB	4.3109001e-05
9,749	Efficient Differential Dependency Discovery	2024	VLDB	4.2897489e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,450	Functional Dependencies for Graphs	2016	SIGMOD	8.7882979e-05
2,574	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	8.5173637e-05
9,649	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB	4.3109001e-05
6,703	Discovering Graph Functional Dependencies	2018	SIGMOD	4.9555163e-05
1,047	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014459715
25	Dependency Inference (Extended Abstract)	1987	VLDB	0.00083101742
9,646	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD	4.3109001e-05
7,366	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7515248e-05
894	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015556428
9,749	Efficient Differential Dependency Discovery	2024	VLDB	4.2897489e-05