Semantics and Complexity of SPARQL

Simple item page
dc.contributor.authorPerez, Jorge
dc.contributor.authorArenas, Marcelo
dc.contributor.authorGutierrez, Claudio
dc.date.accessioned2025-01-21T00:08:20Z
dc.date.available2025-01-21T00:08:20Z
dc.date.issued2009
dc.description.abstractSPARQL 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.
dc.fuente.origenWOS
dc.identifier.doi10.1145/1567274.1567278
dc.identifier.eissn1557-4644
dc.identifier.issn0362-5915
dc.identifier.urihttps://doi.org/10.1145/1567274.1567278
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/95665
dc.identifier.wosidWOS:000270413900004
dc.issue.numero3
dc.language.isoen
dc.revistaAcm transactions on database systems
dc.rightsacceso restringido
dc.subjectAlgorithms
dc.subjectLanguages
dc.subjectPerformance
dc.subjectTheory
dc.subjectComplexity
dc.subjectquery language
dc.subjectRDF
dc.subjectsemantic Web
dc.subjectSPARQL
dc.titleSemantics and Complexity of SPARQL
dc.typeartículo
dc.volumen34
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas