Kaminski Mark, Kostylev Egor V
Department of Computer Science, University of Oxford, Oxford, UK.
Theory Comput Syst. 2018;62(4):772-809. doi: 10.1007/s00224-017-9802-9. Epub 2017 Aug 14.
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 queries and includes most common meaningful non-well-designed queries: our analysis shows that the new fragment captures over 99% of DBpedia queries with OPTIONAL. At the same time, query answering for weakly well-designed SPARQL remains coNP-complete, and our fragment is in a certain sense maximal for this complexity. We show that the fragment's expressive power is strictly in-between well-designed and full SPARQL. Finally, we provide an intuitive normal form for weakly well-designed queries and study the complexity of containment and equivalence.
SPARQL是用于RDF数据的标准查询语言。SPARQL的独特之处在于OPTIONAL运算符，当由于信息不足而无法获得完整答案时，该运算符允许给出部分答案。然而，可选匹配在计算上代价高昂——查询回答是PSPACE完全问题。经过精心设计的SPARQL片段通过限制可选匹配的使用实现了更好的计算属性——查询回答变为coNP完全问题。不利的一面是，精心设计的SPARQL远不能涵盖所有实际查询——事实上，在DBpedia上使用OPTIONAL的查询中，只有大约一半是精心设计的。在本文中，我们研究精心设计的SPARQL之外的查询。我们引入了弱精心设计查询类，它包含精心设计的查询，并包括大多数常见的有意义的非精心设计查询：我们的分析表明，新片段涵盖了超过99%的带有OPTIONAL的DBpedia查询。同时，弱精心设计的SPARQL的查询回答仍然是coNP完全问题，并且我们的片段在这种复杂度方面在某种意义上是最大的。我们表明，该片段的表达能力严格介于精心设计的SPARQL和完整的SPARQL之间。最后，我们为弱精心设计的查询提供了一种直观的范式，并研究了包含和等价的复杂度。
