On the non-efficient PAC learnability of conjunctive queries
This addresses a foundational issue in computational learning theory for researchers, clarifying limitations and conditions for learning CQs, with incremental results on restricted classes.
The paper tackles the problem of whether conjunctive queries (CQs) are efficiently learnable in the PAC model, showing they are not efficiently learnable without membership queries, but are efficiently learnable with membership queries.
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.