A Semi-Deterministic Approach to Object Creation and Non-Determinism in Database Queries

We introduce and study the concept of semi-determinism. A nondeterministic, generic query is called semi-deterministic if any two possible results of the query to a database are isomorphic. Semideterminism is a generalization of determinacy, proposed by Abiteboul and Kanellakis in the context of object-creating query languages. Originally it was conceived merely as a way to avoid the problem of copy elimination connected with determinacy, by offering a less restrictive framework. However, we introduce and study semi-determinism in its own right and argue that it is natural and desirable, though hard to achieve in general. Nevertheless, we exhibit two major applications where semi-deterministic computations are possible. First, we show that there is a universal procedure to compute any semideterministic query in a semi-deterministic manner. Second, we show that the polynomial-time counting queries can be efficiently expressed semi-deterministically. An extended abstract of a prelimin..