| EPSRC Reference: |
EP/V039318/1 |
| Title: |
Query Evaluation |
| Principal Investigator: |
Chen, Dr H |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science and Information Systems |
| Organisation: |
Birkbeck College |
| Scheme: |
New Investigator Award |
| Starts: |
01 May 2021 |
Ends: |
30 April 2024 |
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 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
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 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
|
|
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: |
http://www.bbk.ac.uk/ |