# On the non-efficient PAC learnability of conjunctive queries

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 32 references that are in the map.
- First posted on arXiv 22 Aug 2022.

## Builds on (most cited first, 2 of 2)

- [Conjunctive Queries: Unique Characterizations and Exact Learnability](https://mlsanity.com/paper/2008.06824/) (2020)
- [Extremal Fitting Problems for Conjunctive Queries](https://mlsanity.com/paper/2206.05080/) (2022)

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

- [SAT-Based Bounded Fitting for the Description Logic ALC](https://mlsanity.com/paper/2507.21752/) (2025)
- [Fitting Ontologies and Constraints to Relational Structures](https://mlsanity.com/paper/2508.13176/) (2025)

## Abstract (arXiv)

This note serves three purposes: (i) we provide a self-contained exposition of the fact that conjunctive queries are not efficiently learnable in the Probably-Approximately-Correct (PAC) model, paying clear attention to the complicating fact that this concept class lacks the polynomial-size fitting property, a property that is tacitly assumed in much of the computational learning theory literature; (ii) we establish a strong negative PAC learnability result that applies to many restricted classes of conjunctive queries (CQs), including acyclic CQs for a wide range of notions of "acyclicity"; (iii) we show that CQs (and UCQs) are efficiently PAC learnable with membership queries.