The IRIF lab in Paris and the LABRI lab in Bordeaux, France have funding for a co-supervised PhD studentship in database theory starting in 2019.
IRIF and LABRI are both very strong internationally renown research environments, hosting leading groups in several areas of theoretical computer science. For more information about the two labs please visit IRIF and LABRI.
The PhD topic is in the area of foundations of data management, focusing on querying inconsistent data.
Data management systems nowadays need to handle large data sets often containing inconsistent or incomplete information, and yet guarantee the relevance of query answers. New techniques are needed for making data access more reliable, and new tools are required for making data querying more efficient in this context.
The main focus of the PhD will be the study of consistent query answering. In this scenario the data set may have inconsistencies relative to integrity constraints (e.g., key and foreign key constraints, functional dependencies, inclusion constraints, etc.). Queries issued on the database need to be answered despite the inconsistencies. The goal is to provide only consistent answers, i.e. answers that can be be found after virtually repairing the database to remove inconsistencies. As many repairs may exist for a given database, the widely accepted notion is the one of certain answers, i.e. answers that can be found in all possible database repairs.
The challenge is then to provide efficient algorithms for computing certain answers directly from the inconsistent database, as going through all possible repairs is clearly unfeasible. Particularly attractive is the possibility of obtaining certain answers by query rewriting, i.e. by issuing on the inconsistent database a new query with good computational properties. Despite a rich literature on the topic (see [1,2,3] for instance) many questions remain open even for simple classes of queries and constraints, such as conjunctive queries and primary key constraints.
This PhD topic is part of a larger projet QUID (Efficient Querying for Incomplete and Inconsistent Data), funded by the French research agency ANR, starting in 2019. The project involves researchers from two other research labs in France: École Normale Supérieure (Paris) and the Institut Gaspard Monge (Marne-la-Vallée), and it studies certain answers in relation to three scenarios: ensuring data privacy, querying inconsistent data, and querying incomplete data. All these settings share the notion of certains answers used to answer queries over all possible plausible interpretations of an inconsistent, incomplete or partially specified data.
The PhD student will also be welcome to contribute to the other topics of the project.
Requirements
Candidates should have a strong background in theoretical computer science, preferably in automata, logic, verification, or finite model theory. Some prior knowledge of database theory and systems is also a plus.
Position
The funding is for a 3-year full time position. The PhD must start during 2019; the precise starting date is to some extent negotiable. The PhD student will be co-supervised by Paris and Bordeaux, and is expected to spend time in both sites. Teaching is not mandatory but can be arranged upon request.
Contacts
Informal enquiries about this position are welcome and should be sent to both Diego Figueira (diego.figueira@labri.fr) and Cristina Sirangelo ( cristina@irif.fr).
[1] L.Bertossi. Database Repairing and Consistent Query Answering Synthesis Lectures on Data Management. Morgan & Claypool Publishers [2] P. Koutris, J.Wijsen. (2017) Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints. ACM Transactions on Database Systems 42:2, 1-45. [3] C.Lutz, F.Wolter. On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems. ICDT 2015: 363-379