III: SMALL: Scalable In-Database Prescriptive Analytics for Dynamic Environments

III：小型：适用于动态环境的可扩展数据库内规范分析

• 批准号: 2211918
• 负责人: Peter Haas
• 金额: $ 60万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-09-01 至 2025-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2211918&HistoricalAwards=false
• 关键词: III; SMALL; Scalable; Database; Prescriptive

Decision makers in a broad range of domains, such as finance, transportation, manufacturing, and healthcare, often need to derive optimal decisions given a set of constraints and objectives; that is, they need to employ "prescriptive analytics". Traditional solutions to such constrained optimization problems, while having generated billions of dollars, are typically application-specific, complex, hard to use by non-optimization-experts, and do not generalize. Further, the usual workflow requires slow, cumbersome, and error-prone data movement between a database and predictive-modeling and optimization tools. All of these problems are exacerbated by the unprecedented size of modern data-intensive optimization problems. The goal of this project is to significantly advance the technology underlying in-database prescriptive analytics to provide seamless domain-independent, easy-to-use, and scalable decision-making tools powered in the database system where the data typically reside. Specifically, the project aims to augment prior work on in-database support for constrained optimization problems with capabilities to handle dynamic environments. This is because decision environments are typically highly dynamic, with data that is uncertain and evolving, and decision problems that may be not precisely defined and changing over time. The investigators will contribute new models and evaluation algorithms that handle uncertain and evolving data and problem variants at scale. The improved methods for integrating optimization with database technology will help lower the barriers to use of prescriptive analytics by domain experts who are not experts in optimization, thereby amplifying the benefits of these planning and management techniques to society.In detail, the project will extend prior methods to handle data uncertainty at scale via in-database support for large-scale stochastic integer linear programs (ILPs) that are specified by the user as "stochastic package queries" (SPQs) using an extension of the SQL database query language. Such a query selects an optimal set ("package") of tuples that satisfy both per-tuple and global constraints. Supporting efficient processing of SPQs entails development of fast approximate query evaluation algorithms with accuracy guarantees. The investigators will next develop fast incremental and progressive query evaluation techniques to allow for rapid what-if analysis and planning. They will first focus on deterministic data and investigate strategies to allow for incremental maintenance of a package result when the underlying data or query changes slightly. The team of researchers will investigate several pathways, such as reengineering the ILP solvers to exploit the special structure of package queries in order to speed up intermediate steps in the initial query evaluation and also facilitate incremental re-optimization. These results will then be leveraged and extended to support incremental evaluation over uncertain data. The project will investigate both how data uncertainty impacts the incremental evaluation strategies designed for deterministic data and how to handle additional factors that instigate change in the stochastic setting, such as changes over time to the probability distribution of uncertain items. For the latter, techniques to be considered include updating a package solution via stochastic search, evaluating the effect of query and data changes via stochastic sensitivity analysis, and speeding up incremental SPQ processing using pre-computation techniques. The final stage of the project will integrate the foregoing algorithms and extensions into a full-fledged system equipped to handle large-scale uncertain data, with the ability to employ incremental evaluation strategies to adapt to data and query changes.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

金融、交通、制造业和医疗保健等广泛领域的决策者通常需要在给定一组约束条件和目标的情况下得出最佳决策；也就是说，他们需要采用“规范分析”。此类约束优化问题的传统解决方案虽然已经产生了数十亿美元，但通常是特定于应用程序的、复杂的、非优化专家难以使用的，并且不能泛化。此外，通常的工作流需要在数据库与预测建模和优化工具之间进行缓慢、繁琐且容易出错的数据移动。所有这些问题都因现代数据密集型优化问题的空前规模而加剧。该项目的目标是显著推进数据库内规定性分析的底层技术，以在数据通常驻留的数据库系统中提供无缝的、独立于领域的、易于使用的和可扩展的决策工具。具体来说，该项目旨在通过处理动态环境的能力来增强数据库内对约束优化问题的支持。这是因为决策环境通常是高度动态的，数据是不确定的和不断发展的，决策问题可能没有精确定义，并且随着时间的推移而变化。研究人员将提供新的模型和评估算法，以处理不确定和不断发展的数据以及大规模的问题变体。将优化与数据库技术集成的改进方法将有助于降低不是优化专家的领域专家使用规定性分析的障碍，从而扩大这些计划和管理技术对社会的好处。具体而言，该项目将扩展先前的方法，通过数据库内支持大规模随机整数线性程序（ilp）来大规模处理数据不确定性，这些程序由用户指定为“随机包查询”（spq），使用SQL数据库查询语言的扩展。这样的查询选择满足单个元组和全局约束的元组的最优集合（“包”）。支持spq的高效处理需要开发具有精度保证的快速近似查询求值算法。研究人员接下来将开发快速增量和渐进式查询评估技术，以允许快速的假设分析和规划。他们将首先关注确定性数据，并研究在底层数据或查询发生轻微变化时允许对包结果进行增量维护的策略。研究小组将研究几种途径，例如重新设计ILP求解器以利用包查询的特殊结构，以加快初始查询评估的中间步骤，并促进增量重新优化。这些结果将被利用和扩展，以支持对不确定数据的增量评估。该项目将研究数据不确定性如何影响为确定性数据设计的增量评估策略，以及如何处理随机设置中引发变化的其他因素，例如不确定项目的概率分布随时间的变化。对于后者，需要考虑的技术包括通过随机搜索更新包解决方案，通过随机灵敏度分析评估查询和数据变化的影响，以及使用预计算技术加速增量SPQ处理。项目的最后阶段将把上述算法和扩展集成到一个成熟的系统中，该系统能够处理大规模的不确定数据，并能够采用增量评估策略来适应数据和查询的变化。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

In-Database Decision Support: Opportunities and Challenges

数据库内决策支持：机遇与挑战

• 发表时间: 2022
• 期刊: A Quarterly bulletin of the IEEE Computer Society Technical Committee on Database Engineering
• 作者: Azza Abouzied;Peter J. Haas;Alexandra Meliou
• 通讯作者: Alexandra Meliou