PUMA
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.
 
 
Abstract
(English)
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