Semantics and complexity of SPARQL

By Jorge Pérez, Marcelo Arenas, Claudio Gutiérrez. TODS, 2006

1,662 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/971bca8117088cd31b8353896559d33fb70c2220

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Triple Pattern Fragments: A low-cost knowledge graph interface for the Web (2016, methodology): “A characteristic of SPARQL endpoints is that, in addition to the unpredictability of the total number of users and requests, the processing cost per request can vary significantly because of the relatively high expressive power of SPARQL (with different fragments of SPARQL having a different computa”
TriAL (2018, methodology): “3 Now, since nSPARQL is the extension of a positive fragment of SPARQL 1.0 [45] TriAL: A Navigational Algebra for RDF Triplestores 5:9 with NREs, and SPARQL 1.0 was shown to be equivalent to first order logic [47], we can easily see that Q cannot be expressed in SPARQL 1.0, and therefore in nSPARQL…”
C-SPARQL: a Continuous Query Language for RDF Data Streams (2010, background): “Pervasive Computing is normally applied either to homogeneous large scale areas (e.g., forests, reefs, and glaciers) or, on the other hand, in small-scale ones (e.g., smart rooms and houses).”
Foundations of SPARQL query optimization (2008, methodology): “Among the equivalences in Figure 2, a majority of the rules from groups I and II, as well as (FDecompI+II), (MJ), and (FUPush) are borrowed from [ 24 ].”
Foundations of Modern Query Languages for Graph Databases (2016, methodology): “If difference and optional are also allowed, then SPARQL has the same operators as relational algebra, so the combined complexity is PSPACE-complete (Vardi 1982).”
Querying Distributed RDF Data Sources with SPARQL (2008, methodology): “For a more detailed introduction to RDF and SPARQL we refer the interested reader to [14, 1, 15].”
RuleHub (2020, background): “(ii) discussing the effect of the κ parameter on the results.”
Binary RDF representation for publication and exchange (HDT) (2013, neutral): “We follow [19,17] for graphnotation, with no distinction between URIs, Blank nodes and Literals.”
SP^2Bench: A SPARQL Performance Benchmark (2008, background): “These approaches comprise a wide range of optimization techniques, including normal forms [4], graph pattern reordering based on selectivity estimations [5] (similar to relational join reordering), syntactic rewriting [6], specialized indices [7], [8] and storage schemes [9], [10], [11], [12], [13]…”
A Native and Adaptive Approach for Unified Processing of Linked Streams and Linked Data (2011, methodology): “Similar to the semantics of SPARQL [29], the operators work on the mappings from discrete result sets.”
SPARQL-DL: SPARQL Query for OWL-DL (2007, background): “The semantics for these operations are defined as algebraic operations over the solutions of BGPs [ 6 ].”
Build2SPARQL: A Large-Scale Text-to-SPARQL Benchmark Dataset for Building Knowledge Graph Querying (2026, unknown): “Each corresponds to a core operator of relational algebra restricted to graph-pattern matching (P´erez et al. 2009): selection (linear chains), conjunctive join (branching), disjunctive join (UNION), aggregation (COUNT/GROUP BY), outer join (OPTIONAL), and attribute filtering.”