On the non-efficient PAC learnability of conjunctive 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheorySimilar Papers 제목 키워드 기반
Conjunctive Queries: Unique Characterizations and Exact Learnability
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…
Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
Description Logics are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries, the standard query language in databases, have recently gained…
First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics
We study FO-rewritability of conjunctive queries in the presence of ontologies formulated in a description logic between EL and Horn-SHIF, along with related query containment problems. Apart from providing characterizat…
Mapping-equivalence and oid-equivalence of single-function object-creating conjunctive queries
Conjunctive database queries have been extended with a mechanism for object creation to capture important applications such as data exchange, data integration, and ontology-based data access. Object creation generates ne…
Data IntegrationObjectAnswering Complex Queries in Knowledge Graphs with Bidirectional Sequence Encoders
Representation learning for knowledge graphs (KGs) has focused on the problem of answering simple link prediction queries. In this work we address the more ambitious challenge of predicting the answers of conjunctive que…
Knowledge GraphsLink PredictionRepresentation Learning