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

Complexity of Query Processing in Databases with OR-Objects.

Tomasz Imielinski, Kumar V. Vadaparty: Complexity of Query Processing in Databases with OR-Objects. PODS 1989: 51-65
@inproceedings{DBLP:conf/pods/ImielinskiV89,
  author    = {Tomasz Imielinski and
               Kumar V. Vadaparty},
  title     = {Complexity of Query Processing in Databases with OR-Objects},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {51-65},
  ee        = {http://doi.acm.org/10.1145/73721.73726, db/conf/pods/ImielinskiV89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

If ground disjunctive facts are admitted into a database the data complexity of conjunctive queries grows from PTIME into CoNP with some simple examples of CoNP-Complete conjunctive queries. A natural question which arises in this context is whether it is possible to syntactically characterize those queries which are "bad" (i.e CoNP-Complete) from those that are "good" (i.e. with PTIME data complexity) given a predefined 'pattern" of disjunctions in the database. In this paper, we study the data complexity of conjunctive queries. We give a complete syntactic characterization of CoNP-Complete conjunctive queries for a class of disjunctive databases called OR-Databases. Our results can be used in complexity tailored design where design decisions are motivated by complexity of query processing. Also, we establish that a similar complete syntactic characterization for disjunctive queries, with negation allowed only on base predicates, would answer the open problem "Does Graph Isomorphism belong to PTIME or is it NP-Complete?".

Copyright © 1989 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 Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[Abit87]
Serge Abiteboul, Paris C. Kanellakis, Gösta Grahne: On the Representation and Querying of Sets of Possible Worlds. SIGMOD Conference 1987: 34-48 BibTeX
[BHZ87]
Ravi B. Boppana, Johan Håstad, Stathis Zachos: Does co-NP Have Short Interactive Proofs? Inf. Process. Lett. 25(2): 127-132(1987) BibTeX
[CH80]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. FOCS 1980: 333-347 BibTeX
[CM77]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[CC78]
...
[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
[GJ79a]
...
[Imi84]
Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX
[Imi87]
...
[Imm86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX
[Karp72]
...
[Stoc76]
Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX
[Ull84]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[Var82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

  1. Arbee L. P. Chen, Jui-Shang Chiu, Frank Shou-Cheng Tseng: Evaluating Aggregate Operations Over Imprecise Data. IEEE Trans. Knowl. Data Eng. 8(2): 273-284(1996)
  2. Kumar V. Vadaparty, Shamim A. Naqvi: Using Constraints for Efficient Query Processing in Nondeterministic Databases. IEEE Trans. Knowl. Data Eng. 7(6): 850-864(1995)
  3. Jui-Shang Chiu, Arbee L. P. Chen: An Exploration of Relationships Among Exclusive Disjunctive Data. IEEE Trans. Knowl. Data Eng. 7(6): 928-940(1995)
  4. Frank Shou-Cheng Tseng, Arbee L. P. Chen, Wei-Pang Yang: Searching a Minimal Semantically-Equivalent Subset of a Set of Partial Values. VLDB J. 2(4): 489-512(1993)
  5. José Alberto Fernández, Jack Minker: Semantics of Disjunctive Deductive Databases. ICDT 1992: 21-50
  6. Monica D. Barback, Jorge Lobo, James J. Lu: Minimizing Indefinite Information in Disjunctive Deductive Databases. ICDT 1992: 246-260
  7. Tomasz Imielinski, Shamim A. Naqvi, Kumar V. Vadaparty: Incomplete Objects - A Data Model for Design and Planning Applications. SIGMOD Conference 1991: 288-297
  8. Nong Zhou: Representation and Processing of Uncertain Information in Relational Databases. ER 1991: 371-388
  9. Yves Caseau: The LAURE Model for Object-Oriented Logic Databases. DASFAA 1991: 411-420
  10. Ron van der Meyden: Recursively Indefinite Databases. ICDT 1990: 364-378
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:33:56 2009