On the non-efficient PAC learnability of conjunctive queries |
| |
Affiliation: | 1. ILLC, University of Amsterdam, Postbus 94242, Amsterdam, 1090 GE, the Netherlands;2. Leipzig University, Augustusplatz 10, Leipzig, 04109, Germany;3. TU Dortmund University, August-Schmidt-Straß e 1, Dortmund, 44227, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Computational learning theory Conjunctive queries Inductive logic programming Databases |
本文献已被 ScienceDirect 等数据库收录! |
|