The Dichotomy of Conjunctive Queries on Probabilistic Structures
Nilesh N. DalviDan SuciuPublished in: CoRR (2006)
Keyphrases
- conjunctive queries
- probabilistic databases
- boolean expressions
- query evaluation
- query answering
- query language
- integrity constraints
- data complexity
- np complete
- query rewriting
- special case
- data exchange
- bayesian networks
- query containment
- decision procedures
- relational queries
- normal form
- datalog programs
- unions of conjunctive queries
- containment of conjunctive queries
- databases
- queries using views
- regular expressions
- deductive databases
- uncertain data
- decision problems