Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/697

Title: A Semideterministic Approach to Object Creation and Nondeterminism in Database Queries
Van Gucht, Dirk
Issue Date: 1997
Publisher: Academic Press
Citation: Journal of Computer and System Sciences, 54(1), p. 34-47
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.
URI: http://hdl.handle.net/1942/697
DOI: 10.1006/jcss.1997.1450
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A289.67 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.