Theory of Structured Data group

We are a part of the Laboratoire International Associé SINFIN (langageS, logIque, et vérificatioN pour l'inFormatIque fondameNtale). Our main research topics deal with the foundations of graph-structured data.

We study query languages that combine both constraints based on graph topology, and tests for data ranging over potentially infinite domains. On the one hand, we develop algorithms for efficient evaluation and static analysis for these languages such as decidability and complexity of paradigmatic problems, efficient algorithms for query evaluation and containment, and query optimization. On the other hand, we study the fundamental properties inherent to them -such as the characterization of its expressive power, model theory, definability, axiomatization, etc.

Some of the specific topics we study are the following:

• Modal logics with data. We study specification and verification techniques which are able to deal with explicit data, applied to graph structured databases. We put the focus on modal logics equipped with data-testing modalities, such as the language XPath and its fragments.

• Learning and defining graph-structured datasets. The problem of learning, i.e. reverse engineering, a query satisfying a given set of positive and negative examples, is related to the de definability problem : Given a model M, a query language L, and a target relation R, is there a formula 𝜑 of L whose extension when evaluated on M is exactly R? The complexity of the definability problem for different languages is almost completely unexplored and there are few implemented algorithms.

• Efficient querying of evolving data. Currently, only a few algorithmic tools and basic query languages are able to exploit data evolutions to ease information extraction and verify properties. We aim at developing new query languages and algorithmic tools for efficient querying of graph-structured data evolutions.