Finite queries do not have effective syntax
Alexei P. Stolboushkin, Michael A. Taitslin · 1995
A relational query is called finite, or sometimes safe, iff it yields a finite answer in every database state.The set of finite queries of relational calculus is known to be unsolvable.However, in many cases it is possible to impose syntactical restrictions on the class of queries that guarantee finiteness and do not reduce the expressive power of the calculus.We show that unfortunately this is not always the case, as we construct a recursive domain with decidable theory where any solvable (or enumerable, for that matter) subclsss of queries either contains an infinite query, or misses a finite one.Using the same example, we further show undecidability of the problem of state-jinitene.w,which is, given a query and a database state, to decide upon finiteness of the query in this state.ThB settles two long-standing open problems in the theory of relational databases.