Conjunctive Queries: Unique Characterizations and Exact Learnability
| Authors |
|
|---|---|
| Publication date | 03-2021 |
| Host editors |
|
| Book title | 24th International Conference on Database Theory |
| Book subtitle | ICDT 2021, March 23-26, 2021, Nicosia, Cyprus |
| ISBN (electronic) |
|
| Series | Leibniz International Proceedings in Informatics |
| Event | International Conference on Database Theory (ICDT 2021) |
| Article number | 9 |
| Number of pages | 24 |
| Publisher | Saarbrücken/Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Organisations |
|
| 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. |
| Document type | Conference contribution |
| Language | English |
| Related publication | Conjunctive Queries: Unique Characterizations and Exact Learnability |
| Published at | https://doi.org/10.4230/LIPIcs.ICDT.2021.9 |
| Published at | https://arxiv.org/abs/2008.06824 |
| Downloads |
LIPIcs-ICDT-2021-9
(Final published version)
|
| Permalink to this page | |
