DATALOG WITH NONDETERMINISTIC CHOICE COMPUTES NDB-PTIME

This paper addresses the issue of non-deterministic extensions of logi c database languages. After providing a brief overview of the main pro posals in the literature, we concentrate on the analysis of the dynami c choice construct from the point of view of the expressive power. We show how such construct is capable of expressing several interesting d eterministic problems, such as computing the complement of a relation, and non-deterministic ones, such as computing an ordering of a relati on. We then prove that Datalog augmented with the dynamic choice expre sses exactly the non-deterministic time-polynomial queries. We thus ob tain 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. (C) 1998 Elsevi er Science Inc. All rights reserved.