Complexity of query processing in databases with OR-objects
- 29 March 1989
- proceedings article
- Published by Association for Computing Machinery (ACM)
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?”.Keywords
This publication has 8 references indexed in Scilit:
- Does co-NP have short interactive proofs?Information Processing Letters, 1987
- On the representation and querying of sets of possible worldsPublished by Association for Computing Machinery (ACM) ,1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- Incomplete Information in Relational DatabasesJournal of the ACM, 1984
- The complexity of relational query languages (Extended Abstract)Published by Association for Computing Machinery (ACM) ,1982
- Graph isomorphism and self-complementary graphsACM SIGACT News, 1978
- Optimal implementation of conjunctive queries in relational data basesPublished by Association for Computing Machinery (ACM) ,1977
- The polynomial-time hierarchyTheoretical Computer Science, 1976