ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Semi-determinism.

Jan Van den Bussche, Dirk Van Gucht: Semi-determinism. PODS 1992: 191-201
@inproceedings{DBLP:conf/pods/BusscheG92,
  author    = {Jan Van den Bussche and
               Dirk Van Gucht},
  title     = {Semi-determinism},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {191-201},
  ee        = {http://doi.acm.org/10.1145/137097.137866, db/conf/pods/BusscheG92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We investigate under which conditions a non-deterministic query is semi-deterministic, meaning that two different results of the query to a database are isomorphic. We also consider uniform semi-determinism, meaning that all intermediate results of the computation are isomorphic. Semi-determinism is a concept bridging the new trends of non-determinism and object generation in database query languages. Our results concern decidability, both at compile time and at run time; expressibility of the infamous counting queries; and completeness, which is related to the issue of copy elimination raised by Abiteboul and Kannelakis.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1006 KB]

Journal Version

Jan Van den Bussche, Dirk Van Gucht: A Semideterministic Approach to Object Creation and Nondeterminism in Database Queries. J. Comput. Syst. Sci. 54(1): 34-47(1997) BibTeX

References

[Abi]
...
[ACM90]
Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee. ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX
[ACM91]
Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX
[AK89]
Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX
[AP92]
...
[ASV90]
Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229 BibTeX
[AV90]
Serge Abiteboul, Victor Vianu: Procedural Languages for Database Queries and Updates. J. Comput. Syst. Sci. 41(2): 181-229(1990) BibTeX
[AV91a]
Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX
[AV91b]
Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 BibTeX
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[Cha88]
Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9 BibTeX
[GPVG90]
Marc Gyssens, Jan Paredaens, Dirk Van Gucht: A Graph-Oriented Object Database Model. PODS 1990: 417-424 BibTeX
[HS89]
Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 BibTeX
[HY90]
Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468 BibTeX
[HY91]
Richard Hull, Masatoshi Yoshikawa: On the Equivalence of Database Restructurings Involving Object Identifiers. PODS 1991: 328-340 BibTeX
[Imm86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX
[Kim89]
Won Kim: A Model of Queries for Object-Oriented Databases. VLDB 1989: 423-432 BibTeX
[KLW90]
Michael Kifer, Georg Lausen, James Wu: Logical Foundations of Object-Oriented and Frame-Based Languages. J. ACM 42(4): 741-843(1995) BibTeX
[Kup85]
...
[KV84]
Gabriel M. Kuper, Moshe Y. Vardi: A New Approach to Database Logic. PODS 1984: 86-96 BibTeX
[NT89]
Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX
[SZ90]
Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217 BibTeX
[Var82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[VsBP91]
Jan Van den Bussche, Jan Paredaens: The Expressive Power of Structured Values in Pure OODB's. PODS 1991: 291-299 BibTeX
[Zan89]
Carlo Zaniolo: Object Identity and Inheritance in Deductive Databases - an Evolutionary Approach. DOOD 1989: 7-21 BibTeX

Referenced by

  1. Domenico Saccà: Deterministic and Non-Deterministic Stable Model Semantics for Unbound DATALOG Queries. ICDT 1995: 353-367
  2. Mitch Cherniack, Stanley B. Zdonik, Marian H. Nodine: To Form a More Perfect Union (Intersection, Difference). DBPL 1995: 6
  3. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  4. Karl Denninghoff, Victor Vianu: Database Method Schemas and Object Creation. PODS 1993: 265-275
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:06 2009