School of Informatics

EPSRC Fellowship is MAGIC

Professor Leonid Libkin has been awarded a £1.14M EPSRC Fellowship.

The Established Career Fellowship will fund a project called ‘MAGIC: MAnaGing InComplete Data - New Foundations’ from August 2016 until July 2021.

Professor Leonid Libkin

Professor Libkin says:

“The main goal of this research is to deliver new understanding of uncertain and incomplete information in data processing tasks, and by doing so provide new ways of getting knowledge out of such data.

“It will reconcile correctness guarantees with an efficient algorithmic toolkit that scales to large data sets, and put an end to perceived impossibility of achieving correctness and efficiency simultaneously for large classes of queries over incomplete data.”


Extracts from an abstract on the Research Councils UK website explain the problem which the project aims to address:

“In our data-driven world, one can hardly spend a day without using highly complex software systems that we have learned to rely on. These are systems we have on our laptops, they power websites of companies, and they keep companies and government offices running.

“We can rely on them as long as information they store is complete. In an autonomous environment, this is a reasonable assumption, but these days data is generated by a huge number of users and applications, and its incompleteness is a fact of life. The moment incompleteness enters the picture, everything changes: unexpected behaviour occurs.

“To make matters worse, many modern applications of data, including data integration, data exchange, ontology based data access, data quality, inconsistency management and a host of others, have incompleteness built into them, and try to rely on standard techniques for handling it. Current techniques guaranteeing correctness carry a huge complexity price, and applications look for ways around it, sacrificing correctness in the process.

“Our main goal is to end this sorry state of affairs. Correctness and efficiency can co-exist, but we need to develop new foundations of the field of incomplete information, and a new set of techniques based on these foundations, to reconcile the two. Crucially, we need to understand what it means to answer queries over incomplete data with correctness guarantees.”

Project partners

Professor Libkin will lead the research, working with project partners at the Centre for Semantic Web Research, Institut de Recherche en Informatique Fondamentale at Université Paris-Diderot, University of Rome La Sapienza, and LogicBlox Inc.

Useful links


The award on the Research Councils UK website

Professor Libkin’s Research Explorer webpage

Centre for Semantic Web Research

Institut de Recherche en Informatique Fondamentale

University of Rome La Sapenza