Semantics and expressive power of nondeterministic constructs in deductive databases

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.