Istituto di Scienza e Tecnologie dell'Informazione     
Giannotti F., Pedreschi D., Zaniolo C. Semantic and expressive power of non-deterministic constructs of deductive databases. Internal note CNUCE-B4-96-004, 1996.
Non deterministic extensions of First-Order relational languages and Datalog are needed to enhance the expressive power of such languages, and support efficient formulations of low-complexity problems. In this paper, we study semantics and expressiveness of the various non deterministic constructs proposed in the past, including various versions of the choice operator and the witness operator. We begin by formalizing declarative and fixpoint semantics, and operational semantics of these constructs, and analyze their power of expressing deterministic and non-deterministic queries. The paper presents various soundness and completeness results and an expressiveness hierarchy that relates the various operators with each other and other constructs, such as negation and fixpoint.
Subject deductive databases
logic-based languages
non determinism, expressive power
expressive power
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