Semantic and expressive power of non-deterministic constructs of deductive databases

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.