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

A Non-deterministic Deductive Database Language.

Yeh-Heng Sheng: A Non-deterministic Deductive Database Language. SIGMOD Conference 1991: 188-197
@inproceedings{DBLP:conf/sigmod/Sheng91,
  author    = {Yeh-Heng Sheng},
  editor    = {James Clifford and
               Roger King},
  title     = {A Non-deterministic Deductive Database Language},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {188-197},
  ee        = {http://doi.acm.org/10.1145/115790.115817, db/conf/sigmod/Sheng91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A non-deterministic deductive database language IDLOG that employs tuple-identifiers in DATALOG (with negation) was proposed in [She90b] to enhance the expressive power of deductive database languages. It was shown that a subset of IDLOG programs defines the class of all computable deterministic queries. In this paper, we investigate the non-deterministic part of IDLOG. As discussed in [ASV90], the use of non-deterministic database languages is motivated using both pragmatic and theoretical considerations. There are natural non-deterministic queries whose implementation using deterministic languages is unintuitive and inefficient. One typical example is sampling queries, i.e., queries that randomly choose certain samples from a set of tuples, such as "Find an arbitrary set of employee samples that contains exactly N employees from each department (assuming each department has at least N employees)". Another consideration in favor of non-determinism is optimization. Intuitively, a non-deterministic program gives a certain degree of freedom in the computation of a query, which can be exploited in optimization. We show how IDLOG defines sampling queries and how it can be used to optimize DATALOG programs. Also discussed is the expressive power of non-deterministic IDLOG.

Copyright © 1991 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 BibTeX , SIGMOD Record 20(2), June 1991
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1037 KB]

References

[ABW88]
...
[ASV90]
Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229 BibTeX
[AV87]
Serge Abiteboul, Victor Vianu: A Transcation Language Complete for Database Update and Specification. PODS 1987: 260-268 BibTeX
[AV88]
Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[Cha81]
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX
[End72]
...
[GL88]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[GS85]
Yuri Gurevich, Saharon Shelah: Fixed-Point Extensions of First-Order Logic. FOCS 1985: 346-353 BibTeX
[HS89]
Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 BibTeX
[HS90]
Richard Hull, Jianwen Su: Algebraic and Calculus Query Languages for Recursively Typed Complex Objects. J. Comput. Syst. Sci. 47(1): 121-156(1993) BibTeX
[KN88]
Ravi Krishnamurthy, Shamim A. Naqvi: Non-Deterministic Choice in Datalog. JCDKB 1988: 416-424 BibTeX
[KP88]
Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 BibTeX
[MS88]
Christophe de Maindreville, Eric Simon: Modelling Non Deterministic Queries and Updates in Deductive Databases. VLDB 1988: 395-406 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
[Prz88a]
Teodor C. Przymusinski: On the Declarative and Procedural Semantics of Logic Programs. J. Autom. Reasoning 5(2): 167-205(1989) BibTeX
[Prz88b]
...
[RBK88]
Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102 BibTeX
[Rei83]
...
[She90a]
...
[She90b]
Yeh-Heng Sheng: IDLOG: Extending the Expressive Power of Deductive Database Languages. SIGMOD Conference 1990: 54-63 BibTeX
[SZ90]
Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217 BibTeX
[Gel88]
...
[VGRS88]
...
[Zan86]
Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 BibTeX
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:40:06 2009