Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases.
Paul BeameJerry LiSudeepa RoyDan SuciuPublished in: CoRR (2013)
Keyphrases
- probabilistic databases
- lower bound
- model counting
- query evaluation
- upper bound
- uncertain data
- aggregate queries
- database queries
- conjunctive queries
- probabilistic inference
- satisfiability testing
- knowledge compilation
- polynomial size
- optimal solution
- objective function
- databases
- relational algebra
- np hard
- probabilistic reasoning
- upper and lower bounds
- probabilistic model
- object oriented
- data warehouse
- vc dimension
- propositional formulas