articleACM Transactions on Database SystemsAug 1, 2009BRONZE OA

Semantics and complexity of SPARQL

JEJorge Eduardo Pérez PérezMAMarcelo ArenasCGClaudio Gutiérrez

Pontificia Universidad Católica de Chile · University of Chile

Indexed incrossref

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…

Citation impact

1,134
total citations
FWCI
86.93
Percentile
100%
References
34
Citations per year

Authors

3

Topics & keywords

Topics
Keywords
  • SPARQL
  • Computer science
  • Named graph
  • RDF
  • Semantics (computer science)
  • Rewriting
  • Class (philosophy)
  • Information retrieval
No related works found for this paper.

Funding