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
Authors: VAN DEN BUSSCHE, Jan 
Van Gucht, Dirk
Issue Date: 1997
Publisher: Academic Press
Source: 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.
Document 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:
File Description SizeFormat 
semidet.pdf289.67 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

3
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

1
checked on May 22, 2022

Page view(s)

40
checked on May 26, 2022

Download(s)

92
checked on May 26, 2022

Google ScholarTM

Check

Altmetric


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