Safe Stratified Datalog with Integer Order Programs

. Guaranteeing termination of programs on all valid inputs is important for database applications. Termination cannot be guaranteed in Stratified Datalog with integer (gap)-order, or Datalog :;! Z , programs on generalized databases because they can express any Turingcomputable function [23]. This paper introduces a restriction of Datalog :;! Z that can express only computable queries. The restricted language has a high expressive power and a non-elementary data complexity. 1 Introduction Constraint logic programming [14, 15, 27, 12, 10, 9] has a great potential for being adapted for database use. A successful adaptation of constraint logic programming has to meet usual database requirements. In the constraint query languages framework [19] two requirements are identified as especially important: (a) closed-form evaluation and (b) bottom-up processing. Closed-form evaluation means that all possible tuple answers to a query are represented finitely by an output constraint database ..