Conjunctive queries: unique characterizations and exact learnability
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.