edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Roger Humberto Castillo Espinola
Titel: Indexing RDF data using materialized SPARQL queries – SPARQL query processing and index selection
Gutachter: Ulf Leser; Johann-Christoph Freytag; Adrian Paschke
Erscheinungsdatum: 10.09.2012
Volltext: pdf (urn:nbn:de:kobv:11-100204099)
Fachgebiet(e): Informatik
Schlagwörter (ger): RDF, Indexierung, SPARQL, Graph Datenbanken, Index Selektion, Bearbeitung von SPARQL Anfragen
Schlagwörter (eng): Indexing, RDF, SPARQL, Graph Databases, Index Selection, SPARQL Query Processing
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung - Keine kommerzielle Nutzung (CC BY NC)
Zitationshinweis: Castillo Espinola, Roger Humberto: Indexing RDF data using materialized SPARQL queries – SPARQL query processing and index selection; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 10.09.2012, urn:nbn:de:kobv:11-100204099
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
In dieser Arbeit schlagen wir die Verwendung von materialisierten Anfragen als Indexstruktur für RDF-Daten vor. Wir streben eine Reduktion der Bearbeitungszeit durch die Minimierung der Anzahl der Vergleiche zwischen Anfrage und RDF Datenmenge an. Darüberhinaus betonen wir die Rolle von Kostenmodellen und Indizes für die Auswahl eines efizienten Ausführungsplans in Abhängigkeit vom Workload. Wir geben einen Überblick über das Problem der Auswahl von materialisierten Anfragen in relationalen Datenbanken und diskutieren ihre Anwendung zur Optimierung der Anfrageverarbeitung. Wir stellen RDFMatView als Framework für SPARQL-Anfragen vor. RDFMatView benutzt materializierte Anfragen als Indizes und enthalt Algorithmen, um geeignete Indizes fur eine gegebene Anfrage zu finden und sie in Ausführungspläne zu integrieren. Die Auswahl eines effizienten Ausführungsplan ist das zweite Thema dieser Arbeit. Wir führen drei verschiedene Kostenmodelle für die Verarbeitung von SPARQL Anfragen ein. Ein detaillierter Vergleich der Kostmodelle zeigt, dass ein auf Index-- und Prädikat--Statistiken beruhendes Modell die genauesten Informationen liefert, um einen effizienten Ausführungsplan auszuwählen. Die Evaluation zeigt, dass unsere Methode die Anfragebearbeitungszeit im Vergleich zu unoptimierten SPARQL--Anfragen um mehrere Größenordnungen reduziert. Schließlich schlagen wir eine einfache, aber effektive Strategie für das Problem der Auswahl von materialisierten Anfragen über RDF-Daten vor. Ausgehend von einem bestimmten Workload werden algorithmisch diejenigen Indizes augewählt, die die Bearbeitungszeit des gesamten Workload minimieren sollen. Dann erstellen wir auf der Basis von Anfragemustern eine Menge von Index--Kandidaten und suchen in dieser Menge Zusammenhangskomponenten. Unsere Auswertung zeigt, dass unsere Methode zur Auswahl von Indizes im Vergleich zu anderen, die größten Einsparungen in der Anfragebearbeitungszeit liefert.
Abstract (eng):
In this thesis, we propose to use materialized queries as a special index structure for RDF data. We strive to reduce the query processing time by minimizing the number of comparisons between the query and the RDF dataset. We also emphasize the role of cost models in the selection of execution plans as well as index sets for a given workload. We provide an overview of the materialized view selection problem in relational databases and discuss its application for optimization of query processing. We introduce RDFMatView, a framework for answering SPARQL queries using materialized views as indexes. We provide algorithms to discover those indexes that can be used to process a given query and we develop different strategies to integrate these views in query execution plans. The selection of an efficient execution plan states the topic of our second major contribution. We introduce three different cost models designed for SPARQL query processing with materialized views. A detailed comparison of these models reveals that a model based on index and predicate statistics provides the most accurate cost estimation. We show that selecting an execution plan using this cost model yields a reduction of processing time with several orders of magnitude compared to standard SPARQL query processing. Finally, we propose a simple yet effective strategy for the materialized view selection problem applied to RDF data. Based on a given workload of SPARQL queries we provide algorithms for selecting a set of indexes that minimizes the workload processing time. We create a candidate index by retrieving all connected components from query patterns. Our evaluation shows that using the set of suggested indexes usually achieves larger runtime savings than other index sets regarding the given workload.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
PDF: 26 Zugriffe PDF: 16 Zugriffe PDF: 33 Zugriffe Startseite: 5 Zugriffe PDF: 42 Zugriffe Startseite: 4 Zugriffe PDF: 25 Zugriffe Startseite: 4 Zugriffe PDF: 44 Zugriffe Startseite: 7 Zugriffe PDF: 35 Zugriffe Startseite: 3 Zugriffe PDF: 29 Zugriffe Startseite: 3 Zugriffe PDF: 21 Zugriffe Startseite: 7 Zugriffe PDF: 34 Zugriffe Startseite: 7 Zugriffe PDF: 22 Zugriffe Startseite: 3 Zugriffe PDF: 25 Zugriffe Startseite: 8 Zugriffe PDF: 29 Zugriffe Startseite: 7 Zugriffe PDF: 40 Zugriffe Startseite: 1 Zugriffe PDF: 47 Zugriffe Startseite: 5 Zugriffe PDF: 101 Zugriffe Startseite: 2 Zugriffe PDF: 53 Zugriffe Startseite: 4 Zugriffe PDF: 46 Zugriffe Startseite: 1 Zugriffe PDF: 52 Zugriffe Startseite: 2 Zugriffe PDF: 51 Zugriffe Startseite: 5 Zugriffe PDF: 61 Zugriffe Startseite: 5 Zugriffe PDF: 35 Zugriffe Startseite: 9 Zugriffe PDF: 40 Zugriffe Startseite: 14 Zugriffe PDF: 46 Zugriffe
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Monat Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Startseite       5 4 4 7 3 3 7 7 3 8 7 1 5 2 4 1 2 5 5 9 14
PDF 26 16 33 42 25 44 35 29 21 34 22 25 29 40 47 101 53 46 52 51 61 35 40 46

Gesamtzahl der Zugriffe seit Oct 2012:

  • Startseite – 106 (5.05 pro Monat)
  • PDF – 953 (39.71 pro Monat)
 
 
Generiert am 24.10.2014, 16:40:54