Data complexity of answering conjunctive queries over SHIQ knowledge bases
Magdalena OrtizDiego CalvaneseThomas EiterEnrico FranconiPublished in: CoRR (2005)
Keyphrases
- query answering
- data complexity
- conjunctive query answering
- conjunctive queries
- dl lite
- knowledge base
- combined complexity
- transitive roles
- data exchange
- answering queries
- description logics
- integrity constraints
- query rewriting
- data integration
- incomplete information
- query evaluation
- unions of conjunctive queries
- lower complexity
- query containment
- exptime complete
- inconsistent databases
- decision procedures
- datalog programs
- query answers
- expressive power
- query complexity
- np complete
- regular path queries
- query language
- tuple generating dependencies
- complexity of query answering
- consistent query answering
- relational queries
- double exponential
- relational algebra
- special case