{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:17:10Z","timestamp":1761808630900,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T00:00:00Z","timestamp":1674086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2023,1,19]]},"abstract":"<jats:p>A fitting algorithm for conjunctive queries (CQs) is an algorithm that takes as input a collection of data examples and outputs a CQ that fits the examples. In this column, we propose a set of desirable properties of such algorithms and use this as a guide for surveying results from the authors' recent papers published in PODS 2023, IJCAI 2023, and Inf. Proc. Letters 2024. In particular, we explain and compare several concrete fitting algorithms, and we discuss complexity and size bounds for constructing fitting CQs with desirable properties.<\/jats:p>","DOI":"10.1145\/3641832.3641834","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T05:22:35Z","timestamp":1705728155000},"page":"6-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fitting Algorithms for Conjunctive Queries"],"prefix":"10.1145","volume":"52","author":[{"given":"Balder","family":"ten Cate","sequence":"first","affiliation":[{"name":"ILLC, University of Amsterdam"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maurice","family":"Funk","sequence":"additional","affiliation":[{"name":"Leipzig University and ScaDS.AI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean","family":"Christoph Jung","sequence":"additional","affiliation":[{"name":"TU Dortmund University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Lutz","sequence":"additional","affiliation":[{"name":"Leipzig University and ScaDS.AI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043656"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989338"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116828"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2882989"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-8638-3"},{"key":"e_1_2_1_6_1","first-page":"319","volume-title":"Proc. KR","author":"Baader F.","year":"2018","unstructured":"F. Baader, F. Kriegel, A. Nuradiansyah, and R. Penaloza. Making repairs in description logics more gentle. In Proc. KR, pages 319--328, 2018."},{"key":"e_1_2_1_7_1","first-page":"1","volume-title":"Proc. of ICDT","author":"Barcel\u00b4o P.","year":"2017","unstructured":"P. Barcel\u00b4o and M. Romero. The complexity of reverse engineering problems for conjunctive queries. In Proc. of ICDT, pages 7:1--7:17, 2017."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.01.003"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_2_1_10_1","first-page":"109","volume-title":"Proc. of EDBT","author":"Bonifati A.","year":"2015","unstructured":"A. Bonifati, R. Ciucanu, and A. Lemay. Learning path queries on graph databases. In Proc. of EDBT, pages 109--120, 2015."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2016.06.001"},{"key":"e_1_2_1_12_1","first-page":"161","volume-title":"Proc. of ICDT","author":"B.","year":"2015","unstructured":"B. ten Cate and V. Dalmau. The product homomorphism problem and applications. In Proc. of ICDT, pages 161--176, 2015."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3559756"},{"key":"e_1_2_1_14_1","volume-title":"Proc. of PODS","author":"Cate B.","year":"2023","unstructured":"B. ten Cate, V. Dalmau, M. Funk, and C. Lutz. Extremal fitting problems for conjunctive queries. In Proc. of PODS, 2023."},{"key":"e_1_2_1_15_1","volume-title":"M. Funk, J. C. Jung, and C. Lutz. Extremal fitting CQs do not generalize. CoRR, abs\/2312.03407","author":"B.","year":"2023","unstructured":"B. ten Cate, M. Funk, J. C. Jung, and C. Lutz. Extremal fitting CQs do not generalize. CoRR, abs\/2312.03407, 2023."},{"key":"e_1_2_1_16_1","first-page":"3347","volume-title":"Proc. IJCAI","author":"Cate B.","year":"2023","unstructured":"B. ten Cate, M. Funk, J. C. Jung, and C. Lutz. SAT-based PAC learning of description logic concepts. In Proc. IJCAI, pages 3347--3355, 2023."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2023.106431"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3044712"},{"key":"e_1_2_1_19_1","first-page":"307","volume-title":"Proc. of ECML","author":"P. R.","year":"1994","unstructured":"P. R. J. Laag van der Laag and S. Nienhuys-Cheng. Existence and nonexistence of complete refinement operators. In Proc. of ECML, pages 307--322, 1994."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2890492"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-021-06089-1"},{"key":"e_1_2_1_22_1","volume-title":"Constructing queries from data examples","author":"Filipetto V.","year":"2022","unstructured":"V. Filipetto. Constructing queries from data examples, 2022. MSc Thesis. University of Amsterdam."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.221"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.017"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/233"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2022\/364"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037582"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667055"},{"key":"e_1_2_1_29_1","first-page":"1","article-title":"Refined error bounds for several learning algorithms","volume":"17","author":"Hanneke S.","year":"2016","unstructured":"S. Hanneke. Refined error bounds for several learning algorithms. J. Mach. Learn. Res., 17:1--55, 2016.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3277006.3277009"},{"key":"e_1_2_1_31_1","volume-title":"Proc. of DL","author":"Kriegel F.","year":"2021","unstructured":"F. Kriegel. Navigating the EL subsumption hierarchy. In Proc. of DL, 2021."},{"key":"e_1_2_1_32_1","first-page":"73","volume-title":"Proc. of ILP","author":"Lehmann J.","year":"2009","unstructured":"J. Lehmann and C. Haase. Ideal downward refinement in the EL description logic. In Proc. of ILP, pages 73--87, 2009."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831369"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/541177"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62927-0"},{"key":"e_1_2_1_36_1","volume-title":"Lattice theoretic properties of subsumption. Technical report","author":"Plotkin G.","year":"1970","unstructured":"G. Plotkin. Lattice theoretic properties of subsumption. Technical report, Edinburgh University, Dept. of Machine Intelligence and Perception, 1970."},{"key":"e_1_2_1_37_1","first-page":"446","volume-title":"Proc. of IJCAI","author":"Shapiro E. Y.","year":"1981","unstructured":"E. Y. Shapiro. An algorithm that infers theories from facts. In P. J. Hayes, editor, Proc. of IJCAI, pages 446--451, 1981."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0349-3"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15396-9_4"},{"key":"e_1_2_1_41_1","first-page":"431","volume-title":"Proc. of AFIPS NCC","author":"Zloof M. M.","year":"1975","unstructured":"M. M. Zloof. Query by example. In Proc. of AFIPS NCC, pages 431--438. AFIPS Press, May 1975."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3641832.3641834","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3641832.3641834","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:04:03Z","timestamp":1750291443000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3641832.3641834"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,19]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,1,19]]}},"alternative-id":["10.1145\/3641832.3641834"],"URL":"https:\/\/doi.org\/10.1145\/3641832.3641834","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2023,1,19]]},"assertion":[{"value":"2024-01-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}