On the Complexity of Database Queries.
Christos H. Papadimitriou, Mihalis Yannakakis:
On the Complexity of Database Queries.
PODS 1997: 12-19@inproceedings{DBLP:conf/pods/PapadimitriouY97,
author = {Christos H. Papadimitriou and
Mihalis Yannakakis},
title = {On the Complexity of Database Queries},
booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
publisher = {ACM Press},
year = {1997},
isbn = {0-89791-910-6},
pages = {12-19},
ee = {http://doi.acm.org/10.1145/263661.263664, db/conf/pods/PapadimitriouY97.html},
crossref = {DBLP:conf/pods/97},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
We revisit the issue of the complexity of database queries,
in the light of the recent parametric refinement of complexity
theory. We show that, if the query size (or the number of variables
in the query) is considered as a parameter, then the relational
calculus and its fragments (conjunctive queries, positive queries)
are classified at appropriate levels of the so-called W hierarchy
of Downey and Fellows. These results strongly suggest that the query
size is inherently in the exponent of the data complexity of any
query evaluation algorithm, with the implication becoming stronger as the
expressibility of the query language increases.
For recursive languages (fixpoint logic, Datalog) this is
provably the case [14].
On the positive side,
we show that this exponential dependence can be avoided for
the extension of acyclic queries with != (but not <) inequalities.
Copyright © 1997 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 Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona.
ACM Press 1997, ISBN 0-89791-910-6
Contents BibTeX
[Index Terms]
[Full Text in PDF Format, 1859 KB]
References
- [1]
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX
- [2]
- Noga Alon, Raphael Yuster, Uri Zwick:
Color-Coding.
J. ACM 42(4): 844-856(1995) BibTeX
- [3]
- Jonathan F. Buss, Judy Goldsmith:
Nondeterminism Within P.
SIAM J. Comput. 22(3): 560-572(1993) BibTeX
- [4]
- Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90 BibTeX
- [5]
- Rodney G. Downey, Michael R. Fellows:
Fixed-Parameter Tractability and Completeness I: Basic Results.
SIAM J. Comput. 24(4): 873-921(1995) BibTeX
- [6]
- ...
- [7]
- Paris C. Kanellakis:
Constraint Programming and Database Languages: A Tutorial.
PODS 1995: 46-53 BibTeX
- [8]
- Anthony C. Klug:
On conjunctive queries containing inequalities.
J. ACM 35(1): 146-160(1988) BibTeX
- [9]
- Orna Lichtenstein, Amir Pnueli:
Checking That Finite State Concurrent Programs Satisfy Their Linear Specification.
POPL 1985: 97-107 BibTeX
- [10]
- ...
- [11]
- Christos H. Papadimitriou, Mihalis Yannakakis:
On Limited Nondeterminism and the Complexity of the V-C Dimension.
J. Comput. Syst. Sci. 53(2): 161-170(1996) BibTeX
- [12]
- ...
- [13]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
- [14]
- Moshe Y. Vardi:
The Complexity of Relational Query Languages (Extended Abstract).
STOC 1982: 137-146 BibTeX
- [15]
- Moshe Y. Vardi:
On the Complexity of Bounded-Variable Queries.
PODS 1995: 266-276 BibTeX
- [16]
- Mihalis Yannakakis:
Algorithms for Acyclic Database Schemes.
VLDB 1981: 82-94 BibTeX
- [17]
- Mihalis Yannakakis:
Perspectives on Database Theory.
FOCS 1995: 224-246 BibTeX
Referenced by
- Georg Gottlob, Nicola Leone, Francesco Scarcello:
Hypertree Decompositions and Tractable Queries.
PODS 1999: 21-32
- Sergei G. Vorobyov, Andrei Voronkov:
Complexity of Nonrecursive Logic Programs with Complex Values.
PODS 1998: 244-253
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:16 2009