Semantics and Complexity of SPARQL

Perez J.; Arenas, M; Gutierrez C.

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. © 2009 ACM.

Más información

Título según WOS: Semantics and Complexity of SPARQL
Título según SCOPUS: Semantics and complexity of SPARQL
Título de la Revista: ACM TRANSACTIONS ON DATABASE SYSTEMS
Volumen: 34
Número: 3
Editorial: ASSOC COMPUTING MACHINERY
Fecha de publicación: 2009
Idioma: English
URL: http://portal.acm.org/citation.cfm?doid=1567274.1567278
DOI:

10.1145/1567274.1567278

Notas: ISI, SCOPUS