A Trichotomy in the Data Complexity of Certain Query Answering for Conjunctive Queries.
Paraschos KoutrisJef WijsenPublished in: CoRR (2015)
Keyphrases
- query answering
- data complexity
- conjunctive queries
- data exchange
- integrity constraints
- combined complexity
- answering queries
- data integration
- incomplete information
- query rewriting
- lower complexity
- decision procedures
- exptime complete
- query containment
- conjunctive query answering
- datalog programs
- probabilistic databases
- ontology languages
- dl lite
- regular path queries
- query complexity
- unions of conjunctive queries
- schema mappings
- query answers
- relational queries
- knowledge base
- inconsistent databases
- query evaluation
- double exponential