One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries.
Hubie ChenMoritz MüllerPublished in: CoRR (2013)
Keyphrases
- conjunctive queries
- bounded treewidth
- query answering
- integrity constraints
- data complexity
- np complete
- conjunctive query containment
- conp complete
- query evaluation
- conjunctive regular path queries
- query language
- decision trees
- data exchange
- lower complexity
- query rewriting
- decision problems
- special case
- graph model
- computational complexity
- tree width
- optimal solution
- deductive databases
- spanning tree
- data model
- incomplete information
- decision procedures
- data integration
- query complexity
- fixed parameter tractable
- hypertree decomposition
- databases