Scalable Package Queries in Relational Database Systems
Scalable Package Queries in Relational Database Systems
复制标题
DOI：
10.14778/2904483.2904489
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Matteo Brucato;J. F. Beltran;A. Abouzeid;A. Meliou
中科院分区：
文献类型：
--
作者：
Matteo Brucato;J. F. Beltran;A. Abouzeid;A. Meliou
传统的数据库查询遵循一个简单的模型：它们定义结果中的每个元组必须满足的约束。该模型在计算上是高效的，因为数据库系统可以单独评估每个元组上的查询条件。然而，许多实际的现实问题需要一组结果元组来共同满足约束，而不是单独满足。在本文中，我们提出了包查询，这是一种新的查询模型，它扩展了传统的数据库查询，以处理复杂的约束和对答案集的偏好。我们开发了一个成熟的包查询系统，该系统在传统的数据库引擎上实现。我们的工作做出了几项贡献。首先，我们设计了PaQL，这是一种基于SQL的查询语言，支持包查询的声明性规范。我们证明了PaQL至少和整数线性规划一样有表达能力，因此包查询的计算在一般情况下是NP难的。其次，我们提出了一种基本的评估策略，该策略结合了数据库和约束优化求解器的能力来获得包查询的解决方案。该方法的核心是一组将包查询转换为整数线性规划的转换规则。第三，我们引入了离线数据分区策略，允许查询计算扩展到大数据大小。第四，我们介绍了一种可扩展的包评估算法SketchRefine，它具有强逼近保证((1±e)6因子逼近)。最后，我们给出了在真实世界和基准数据上的广泛实验。结果表明，SketchRefining在获取高质量的包结果方面是有效的，并且获得的运行时性能比直接在大型数据集上使用ILP解算器快一个数量级。
Traditional database queries follow a simple model: they define constraints that each tuple in the result must satisfy. This model is computationally efficient, as the database system can evaluate the query conditions on each tuple individually. However, many practical, real-world problems require a collection of result tuples to satisfy constraints collectively, rather than individually. In this paper, we present package queries, a new query model that extends traditional database queries to handle complex constraints and preferences over answer sets. We develop a full-fledged package query system, implemented on top of a traditional database engine. Our work makes several contributions. First, we design PaQL, a SQL-based query language that supports the declarative specification of package queries. We prove that PaQL is at least as expressive as integer linear programming, and therefore, evaluation of package queries is in general NP-hard. Second, we present a fundamental evaluation strategy that combines the capabilities of databases and constraint optimization solvers to derive solutions to package queries. The core of our approach is a set of translation rules that transform a package query to an integer linear program. Third, we introduce an offline data partitioning strategy allowing query evaluation to scale to large data sizes. Fourth, we introduce SketchRefine, a scalable algorithm for package evaluation, with strong approximation guarantees ((1 ± e)6-factor approximation). Finally, we present extensive experiments over real-world and benchmark data. The results demonstrate that SketchRefine is effective at deriving high-quality package results, and achieves runtime performance that is an order of magnitude faster than directly using ILP solvers over large datasets.