Complexity and expressive power of weakly well-designed SPARQL
SPARQL is the standard query language for RDF data. The distinctive feature of SPARQL is the OPTIONAL operator, which allows for partial answers when complete answers are not available due to lack of information. However, optional matching is computationally expensive—query answering is PSPACE-complete. The well-designed fragment of SPARQL achieves much better computational properties by restricting the use of optional matching—query answering becomes coNP-complete. On the downside, well-desi...Expand abstract
- Publication status:
- Peer review status:
- Peer reviewed
(Version of record, pdf, 1.7MB)
- Publisher copy:
- Copyright holder:
- Kaminski and Kostylev
- Copyright date:
Copyright © 2017 The Authors.
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record