Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Conjunctive queries: unique characterizations and exact learnability

  • ten Cate, Balder
  • Dalmau, Víctor
Comunicació 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., Victor Dalmau was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Conjunctive queries: unique characterizations and exact learnability

  • ten Cate, Balder
  • Dalmau, Víctor
Comunicació 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., Victor Dalmau was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22.