Conjunctive queries: unique characterizations and exact learnability

Mostra el registre complet Registre parcial de l'ítem

  • dc.contributor.author ten Cate, Balder
  • dc.contributor.author Dalmau, Víctor
  • dc.date.accessioned 2023-02-01T13:25:19Z
  • dc.date.available 2023-02-01T13:25:19Z
  • dc.date.issued 2021
  • dc.description Comunicació presentada a: ICDT 2021 celebrat del 23 a 26 de març de 2021 a Nicòsia, Xipre.
  • dc.description.abstract 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.
  • dc.description.sponsorship Victor Dalmau was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22.
  • dc.format.mimetype application/pdf
  • dc.identifier.citation ten 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.9
  • dc.identifier.doi http://dx.doi.org/10.4230/LIPIcs.ICDT.2021.9
  • dc.identifier.issn 1868-8969
  • dc.identifier.uri http://hdl.handle.net/10230/55516
  • dc.language.iso eng
  • dc.publisher Dagstuhl Publishing
  • dc.relation.ispartof 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.
  • dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/PID2019-109137G
  • dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/TIN2016-76573-C2-1P
  • dc.rights © Balder ten Cate and Victor Dalmau; licensed under Creative Commons License CC-BY 4.0.
  • dc.rights.accessRights info:eu-repo/semantics/openAccess
  • dc.rights.uri http://creativecommons.org/licenses/by/4.0/
  • dc.subject.keyword Conjunctive Queries
  • dc.subject.keyword Homomorphisms
  • dc.subject.keyword Frontiers
  • dc.subject.keyword Unique Characterizations
  • dc.subject.keyword Exact Learnability
  • dc.subject.keyword Schema Mappings
  • dc.subject.keyword Description Logic
  • dc.title Conjunctive queries: unique characterizations and exact learnability
  • dc.type info:eu-repo/semantics/conferenceObject
  • dc.type.version info:eu-repo/semantics/publishedVersion

Col·leccions

Congressos (Departament de Tecnologies de la Informació i les Comunicacions)