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.
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
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