Journal article
Complexity and expressive power of weakly well-designed SPARQL
- Abstract:
-
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:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Funding
+ Engineering and Physical Sciences Research Council
More from this funder
Grant:
ED3
projectsScore!,DBOnto,
Bibliographic Details
- Publisher:
- Springer US Publisher's website
- Journal:
- Theory of Computing Systems Journal website
- Volume:
- 62
- Issue:
- 4
- Pages:
- 772–809
- Publication date:
- 2017-08-14
- Acceptance date:
- 2017-06-29
- DOI:
- EISSN:
-
1433-0490
- ISSN:
-
1432-4350
- Source identifiers:
-
702204
Item Description
- Keywords:
- Pubs id:
-
pubs:702204
- UUID:
-
uuid:18e702c1-2a0a-44f7-9376-46d58a79892d
- Local pid:
- pubs:702204
- Deposit date:
- 2017-06-29
Terms of use
- Copyright holder:
- Kaminski and Kostylev
- Copyright date:
- 2017
- Notes:
-
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.
- Licence:
- 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