Datalog with non deterministic choice computers NDB-PTIME

This paper addresses the issue of non deterministic extensions of logic database languages. After providing an overview of the main proposals in the literature, we concentrate on the analysis of the dynamic choice construct from the point of view of the expressive power. We show how such construct is capable of expressing several interesting deterministic and non deterministic problems, such as forms of negation, and ordering. We then prove that Datalog augmented with the dynamic choice expresses exactly the non deterministic time-polynomial queries. We thus obtain a complete characterization of the class of queries NDB-PTIME by means of a simple, declarative, and efficiently implementable language.