Expressive Power of Non-Deterministic Operators for Logic-based Languages.
Luca Corciulo, Fosca Giannotti, Dino Pedreschi, Carlo Zaniolo · 1994
Non-deterministic operators are needed in First-Order relational languages and Datalog to extend the expressive power of such languages and support efficient formulations of low complexity problems. In this paper, we study the operators proposed in the literature, including witness, lazy choice and dynamic choice, and compare their power of expressing deterministic and non-deterministic queries. We obtain a simple hierarchy that relates these operators with each other and with other constructs, such as negation and fixpoint.