权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

PDQ: Proof-driven Query Planning

PDQ：证明驱动的查询规划

基本信息

批准号：
EP/M005852/1
负责人：
Michael Benedikt
金额：
$ 119.57万
依托单位：
University of Oxford
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2015
资助国家：
英国
起止时间：
2015 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FM005852%2F1
关键词：
PDQ Proof driven Query Planning

项目摘要

Current data management solutions have several bottlenecks. One concerns scale -- how to get complex queries to run more quickly over ever-larger datasets. Another one, increasingly recognized by the research community, concerns usability: the most common data management solutions require data to be available in an SQL schema, with application programmers needing to write custom code to transform data from a myriad of other formats into the one "gold standard'' flat data description. This project provides assistance on both of these problems through the development of an advanced query planning system that can deal with sources that have complex interfaces and rich integrity constraints.By query planning we refer to a process that takes as input a query specified in terms of one vocabulary, translating it into a description in another vocabulary that can be more efficiently executed. Our approach to query planning, proof-driven query planning (PDQ), is based onfoundational ideas from computational logic: we search for "a proof that the query is answerable'' relative to the interfaces and constraints.For each such proof we can use a variation of a technique from logic -- interpolation -- to produce a query plan that abides by the interfaces while making use of the constraints. As we search for a proof, we can estimate the cost of the generated plan, thus taking intoaccount proof structure and cost in searching for the optimal plan. Thus PDQ combines ideas from logic, query optimization, and search.The importance of taking into account interface restrictions and data semantics in new data-driven applications, along with recent advances in reasoning systems for relational data, make this exactly the right time to take a fresh look at exploiting reasoning within query planning.Proof-driven query planning provides benefits in diverse application scenarios. It can be applied within a middleware setting in which the user queries refer to external data that is difficult to access. It applies also to the problem of finding more efficient plans within a single database manager, either running on top of the DBMS or subsuming the setting of traditional database query optimization. The impact of PDQ is foundational as well as practical:proof-driven query planning gives a new methodology for transforming a logical plan to a physical plan that unifies application-level integrity constraints with logical/physical mappings, giving the prospect of a fully logic-based approach to query optimization in database management systems. We will develop not only the underlying foundation of proof-driven planning, but also create proof-of-concept systems for the middleware and centralized settings.

当前的数据管理解决方案存在几个瓶颈。一个是规模问题——如何让复杂的查询在越来越大的数据集上运行得更快。另一个逐渐被研究团体认识到的问题与可用性有关：最常见的数据管理解决方案要求数据在SQL模式中可用，应用程序程序员需要编写自定义代码将数据从无数其他格式转换为一个“黄金标准”平面数据描述。该项目通过开发高级查询规划系统来帮助解决这两个问题，该系统可以处理具有复杂接口和丰富完整性约束的源。通过查询规划，我们指的是这样一种流程，它将用一种词汇表指定的查询作为输入，并将其转换为另一种词汇表中的描述，以便更有效地执行。我们的查询规划方法，证明驱动的查询规划（PDQ），是基于计算逻辑的基本思想：我们搜索相对于接口和约束的“查询是可回答的证明”。对于每一个这样的证明，我们都可以使用逻辑技术的一种变体——插值——来生成一个在使用约束的同时遵守接口的查询计划。在寻找证明时，我们可以估计生成的方案的成本，从而在寻找最优方案时考虑到证明结构和成本。因此，PDQ结合了逻辑、查询优化和搜索的思想。在新的数据驱动的应用程序中考虑接口限制和数据语义的重要性，以及关系数据推理系统的最新进展，使得现在正是重新审视在查询计划中利用推理的最佳时机。证明驱动的查询规划在不同的应用场景中提供了好处。它可以应用于中间件设置中，其中用户查询引用难以访问的外部数据。它还适用于在单个数据库管理器中找到更有效的计划的问题，这些计划要么运行在DBMS之上，要么包含传统数据库查询优化的设置。PDQ的影响既基础又实用：证明驱动的查询规划提供了一种将逻辑计划转换为物理计划的新方法，该方法将应用程序级别的完整性约束与逻辑/物理映射统一起来，从而为数据库管理系统中的查询优化提供了一种完全基于逻辑的方法。我们不仅将开发证明驱动计划的底层基础，还将为中间件和集中设置创建概念证明系统。