EPSRC logo

Details of Grant 

EPSRC Reference: EP/M005852/1
Title: PDQ: Proof-driven Query Planning
Principal Investigator: Benedikt, Professor M
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Computer Science
Organisation: University of Oxford
Scheme: EPSRC Fellowship
Starts: 30 June 2015 Ends: 30 December 2020 Value (£): 938,362
EPSRC Research Topic Classifications:
Information & Knowledge Mgmt
EPSRC Industrial Sector Classifications:
Information Technologies
Related Grants:
Panel History:
Panel DatePanel NameOutcome
17 Jul 2014 EPSRC ICT Prioritisation Panel - July 2014 Announced
04 Sep 2014 ICT Fellowships Interview Meeting - 4 Sept 2014 Announced
Summary on Grant Application Form
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.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.ox.ac.uk