Implementation and optimisation of queries in XSPARQL

Abstract

XSPARQL ist eine Sprache zur Transformation von Daten zwischen XML und RDF. XML ist ein weit verbreitetes Format zum Austausch von Daten. RDF ist ein Datenformat basierend auf gerichteten Graphen, das primär zur Repräsentation von Daten im Semantic Web verwendet wird.<br />XSPARQL kombiniert die Stärken der beiden zugehörigen Anfragesprachen XQuery für XML und SPARQL für RDF. In dieser Diplomarbeit präsentieren wir zwei Verbesserungen der XSPARQL-Sprache, die Constructed Dataset und Dataset Scoping genannt werden, die XDEP Dependent Join Optimierung sowie eine neue Implementierung von XSPARQL. Constructed Dataset erlaubt das Erstellen und Abfragen temporärer RDF-Graphen. Durch Dataset Scoping können unerwartete Ergebnisse, die beim Auswerten einer komplexen XSPARQL-Anfrage mit verschachtelten SPARQL-Anfrageteilen auftreten können, vermieden werden. Die XSPARQL-Implementierung schreibt eine XSPARQL-Anfrage in eine XQuery-Anfrage um, die, zur Verarbeitung von RDF Daten, eingeschobene Aufrufe einer SPARQL-Engine enthält. Die resultierende Anfrage wird dann von einem XQuery-Prozessor und einer SPARQL-Engine gemeinsam ausgewertet. Die Dependent Join Optimierung XDEP zielt auf eine Reduktion der Auswertungsdauer für Anfragen ab, die eingebettete SPARQL-Anfrageteile wiederholt auswerten müssen. XDEP minimiert die Anzahl von Interaktionen zwischen dem XQuery-Prozessor und der SPARQL-Engine, indem ähnliche SPARQL-Anfragen zusammengefasst und das Auswählen der relevanten Daten dem XQuery-Prozessor überlassen wird.<br />Anhand einer adaptierten Version des XQuery-Benchmarks XMark haben wir eine experimentelle Evaluation unseres Ansatzes durchgeführt. Wir werden zeigen, dass die XDEP-Optimierung die Auswertungsdauer von allen kompatiblen Anfragen reduzieren konnte. Durch die Optimierung konnten wir bestimmte Anfragen um zwei Größenordnungen schneller auswerten als in der unoptimierten Version.<br />

XSPARQL is a language for transforming data between XML and RDF.<br />XML is a widely used format for data exchange. RDF is a data format based on directed graphs, primarily used to represent Semantic Web data.<br />XSPARQL is built by combining the strengths of the two corresponding query languages XQuery for XML, and SPARQL for RDF. In this thesis we present two XSPARQL enhancements called Constructed Dataset and Dataset Scoping, the XDEP dependent join optimisation, and a new XSPARQL implementation. Constructed Dataset allows to create and query intermediary RDF graphs. The Dataset Scoping enhancement provides an optional fix for unintended results which may occur when evaluating complex XSPARQL queries containing nested SPARQL query parts. The XSPARQL implementation works by first rewriting an XSPARQL query to XQuery expressions containing interleaved calls to a SPARQL engine for processing RDF data. The resulting query is then evaluated by standard XQuery and SPARQL engines. The dependent join optimisation XDEP is designed to reduce query evaluation time for queries demanding repeated evaluation of embedded SPARQL query parts. XDEP minimises the number of interactions between the XQuery and SPARQL engines by bundling similar queries and let the XQuery engine select relevant data on its own. We did an experimental evaluation of our approach using an adapted version of the XQuery benchmark suite XMark. We will show that the XDEP optimisation reduces the evaluation time of all compatible benchmark queries. Using this optimisation we could evaluate certain XSPARQL queries by two orders of magnitude faster than with unoptimised XSPARQL.