Query containment of tier-2 queries over a probabilistic database
Katherine F. Moore, Vibhor Rastogi, Christopher Ré, Dan Mircea Suciu · 2009
Abstract. We 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). Our main technical result is that the containment problem is decidable, and we give an EXPSPACE-algorithm based on linear programming for it. We believe that we are the first to study the containment problem for any such probabilistic languages. 1