Journal article
Static analysis of navigational XPath over graph databases
- Abstract:
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 304.6KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.ipl.2016.03.006
Authors
- Publisher:
- Elsevier
- Journal:
- Information Processing Letters More from this journal
- Volume:
- 116
- Issue:
- 7
- Pages:
- 467–474
- Publication date:
- 2016-03-16
- Acceptance date:
- 2016-03-09
- DOI:
- EISSN:
-
1872-6119
- ISSN:
-
0020-0190
- Keywords:
- Pubs id:
-
pubs:611153
- UUID:
-
uuid:8cd697f2-d481-4ca9-a631-81b20a26eb4b
- Local pid:
-
pubs:611153
- Source identifiers:
-
611153
- Deposit date:
-
2016-03-20
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier
- Copyright date:
- 2016
- Notes:
- © 2016 Elsevier B.V. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: 10.1016/j.ipl.2016.03.006
If you are the owner of this record, you can report an update to it here: Report update to this record