Conjunctive Queries: Unique Characterizations and Exact Learnability
This work solves a theoretical problem in database query learning, with potential applications in schema mappings and description logic, but it appears incremental as it builds on existing frontiers in homomorphism lattices.
The paper addresses which conjunctive queries can be uniquely identified using a polynomial number of positive and negative examples, and it develops an efficient exact learning algorithm for a class of such queries.
We answer the question 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.