Luis Perez, Monte Carlo Evaluation of Satisfiability Queries on Uncertain Databases

The Monte Carlo Database (MCDB) is an uncertain data management framework that relies on Monte Carlo sampling to perform scalable query processing. While MCDB provides an efficient query processing model, it does not allow for error control over the random samples it generates. We introduce satisfiability queries, a special type of database queries associated with confidence intervals and false positive/false negative error control information. Furthermore, we propose a set of algorithms and query processing techniques that allow for these types of queries to be efficiently evaluated in the context of the MCDB framework.