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

On the Complexity of Bounded-Variable Queries.

Moshe Y. Vardi: On the Complexity of Bounded-Variable Queries. PODS 1995: 266-276
@inproceedings{DBLP:conf/pods/Vardi95,
  author    = {Moshe Y. Vardi},
  title     = {On the Complexity of Bounded-Variable Queries},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {266-276},
  ee        = {http://doi.acm.org/10.1145/212433.212474, db/conf/pods/Vardi95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

It is known that the expression complexity and combined complexity of query evaluation in relational databases are in general exponentially higher than the data complexity of query evaluation. This gap in complexity is caused by the fact that evaluating a relational query may involve intermediate results that are exponentially larger than the input. In this paper we study the complexity of query evaluation with intermediate results of polynomial size. This bound is accomplished by restricting the queries to have a bounded number of individual variables. We show that, for bounded-variable queries, the gap between their expression and combined complexities, one one hand, and their data complexity, on the other hand, narrows and in some cases disappears. These results confirm the practice of trying to minimize the size of intermediate relations in database query evaluation, and suggest variable minimization as a query optimization methodology.

Copyright © 1995 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 Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California. ACM Press 1995, ISBN 0-89791-730-8
Contents BibTeX

Online Edition: ACM Digital Library

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

References

[Ajt83]
...
[And94]
Henrik Reif Andersen: Model Checking and Boolean Graphs. Theor. Comput. Sci. 126(1): 3-30(1994) BibTeX
[AV89]
Serge Abiteboul, Victor Vianu: Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. LICS 1989: 71-79 BibTeX
[BFMY83]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[BIS90]
David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306(1990) BibTeX
[Bus87]
Samuel R. Buss: The Boolean Formula Value Problem Is in ALOGTIME. STOC 1987: 123-131 BibTeX
[BVW94]
...
[CES86]
Edmund M. Clarke, E. Allen Emerson, A. Prasad Sistla: Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications. ACM Trans. Program. Lang. Syst. 8(2): 244-263(1986) BibTeX
[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
[Cha88]
Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9 BibTeX
[Cle90]
Rance Cleaveland: Tableau-Based Model Checking in the Propositional Mu-Calculus. Acta Inf. 27(8): 725-747(1989) BibTeX
[Cle92]
...
[Cle93]
...
[CM77]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[Cod72]
...
[Coo74]
Stephen A. Cook: An Observation on Time-Storage Trade Off. J. Comput. Syst. Sci. 9(3): 308-316(1974) BibTeX
[Cos83]
Stavros S. Cosmadakis: The Complexity of Evaluating Relational Queries. Information and Control 58(1-3): 101-112(1983) BibTeX
[EJ88]
E. Allen Emerson, Charanjit S. Jutla: The Complexity of Tree Automata and Logics of Programs (Extended Abstract). FOCS 1988: 328-337 BibTeX
[EJS93]
...
[EL86]
E. Allen Emerson, Chin-Laung Lei: Efficient Model Checking in Fragments of the Propositional Mu-Calculus (Extended Abstract). LICS 1986: 267-278 BibTeX
[Eme85]
...
[Fag74]
...
[FSS81]
Merrick L. Furst, James B. Saxe, Michael Sipser: Parity, Circuits, and the Polynomial-Time Hierarchy. FOCS 1981: 260-270 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
[GS86]
...
[Hod93]
...
[IK89]
Neil Immerman, Dexter Kozen: Definability with Bounded Number of Bound Variables. Inf. Comput. 83(2): 121-139(1989) BibTeX
[Imm82]
Neil Immerman: Upper and Lower Bounds for First Order Expressibility. J. Comput. Syst. Sci. 25(1): 76-98(1982) BibTeX
[Imm86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX
[Imm87]
...
[Imm89]
Neil Immerman: Expressibility and Parallel Complexity. SIAM J. Comput. 18(3): 625-638(1989) BibTeX
[Koz83]
Dexter Kozen: Results on the Propositional mu-Calculus. Theor. Comput. Sci. 27: 333-354(1983) BibTeX
[KV92]
Phokion G. Kolaitis, Moshe Y. Vardi: Infinitary Logic for Computer Science. ICALP 1992: 450-473 BibTeX
[Lei90]
Daniel Leivant: Inductive Definitions Over Finite Structures. Inf. Comput. 89(2): 95-108(1990) BibTeX
[Lyn77]
Nancy A. Lynch: Log Space Recognition and Translation of Parenthesis Languages. J. ACM 24(4): 583-590(1977) BibTeX
[SW91]
Colin Stirling, David Walker: Local Model Checking in the Modal mu-Calculus. Theor. Comput. Sci. 89(1): 161-177(1991) BibTeX
[Tar55]
...
[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
[VS85]
Moshe Y. Vardi, Larry J. Stockmeyer: Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report. STOC 1985: 240-251 BibTeX
[Win91]
Glynn Winskel: A Note on Model Checking the Modal nu-Calculus. Theor. Comput. Sci. 83(1): 157-167(1991) BibTeX
[Yan81]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX

Referenced by

  1. Jörg Flum, Markus Frick, Martin Grohe: Query Evaluation via Tree-Decompositions. ICDT 2001: 22-38
  2. Moshe Y. Vardi: Constraint Satisfaction and Database Theory: a Tutorial. PODS 2000: 76-85
  3. Marc Spielmann: Verification of Relational Transducers for Electronic Commerce. PODS 2000: 92-103
  4. Sergei G. Vorobyov, Andrei Voronkov: Complexity of Nonrecursive Logic Programs with Complex Values. PODS 1998: 244-253
  5. Phokion G. Kolaitis, Moshe Y. Vardi: Conjunctive-Query Containment and Constraint Satisfaction. PODS 1998: 205-213
  6. Christos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. PODS 1997: 12-19
  7. Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98
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:13 2009