Static analysis of navigational XPath over graph databases

• The paper deals with GXPath, the adaptation of XPath for graph databases.
• The central problems we study are containment and satisfiability of GXPath formulas.
• Both problems turn out to be undecidable for the full language.
• By restricting binary negation in GXPath we can show EXPTIME tight bounds for both problems.
• When no negation is allowed we show PSPACE-completeness of the containment problem.

Most query languages for graph databases rely on exploring the topological properties of the data by using paths. However, many applications require more complex patterns to be matched against the graph to obtain desired results. For this reason a version of the standard XML query language XPath has been adapted to work over graphs. In this paper we study static analysis aspects of this language, concentrating on problems such as containment, equivalence and satisfiability. We show that for the full language all of the problems are undecidable. By restricting the language we then obtain several natural fragments whose complexity ranges from PSpace-complete to ExpTime-complete.