PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Giannotti F., Pedreschi D., Zaniolo C. Semantics and expressive power of nondeterministic constructs in deductive databases. In: Journal of Computer and System Sciences, vol. 62 (1) pp. 15 - 42. Academic Press, 2001.
 
 
Abstract
(English)
Nondeterministic extensions are needed in logic-based languages, such as first-order relational languages and Datalog, to enhance their expressive power and support the efficient formulation of low-complexity problems and database queries. In this paper, we study the semantics and expressive power of the various nondeterministic constructs proposed in the past, including various versions of the choice operator and the witness operator. The paper develops a model-theoretic semantics, a fixpoint semantics, and an opera- tional semantics for these constructs, and characterizes their power of expressing deterministic and nondeterministic queries. The paper presents various soundness and completeness results and establishes an expressiveness hierarchy that correlates the various operators with each other and with other constructs such as negation and fixpoint.
Subject deductive databases
logic-based languages
nondeterminism
H.2.3 Databases management. Languages
D.1.6 Programming techniques. Logic programming


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