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

Queries Are Easier Than You Thought (Probably).

Serge Abiteboul, Kevin J. Compton, Victor Vianu: Queries Are Easier Than You Thought (Probably). PODS 1992: 23-32
@inproceedings{DBLP:conf/pods/AbiteboulCV92,
  author    = {Serge Abiteboul and
               Kevin J. Compton and
               Victor Vianu},
  title     = {Queries Are Easier Than You Thought (Probably)},
  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     = {23-32},
  ee        = {http://doi.acm.org/10.1145/137097.137105, db/conf/pods/AbiteboulCV92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The optimization of a large class of queries is explored, using a powerful normal form recently proven. The queries include the fixpoint and while queries, and an extension of while with arithmetic. The optimization method is evaluated using a probabilistic analysis. In particular, the average complexity of fixpoint and while is considered and some surprising results are obtained. They suggest that the worst-case complexity is sometimes overly pessimistic for such queries, whose average complexity is often much more reasonable than the provably rare worst case. Some computational properties of queries are also investigated. A probabilistic notion of boundedness is defined, and it is shown that all programs in the class considered are bounded almost everywhere. An effective way of using this fact is provided.

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, 993 KB]

References

[AG92]
Serge Abiteboul, Allen Van Gelder: Optimizing Active Databases using the Split Technique. ICDT 1992: 171-187 BibTeX
[AS91]
Serge Abiteboul, Eric Simon: Fundamental Properties of Deterministic and Nondeterministic Extensions of Datalog. Theor. Comput. Sci. 78(1): 137-158(1991) 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
[AVV91]
Serge Abiteboul, Moshe Y. Vardi, Victor Vianu: Fixpoint logics, relational machines, and computational complexity. J. ACM 44(1): 30-56(1997) BibTeX
[AVV92]
Serge Abiteboul, Moshe Y. Vardi, Victor Vianu: Computing with Infinitary Logic. Theor. Comput. Sci. 149(1): 101-128(1995) BibTeX
[Bol85]
...
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[CH82]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[Cha81]
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX
[Dah87]
...
[Fag90]
Ronald Fagin: Finite-Model Theory - a Personal Perspective. ICDT 1990: 3-24 BibTeX
[Gel89]
Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX
[GJ79]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[Gra83]
Etienne Grandjean: Complexity of the First-Order Theory of Almost All Finite Structures. Information and Control 57(2/3): 180-204(1983) BibTeX
[GS86]
...
[Gur91]
Yuri Gurevich: Average Case Completeness. J. Comput. Syst. Sci. 42(3): 346-398(1991) BibTeX
[Imm86]
...
[Imm87]
...
[KA89]
Paris C. Kanellakis, Serge Abiteboul: Database Theory Column: Deciding Bounded Recursion in Database Logic Programs. SIGACT News 20(4): 17-23(1989) BibTeX
[Kan91]
...
[Kol91]
Phokion G. Kolaitis: The Expressive Power of Stratified Programs. Inf. Comput. 90(1): 50-66(1991) BibTeX
[KP88]
Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 BibTeX
[KV87]
Phokion G. Kolaitis, Moshe Y. Vardi: The Decision Problem for the Probabilities of Higher-Order Properties. STOC 1987: 425-435 BibTeX
[KV90]
Phokion G. Kolaitis, Moshe Y. Vardi: 0-1 Laws for Infinitary Logics (Preliminary Report). LICS 1990: 156-167 BibTeX
[KV92]
Phokion G. Kolaitis, Moshe Y. Vardi: Infinitary Logics and 0-1 Laws. Inf. Comput. 98(2): 258-294(1992) BibTeX
[Lev86]
Leonid A. Levin: Average Case Complete Problems. SIAM J. Comput. 15(1): 285-286(1986) BibTeX
[SN91]
S. Seshadri, Jeffrey F. Naughton: On the Expected Size of Recursive Datalog Queries. PODS 1991: 268-279 BibTeX
[SS88]
...
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[Var82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[Var92]
...
[Wil84]
Herbert S. Wilf: Backtrack: An O(1) Expected Time Algorithm for the Graph Coloring Problem. Inf. Process. Lett. 18(3): 119-121(1984) BibTeX

Referenced by

  1. James F. Lynch: Analysis and Application of Adaptive Sampling. PODS 2000: 260-267
  2. Jerzy Tyszkiewicz: On the Kolmogorov Expressive Power of Boolean Query Languages. ICDT 1995: 97-110
  3. Sérgio Lifschitz, Victor Vianu: A Probabilistic View of Datalog Parallelization. ICDT 1995: 294-307
  4. Stéphane Grumbach: A Paradox in Database Theory. ICDT 1992: 312-325
  5. Serge Abiteboul, Allen Van Gelder: Optimizing Active Databases using the Split Technique. ICDT 1992: 171-187
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:05 2009