On the complexity of single-rule datalog queries.

DOI10.1016/S0890-5401(03)00012-9MaRDI QIDQ1401945zbMATH OpenFDO

Authors Georg Gottlob, Christos Papadimitriou

Publication date 19 August 2003

Published in Information and Computation (Search for Journal in Brave)

zbMATH Keywords

DatalogComplexityDescriptive complexityLogic programmingExpressive powerExponential timeLinear recursionSingle rule programSirup clause implicationSubsumption

Mathematics Subject Classification ID

Logic programming (68N17) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 1405452
• scientific article; zbMATH DE number 638303
• On datalog vs polynomial time
• The parallel complexity of single rule logic programs
• Inherent complexity of recursive queries

Cites work

• scientific article; zbMATH DE number 4147465 (Why is no real title available?)
• scientific article; zbMATH DE number 176527 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1256672 (Why is no real title available?)
• scientific article; zbMATH DE number 512814 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• scientific article; zbMATH DE number 3366917 (Why is no real title available?)
• Boundedness is undecidable for datalog programs with a single recursive rule
• Capturing complexity classes by fragments of second-order logic
• Krom formulas with one dyadic predicate letter
• Parallel complexity of logical query programs
• Relational queries computable in polynomial time
• Satisfiability of the smallest binary program
• Subsumption and implication
• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
• The expressive powers of the logic programming semantics
• The parallel complexity of simple logic programs
• Undecidable boundedness problems for datalog programs

Cited in

(16)

• Preserving constraints with the stable chase
• Inherent complexity of recursive queries
• The minimum oracle circuit size problem
• Guarded negation
• Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
• The power of non-ground rules in Answer Set Programming
• A single recursive predicate is sufficient for pure datalog
• Complexity results of STIT fragments
• A tetrachotomy of ontology-mediated queries with a covering axiom
• On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
• Query languages for data exchange: beyond unions of conjunctive queries
• The Complexity of Datalog on Linear Orders
• Relaxed notions of schema mapping equivalence revisited
• The complexity of higher-order queries
• The parallel complexity of single rule logic programs
• scientific article; zbMATH DE number 1405452 (Why is no real title available?)

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: On the complexity of single-rule datalog queries.

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