Journal article

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.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Kostylev, E., Reutter, J., & Vrgoč, D. (2017). Containment of queries for graphs with data. Journal of Computer and System Sciences, 92, 65–91.

MLA Style

Kostylev, E, et al. “Containment of Queries for Graphs with Data.” Journal of Computer and System Sciences, vol. 92, 2017, pp. 65–91.

Chicago Style

Kostylev, E, J Reutter, and D Vrgoč. 2017. “Containment of Queries for Graphs with Data.” Journal of Computer and System Sciences 92: 65–91.
Print

Access Document

Files:: containment-v-jcss.pdf

(Preview, Accepted manuscript, pdf, 408.6KB, Terms of use)

Publisher copy:: 10.1016/j.jcss.2017.09.005

Authors

+ Kostylev, E More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Role:: Author

+ Reutter, J More by this author

Role:: Author

+ Vrgoč, D More by this author

Role:: Author

Publisher:: Elsevier
Journal:: Journal of Computer and System Sciences More from this journal
Volume:: 92
Pages:: 65-91
Publication date:: 2017-09-29
Acceptance date:: 2017-09-15
DOI:: 10.1016/j.jcss.2017.09.005
ISSN:: 0022-0000

Keywords:: query containment

query languages

data values

graph databases
Pubs id:: pubs:735076
UUID:: uuid:17813933-c00c-4c78-ba4d-7e6f70394a0e
Local pid:: pubs:735076
Source identifiers:: 735076
Deposit date:: 2017-10-11
ARK identifier:: ark:/29072/ora_17813933c00c4c78ba4d7e6f70394a0e

Terms of use

Copyright holder:: Elsevier Inc
Copyright date:: 2017
Notes:: Copyright © 2017 Elsevier Inc. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: https://doi.org/10.1016/j.jcss.2017.09.005

Licence:: CC Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND)

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP