2014-06-20 Prioritized Repairing and Consistent Query Answering in Relational Databases

20 juin 2014, 14h, Lirmm Slawek Staworko (INRIA Lille)Prioritized Repairing and Consistent Query Answering in Relational Databases

I will present my work on incorporating preferences on how to resolve conflicts into the framework of consistent query answers (CQA) for relational databases.
The standard framework defines consistent answers to a query essentially by evaluating the query in every possible repair of the given (inconsistent) databases. A repair is a minimally-different consistent database, which corresponds to a particular choice of resolution of all conflicts. However, in many scenarios, we may have a preference on how certain conflicts should be resolved. For instance, when conflicts arise from integrating a number of consistent independent databases, we may have a measure of confidence in each database and wish to use it to influence the conflict resolution process. This ideally should lead to a smaller number of more refined repairs, and consequently, more informative consistent answers to the query.
The framework we propose allows to express the preferences on solving conflicts as priority, binary relation on conflicting tuples indicating the preferred resolution of every conflict. The main purpose of the priority relation is to define a preference relation on repairs, ideally allowing to identify the most preferred repairs. This task is far from being trivial because: 1) lifting a relation on objects to a relation on sets of objects is a (well-studied) problem with a number of possible solutions and 2) conflict resolution process is a convoluted task: resolving one conflict in one particular way may influence the number of possible ways other conflicts can be resolved. We formalise the problem of lifting priorities on conflicts to a preference relation on repairs and identify a number of desirable properties that a suitable solution should satisfy. We then propose a number of solutions that vary with the strength of preference enforcement in the conflict resolution and identify relationships among the proposed solutions. Finally, we analyse the computational implications of extending the framework of CQA with preferences.

Dernière mise à jour le 25/02/2015