Prediction-hardness of acyclic conjunctive queries

DOI10.1016/j.tcs.2005.09.006zbMath1081.68016OpenAlexW2088471214MaRDI QIDQ2581365

Kouichi Hirata

Publication date: 10 January 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.006

zbMATH Keywords

Inductive logic programmingPredictionSubsumptionAcyclic conjunctive queryPrediction-preserving reduction

Mathematics Subject Classification ID

Database theory (68P15)

Related Items (1)

On the non-efficient PAC learnability of conjunctive queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Prediction-preserving reducibility
• Subsumption and implication
• First-order \(jk\)-clausal theories are PAC-learnable
• Conjunctive query containment revisited
• Learning function-free Horn expressions
• Learning action strategies for planning domains
• On the Desirability of Acyclic Database Schemes
• Degrees of acyclicity for hypergraphs and relational database schemes
• The complexity of acyclic conjunctive queries
• A theory of the learnable
• Cryptographic limitations on learning Boolean formulae and finite automata
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Pac-learning non-recursive Prolog clauses
• Learning logic programs with structured background knowledge

This page was built for publication: Prediction-hardness of acyclic conjunctive queries