Semantics and complexity of SPARQL

TLDR

SPARQL is the standard language for querying RDF data. This article systematically studies the database aspects of SPARQL, focusing on its graph pattern matching facility. The authors provide a compositional semantics for core SPARQL, identify a syntactically restricted class of patterns that enables more efficient evaluation, and offer rewriting rules that can significantly reduce query evaluation cost. They demonstrate that general SPARQL pattern evaluation is PSPACE‑complete, that evaluation for the well‑designed pattern class is coNP‑complete, and that the proposed rewriting rules can substantially lower evaluation cost.

Abstract

SPARQL is the standard language for querying RDF data. In this article, we address systematically the formal study of the database aspects of SPARQL, concentrating in its graph pattern matching facility. We provide a compositional semantics for the core part of SPARQL, and study the complexity of the evaluation of several fragments of the language. Among other complexity results, we show that the evaluation of general SPARQL patterns is PSPACE-complete. We identify a large class of SPARQL patterns, defined by imposing a simple and natural syntactic restriction, where the query evaluation problem can be solved more efficiently. This restriction gives rise to the class of well-designed patterns. We show that the evaluation problem is coNP-complete for well-designed patterns. Moreover, we provide several rewriting rules for well-designed patterns whose application may have a considerable impact in the cost of evaluating SPARQL queries.