On the Satisfiability Problem of Patterns in SPARQL 1.1

Authors

  • Xiaowang Zhang Tianjin University
  • Jan Van den Bussche Hasselt University
  • Kewen Wang Griffith University
  • Zhe Wang Griffith University

DOI:

https://doi.org/10.1609/aaai.v32i1.11549

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.

AAAI 2018 Proceedings Cover

Downloads

Published

2018-04-25

How to Cite

Zhang, X., Van den Bussche, J., Wang, K., & Wang, Z. (2018). On the Satisfiability Problem of Patterns in SPARQL 1.1. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11549

Issue

Vol. 32 No. 1 (2018): Thirty-Second AAAI Conference on Artificial Intelligence

Section

AAAI Technical Track: Knowledge Representation and Reasoning