Using variable automata for querying data graphs

• Past query languages for graph databases have tractable or PSpace-hard combined complexity.
• We propose variable automata as a language with intermediate (NP) complexity.
• We show that they are incomparable to previously studied languages.
• We show how to add them to previously used languages without increasing complexity.

Thus far query languages for graphs databases that, in addition to navigating the structure of a graph, also consider data values encountered along the paths they traverse, seem to exhibit somewhat dual behaviour in terms of the efficiency of their query evaluation problem. Namely, their combined complexity is either tractable, or are at least PSpace-hard. In this paper we show how to use the model of variable automata to get a query language with intermediate (NP-complete) combined complexity of query evaluation. Since variable automata are incomparable in terms of expressive power with previously studied querying mechanisms for data graphs we also show how to join their capabilities with the ones of previously used languages without an increase in the complexity of query evaluation, thus getting the best of both worlds.