On the Satisfiability Problem of Patterns in SPARQL 1.1
On the Satisfiability Problem of Patterns in SPARQL 1.1
复制标题
DOI：
10.1609/aaai.v32i1.11549
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Xiaowang Zhang;J. V. D. Bussche;Kewen Wang;Zhe Wang
中科院分区：
文献类型：
--
作者：
Xiaowang Zhang;J. V. D. Bussche;Kewen Wang;Zhe Wang
模式可满足性是 SPARQL 的一个基本问题。本文对 SPARQL 1.1 模式的可满足性问题的可判定性/不可判定性进行了完整的分析。令人惊讶的结果是，当仅 AND 和 MINUS 可表达时，SPARQL 1.1 模式的可满足性具有不可判定性。此外，还表明，不表达 AND 和 MINUS 的 SPARQL 1.1 的任何片段都是可判定的。这些结果为未来SPARQL查询语言的设计和实现提供了指导。
The pattern satisfiability is a fundamental problem for SPARQL. This paper provides a complete analysis of decidability/undecidability of satisfiability problems for SPARQL 1.1 patterns. A surprising result is the undecidability of satisfiability for SPARQL 1.1 patterns when only AND and MINUS are expressible. Also, it is shown that any fragment of SPARQL 1.1 without expressing both AND and MINUS is decidable. These results provide a guideline for future SPARQL query language design and implementation.