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},
editor = {Avi Silberschatz},
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, USA},
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}
}
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 ...
Printed Edition
Avi Silberschatz (Ed.):
Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania, USA.
ACM Press 1989, ISBN 0-89791-308-6
Contents 
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
- [BHZ87]
- Ravi B. Boppana, Johan Håstad, Stathis Zachos:
Does co-NP Have Short Interactive Proofs?
Inf. Process. Lett. 25(2): 127-132(1987)
- [CH80]
- Ashok K. Chandra, David Harel:
Structure and Complexity of Relational Queries.
FOCS 1980: 333-347
- [CM77]
- Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90
- [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
- [GJ79a]
- ...
- [Imi84]
- Tomasz Imielinski, Witold Lipski Jr.:
Incomplete Information in Relational Databases.
J. ACM 31(4): 761-791(1984)
- [Imi87]
- ...
- [Imm86]
- Neil Immerman:
Relational Queries Computable in Polynomial Time.
Information and Control 68(1-3): 86-104(1986)
- [Karp72]
- ...
- [Stoc76]
- Larry J. Stockmeyer:
The Polynomial-Time Hierarchy.
Theor. Comput. Sci. 3(1): 1-22(1976)
- [Ull84]
- Jeffrey D. Ullman:
Principles of Database Systems, 2nd Edition.
Computer Science Press 1982, ISBN 0-914894-36-6
- [Var82]
- Moshe Y. Vardi:
The Complexity of Relational Query Languages (Extended Abstract).
STOC 1982: 137-146
Referenced by
- 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)
- 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)
- 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)
- 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)
- José Alberto Fernández, Jack Minker:
Semantics of Disjunctive Deductive Databases.
ICDT 1992: 21-50
- Monica D. Barback, Jorge Lobo, James J. Lu:
Minimizing Indefinite Information in Disjunctive Deductive Databases.
ICDT 1992: 246-260
- Tomasz Imielinski, Shamim A. Naqvi, Kumar V. Vadaparty:
Incomplete Objects - A Data Model for Design and Planning Applications.
SIGMOD Conference 1991: 288-297
- Nong Zhou:
Representation and Processing of Uncertain Information in Relational Databases.
ER 1991: 371-388
- Yves Caseau:
The LAURE Model for Object-Oriented Logic Databases.
DASFAA 1991: 411-420
- Ron van der Meyden:
Recursively Indefinite Databases.
ICDT 1990: 364-378
Last update Fri May 25 08:32:43 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
