Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-71483
URL: http://www.freidok.uni-freiburg.de/volltexte/7148/


Schmidt, Michael

Foundations of SPARQL query optimization

Grundlagen der SPARQL Anfrageoptimierung

Dokument1.pdf (1.872 KB) (md5sum: a89a33faa886d92c7ea756a130ac01c5)

Kurzfassung in Englisch

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.


Kurzfassung in Deutsch

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 Fragestellungen, die im direkten Zusammenhang mit der effizienten Auswertung von SPARQL Anfragen stehen. Ein erster wichtiger Beitrag der Arbeit ist eine vollständige Komplexitätsanalyse für alle Fragmente der SPARQL Anfragesprache, welche Operatorkonstellationen aufzeigt, die für die Komplexität der Auswertung hauptverantwortlich sind. Ein zentrales Ergebnis in diesem Zusammenhang ist, dass schon der SPARQL Operator OPTIONAL allein, der zur optionalen Extraktion von Komponenten aus RDF Graphen genutzt werden kann, für die PSpace-Vollständigkeit der Anfragesprache verantwortlich ist. Motiviert durch die Komplexitätsergebnisse wird im Folgenden die algebraische Optimierung von SPARQL Anfragen untersucht. Als zentrales Hilfsmittel in dieser Analyse entwickeln wir die Konzepte der möglichen und sicheren Variablen in SPARQL-Anfragen, welche obere und untere Grenzen für die in SPARQL Ergebnis-Mappings gebundenden Variablen festlegen und somit der Besonderheit ungebundener Variablen in SPARQL Mappings gerecht werden. Diese Konzepte ermöglichen es, Äquivalenzen über SPARQL Algebra Ausdrücken präzise und kompakt zu spezifizieren und mit ihrer Hilfe entwickeln wir eine Vielzahl von Umformungsregeln über SPARQL Algebra, einerseits mit dem Ziel etablierte Optimierungstechniken aus der Relationalen Algebra, wie z.B. Filter und Projection Pushing, in den Kontext von SPARQL zu übertragen, andererseits um SPARQL-spezifische Transformations-Schemata zu unterstützen. Unser Ansatz zur algebraischen Optimierung wird schließlich durch einen Ansatz zur semantischen Optimierung von SPARQL Anfragen ergänzt, der auf dem klassischen Chase-Algorithmus zur semantischen Optimierung von Konjunktiven Anfragen aufbaut. Unsere theoretischen Ergebnisse bezüglich algebraischer und semantischer Optimierung sind von direkter praktischer Bedeutung, da sie die Grundlage zur Entwicklung von kostenbasierten Optimierungsansätzen für SPARQL bilden. Abschließend stellen wir einen sprachspezifischen Benchmark für die SPARQL Anfragesprache, genannt SP2Bench, vor, der es ermöglicht die Performanz sowie Stärken und Schwächen von SPARQL Interpretern in einem umfassenden und anwendungsunabhängigen Szenario zu ermitteln.


SWD-Schlagwörter: Datenbank , Semantic Web , Optimierung , Komplexität , Benchmark , RDF <Informatik>
Freie Schlagwörter (deutsch): SPARQL , Integritätsbedingungen , SPARQL Algebra
Freie Schlagwörter (englisch): SPARQL , Constraint , SPARQL Algebra
CCS Klassifikation H.2.3 Lang
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Lausen, Georg (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 22.12.2009
Erstellungsjahr: 2009
Publikationsdatum: 14.01.2010
Indexliste