Tractable Counting of the Answers to Conjunctive Queries.
Reinhard PichlerSebastian SkritekPublished in: AMW (2011)
Keyphrases
- conjunctive queries
- np complete
- bounded treewidth
- complexity of query answering
- queries using views
- query answering
- query evaluation
- integrity constraints
- data complexity
- hypertree decomposition
- special case
- computational complexity
- database theory
- query language
- data exchange
- query answers
- query rewriting
- fixed parameter tractable
- np hard
- decision procedures
- dl lite
- datalog programs
- answering queries
- constraint satisfaction problems
- computational problems
- conjunctive query containment
- data management
- data sets
- containment of conjunctive queries
- tree width
- incomplete information
- probabilistic databases
- boolean expressions
- consistent answers
- relational queries
- data model
- unions of conjunctive queries
- expressive power
- xml data
- transitive closure
- tight complexity bounds