Boundedness is undecidable for datalog programs with a single recursive rule

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

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)

Cites Work

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

Cited In (9)

• Characterizing Boundedness in Chase Variants
• About boundedness for some datalog and DATALOGneg programs
• 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.
• 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)