Querying graph databases (a theoretician's perspective)

Several query languages for graph data have been considered in the past, ranging from relational approaches that supported extraction of attribute values, to regular path queries and their extensions that examine patterns connecting the nodes, but completely disregard the data they encounter. In this presentation we will introduce several languages that mix these two modes of querying thus allowing the user to explore how the actual data changes along paths and patterns connecting graph nodes. We will start with a brief discussion of the data model and show how different features can be coded in a simple theoretical model supporting values and labels. We then introduce a number of new query languages using ideas from automata theory and XML and examine some of their fundamental properties such as query evaluation and expressive power.