A Semideterministic Approach to Object Creation and Nondeterminism in Database Queries

ISSN： 0022-0000

Source： Journal of Computer and System Sciences, Vol.54, Iss.1, 1997-02, pp. : 34-47

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We introduce and study the concept of semideterminism. A non-deterministic, generic query is called semideterministic 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. The framework of semi-deterministic queries is less restrictive than that of the determinate queries and avoids the problem of copy elimination connected with determinacy. We argue that semideterminism is also interesting in its own right and show that it is natural and desirable, although hard to achieve in general. Nevertheless, we exhibit two major applications where semideterministic computations are possible. First, we show that there is a universal procedure to compute any semideterministic query in a semideterministic manner. Second, we show that the polynomial-time counting queries can be efficiently expressed semideterministically.