On the non-efficient PAC learnability of conjunctive queries

DOI10.1016/J.IPL.2023.106431MaRDI QIDQ6072217zbMATH OpenFDO

Authors Balder ten Cate, Maurice Funk, Jean Christoph Jung, Carsten Lutz

Publication date 12 October 2023

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2208.10255

zbMATH Keywords

computational learning theoryconjunctive queriesdatabasesinductive logic programming

Mathematics Subject Classification ID

Logic programming (68N17) Database theory (68P15) Computational learning theory (68Q32)

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 are efficiently PAC learnable with membership queries.

Recommendations

• scientific article; zbMATH DE number 2080453
• Learnability of solutions to conjunctive queries
• Prediction-hardness of acyclic conjunctive queries
• Learning unions of tree patterns using queries
• scientific article; zbMATH DE number 1301789

Cites work

• A dichotomy theorem for learning quantified Boolean formulas
• A theory of the learnable
• Computational limitations on learning from examples
• Degrees of acyclicity for hypergraphs and relational database schemes
• Equivalence of models for polynomial learnability
• Foundations of inductive logic programming
• scientific article; zbMATH DE number 53984 (Why is no real title available?)
• scientific article; zbMATH DE number 795584 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• Learnability of quantified formulas.
• Learnability of solutions to conjunctive queries
• Learning closed Horn expressions
• Learning schema mappings
• Prediction-hardness of acyclic conjunctive queries
• Queries and concept learning
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The product homomorphism problem and applications
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries

This page was built for publication: On the non-efficient PAC learnability of conjunctive queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072217)