Lab Lunch: 8 May 2018 - Andreas Pieris

Title: An Operational Approach ot Consistant Query Answering

Abstract:

Consistent query answering (CQA) aims to find 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, which 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. Can we achieve this goal? I will try to give a positive answer to this question.

This is joint work with Marco Calautti and Leonid Libkin.