Efficient querying of incomplete and inconsistent data – QUID

Data management systems nowadays need to cope with large data sets, often integrated from many heterogeneous sources, containing redundant, inconsistent and incomplete data. Moreover, data is often not available in its whole, due to prohibitively large data volumes or access restrictions. In this scenario, data management becomes error-prone and vulnerable to data leakage.

At the same time, we witness an increasing need for reliable and efficient systems, providing more privacy, more security, and more relevant answers to user queries.

Our proposal aims at narrowing the gap between current capabilities of data management systems on the one hand, and user requirements on the other hand. This will be done by developing formal methods for analysing data management protocols as well as efficient algorithms for computing relevant answers. These new methods will make access control and privacy more reliable, and they will enable the exploitation of data containing inconsistencies or incomplete information.

Our research program is targeted towards three different but related scenarios. In the first scenario we are interested in querying data views, and analysing the information they may leak on the original data, impacting privacy and data leakage issues. The second one concerns repairs of inconsistent data sets, with a direct impact on efficient algorithms for retrieving relevant answers. In the third scenario we deal with the presence of missing data, and aim at providing effective methods to answer user queries efficiently.

Despite the specificity of each of these scenarios, they have one main aspect in common. In each of them one lacks full information on the data that needs to be queried, but the system still needs to answer user queries with certainty, and provide security guarantees. The certainty aspect is the main technical difficulty in finding good solutions and this has been extensively studied in the literature. Despite all the attention attracted, effective and efficient methods are still missing in all three scenarios above, and the development of these methods is the main goal of this proposal.

Moreover, recent studies have independently shown evidence that certainty in query answering is intimately related to Constraint Satisfaction Problems (CSP), a very active area of research at the frontier of mathematics and graph theory. So far, these relationships with CSP have been shown in an ad-hoc way, each tailored to a particular problem. However, we think that there is ground for a unified approach which can also feedback the CSP area with novel interesting questions. This constitutes the most prospective goal of this proposal.

QUID is a collaborative project involving research groups working on different areas of database theory. The consortium brings together 8 researchers from 4 laboratories: Laboratoire d'Informatique Gaspard-Monge (LIGM, Université Marne-la-Vallée), Institut de Recherche en Informatique Fondamentale (IRIF, Paris Diderot), École Normale Supérieure de Paris (ENS Ulm) and Laboratoire Bordelais de Recherche en Informatique (LaBRI, Université de Bordeaux). The project also includes the hiring of a PhD student and two 1-year post-doctoral fellows.