A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries.
Hubie ChenStefan MengelPublished in: CoRR (2014)
Keyphrases
- conjunctive queries
- conjunctive query containment
- data complexity
- query answering
- query evaluation
- combined complexity
- queries using views
- integrity constraints
- np complete
- query language
- conp complete
- conjunctive regular path queries
- complexity of query answering
- data exchange
- lower complexity
- bounded treewidth
- special case
- query answers
- pspace complete
- unions of conjunctive queries
- query containment
- computational complexity
- decision procedures
- query rewriting
- dl lite
- fixed parameter tractable
- containment of conjunctive queries
- decision problems
- boolean expressions
- exptime complete
- answering queries
- transitive closure
- expressive power
- query complexity
- regular path queries
- relational algebra
- tuple generating dependencies
- schema mappings
- data integration
- data management
- query processing