## Paper: Undecidable Optimization Problems for Database Logic Programs (at LICS 1987)

**Haim Gaifman Harry G. Mairson Yehoshua Sagiv Moshe Y. Vardi**

### 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 *P*, then *P* is said to
be *bounded*. We show that the problem of deciding whether a given Datalog
program is bounded is undecidable, even for linear programs (i.e. programs
where each rule contains at most one occurrence of a recursive predicate). We
then show that every strongly nontrivial semantic property of Datalog programs
that contain boundedness is undecidable.

### BibTeX

@InProceedings{GaifmanMairsonSagiv-UndecidableOptimiza, author = {Haim Gaifman and Harry G. Mairson and Yehoshua Sagiv and Moshe Y. Vardi}, title = {Undecidable Optimization Problems for Database Logic Programs}, booktitle = {Proceedings of the Second Annual IEEE Symposium on Logic in Computer Science (LICS 1987)}, year = {1987}, month = {June}, pages = {106--115 }, location = {Ithaca, NY, USA}, publisher = {IEEE Computer Society Press} }