论文标题
连词查询：独特的特征和精确的可学习性
Conjunctive Queries: Unique Characterizations and Exact Learnability
论文作者
论文摘要
我们回答以下问题，哪些结合性查询的特征在于多种正面和负面的示例，以及如何有效地构建此类示例。结果，我们为一类连接的查询获得了一种新的有效的精确学习算法。我们贡献的核心是两个新的多项式时间算法，用于在有限结构的同态晶格中构建前沿。我们还讨论了模式映射和描述逻辑概念的独特特征性和可学习性的影响。
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.
