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: 6914
Venue: SIGMOD
Year: 2024
Pagerank: 5.2209769e-05
Overall Rank: 9,780 | 32.91%
DOI: 10.1145/3639298

Incoming Non-self Citations Over Time

Authors

1. Tobias Bleifuß (Hasso Plattner Institute; University of Potsdam)
2. Thorsten Papenbrock (Philipps University Marburg)
3. Thomas Bläsius (Karlsruhe Institute of Technology)
4. Martin Schirneck (University of Vienna)
5. Felix Naumann (Hasso Plattner Institute; University of Potsdam)

BibTeX Citation

@inproceedings{bleifu_sigmod24,
        title = {{Discovering Functional Dependencies through Hitting Set Enumeration}},
        author = {Bleifuß, Tobias and Papenbrock, Thorsten and Bläsius, Thomas and Schirneck, Martin and Naumann, Felix},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3639298},
        url = {https://dl.acm.org/doi/10.1145/3639298},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	5.093636e-05
10,925	Meaningful Data Erasure in the Presence of Dependencies	2025	VLDB	5.093636e-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
203	Dependency Inference	1987	VLDB	0.00025381538
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,216	Partition Semantics for Relations	1985	PODS	0.00011633715
1,374	Data Profiling with Metanome	2015	VLDB	0.00010986078
1,476	Baran: Effective Error Correction via a Unified Context Representation and Transfer Learning	2020	VLDB	0.00010659277
3,301	Stitching Web Tables for Improving Matching Quality	2017	VLDB	7.5408662e-05
3,609	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	7.2602055e-05
4,990	Explaining Dataset Changes for Semantic Data Versioning with Explain-Da-V	2023	VLDB	6.4105738e-05
5,052	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.3846183e-05
7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.6776392e-05
8,844	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3588479e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,743	Making DBMSes Dependency-Aware	2020	CIDR
2	1,332	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
3	9,923	Efficient Differential Dependency Discovery	2024	VLDB
4	11,221	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB
5	8,844	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB
6	2,123	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB
7	729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
8	7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
9	10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
10	618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD