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-designed SPARQL captures far from all real-life queries-in fact, only about half of the queries over DBpedia that use OPTIONAL are well-designed. In the present paper, we study queries outside of well-designed SPARQL. We introduce the class of weakly well-designed queries that subsumes well-designed querie

SUBMITTER: Kaminski M 

PROVIDER: S-EPMC6560828 | biostudies-literature | 2018

REPOSITORIES: biostudies-literature