{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:31:07Z","timestamp":1776785467093,"version":"3.51.2"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Inclusion dependencies (INDs) are a well-known type of data dependency, specifying that the values of one column are contained in those of another column. INDs can be used for various purposes, such as foreign-key candidate selection or join partner discovery. The traditional notion of INDs is based on clean data, where the dependencies hold without exceptions. Unfortunately, data often contain errors, preventing otherwise valid INDs from being discovered. A typical response to this problem is to relax the dependency definition using a similarity measure to account for minor data errors, such as typos or different formatting. While this relaxation is known for functional dependencies, for inclusion dependencies no such relaxation has been defined.<\/jats:p>\n          <jats:p>We formally introduce similarity inclusion dependencies, which relax the inclusion by demanding the existence only of sufficiently similar values. Similarity inclusion dependencies can fulfill traditional IND use cases, such as foreign-key candidate discovery, even in the presence of dirty data. We present Sawfish, the first algorithm to discover all similarity inclusion dependencies in a given dataset efficiently. Our algorithm combines approaches for the discovery of traditional INDs and string similarity joins with a novel sliding-window approach and lazy candidate validation. Our experimental evaluation shows that Sawfish can outperform a baseline by a factor of up to 6.5.<\/jats:p>","DOI":"10.1145\/3588929","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-24","source":"Crossref","is-referenced-by-count":14,"title":["Discovering Similarity Inclusion Dependencies"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-6547-592X","authenticated-orcid":false,"given":"Youri","family":"Kaminsky","sequence":"first","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4852-3113","authenticated-orcid":false,"given":"Eduardo H. M.","family":"Pena","sequence":"additional","affiliation":[{"name":"Federal University of Technology - Paran\u00e1, Campo Mour\u00e3o, Brazil"}],"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":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398580"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.369032"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB), 243--254","author":"Bravo Loreto","year":"2007","unstructured":"Loreto Bravo, Wenfei Fan, and Shuai Ma. 2007. Extending dependencies with conditions. In Proceedings of the International Conference on Very Large Databases (VLDB), 243--254."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2472010"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00046"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45876-X_30"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2003.1250899"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","unstructured":"Gy\u00f6rgy D\u00f3sa. 2007. The tight bound of first fit decreasing bin-packing algorithm is FFD(I) \u2264 11\/9OPT(I) 6\/9. In Combinatorics Algorithms Probabilistic and Experimental Methodologies 1--11. doi: 10.1007\/978--3--540--74450--4_1.","DOI":"10.1007\/978--3--540--74450--4_1"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357916"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376940"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0252--8"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1998.655768"},{"key":"e_1_2_2_13_1","unstructured":"Sebastian Kruse Thorsten Papenbrock Christian Dullweber Moritz Finke Manuel Hegner Martin Zabel Christian Z\u00f6llner and Felix Naumann. 2017. Fast approximate discovery of inclusion dependencies. In Datenbanksysteme f\u00fcr Business Technologie und Web (BTW) 207-- 226. https:\/\/dl.gi.de\/20.500.12116\/629."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872518.2889386"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842267"},{"key":"e_1_2_2_16_1","volume-title":"Soviet Physics Doklady number 8.","author":"Levenshtein Vladimir I","unstructured":"Vladimir I Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. In Soviet Physics Doklady number 8. Volume 10, 707--710."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487259.2487261"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.dbm.3240247"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166--218X(90)"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/373626.373713"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824086"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752946"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3392778"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105959"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3021067"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-015--5900--5"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588929","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588929","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:37Z","timestamp":1750178857000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588929"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588929"],"URL":"https:\/\/doi.org\/10.1145\/3588929","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}