Datalog with non-deterministic choice computes NDB-PTIME

AbstractThis paper addresses the issue of non-deterministic extensions of logic database languages. After providing a brief 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 problems, such as computing the complement of a relation, and non-deterministic ones, such as computing an ordering of a relation. 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 expressiveness of the dynamic choice, and conversely achieve a characterization of the class of non-deterministic time-polynomial queries (NDB-PTIME) by means of a simple, declarative, and efficiently implementable language