Containment of queries for graphs with data

Abstract

We consider the containment problem for regular queries with memory and regular queries with data tests: two recently proposed query languages for graph databases that, in addition to allowing the user to ask topological queries, also track how the data changes along paths connecting various points in the database.Our results show that the problem is undecidable in general. However, by allowing only positive data comparisons we find natural fragments with better static analysis properties: the containment problem is PSPACE-complete in the case of regular queries with data tests and EXPSPACE-complete in the case of regular queries with memory.