Undecidable Optimization Problems for Database Logic Programs

Abstract

Datalog is the language of logic programs without function symbols. It is used as a database query language. If it is possible to eliminate recursion from a Datalog program F�, then t� is said to be bounded. It is shown that the problem of deciding whether a given Datalog program is bounded is undecidable, even for linear programs (i.e., programs in which each rule contains at most one occurrence of a recursive predicate). It is then shown that every semantic property of Datalog programs is undecidable if it is stable, is strongly nontrivial, and contains An earlier version of this work appeared under the same title in the Proceedings of the 2nd IEEE Symposium on Logic in Computer Science (Ithaca, N.Y.). IEEE, New York, 1987, pp. 106-115. Most of the research reported here was done while H. Gaifman was visiting the AI Center of SRI International whose support he wishes to acknowledge. He also wishes to thank IBM Watson Research Center and IBM Almaden Research Center for support in the summer of 1989, when the concluding work on this paper was done. © 1993, ACM. All rights reserved.