Semi-Inflationary DATALOG : A declarative Database Language with Procedural Features

This paper presents a rule-based database language which extends stratified DATALOG by adding a controlled form of inflationary fixpoint, immersed in a context of classical stratified negation with least fixpoint. The proposed language, called Semi-Inflationary DATALOG (DATALOG@(*) for short), smoothly combines the declarative purity of stratified negation with the procedural style of the inflationary fixpoint, DATALOG@(*) is particularly suitable to express algorithms in a mixed style: declarative rules, whenever it is natural and convenient, and procedural ones, any time it is easier to list the sequence of single actions. In the latter case, in order not to oblige the programmer to supply unnecessary procedural details, a number of choice constructs are available to express don't care non-determinism. The semantics of a DATALOG@(*) program is given using stable models by means of rule rewriting into a DATALOG program with choice and XY-stratification. In addition the complexity and expressive power of DATALOG@(*) queries is precisely characterized and some lights are put on the related class NQPTIME as well.