  We provide methods for in-database support of decision making under
uncertainty. Many important decision problems correspond to selecting a package
(bag of tuples in a relational database) that jointly satisfy a set of
constraints while minimizing some overall cost function; in most real-world
problems, the data is uncertain. We provide methods for specifying -- via a SQL
extension -- and processing stochastic package queries (SPQs), in order to
solve optimization problems over uncertain data, right where the data resides.
Prior work in stochastic programming uses Monte Carlo methods where the
original stochastic optimization problem is approximated by a large
deterministic optimization problem that incorporates many scenarios, i.e.,
sample realizations of the uncertain data values. For large database tables,
however, a huge number of scenarios is required, leading to poor performance
and, often, failure of the solver software. We therefore provide a novel
SummarySearch algorithm that, instead of trying to solve a large deterministic
problem, seamlessly approximates it via a sequence of smaller problems defined
over carefully crafted summaries of the scenarios that accelerate convergence
to a feasible and near-optimal solution. Experimental results on our prototype
system show that SummarySearch can be orders of magnitude faster than prior
methods at finding feasible and high-quality packages.
