Conjunctive Queries: Unique Characterizations and Exact Learnability
Open Access
- 6 November 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 47 (4) , 1-41
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.Keywords
All Related Versions
Funding Information
- MICCIN (TIN2016-76573-C2-1P, and PID2019-109137GB-C22)
- European Union’s Horizon 2020 (MSCA-101031081)
This publication has 29 references indexed in Scilit:
- Characterizing schema mappings via data examplesACM Transactions on Database Systems, 2011
- Schema mapping discovery from data instancesJournal of the ACM, 2010
- 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
- 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
- The core of a graphDiscrete Mathematics, 1992
- Degrees of acyclicity for hypergraphs and relational database schemesJournal of the ACM, 1983