One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries.
Hubie ChenMoritz MüllerPublished in: ACM Trans. Comput. Log. (2017)
Keyphrases
- conjunctive queries
- bounded treewidth
- query answering
- query evaluation
- conjunctive query containment
- np complete
- query language
- conjunctive regular path queries
- tree width
- integrity constraints
- data complexity
- conp complete
- query rewriting
- data exchange
- query containment
- probabilistic databases
- graph model
- lower complexity
- decision problems
- computational complexity
- decision trees
- decision procedures
- datalog programs
- databases
- incomplete information
- regular path queries
- special case