Size and treewidth bounds for conjunctive queries.
Georg GottlobStephanie Tien LeeGregory ValiantPublished in: PODS (2009)
Keyphrases
- bounded treewidth
- conjunctive queries
- np complete
- query answering
- query evaluation
- integrity constraints
- upper bound
- data complexity
- query language
- data exchange
- decision problems
- query rewriting
- lower bound
- special case
- acyclic conjunctive queries
- fixed parameter tractable
- relational database theory
- decision procedures
- query containment
- unions of conjunctive queries
- queries using views
- containment of conjunctive queries
- space complexity
- probabilistic databases
- databases
- computational complexity
- relational queries
- regular path queries
- relational learning
- conp complete
- schema mappings
- optimal solution
- database systems