Conjunctive Queries: Unique Characterizations and Exact Learnability
Authors:
- Balder Ten CateBCBalder Ten Cate
- Victor DalmauVDVictor Dalmau
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Learning Description Logic Ontologies: Five Approaches. Where Do They Stand?KI - Künstliche Intelligenz, 2020
- Sparsity2012
- Grad and classes with bounded expansion III. Restricted graph homomorphism dualitiesEuropean Journal of Combinatorics, 2008
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structuresEuropean Journal of Combinatorics, 2008
- Grad and classes with bounded expansion I. DecompositionsEuropean Journal of Combinatorics, 2008
- Basic Description Logics2007
- Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism DualitySIAM Journal on Discrete Mathematics, 2005
- Duality Theorems for Finite Structures (Characterising Gaps and Good Characterisations)Journal of Combinatorial Theory, Series B, 2000
- Pac-learning non-recursive prolog clausesArtificial Intelligence, 1995
- Queries and Concept LearningMachine Learning, 1988