Boundedness is undecidable for datalog programs with a single recursive rule

DOI10.1016/0020-0190(89)90019-7MaRDI QIDQ1123647zbMATH OpenOpenAlexWikidataFDO

Authors Serge Abiteboul

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90019-7

zbMATH Keywords

boundednessdatabasesdeductive databasesdata processingdatalog

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Undecidable boundedness problems for datalog programs
• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
• About Boundedness for some Datalog and Datalog^neg Programs
• Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs
• PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE

Cites work

• scientific article; zbMATH DE number 4147465 (Why is no real title available?)
• On the foundations of the universal relation model

Cited in

(9)

• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
• scientific article; zbMATH DE number 219219 (Why is no real title available?)
• A semantic approach to optimize linear datalog programs
• Undecidable optimization problems for database logic programs
• On the decidability of the termination problem of active database systems
• On the complexity of single-rule datalog queries.
• About boundedness for some DATALOG and DATALOG\textsuperscript{neg} programs
• Characterizing boundedness in chase variants
• PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Boundedness is undecidable for datalog programs with a single recursive rule

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