Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs

DOI10.1137/S0097539797322140MaRDI QIDQ4268878zbMATH OpenOpenAlexWikidataFDO

Authors Jerzy Marcinkowski

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539797322140

zbMATH Keywords

DATALOGdecidabilityquery optimization

Mathematics Subject Classification ID

Database theory (68P15)

Recommendations

• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
• Undecidable boundedness problems for datalog programs
• Boundedness is undecidable for datalog programs with a single recursive rule
• About Boundedness for some Datalog and Datalog^neg Programs

Cited in

(10)

• Boundedness is undecidable for datalog programs with a single recursive rule
• A tetrachotomy of ontology-mediated queries with a covering axiom
• Undecidable boundedness problems for datalog programs
• Undecidable optimization problems for database logic programs
• PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE
• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
• Restricted chase termination for existential rules: a hierarchical approach and experimentation
• Characterizing boundedness in chase variants
• On the k-Boundedness for Existential Rules
• Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs

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