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: he644929a0dd626f9
Venue: SIGMOD
Year: 2024
Pagerank: 5.1038322e-05
Overall Rank: 9,958 | 33.05%
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 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,953	HaDA: Empower Database Experts with Data Dependencies	2026	VLDB	4.9793485e-05
11,254	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.9793485e-05
11,316	Meaningful Data Erasure in the Presence of Dependencies	2025	VLDB	4.9793485e-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
209	Dependency Inference	1987	VLDB	0.00024877096
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015699254
727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014443394
1,223	Partition Semantics for Relations	1985	PODS	0.00011452588
1,342	Baran: Effective Error Correction via a Unified Context Representation and Transfer Learning	2020	VLDB	0.00010968223
1,395	Data Profiling with Metanome	2015	VLDB	0.00010794808
3,254	Stitching Web Tables for Improving Matching Quality	2017	VLDB	7.4899241e-05
3,475	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	7.2707661e-05
5,097	Explaining Dataset Changes for Semantic Data Versioning with Explain-Da-V	2023	VLDB	6.2742361e-05
5,130	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.2603084e-05
7,287	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.5658087e-05
8,203	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3786539e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,046	Making DBMSes Dependency-Aware	2020	CIDR
2	1,348	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
3	10,106	Efficient Differential Dependency Discovery	2024	VLDB
4	11,558	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB
5	8,203	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB
6	2,125	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB
7	727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
8	7,287	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
9	11,254	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
10	603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD