{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T22:53:53Z","timestamp":1778540033488,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Functional dependencies (FDs) are among the most important integrity constraints in databases. They serve to normalize datasets and thus resolve redundancies, they contribute to query optimization, and they are frequently used to guide data cleaning efforts. Because the FDs of a particular dataset are usually unknown, automatic profiling algorithms are needed to discover them. These algorithms have made considerable advances in the past few years, but they still require a significant amount of time and memory to process datasets of practically relevant sizes.<\/jats:p>\n          <jats:p>We present FDHits, a novel FD discovery algorithm that finds all valid, minimal FDs in a given relational dataset. FDHits is based on several discovery optimizations that include a hybrid validation approach, effective hitting set enumeration techniques, one-pass candidate validations, and parallelization. Our experiments show that FDHits, even without parallel execution, has a median speedup of 8.1 compared to state-of-the-art FD discovery algorithms while using significantly less memory. This allows the discovery of all FDs even on datasets that could not be processed by the current state-of-the-art.<\/jats:p>","DOI":"10.1145\/3639298","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-24","source":"Crossref","is-referenced-by-count":7,"title":["Discovering Functional Dependencies through Hitting Set Enumeration"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-9517-7707","authenticated-orcid":false,"given":"Tobias","family":"Bleifu\u00df","sequence":"first","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4019-8221","authenticated-orcid":false,"given":"Thorsten","family":"Papenbrock","sequence":"additional","affiliation":[{"name":"Philipps University of Marburg, Marburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2450-744X","authenticated-orcid":false,"given":"Thomas","family":"Bl\u00e4sius","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7086-5577","authenticated-orcid":false,"given":"Martin","family":"Schirneck","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4483-1389","authenticated-orcid":false,"given":"Felix","family":"Naumann","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0389-y"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661884"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 487--499","author":"Agrawal Rakesh","year":"1994","unstructured":"Rakesh Agrawal and Ramakrishnan Srikant. 1994. Fast Algorithms for Mining Association Rules in Large Databases. In Proceedings of the International Conference on Very Large Databases (VLDB). 487--499."},{"key":"e_1_2_2_4_1","volume-title":"Hypergraphs - Combinatorics of Finite Sets","author":"Berge Claude","unstructured":"Claude Berge. 1989. Hypergraphs - Combinatorics of Finite Sets. North-Holland Mathematical Library, Vol. 45. North-Holland Publishing Company, Amsterdam, Netherlands."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407824"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983781"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.11.020"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60795-5_4"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367920"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/25.1.68"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-019-00667-7"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_2_13_1","volume-title":"Further normalization of the data base relational model. Data base systems","author":"Codd Edgar F","year":"1972","unstructured":"Edgar F Codd. 1972. Further normalization of the data base relational model. Data base systems, Vol. 6 (1972), 33--64."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90019-X"},{"key":"e_1_2_2_15_1","volume-title":"AAAI Symposium on Intelligent Relevance. AAAI Press Menlo Park, 37--39","author":"Davies Scott","year":"1994","unstructured":"Scott Davies and Stuart Russell. 1994. NP-completeness of searches for smallest possible feature sets. In AAAI Symposium on Intelligent Relevance. AAAI Press Menlo Park, 37--39."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.04.017"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.154"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1216155.1216159"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1055024"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00586-5"},{"key":"e_1_2_2_21_1","volume-title":"Comput. J.","volume":"42","author":"Juha","year":"1999","unstructured":"Yk\"a Huhtala, Juha K\"arkk\"ainen, Pasi Porkka, and Hannu Toivonen. 1999. TANE: An efficient algorithm for discovering functional and approximate dependencies. Comput. J., Vol. 42, 2 (1999), 100--111."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00676-3"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137657"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46439-5_24"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407801"},{"key":"e_1_2_2_26_1","volume-title":"Dependency Inference. In Proceedings of the International Conference on Very Large Databases (VLDB). 155--158","author":"Mannila Heikki","year":"1987","unstructured":"Heikki Mannila and Kari-Jouko R\"a ih\"a. 1987. Dependency Inference. In Proceedings of the International Conference on Very Large Databases (VLDB). 155--158."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(94)90023-X"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/373626.373713"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.01.012"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44503-X_13"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824086"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794377"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915203"},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT)","volume":"17","author":"Papenbrock Thorsten","year":"2017","unstructured":"Thorsten Papenbrock and Felix Naumann. 2017. Data-driven Schema Normalization. In Proceedings of the International Conference on Extending Database Technology (EDBT), Vol. 17. 342--353."},{"key":"e_1_2_2_35_1","unstructured":"Glenn Norman Paulley. 2000. Exploiting Functional Dependence in Query Optimization. Technical Report. University of Waterloo."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342638"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583169"},{"key":"e_1_2_2_38_1","volume-title":"International Conference on Multimedia Big Data (BigMM). 426--431","author":"Tu S.","unstructured":"S. Tu and M. Huang. 2016. Scalable Functional Dependencies Discovery from Big Data. In International Conference on Multimedia Big Data (BigMM). 426--431."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00684-3"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00137"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342626"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.3390\/s22103856"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44801-2_11"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2925014"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639298","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639298","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:17:58Z","timestamp":1755789478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639298"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639298"],"URL":"https:\/\/doi.org\/10.1145\/3639298","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}