Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
We study fundamental aspects related to the efficient evaluation of SPARQL, a prominent query language for the RDF data format that has been developed for the encoding of machine-readable information in the Semantic Web. Our key contributions include (i) a complete complexity analysis for all operator fragments of the SPARQL query language, which identifies operator constellations that make query evaluation hard and - as a central result - shows that the SPARQL OPTIONAL operator alone, which allows for the optional selection of components in RDF graphs, is responsible for the PSpace-completeness of the SPARQL evaluation problem; (ii) the novel concepts of possible and certain variables in SPARQL queries, which constitute upper and lower bounds for variables that might be bound in SPARQL result mappings, account for the specifics of the SPARQL query language, and allow to state equivalences over SPARQL expressions in a precise and compact way; (iii) a comprehensive analysis of equivalences over SPARQL algebra, including both the investigation of rewriting rules like filter and projection pushing that are well-known from relational algebra optimization as well as SPARQL-specific rewriting schemes; (iv) an approach to the semantic optimization of SPARQL queries, built on top of the classical chase algorithm; (v) a language-specific benchmark suite for SPARQL, called SP2Bench, which allows to assess the performance of SPARQL implementations in a comprehensive, application-independent setting. Although theoretical in nature, our results on algebraic and semantic query optimization for SPARQL are of immediate practical interest and facilitate the development of cost-based SPARQL optimization schemes. ; Die SPARQL Anfragesprache wurde vom W3C als Standardsprache zur Extraktion von Daten aus RDF Datenbanken vorgeschlagen, einem Datenformat das speziell zur maschinenlesbaren Repräsentation von Informationen im Semantischen Web entwickelt wurde. Die vorliegende Arbeit beschäftigt sich mit unterschiedlichen ...