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 | Size | Format | |
---|---|---|---|---|
semidet.pdf | 289.67 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
3
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
1
checked on Oct 14, 2024
Page view(s)
52
checked on Sep 7, 2022
Download(s)
108
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.