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 on
foundational 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 into
account 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.

The project outlines a new way to inject logical methods into database systems. This has significant industrial impact as well as foundational impact.


I. Impact for users of data management products includes:

-- the project provides an approach to improve performance in running complex queries over datasets that are mushrooming in size, by allowing more powerful integrity constraint-aware optimization. The impact can be particularly significant when the data to be accessed resides on the web, and thus the overhead of accessing data dominates processing time.

-- the project gives a significant increase to the usability of data management systems by:

--- allowing data from web-based sources to be pulled in transparently to answer queries

--- insulating database developers from the details of mappings -- both mappings between the programmer view of data objects and the underlying stored data and mappings among datasources -- while exploiting these mappings in generating efficient query plans. The current need to create and maintain these mappings is known to be a huge "pain point" for database users.

Furthermore:

--- The technology makes the benefits of logic-based optimization available to current database management environments, targeting "closed world'' systems based on the relational model and its extensions (e.g. nested relations). This proposal thus represents an excellent complement to existing research initiatives focusing on newer data models.

--- The techniques can be used in a ``pay-as-you-go'' manner, allowing a trade-off between the sophistication of plan search applied and the time spent during search.


II. For designers of data management systems, the project investigates a more general approach to accounting for reasoning in query processing compared to that used in current systems. The PDQ approach can incorporate reasoning within optimization for formulas with arbitrary quantifier nesting, and allows by default a set of background integrity constraints. This is a significant improvement over current practice.

III. From the foundational perspective, the full realization of the project's goals holds out the promise of a new logic-based approach to query
processing based on proof search and interpolation. This is exciting not just from the perspective of database systems, but for the wider program of using declarative methods within computing.

Constraint-based optimization of database queries has long been a goal of the research community, but the time is ripe for taking the next step in making constraint-aware systems the norm. The explosion of web-accessible datasources has made querying in non-traditional settings, with greater overlap of sources and longer-running and more expensive computations, more urgent.
At the same time, research on reasoning systems for relational database constraints has made great strides in recent years, providing the basis for reasoning-based components in a query optimizer.

Not only is this the right time to carry out this research, Oxford is certainly the ideal place for it. It has world-class research groups in data management and knowledge representation as well as in all aspects of computational logic. It also has research strengths in many areas that border on the project, from programming languages to verification.