Stochastic Package Queries in Probabilistic Databases
Stochastic Package Queries in Probabilistic Databases
复制标题
DOI：
10.1145/3318464.3389765
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Matteo Brucato;Nishant Yadav;A. Abouzied;P. Haas;A. Meliou
中科院分区：
文献类型：
--
作者：
Matteo Brucato;Nishant Yadav;A. Abouzied;P. Haas;A. Meliou
我们提供了在不确定性下的决策支持的数据库中的方法。许多重要的决策问题对应于选择一个“包”（关系数据库中的元组包），这些“包”共同满足一组约束，同时最小化一些总体“成本”函数;在大多数现实世界的问题中，数据是不确定的。我们提供的方法指定-通过SQL扩展-和处理随机包查询（SPQS），以解决不确定数据的优化问题，就在数据驻留的地方。随机规划中的先前工作使用蒙特卡罗方法，其中原始随机优化问题由包含许多“场景”的大型确定性优化问题来近似，即，不确定数据值的示例实现。然而，对于大型数据库表，需要大量的场景，导致性能低下，并且经常导致求解器软件失败。因此，我们提供了一种新的SSS算法，而不是试图解决一个大的确定性问题，无缝地近似它通过一系列的小问题定义在精心制作的“摘要”的情况下，加速收敛到一个可行的和接近最优的解决方案。在我们的原型系统上的实验结果表明，在寻找可行的和高质量的软件包时，ßs可以比以前的方法快几个数量级。
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 ßs 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 ßs can be orders of magnitude faster than prior methods at finding feasible and high-quality packages.