Journal article icon

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
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.1007/s00224-017-9802-9

Authors


More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
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
Pubs id:
pubs:702204
URN:
uri:18e702c1-2a0a-44f7-9376-46d58a79892d
UUID:
uuid:18e702c1-2a0a-44f7-9376-46d58a79892d
Local pid:
pubs:702204

Terms of use


Metrics


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