ten Cate, BalderDalmau, Víctor2023-02-012023-02-012021ten Cate B, Dalmau V. Conjunctive queries: unique characterizations and exact learnability. In: Ke Y, Wei Z, editors. 24th International Conference on Database Theory (ICDT 2021); 2021 Mar 23-26; Nicosia, Cyprus. Germany: Dagstuhl Publishing; 2021. 24 p. DOI: 10.4230/LIPIcs.ICDT.2021.91868-8969http://hdl.handle.net/10230/55516Comunicació presentada a: ICDT 2021 celebrat del 23 a 26 de març de 2021 a Nicòsia, Xipre.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.application/pdfeng© Balder ten Cate and Victor Dalmau; licensed under Creative Commons License CC-BY 4.0.info:eu-repo/semantics/conferenceObjecthttp://dx.doi.org/10.4230/LIPIcs.ICDT.2021.9Conjunctive QueriesHomomorphismsFrontiersUnique CharacterizationsExact LearnabilitySchema MappingsDescription Logicinfo:eu-repo/semantics/openAccess