FUNDAMENTAL PROPERTIES OF DETERMINISTIC AND NONDETERMINISTIC EXTENSIONS OF DATALOG

Fundamental properties of deterministic and nondeterministic extensions of Datalog from Abiteboul and Vianu (1988) are studied. The extensions involve the use of negative literals both in bodies and heads of rules. Negative literals in heads are interpreted as deletions. A deterministic semantics is obtained by firing in parallel all applicable rules. The nondeterministic semantics results from firing (nondeterministically) one rule at a time. In the nondeterministic case, programs do not describe functions but relations between database states. In both cases, the result is an increase in expressive power over Datalog. The price for it is that programs do not always terminate. We study when a program (i) is such that on a given input, all its successful computations reach a unique fixpoint, (ii) yields at least one output on every input and (iii) has only loop-free computations. We also show how to stimulate programs containing loops by loop-free programs.