About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM (JACM)
Paper
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.