Undecidable boundedness problems for datalog programs

• Published in: The journal of logic programming 1995-11, Vol.25 (2), p.163-190
• Main Authors: Hillebrand, Gerd G, Kanellakis, Paris C, Mairson, Harry G, Vardi, Moshe Y
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer science; control theory; systems; Exact sciences and technology; Information systems. Data bases; Memory organisation. Data processing; Programming languages; Software
• ISSN: 0743-1066; 1873-5789
• DOI: 10.1016/0743-1066(95)00051-K

A given Datalog program is bounded if its depth of recursion is independent of the input database. Deciding boundedness is a basic task for the analysis of database logic programs. The undecidability of Datalog boundedness was first demonstrated by Gaifman et al. [7]. We introduce new techniques for proving the undecidability of (various kinds of) boundedness, which allow us to considerably strengthen the results of Gaifman et al. [7]. In particular, (1) we use a new generic reduction technique to show that program boundedness is undecidable for arity 2 predicates, even with linear rules; (2) we use the mortality problem of Turing machines to show that uniform boundedness is undecidable for arity 3 predicates and for arity 1 predicates when ≠ is also allowed; (3) by encoding all possible transitions of a two-counter machine in a single rule, we show that program (resp., predicate) boundedness is undecidable for two linear rules (resp., one rule and a projection) and one initialization rule, where all predicates have small arities (6 or 7).