UNDECIDABLE OPTIMIZATION PROBLEMS FOR DATABASE LOGIC PROGRAMS

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. It i s shown that the problem of deciding whether a given Datalog program i s bounded is undecidable, even for linear programs (i.e., programs in which each rule contains at most one occurrence of a recursive predica te). It is then shown that every semantic property of Datalog programs is undecidable if it is stable, is strongly nontrivial, and contains