EPSRC Reference: 
EP/V039318/1 
Title: 
Query Evaluation 
Principal Investigator: 
Chen, Dr H 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Informatics 
Organisation: 
Kings College London 
Scheme: 
New Investigator Award 
Starts: 
01 August 2023 
Ends: 
31 July 2026 
Value (£): 
475,688

EPSRC Research Topic Classifications: 
Fundamentals of Computing 
Information & Knowledge Mgmt 
Logic & Combinatorics 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
27 Jan 2021

EPSRC ICT Prioritisation Panel January 2021

Announced


Summary on Grant Application Form 
Ever since the birth of the theory of NPhardness,
computer science has had to cope with the realization
that many computational problems of interest
are unlikely to be computationally tractable.
As instances of such hard problems need to be
coped with and solved in practice,
it is natural to seek restricted cases (of such problems)
that are computationally tractable, in hopes of better understanding
the sources of tractability and intractability.
We propose to study the problem
of query evaluation from this angle.
Query evaluation is (here) defined
to be the following problem:
an instance consists of
a formula and a relational structure;
the task is to
compute the answers (or satisfying assignments)
to the formula over the structure.
Motivations for studying query evaluation arise from
the fact that this problem occurs prominently in many areas, such as
database theory, realworld problem modelling, and
computational complexity theory.
Here, we aim to understand how the nature of
various formulas impacts the complexity of this task:
a key aim of this project is to prove systematic complexity
classification theorems that describe, for a logic,
the classes of formulas on which this task is tractable.
In addition to proving classification theorems,
we plan to study many associated research issues that
arise naturally from the described motivation;
these issues relate to a diversity of research areas including graph theory,
database theory, and finite model theory.
For example, we will strive to
understand the nature of the tractable cases, in particular,
the types of efficient algorithms that can solve them.
Towards proving such classification theorems,
we aim to develop complexity measures for formulas
that will allow for the identification of tractability results for query evaluation,
much as the established measure of treewidth on graphs allows for tractability results
for problems involving graphs.
This objective may thus be of broad and conceptual interest throughout computer science, as it involves
finding ways to decompose objects that are more complex than
graphs.
Let us note that treewidth itself
has already been applied to measure and understand logical formulas
in previously completed research.
The complexity measures to be developed will potentially constitute
further interesting generalizations of treewidth, and there is
the potential for an interplay with and broadening of
the existing rich theory of treewidth.
Successful research in the scope of this project will
have strong academic ramifications, which then have the ability
to improve stateoftheart practice in database query evaluation.
In essence, this project asks foundational questions that support
a much deeper and richer understanding of database query evaluation, and crucially focuses on its efficiency; these research issues can now be advanced due to the maturity of the theoretical point of view.
Via implementations of the developed techniques,
there is thus the potential to make query evaluation much more efficient, on the foundational classes of queries considered here,
reducing costs and allowing for higher capabilities in the industry.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

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: 
