Conjunctive Queries: Unique Characterizations and Exact Learnability
| Autor: | ten Cate, B., Dalmau, V., Yi, K., Wei, Z. |
|---|---|
| Přispěvatelé: | ILLC (FNWI), Logic and Computation (ILLC, FNWI/FGw) |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science I.2.4 Theory of computation → Machine learning theory Computer Science - Artificial Intelligence I.2.6 H.2.3 68Q32 Schema Mappings Conjunctive Queries Unique Characterizations Databases (cs.DB) Description Logic Homomorphisms Theory of computation → Logic Logic in Computer Science (cs.LO) Frontiers Artificial Intelligence (cs.AI) Computer Science - Databases Exact Learnability Information systems → Query languages Information Systems |
| Zdroj: | ACM Transactions on Database Systems, 47(4):14. Association for Computing Machinery (ACM) 24th International Conference on Database Theory: ICDT 2021, March 23-26, 2021, Nicosia, Cyprus 24th International Conference on Database Theory |
| ISSN: | 1557-4644 0362-5915 |
| DOI: | 10.1145/3559756 |
| Popis: | 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. LIPIcs, Vol. 186, 24th International Conference on Database Theory (ICDT 2021), pages 9:1-9:24 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|