Stratified Datalog with integer (gap)-order (or Datalog ¬,< z ) is considered. A Datalog ¬,< z -program is said to be safe if its bottom-up processing terminates on all valid inputs. We prove that safe Datalog ¬,< z programs do not have effective syntax in the sense that there is no recursively enumerable set S of safe Datalog ¬,< z programs such that every safe Datalog ¬,< z program is equivalent to a program in S .

We consider relational databases organized over an ordered domain with some additional relations---a typical example is the ordered domain of rational numbers together with the ternary relation + of addition. In the focus of our study are the first order queries that are invariant under order-preserving "permutations"---such queries are called (order-)generic. We show that for an arbitrary ordered divisible Abelian group order-generic queries fail to express more than pure order queries, and that, moreover, the generic queries can be effectively translated into pure order queries. For example, every order-generic query over rational numbers with + can be effectively rewritten without +. An important difference of this paper from a recent series of related pape...

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.