PDQ: Proof-driven Query Planning

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

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.