Boundedness is undecidable for datalog programs with a single recursive rule

DOI10.1016/0020-0190(89)90019-7zbMATH Open0677.68103OpenAlexW1983914494WikidataQ51221214 ScholiaQ51221214MaRDI QIDQ1123647FDOQ1123647

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

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

zbMATH Keywords

boundednessdatabasesdeductive databasesdata processingdatalog

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the foundations of the universal relation model

Cited In (9)

• Title not available (Why is that?)
• Undecidable optimization problems for database logic programs
• A semantic approach to optimize linear datalog 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
• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs

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)