On the Satisfiability Problem of Patterns in SPARQL 1.1

Xiaowang Zhang, Jan Van den Bussche, Kewen Wang, Zhe Wang

AAAI 2018 pp. 2054-2062

doi:10.1609/AAAI.V32I1.11549 /aaai/2018/zhang2018aaai-satisfiability/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Zhang et al. "On the Satisfiability Problem of Patterns in SPARQL 1.1." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11549

Markdown

[Zhang et al. "On the Satisfiability Problem of Patterns in SPARQL 1.1." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/zhang2018aaai-satisfiability/) doi:10.1609/AAAI.V32I1.11549

BibTeX

@inproceedings{zhang2018aaai-satisfiability,
  title     = {{On the Satisfiability Problem of Patterns in SPARQL 1.1}},
  author    = {Zhang, Xiaowang and Van den Bussche, Jan and Wang, Kewen and Wang, Zhe},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {2054-2062},
  doi       = {10.1609/AAAI.V32I1.11549},
  url       = {https://mlanthology.org/aaai/2018/zhang2018aaai-satisfiability/}
}