Efficient Discovery of Relaxed Functional Dependencies

Summary: First complete discovery algorithm for minimal relaxed FDs, combining similarity-threshold equality with bounded violations. Extends difference-sets to threshold predicates and exploits RHS subsumption, achieving orders-of-magnitude speedups and uncovering FDs in dirty data. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14046
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,848 | 25.58%
DOI: 10.14778/3734839.3734843

Incoming Non-self Citations Over Time

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

Authors

1. Mengran Li (Fudan University)
2. Zijing Tan (Fudan University)
3. Honghui Yang (Fudan University)
4. Shuai Ma (Beihang University)

BibTeX Citation

@article{li_vldb25,
        title = {{Efficient Discovery of Relaxed Functional Dependencies}},
        author = {Li, Mengran and Tan, Zijing and Yang, Honghui and Ma, Shuai},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {7},
        pages = {2044--2056},
        doi = {10.14778/3734839.3734843},
        url = {https://doi.org/10.14778/3734839.3734843},
        year = {2025}
}

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
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
376	Discovering Denial Constraints	2013	VLDB	0.00019677674
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
1,033	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012529852
1,500	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010561098
1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.4166032e-05
2,685	Approximate Denial Constraints	2020	VLDB	8.2594662e-05
3,387	Data Profiling – A Tutorial	2017	SIGMOD	7.4534663e-05
3,441	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.4138323e-05
4,454	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.6929626e-05
5,052	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.3846183e-05
5,312	Explaining Repaired Data with CFDs	2018	VLDB	6.2698779e-05
5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.1504635e-05
6,930	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7367175e-05
7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.6776392e-05
7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB	5.5138609e-05
9,780	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD	5.2209769e-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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,973	Functional Dependencies for Graphs	2016	SIGMOD
2	2,123	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB
3	9,783	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB
4	7,099	Discovering Graph Functional Dependencies	2018	SIGMOD
5	729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
6	203	Dependency Inference	1987	VLDB
7	9,780	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD
8	7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
9	618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
10	9,923	Efficient Differential Dependency Discovery	2024	VLDB