Show simple item record

2012-06-14Dissertation DOI: 10.18452/16544
Cost-based optimization of graph queries in relational database management systems
dc.contributor.authorTrissl, Silke
dc.date.accessioned2017-06-18T11:34:28Z
dc.date.available2017-06-18T11:34:28Z
dc.date.created2012-07-13
dc.date.issued2012-06-14
dc.identifier.urihttp://edoc.hu-berlin.de/18452/17196
dc.description.abstractGraphen 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.ger
dc.description.abstractGraphs 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.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
dc.rightsNamensnennung - Keine kommerzielle Nutzung
dc.rights.urihttp://creativecommons.org/licenses/by-nc/3.0/de/
dc.subjectGraphanfragenger
dc.subjectAnfrageoptimierungger
dc.subjectErreichbarkeitsanfragenger
dc.subjectPfadanfragenger
dc.subjectSubgraph-homeomorphismusger
dc.subjectGraph Queryeng
dc.subjectQuery Optimizationeng
dc.subjectReachability Queryeng
dc.subjectPath Queryeng
dc.subjectSubgraph homeomorphismeng
dc.subject.ddc004 Informatik
dc.titleCost-based optimization of graph queries in relational database management systems
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-100203284
dc.identifier.doihttp://dx.doi.org/10.18452/16544
dc.identifier.alephidBV040309814
dc.date.accepted2012-02-16
dc.contributor.refereeLeser, Ulf
dc.contributor.refereeFreytag, Johann-Christoph
dc.contributor.refereeGrust, Thorsten
dc.subject.dnb28 Informatik, Datenverarbeitung
dc.subject.rvkST 270
local.edoc.pages205
local.edoc.type-nameDissertation
local.edoc.institutionMathematisch-Naturwissenschaftliche Fakultät II

Show simple item record