EPSRC logo

Details of Grant 

EPSRC Reference: EP/V039318/1
Title: Query Evaluation
Principal Investigator: Chen, Dr H
Other Investigators:
Researcher Co-Investigators:
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 DatePanel NameOutcome
27 Jan 2021 EPSRC ICT Prioritisation Panel January 2021 Announced
Summary on Grant Application Form
Ever since the birth of the theory of NP-hardness,

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, real-world 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


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 state-of-the-art 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 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: