edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Silke Trissl
Titel: Cost-based optimization of graph queries in relational database management systems
Gutachter: Ulf Leser; Johann-Christoph Freytag; Thorsten Grust
Erscheinungsdatum: 14.06.2012
Volltext: pdf (urn:nbn:de:kobv:11-100203284)
Fachgebiet(e): Informatik
Schlagwörter (ger): Graphanfragen, Anfrageoptimierung, Erreichbarkeitsanfragen, Pfadanfragen, Subgraph-homeomorphismus
Schlagwörter (eng): Graph Query, Query Optimization, Reachability Query, Path Query, Subgraph homeomorphism
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung - Keine kommerzielle Nutzung (CC BY NC)
Zitationshinweis: Trissl, Silke: Cost-based optimization of graph queries in relational database management systems; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 14.06.2012, urn:nbn:de:kobv:11-100203284
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.

Abstract (ger):
Graphen sind in vielen Bereichen des Lebens zu finden, wobei wir speziell an Graphen in der Biologie interessiert sind. Knoten in solchen Graphen sind chemische Komponenten, Enzyme, Reaktionen oder Interaktionen, die durch Kanten miteinander verbunden sind. Eine effiziente Ausführung von Graphanfragen ist eine Herausforderung. In dieser Arbeit präsentieren wir GRIcano, ein System, das die effiziente Ausführung von Graphanfragen erlaubt. Wir nehmen an, dass Graphen in relationalen Datenbankmanagementsystemen (RDBMS) gespeichert sind. Als Graphanfragesprache schlagen wir eine erweiterte Version der Pathway Query Language (PQL) vor. Der Hauptbestandteil von GRIcano ist ein kostenbasierter Anfrageoptimierer. Diese Arbeit enthält Beiträge zu allen drei benötigten Komponenten des Optimierers, der relationalen Algebra, Implementierungen und Kostenmodellen. Die Operatoren der relationalen Algebra sind nicht ausreichend, um Graphanfragen auszudrücken. Daher stellen wir zuerst neue Operatoren vor. Wir schlagen den Erreichbarkeits-, Distanz-, Pfadlängen- und Pfadoperator vor. Zusätzlich geben wir Regeln für die Umformung von Ausdrücken an. Des Weiteren präsentieren wir Implementierungen für jeden vorgeschlagenen Operator. Der Hauptbeitrag ist GRIPP, eine Indexstruktur, die die effiziente Ausführung von Erreichbarkeitsanfragen auf sehr großen Graphen erlaubt. Wir zeigen, wie GRIPP und die rekursive Anfragestrategie genutzt werden können, um Implementierungen für alle Operatoren bereitzustellen. Die dritte Komponente von GRIcano ist das Kostenmodell, das Kardinalitätsabschätzungen der Operatoren und Kostenfunktionen für die Implementierungen benötigt. Basierend auf umfangreichen Experimenten schlagen wir in dieser Arbeit Funktionen dafür vor. Der neue Ansatz unserer Kostenmodelle ist, dass die Funktionen nur Kennzahlen der Graphen verwenden. Abschließend zeigen wir die Wirkungsweise von GRIcano durch Beispielanfragen auf echten biologischen Graphen.
Abstract (eng):
Graphs occur in many areas of life. We are interested in graphs in biology, where nodes are chemical compounds, enzymes, reactions, or interactions that are connected by edges. Efficiently querying these graphs is a challenging task. In this thesis we present GRIcano, a system that efficiently executes graph queries. For GRIcano we assume that graphs are stored and queried using relational database management systems (RDBMS). We propose an extended version of the Pathway Query Language PQL to express graph queries. The core of GRIcano is a cost-based query optimizer. This thesis makes contributions to all three required components of the optimizer, the relational algebra, implementations, and cost model. Relational algebra operators alone are not sufficient to express graph queries. Thus, we first present new operators to rewrite PQL queries to algebra expressions. We propose the reachability, distance, path length, and path operator. In addition, we provide rewrite rules for the newly proposed operators in combination with standard relational algebra operators. Secondly, we present implementations for each proposed operator. The main contribution is GRIPP, an index structure that allows us to answer reachability queries on very large graphs. GRIPP has advantages over other existing index structures, which we review in this work. In addition, we show how to employ GRIPP and the recursive query strategy as implementation for all four proposed operators. The third component of GRIcano is the cost model, which requires cardinality estimates for operators and cost functions for implementations. Based on extensive experimental evaluation of our proposed algorithms we present functions to estimate the cardinality of operators and the cost of executing a query. The novelty of our approach is that these functions only use key figures of the graph. We finally present the effectiveness of GRIcano using exemplary graph queries on real biological networks.
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.
Startseite: 13 Zugriffe PDF: 22 Zugriffe PDF: 20 Zugriffe PDF: 27 Zugriffe PDF: 14 Zugriffe PDF: 37 Zugriffe Startseite: 5 Zugriffe PDF: 37 Zugriffe Startseite: 5 Zugriffe PDF: 44 Zugriffe Startseite: 5 Zugriffe PDF: 24 Zugriffe PDF: 33 Zugriffe Startseite: 6 Zugriffe PDF: 38 Zugriffe Startseite: 1 Zugriffe PDF: 35 Zugriffe Startseite: 2 Zugriffe PDF: 26 Zugriffe Startseite: 5 Zugriffe PDF: 34 Zugriffe Startseite: 3 Zugriffe PDF: 27 Zugriffe Startseite: 9 Zugriffe PDF: 44 Zugriffe Startseite: 3 Zugriffe PDF: 35 Zugriffe Startseite: 5 Zugriffe PDF: 61 Zugriffe PDF: 56 Zugriffe Startseite: 3 Zugriffe PDF: 93 Zugriffe Startseite: 2 Zugriffe PDF: 74 Zugriffe Startseite: 3 Zugriffe PDF: 87 Zugriffe Startseite: 2 Zugriffe PDF: 118 Zugriffe Startseite: 3 Zugriffe PDF: 61 Zugriffe Startseite: 4 Zugriffe PDF: 55 Zugriffe Startseite: 4 Zugriffe PDF: 32 Zugriffe Startseite: 4 Zugriffe PDF: 69 Zugriffe Startseite: 2 Zugriffe PDF: 58 Zugriffe
Aug
12
Sep
12
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
Oct
14
Monat Aug
12
Sep
12
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
Oct
14
Startseite 13         5 5 5   6 1 2 5 3 9 3 5   3 2 3 2 3 4 4 4 2
PDF 22 20 27 14 37 37 44 24 33 38 35 26 34 27 44 35 61 56 93 74 87 118 61 55 32 69 58

Gesamtzahl der Zugriffe seit Aug 2012:

  • Startseite – 89 (3.3 pro Monat)
  • PDF – 1261 (46.7 pro Monat)
 
 
Generiert am 26.11.2014, 13:30:15