AAAI

Association for the Advancement of Artificial Intelligence

Home / Proceedings / Proceedings of the AAAI Conference on Artificial Intelligence, 32

On the Satisfiability Problem of Patterns in SPARQL 1.1

Download PDF

Published Date: 2018-02-08

Registration: ISSN 2374-3468 (Online) ISSN 2159-5399 (Print)

Copyright: Published by AAAI Press, Palo Alto, California USA Copyright © 2018, Association for the Advancement of Artificial Intelligence All Rights Reserved.

Authors

Xiaowang Zhang

Tianjin University


Jan Van den Bussche

Hasselt University


Kewen Wang

Griffith University


Zhe Wang

Griffith University


DOI:

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.