View-based query determinacy and rewritings over graph databases
At the École Normale Supérieure de Cachan, room Fonteneau, on Tuesday, December, 8th at 2pm.
Graph databases appear naturally in various scenarios, such as social networks and the semantic Web. In these cases, the information contained in the database lies as much in the data itself as in the topology of the graph, that is, in how the data points are linked together. This leads to considering traditional database theory questions for query languages that return data nodes based on the paths of the graph connecting them.
We focus our attention on the view-based query determinacy and rewriting problems. They ask the question whether a view of the database contains enough information to fully answer a query without accessing the database directly. If so, we then want to express the answer to the query directly with regards to the view. This setting occurs in many applications, such as data integration and query optimization.
We start by comparing these two tasks to other common task in this setting: computing certain answers, checking consistency of a view instance and updating it. We then build on these results in two specific cases. First, we show that for regular path queries, the existence of a monotone rewriting coincides with the existence of a rewriting expressible in Datalog. Then, we show that for views that only consider the lengths of the path in the graph, we can decide a weaker form of determinacy, called asymptotic determinacy, and produce first-order rewritings for the queries that are asymptotically determined.
Following the tragic events in Paris, ENS Cachan has strengthened the security rules on the campus. If you already come frequently to the campus, then you don't have to do anything special: you can directly come to the room at the time and date of the defense. Otherwise, you must send me an email by December, 2nd at the latest to confirm your intention to come, so that I can send the list of visitors to the welcome desk. You will also need an ID for the security guards to let you in the campus.