Beyond Well-designed SPARQL
Beyond Well-designed SPARQL
复制标题
DOI：
10.4230/lipics.icdt.2016.5
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Kaminski;Egor V. Kostylev
中科院分区：
文献类型：
--
作者：
M. Kaminski;Egor V. Kostylev
SPARQL是RDF数据的标准查询语言。SPARQL的显著特征是OPTIONAL运算符，当由于缺乏信息而无法获得完整答案时，它允许部分答案。然而，可选匹配在计算上是昂贵的-查询应答是PSPACE完全的。SPARQL的精心设计的片段通过限制可选匹配的使用实现了更好的计算特性-查询应答变得是coNP完全的。然而，精心设计的SPARQL捕获的是远远不是所有现实生活中的查询--事实上，在使用OPTIONAL的DBpedia上，只有大约一半的查询是精心设计的。在本文中，我们研究了精心设计的SPARQL之外的查询。我们引入了一类弱的精心设计的查询，包括精心设计的查询，并包括最常见的有意义的非精心设计的查询：我们的分析表明，新的片段捕获约99%的DBpedia查询与OPTIONAL。同时，弱精心设计的SPARQL查询回答仍然是NP完全的，我们的片段在一定意义上是最大的这种复杂性。我们表明，片段的表达能力是严格的精心设计和完整的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. However, 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 about 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.