Discovering Functional Dependencies through Hitting Set Enumeration

Summary: FDhits finds all valid, minimal FDs via hitting-set enumeration, with hybrid validation and one-pass candidate checks, plus parallelization. It yields a median 8.1× speedup over prior work with lower memory, enabling FD profiling on larger datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6852
Venue: SIGMOD
Year: 2024
Pagerank: 4.3109001e-05
Overall Rank: 9,646 | 32.90%
DOI: 10.1145/3639298

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,587	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.1945683e-05
10,676	Meaningful Data Erasure in the Presence of Dependencies	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
25	Dependency Inference (Extended Abstract)	1987	VLDB	0.00083101742
751	Partition Semantics for Relations	1985	PODS	0.0001721247
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,625	Data Profiling with Metanome	2015	VLDB	0.00011094926
1,894	Baran: Effective Error Correction via a Unified Context Representation and Transfer Learning	2020	VLDB	0.0001018378
3,797	Stitching Web Tables for Improving Matching Quality	2017	VLDB	6.7597149e-05
3,818	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	6.7300958e-05
5,280	Explaining Dataset Changes for Semantic Data Versioning with Explain-Da-V	2023	VLDB	5.5896735e-05
5,613	Distributed implementations of dependency discovery algorithms	2019	VLDB	5.4102298e-05
7,366	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7515248e-05
8,850	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	4.4364648e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,546	Making DBMSes Dependency-Aware	2020	CIDR	4.1945683e-05
1,624	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00011099222
9,749	Efficient Differential Dependency Discovery	2024	VLDB	4.2897489e-05
11,010	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	4.1945683e-05
8,850	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	4.4364648e-05
2,574	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	8.5173637e-05
1,047	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014459715
7,366	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7515248e-05
10,587	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.1945683e-05
894	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015556428