Testing Containment of Object-Oriented Conjunctive Queries is Pi_2^p-hard.
Edward P. F. ChanRon van der MeydenPublished in: COCOON (1995)
Keyphrases
- conjunctive queries
- object oriented
- query language
- query answering
- integrity constraints
- query evaluation
- query containment
- np complete
- data complexity
- data exchange
- data model
- special case
- database schema
- decision procedures
- probabilistic databases
- query rewriting
- unions of conjunctive queries
- relational databases
- object oriented databases
- datalog programs
- regular path queries
- database design
- containment of conjunctive queries
- conjunctive regular path queries
- expressive power
- deductive databases
- incomplete information
- dl lite
- boolean expressions
- database applications
- database
- autonomous agents
- lower bound