Conjunctive queries: unique characterizations and exact learnability

Citació

  • 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

Enllaç permanent

Descripció

  • Resum

    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.
  • Descripció

    Comunicació presentada a: ICDT 2021 celebrat del 23 a 26 de març de 2021 a Nicòsia, Xipre.
  • Mostra el registre complet