1. INVITED TALK ABSTRACT
Several modern graph query languages are capable of expressing sophisticated graph queries, which return nodes connected by arbitrarily complex paths. Such paths can be synthesized by regular expressions and often involve recursion. Such graph queries are known as Regular Path Queries and correspond to Property Paths in Sparql 1.1. Recently, with my colleagues I have been investigating regular path queries and their combinations by looking at the generation problem [1, 2, 3, 10], the complexity of query evaluation [5] and the learning problem [9, 7, 6, 8]. Precisely, we focused on schema-driven generation of complex and broad graph queries with user-de ned features, on the complexity of the evaluation of regular simple path queries and on learning algorithms for regular path queries. In this talk, I will begin with a brief recap of graph queries and their expressive power. I will then provide an overview of a comprehensive query-oriented graph benchmark that we have designed and assessed [1, 2, 3, 10]. I will next discuss the theoretical results of our study on the complexity of regular simple path queries [5]. I will then present a learning framework for regular path queries and discuss its potential along with its practical feasibility [7, 6, 8]. To conclude, I will brie y outline our ongoing work [4] and pinpoint lingering issues and research directions in the study of graph queries.
Acknowledgements This is joint work with my colleagues at CNRS, Eindhoven University of Technology, Universite Clermont Auvergne, Universite Lille 3 and Universite Paris Sud. This work is partially supported by the Palse Impulsion Individual Grant and by the CNRS Mastodons MedClean.