Description


Summary

Data management systems nowadays need to handle large data sets often containing inconsistent or incomplete information, and yet provide meaningful answers while guaranteeing data privacy requirements. This project aims at advancing the foundations of query answering in the presence of incomplete or inconsistent data. For various query languages and data integrity constraints, we will develop new techniques for making access control and privacy more reliable and develop new tools for making data querying more efficient. These developments hinge upon the key notion of certain answers of a query: answers found in all possible plausible interpretations of an inconsistent 1/20or incomplete data set. A special case of incomplete data arises from concealing information to certain users, with the purpose of preserving data privacy. The question of whether this concealment indeed leaks private data is then a delicate matter, known as the determinacy problem, and it is still not well understood.

Our research program focuses on the problems of certain answers and determinacy in relation to three scenarios: ensuring data privacy, querying inconsistent data, and querying incomplete data. We will develop 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. Further, we will investigate formal connections with certain Constraint Satisfaction Problems (CSP), which shall bring new insights both to the database and CSP communities.

Project QUID is a 48-month 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). It will also benefit from existing international collaborations. The project also includes the hiring of a PhD student who will be jointly supervised between LaBRI and IRIF, and a 1-year post-doctoral fellow.

Objectives

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, e.g. [GLS14; Lib15; Wij12]. Despite all the attention attracted, effective and efficient methods are still missing in all three scenarios above, and the development of these methods are the main goal of this proposal.

Moreover, recent studies [FSS15; Fon15; LW15] 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.