On the complexity of single-rule datalog queries.

DOI10.1016/S0890-5401(03)00012-9zbMATH Open1055.68033MaRDI QIDQ1401945FDOQ1401945

Authors: Georg Gottlob, Christos Papadimitriou 

Publication date: 19 August 2003

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

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

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)

Cites Work

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

Cited In (16)

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

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)