Date Added: Aug 2009
The authors study the containment problem for a query language over probabilistic relational databases that allows queries like "Is the probability that q1 holds greater than 0.2 and the probability that q2 holds greater than 0.6?" where q1 and q2 are Boolean conjunctive queries. In addition to being a fundamental problem in its own right, the containment problem is the key problem that an optimizer must solve for many standard optimizations (such as picking up an index or using a materialized view). The main technical result is that the containment problem is decidable, and the authors give an EXPSPACE-algorithm based on linear programming for it.