On the complexity of single-rule datalog queries.

DOI10.1016/S0890-5401(03)00012-9zbMath1055.68033MaRDI QIDQ1401945

Georg Gottlob, Christos H. Papadimitriou

Publication date: 19 August 2003

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

zbMATH Keywords

Logic programmingComplexityDatalogDescriptive complexityExpressive powerExponential timeLinear recursionSingle rule programSirup clause implicationSubsumption

Mathematics Subject Classification ID

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

Related Items

Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies, A tetrachotomy of ontology-mediated queries with a covering axiom, Relaxed notions of schema mapping equivalence revisited, Preserving Constraints with the Stable Chase, The minimum oracle circuit size problem, Complexity results of STIT fragments, The power of non-ground rules in Answer Set Programming, Query languages for data exchange: beyond unions of conjunctive queries, The complexity of higher-order queries, Guarded Negation, On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules

Uses Software

• Datalog

Cites Work

• Subsumption and implication
• Parallel complexity of logical query programs
• Boundedness is undecidable for datalog programs with a single recursive rule
• Capturing complexity classes by fragments of second-order logic
• The expressive powers of the logic programming semantics
• Satisfiability of the smallest binary program
• Undecidable boundedness problems for datalog programs
• Relational queries computable in polynomial time
• Krom formulas with one dyadic predicate letter
• The parallel complexity of simple logic programs
• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item