Size and Treewidth Bounds for Conjunctive Queries.
Georg GottlobStephanie Tien LeeGregory ValiantPaul ValiantPublished in: J. ACM (2012)
Keyphrases
- bounded treewidth
- conjunctive queries
- np complete
- upper bound
- query answering
- query evaluation
- integrity constraints
- query language
- data complexity
- data exchange
- probabilistic databases
- space complexity
- decision procedures
- query containment
- fixed parameter tractable
- datalog programs
- worst case
- unions of conjunctive queries
- lower bound
- boolean expressions
- containment of conjunctive queries
- decision problems
- query rewriting
- answering queries
- incomplete information
- queries using views
- conjunctive regular path queries