Istituto di Scienza e Tecnologie dell'Informazione     
Giannotti F., Pedreschi D. Datalog with non deterministic choice computers NDB-PTIME. Internal note CNUCE-B4-96-003, 1996.
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.
Subject Logic programming
H.2.8 Databases applications
H.2.3 Databases management. Languages

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional