{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T21:57:44Z","timestamp":1790373464113,"version":"4.1.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p>\n                    Functional dependencies (FDs) and unique column combinations (UCCs) form a valuable ingredient for many data management tasks, such as data cleaning, schema recovery, and query optimization. Because these dependencies are unknown in most scenarios, their automatic discovery has been well researched. However, existing methods mostly discover only exact dependencies, i.e., those without violations. Real-world dependencies, in contrast, are frequently approximate due to data exceptions, ambiguities, or data errors. This relaxation to approximate dependencies renders their discovery an even harder task than the already challenging exact dependency discovery. To this end, we propose the novel and highly efficient algorithm P\n                    <jats:sc>yro<\/jats:sc>\n                    to discover both approximate FDs and approximate UCCs. P\n                    <jats:sc>yro<\/jats:sc>\n                    combines a separate-and-conquer search strategy with sampling-based guidance that quickly detects dependency candidates and verifies them. In our broad experimental evaluation, P\n                    <jats:sc>yro<\/jats:sc>\n                    outperforms existing discovery algorithms by a factor of up to 33, scales to larger datasets, and at the same time requires the least main memory.\n                  <\/jats:p>","DOI":"10.14778\/3192965.3192968","type":"journal-article","created":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T15:56:10Z","timestamp":1527004570000},"page":"759-772","source":"Crossref","is-referenced-by-count":82,"title":["Efficient discovery of approximate dependencies"],"prefix":"10.14778","volume":"11","author":[{"given":"Sebastian","family":"Kruse","sequence":"first","affiliation":[{"name":"Hasso Plattner Institute, Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Felix","family":"Naumann","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0389-y"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661884"},{"key":"e_1_2_1_3_1","first-page":"487","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB)","author":"Agrawal R.","year":"1994"},{"key":"e_1_2_1_4_1","first-page":"580","volume-title":"IFIP Congress","author":"Armstrong W. W.","year":"1974"},{"issue":"2","key":"e_1_2_1_5_1","first-page":"338","article-title":"Mining approximate functional dependencies from databases based on minimal cover and equivalent classes","volume":"33","author":"Atoum J.","year":"2009","journal-title":"European Journal of Scientific Research"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322414"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920870"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983781"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2472010"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compeleceng.2013.11.024"},{"key":"e_1_2_1_11_1","unstructured":"P. A. Flach and I. Savnik. FDEP source code. http:\/\/www.cs.bris.ac.uk\/~flach\/fdep\/.  P. A. Flach and I. Savnik. FDEP source code. http:\/\/www.cs.bris.ac.uk\/~flach\/fdep\/."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1216155.1216159"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536363"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732240.2732248"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007641"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747646"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1155\/S117391260300004X"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/645500.655906"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00028-U"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809975"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514901"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133180"},{"issue":"2","key":"e_1_2_1_26_1","first-page":"8","article-title":"Data anamnesis: admitting raw data into an organization","volume":"39","author":"Kruse S.","year":"2016","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-45817-5_23"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.197"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/09528130210164143"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098062"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009796218281"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1041624.1041658"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/373626.373713"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017093"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824086"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794377"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915203"},{"key":"e_1_2_1_39_1","first-page":"342","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT)","author":"Papenbrock T.","year":"2017"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-008-0092-3"},{"key":"e_1_2_1_41_1","first-page":"691","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB)","author":"Sismanis Y.","year":"2006"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064024"},{"key":"e_1_2_1_43_1","volume-title":"Quicker ways of doing fewer things: improved index structures and algorithms for data profiling. Master's thesis","author":"Zwiener J.","year":"2015"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3192965.3192968","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T06:14:13Z","timestamp":1672208053000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3192965.3192968"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":43,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.14778\/3192965.3192968"],"URL":"https:\/\/doi.org\/10.14778\/3192965.3192968","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,3]]}}}