# Conjunctive Queries: Unique Characterizations and Exact Learnability

arXiv: https://arxiv.org/abs/2008.06824 · HTML: https://mlsanity.com/paper/2008.06824/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2020.

## Built on by (most cited first, 6 of 6)

- [SAT-Based PAC Learning of Description Logic Concepts](https://mlsanity.com/paper/2305.08511/) (2023)
- [Actively Learning Concepts and Conjunctive Queries under ELr-Ontologies](https://mlsanity.com/paper/2105.08326/) (2021)
- [Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies](https://mlsanity.com/paper/2204.14172/) (2022)
- [On the non-efficient PAC learnability of conjunctive queries](https://mlsanity.com/paper/2208.10255/) (2022)
- [On the Power and Limitations of Examples for Description Logic Concepts](https://mlsanity.com/paper/2412.17345/) (2024)
- [Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology](https://mlsanity.com/paper/2306.07662/) (2023)

## Abstract (arXiv)

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.