Tiresias: the database oracle for how-to queries
Tiresias: the database oracle for how-to queries
复制标题
Tiresias：用于操作查询的数据库预言机
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Dan Suciu
中科院分区：
文献类型：
--
作者：
A. Meliou;Dan Suciu
如何查询回答形式的基本数据分析问题：“输入应该如何变化以实现所需的输出”。作为一个反向数据管理问题，对方法查询的评估要比其“向前”对应物更难：假设或Queries。在本文中，我们介绍了Tiresias，这是第一个为操作问题提供支持的系统，允许对一组约束优化问题，特别是混合整数编程问题的定义和集成评估，以及关系数据库系统。 Tiresias通过发出标准SQL语句来生成问题变量，约束和目标，从而允许其与任何RDBMS集成。这项工作的贡献如下：（a）我们使用可能的世界语义来定义操作方法查询，并根据对标准数据标准数据的简单扩展提出规范语言TIQL（对于Tiresias查询语言）。 （b）我们定义了从TIQL规范生成混合整数程序（MIP）的翻译规则，可以使用现有工具来解决。 （c）Tiresias实现了功能强大的“数据感知”优化，这些优化超出了现代MIP求解器的功能，从而极大地改善了系统性能。 （d）最后，对TPC-H数据集进行了广泛的性能评估，证明了这些优化的有效性，尤其是强调了将分裂和争议方法应用于较小实例的能力。
How-To queries answer fundamental data analysis questions of the form: "How should the input change in order to achieve the desired output". As a Reverse Data Management problem, the evaluation of how-to queries is harder than their "forward" counterpart: hypothetical, or what-if queries. In this paper, we present Tiresias, the first system that provides support for how-to queries, allowing the definition and integrated evaluation of a large set of constrained optimization problems, specifically Mixed Integer Programming problems, on top of a relational database system. Tiresias generates the problem variables, constraints and objectives by issuing standard SQL statements, allowing for its integration with any RDBMS. The contributions of this work are the following: (a) we define how-to queries using possible world semantics, and propose the specification language TiQL (for Tiresias Query Language) based on simple extensions to standard Datalog. (b) We define translation rules that generate a Mixed Integer Program (MIP) from TiQL specifications, which can be solved using existing tools. (c) Tiresias implements powerful "data-aware" optimizations that are beyond the capabilities of modern MIP solvers, dramatically improving the system performance. (d) Finally, an extensive performance evaluation on the TPC-H dataset demonstrates the effectiveness of these optimizations, particularly highlighting the ability to apply divide-and-conquer methods to break MIP problems into smaller instances.