CSE Research Seminar: An Operational Approach to Consistent Query Answering

Speaker Name: 
Andreas Pieris
Speaker Title: 
Speaker Organization: 
University of Edinburgh, UK
Start Time: 
Tuesday, November 13, 2018 - 2:00pm
End Time: 
Tuesday, November 13, 2018 - 3:30pm
Phokion G. Kolaitis

Abstract: Consistent query answering (CQA) aims at finding meaningful answers to queries when databases are inconsistent, i.e., do not conform to their specifications. Such answers must be certainly true in all repairs, which are consistent databases whose difference from the inconsistent one is minimal, according to some measure. This task is often computationally intractable, and much of CQA research concentrated on finding islands of tractability. Nevertheless, there are many relevant queries for which no efficient solutions exist. This is reflected by the limited practical applicability of the CQA approach. We are convinced that the ultimate goal of a practically applicable CQA approach should be efficient approximation algorithms that quickly deliver sufficiently good consistent answers with explicit error guarantees. In this talk, I will present a new framework for CQA based on revised definitions of repairs and query answering that opens up the possibility of efficient approximate query answering. I will then discuss the complexity of both exact and approximate CQA. Even though some of the problems remain hard, for many common classes of constraints we can provide meaningful answers in reasonable time, for queries going far beyond the standard approach.

This is joint work with Marco Calautti and Leonid Libkin. 
Bio: Andreas Pieris has been a Lecturer in the School of Informatics at the University of Edinburgh since September 2016. Prior to this, he was a postdoctoral researcher at the Institute of Information Systems (now called Institute of Logic and Computation) of the Vienna University of Technology from November 2014 until September 2016, and a postdoctoral researcher at the Department of Computer Science of the University of Oxford from October 2011 until October 2014. His research interests are database theory with emphasis on query languages, knowledge representation and reasoning, computational logic and its applications to computer science. He has published more than seventy papers, most of them in leading international conferences and journals. He has served on the PCs of numerous international conferences and workshops, including the top-tier database and AI conferences (PODS, ICDT, IJCAI, AAAI, and KR). He has also given invited talks and tutorials at international workshops and summer schools.