{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:58:48Z","timestamp":1758272328786,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,11,6]],"date-time":"2022-11-06T00:00:00Z","timestamp":1667692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MICCIN","award":["TIN2016-76573-C2-1P, and PID2019-109137GB-C22"],"award-info":[{"award-number":["TIN2016-76573-C2-1P, and PID2019-109137GB-C22"]}]},{"name":"European Union\u2019s Horizon 2020","award":["MSCA-101031081"],"award-info":[{"award-number":["MSCA-101031081"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>We answer the question of which conjunctive queries are uniquely characterized by polynomially many positive and negative examples and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for a class of conjunctive queries. At the core of our contributions lie two new polynomial-time algorithms for constructing frontiers in the homomorphism lattice of finite structures. We also discuss implications for the unique characterizability and learnability of schema mappings and of description logic concepts.<\/jats:p>","DOI":"10.1145\/3559756","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T12:37:59Z","timestamp":1661949479000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Conjunctive Queries: Unique Characterizations and Exact Learnability"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2538-5846","authenticated-orcid":false,"given":"Balder Ten","family":"Cate","sequence":"first","affiliation":[{"name":"Universiteit van Amsterdam, Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9365-7372","authenticated-orcid":false,"given":"Victor","family":"Dalmau","sequence":"additional","affiliation":[{"name":"Universitat Pompeu Fabra, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,6]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2","DOI":"10.1145\/2043652.2043656"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_2","DOI":"10.1023\/A:1022821128753"},{"key":"e_1_3_2_4_2","volume-title":"IFIP Congress","author":"Armstrong William Ward","year":"1974","unstructured":"William Ward Armstrong. 1974. Dependency structures of data base relationships. In IFIP Congress."},{"doi-asserted-by":"publisher","key":"e_1_3_2_5_2","DOI":"10.1017\/9781139025355"},{"key":"e_1_3_2_6_2","first-page":"43","volume-title":"Basic Description Logics","author":"Baader Franz","year":"2003","unstructured":"Franz Baader and Werner Nutt. 2003. Basic Description Logics. Cambridge University Press, 43\u201395."},{"doi-asserted-by":"publisher","key":"e_1_3_2_7_2","DOI":"10.2168\/LMCS-10(2:3)2014"},{"key":"e_1_3_2_8_2","first-page":"7:1\u20137:17","volume-title":"Proceedings of the 20th International Conference on Database Theory","author":"Barcel\u00f3 Pablo","year":"2017","unstructured":"Pablo Barcel\u00f3 and Miguel Romero. 2017. The complexity of reverse engineering problems for conjunctive queries. In Proceedings of the 20th International Conference on Database Theory. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 7:1\u20137:17."},{"unstructured":"Google Blog. 2020. A reintroduction to our Knowledge Graph and knowledge panels. https:\/\/blog.google\/products\/search\/about-knowledge-graph-and-knowledge-panels\/.","key":"e_1_3_2_9_2"},{"key":"e_1_3_2_10_2","first-page":"109","volume-title":"Proceedings of the 18th International Conference on Extending Database Technology","author":"Bonifati Angela","year":"2015","unstructured":"Angela Bonifati, Radu Ciucanu, and Aur\u00e9lien Lemay. 2015. Learning path queries on graph databases. In Proceedings of the 18th International Conference on Extending Database Technology. OpenProceedings.org, 109\u2013120."},{"issue":"4","key":"e_1_3_2_11_2","first-page":"24:1\u201324:38","article-title":"Learning join queries from user examples","volume":"40","author":"Bonifati Angela","year":"2016","unstructured":"Angela Bonifati, Radu Ciucanu, and Slawek Staworko. 2016. Learning join queries from user examples. ACM Trans. Datab. Syst. 40, 4 (2016), 24:1\u201324:38.","journal-title":"ACM Trans. Datab. Syst."},{"doi-asserted-by":"publisher","key":"e_1_3_2_12_2","DOI":"10.1145\/800105.803397"},{"key":"e_1_3_2_13_2","first-page":"80","volume-title":"Proceedings of the 11th National Conference on Artificial Intelligence","author":"Cohen William W.","year":"1993","unstructured":"William W. Cohen. 1993. Cryptographic limitations on learning one-clause logic programs. In Proceedings of the 11th National Conference on Artificial Intelligence. AAAI Press\/The MIT Press, 80\u201385."},{"key":"e_1_3_2_14_2","first-page":"676","volume-title":"Proceedings of the 12th National Conference on Artificial Intelligence","author":"Cohen William W.","year":"1994","unstructured":"William W. Cohen. 1994. PAC-learning nondeterminate clauses. In Proceedings of the 12th National Conference on Artificial Intelligence. AAAI Press\/The MIT Press, 676\u2013681."},{"doi-asserted-by":"publisher","key":"e_1_3_2_15_2","DOI":"10.1016\/0004-3702(94)00034-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_16_2","DOI":"10.1007\/3-540-46135-3_21"},{"doi-asserted-by":"publisher","key":"e_1_3_2_17_2","DOI":"10.1145\/2402.322390"},{"doi-asserted-by":"publisher","key":"e_1_3_2_18_2","DOI":"10.1145\/1376916.1376922"},{"doi-asserted-by":"publisher","key":"e_1_3_2_19_2","DOI":"10.1016\/j.ejc.2007.11.017"},{"doi-asserted-by":"publisher","key":"e_1_3_2_20_2","DOI":"10.24963\/ijcai.2021\/260"},{"doi-asserted-by":"publisher","key":"e_1_3_2_21_2","DOI":"10.24963\/ijcai.2022\/364"},{"doi-asserted-by":"publisher","key":"e_1_3_2_22_2","DOI":"10.1145\/1667053.1667055"},{"doi-asserted-by":"publisher","key":"e_1_3_2_23_2","DOI":"10.1023\/A:1022601210986"},{"doi-asserted-by":"publisher","key":"e_1_3_2_24_2","DOI":"10.1016\/0012-365X(92)90282-K"},{"doi-asserted-by":"publisher","key":"e_1_3_2_25_2","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"doi-asserted-by":"publisher","key":"e_1_3_2_26_2","DOI":"10.5555\/647718.735908"},{"key":"e_1_3_2_27_2","article-title":"First-order queries on classes of structures with bounded expansion","volume":"16","author":"Kazana Wojtek","year":"2020","unstructured":"Wojtek Kazana and Luc Segoufin. 2020. First-order queries on classes of structures with bounded expansion. Logic. Meth. Comput. Sci. 16, 1 (Feb. 2020).","journal-title":"Logic. Meth. Comput. Sci."},{"doi-asserted-by":"publisher","key":"e_1_3_2_28_2","DOI":"10.1145\/1065167.1065176"},{"doi-asserted-by":"publisher","key":"e_1_3_2_29_2","DOI":"10.1145\/6012.15415"},{"key":"e_1_3_2_30_2","volume-title":"Proceedings of the International Workshop on Description Logics","author":"Marx Maarten","year":"2002","unstructured":"Maarten Marx. 2002. Narcissists, stepmothers and spies. In Proceedings of the International Workshop on Description Logics. CEUR-WS.org."},{"doi-asserted-by":"publisher","key":"e_1_3_2_31_2","DOI":"10.1016\/j.ejc.2007.11.019"},{"doi-asserted-by":"publisher","key":"e_1_3_2_32_2","DOI":"10.1016\/j.ejc.2006.07.013"},{"doi-asserted-by":"publisher","key":"e_1_3_2_33_2","DOI":"10.1007\/978-3-642-27875-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_34_2","DOI":"10.1006\/jctb.2000.1970"},{"doi-asserted-by":"publisher","key":"e_1_3_2_35_2","DOI":"10.1137\/S0895480104445630"},{"doi-asserted-by":"publisher","key":"e_1_3_2_36_2","DOI":"10.1007\/s13218-020-00656-9"},{"doi-asserted-by":"publisher","key":"e_1_3_2_37_2","DOI":"10.1145\/2274576.2274592"},{"key":"e_1_3_2_38_2","volume-title":"Proceedings of the International Conference on Database Theory.","author":"Staworko Slawomir","year":"2015","unstructured":"Slawomir Staworko and Piotr Wieczorek. 2015. Characterizing XML twig queries with examples. In Proceedings of the International Conference on Database Theory.https:\/\/hal.inria.fr\/hal-01205417."},{"doi-asserted-by":"publisher","key":"e_1_3_2_39_2","DOI":"10.14778\/1687627.1687741"},{"key":"e_1_3_2_40_2","first-page":"161","volume-title":"Proceedings of the 18th International Conference on Database Theory","author":"Cate Balder ten","year":"2015","unstructured":"Balder ten Cate and V\u00edctor Dalmau. 2015. The product homomorphism problem and applications. In Proceedings of the 18th International Conference on Database Theory. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 161\u2013176."},{"key":"e_1_3_2_41_2","volume-title":"Proceedings of the International Conference on Database Theory","author":"Cate Balder ten","year":"2021","unstructured":"Balder ten Cate and Victor Dalmau. 2021. Conjunctive queries: Unique characterizations and exact learnability. In Proceedings of the International Conference on Database Theory. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"doi-asserted-by":"publisher","key":"e_1_3_2_42_2","DOI":"10.1145\/2539032.2539035"},{"doi-asserted-by":"publisher","key":"e_1_3_2_43_2","DOI":"10.1145\/3196959.3196974"},{"doi-asserted-by":"publisher","key":"e_1_3_2_44_2","DOI":"10.1145\/3034786.3056112"},{"doi-asserted-by":"publisher","key":"e_1_3_2_45_2","DOI":"10.5555\/1886008.1886014"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559756","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3559756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:07:57Z","timestamp":1750183677000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559756"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,6]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3559756"],"URL":"https:\/\/doi.org\/10.1145\/3559756","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2022,11,6]]},"assertion":[{"value":"2021-11-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}