Im Rahmen dieser Diplomarbeit wird ein Optimierer für die TGraphen-Anfragesprache GReQL2 entworfen und implementiert.
GReQL2 besteht im wesentlichen aus drei Komponenten: dem Parser, dem Auswerter und dem Optimierer.
Der Parser wurde bereits in [Mar06] von Katrin Marchewka implementiert, und der Auswerter ist Resultat von Daniel Bildhauers Diplomarbeit ([Bil06]).
Der in der vorliegenden Arbeit entwickelte Optimierer besitzt eine Komponente zum Loggen von Auswertungsgrößen, ein Kostenmodell, welches auf Basis der geloggten Erfahrungswerte die Auswertungskosten einer Anfrage abschätzen kann, einen Mechanismus zur Wiederverwendung bereits optimierter Syntaxgraphen und eine Reihe von Transformationen, die einen gegebenen GReQL2-Syntaxgraphen derart umformen, dass er effizienter ausgewertet werden kann.
Dabei sind einige dieser Transformationen ganz speziell auf die Sprache GReQL2 abgestimmt während andere Adaptionen von bekannten Optimierungsstrategien (z.B. "Selektion so früh wie möglich" bei der algebraischen Optimierung in relationalen Datenbanksystemen) darstellen.
Der in der vorliegenden Diplomarbeit entwickelte Optimierer hat sich mittlerweile im Produktiveinsatz innerhalb der TGraphen-Bibliothek JGraLab des Instituts für Softwaretechnik an der Universität Koblenz-Landau bewährt.
GUPRO and GREQL2 Optimizer: Frequently Asked Questions
Was ist GUPRO und welche Rolle spielt GREQL2?
GUPRO ist eine integrierte Umgebung zum Programmverständnis, insbesondere im Reengineering. GREQL2 ist eine neue, verbesserte Anfragesprache für GUPRO, die auf TGraphen (typisierte, gerichtete, angeordnete Graphen) arbeitet und die Extraktion von Informationen aus Programm-Artefakten ermöglicht. Dieses Dokument beschreibt einen neuen GREQL2-Optimierer, der die Effizienz der Anfrageauswertung verbessern soll.
Welche Bestandteile umfasst das GUPRO-System?
Das GUPRO-System umfasst einen Parser, der Anfragen in Syntaxgraphen umwandelt, einen Optimierer (das zentrale Thema dieses Dokuments), einen Auswerter, der die optimierten Anfragen an den Datengraphen anwendet, und eine Klassenbibliothek (JGRALAB) zur Verwaltung von TGraphen. Die Interaktion erfolgt über eine graphische Benutzeroberfläche.
Wie funktioniert die Anfrageverarbeitung in GUPRO?
Der Prozess verläuft in folgenden Schritten: 1. Der Benutzer stellt eine Anfrage in GREQL2. 2. Der Parser wandelt die Anfrage in einen Syntaxgraphen um. 3. Der Optimierer optimiert den Syntaxgraphen. 4. Der Auswerter wertet den optimierten Syntaxgraphen auf dem Datengraph aus und liefert das Ergebnis.
Welche Arten der Anfrageoptimierung gibt es in GUPRO?
Es wird zwischen Online- und Offline-Optimierung unterschieden. Online-Optimierung nutzt Informationen aus dem Datengraphen, ist aber zeitlich begrenzt. Offline-Optimierung ist zeitlich nicht begrenzt, hat aber weniger Informationen zur Verfügung.
Was sind die Hauptmerkmale von GREQL2?
GREQL2 erweitert die Funktionalität von GREQL, unterstützt kontextfreie Pfadausdrücke und liefert Ergebnisse im generischen Containerformat JValue. Der Parser generiert einen abstrakten Syntaxgraphen, der dem GREQL2-Schema genügt.
Wie funktioniert der GREQL2-Auswerter?
Der Auswerter verwendet eine hierarchische Struktur von Auswerterklassen (VertexEvaluator), um den Syntaxgraphen rekursiv zu verarbeiten. Er verwendet Lazy Evaluation, soweit möglich, um die Effizienz zu steigern. Funktionen der GREQL2-Funktionsbibliothek verwenden jedoch Eager Evaluation.
Wie funktioniert die Anfrageoptimierung in relationalen Datenbanksystemen?
In relationalen Datenbanksystemen wird die Anfrageoptimierung in vier Phasen unterteilt: 1. Vorverarbeitung, 2. Algebraische Optimierung (High-Level), 3. Low-Level-Optimierung (Erstellung des Ausführungsplans), 4. Anfrage-Ausführung. Die algebraische Optimierung beinhaltet unter anderem das Verschieben von Selektionen und Projektionen im Anfragebaum.
Wie unterscheidet sich die Optimierung in Datenbanken von der in GREQL2?
Im Gegensatz zu relationalen Datenbanksystemen, wo ein Großteil der Kosten auf Hintergrundspeicherzugriffe entfällt, liegt der Fokus bei GREQL2 auf den reinen Berechnungskosten, da der Datengraph komplett im Hauptspeicher gehalten wird.
Wie arbeitet der GREQL1-Optimierer?
Der GREQL1-Optimierer (als Vergleichsbasis) vermeidet Mehrfachberechnungen gleicher Teilausdrücke, verwendet eine Bewertungsfunktion zur Abschätzung der Optimierungseffekte und wendet verschiedene Transformationen auf den Syntaxgraphen an (z. B. Selektion so früh wie möglich, Umwandlung von Pfadausdrücken).
Welche Themen werden in den einzelnen Kapiteln behandelt?
Das Dokument gliedert sich in Einleitung (Einführung in GUPRO und GREQL2), Grundlagen (GREQL2-Sprache, -Schema, -Auswerter und Anfrageoptimierung in relationalen Datenbanken), Arbeitsweise des GREQL1-Optimierers (als Vergleich), GREQL2-Optimierer (Architektur, Kostenmodell, Transformationen, Optimierungsstrategie), Bewertung und Ausblick (Testanfragen und Bewertung der Optimierungsleistung).
Inhaltsverzeichnis
1. Einleitung
1.1. Programmverstehen mit GUPRO
1.2. Die nächste Generation von GUPRO
2. Grundlagen
2.1. Die Anfragesprache GREQL2
2.1.1. Das Beispielschema RoadMap
2.1.2. Die Beispielinstanz des RoadMap-Schemas
2.1.3. Zwei exemplarische GREQL2-Anfragen
2.2. Das GREQL2-Schema
2.3. Der GREQL2-Auswerter
2.4. Die Anfrageoptimierung in relational Datenbankensystemen
2.4.1. Die algebraische Optimierung
2.4.2. Die Low-Level-Optimierung
2.4.3. Die Optimierung in Datenbanken und GREQL2
3. Die Arbeitsweise des GREQL1-Optimierers
3.1. Die Erkennung gleicher Teilausdrücke
3.2. Die Bewertungsfunktion
3.3. Die Transformationen
3.3.1. Selektion so früh wie möglich
3.3.2. Pfadprädikate in Pfadausdrücke wandeln
3.3.3. Boolsche Terme in IF-Form wandeln
3.3.4. Boolsche Terme in Konjunktionsketten wandeln
3.3.5. Variablen-Permutation 12 Inhaltsverzeichnis
3.3.6. Variablen mittels Heuristiken anordnen
3.3.7. Verlagere den Body quantifizierter Prädikate in Bedingung
3.3.8. Pfadprädikate zusammenfassen
3.4. Der Suchalgorithmus
4. Der GREQL2-Optimierer
4.1. Die Architektur des Optimierers
4.2. Wiederverwendung von optimierten Syntaxgraphen
4.3. Das Logging von Auswertungsgrößen
4.3.1. Das Interface EvaluationLogger
4.3.2. Granularitätsstufen beim Logging
4.3.3. Logging bei paralleler Anfrageauswertung
4.3.4. Die Wahl der Loggingdatei
4.3.5. Das Logging der Auswertungsgrößen der einzelnen Syntaxgraph- knoten
4.3.6. Zusammenfassung
4.4. Ein Kostenmodell basierend auf Erfahrungswerten
4.4.1. Das Interface CostModel
4.4.2. Die konkreten Kostenmodelle
4.5. Die Erkennung und Verschmelzung gemeinsamer Teilgraphen
4.6. Das Zusammenfassen von SimpleDeclarations
4.7. Die Transformation “Selektion so früh wie möglich”
4.7.1. Die Struktur der hier betrachteten Anfragen
4.7.2. Die Auswertung der betrachteten Anfragen
4.7.3. Das Finden von vorziehbaren Prädikaten
4.7.4. Die Transformationen für die frühe Selektion
4.7.5. Das Splitten einer SimpleDeclaration
4.7.6. Das Vorziehen von Prädikaten in eine SimpleDeclaration mit einer Variable
4.7.7. Das Vorziehen von Prädikaten in eine SimpleDeclaration mit mehreren Variablen
4.7.8. Einige Beispiele Inhaltsverzeichnis
4.8. Die Transformation “Pfadexistenz-Prädikate in Funktionsanwendungen wandeln”
4.8.1. Die Auswertung von Pfadexistenz-Prädikaten
4.8.2. Die Transformation
4.8.3. Einige Beispiele
4.9. Die Transformation “Variablendeklarationen anordnen”
4.9.1. Die Transformation
4.9.2. Ein Beispiel
4.10. Die Transformation “Minimierung von logischen Formeln”
4.10.1. Pfad-Dissolution
4.10.2. Ein Beispiel
4.10.3. Der DissolutionOptimizer
4.11. Die Transformation “Zusammengesetzte Prädikate in Konditionalausdrücke wandeln”
4.11.1. Das Verfahren
4.11.2. Ein Beispiel
4.11.3. Der ConditionalExpressionOptimizer
4.12. Die Optimierungsstrategie
5. Eine Bewertung und Ausblick
5.1. Einige Testanfragen zur Bewertung des Optimierers
5.1.1. Drei Phasen der Anfragebearbeitung
5.1.2. Der Testdatengraph
5.1.3. Die erste Testanfrage
5.1.4. Die zweite Testanfrage
5.1.5. Die dritte Testanfrage
5.2. Eine Bewertung der Optimierungsleistung und Ausblick
A. Glossar
B. Abbildungen
Abbildungsverzeichnis
Tabellenverzeichnis
Literaturverzeichnis
1. Einleitung
Dieses Kapitel soll kurz in die Begriffswelt rund um GUPRO und TGra- phen einführen, um die Einordnung des zu entwerfenden GREQL2- Optimierers zu erleichtern. Dazu wird das Themengebiet rund um GU- PRO beschrieben und eine kurze historische Einführung gegeben
1.1. Programmverstehen mit GUPRO
GUPRO1 ist eine vom Institut für Softwaretechnik der Universität Koblenz-Landau ent- wickelte integrierte Umgebung, die der Unterstützung des Verstehens von Programmen dient. Gerade im Reengineering ist es eine Hauptaufgabe die Struktur und etwaige Be- ziehungen zwischen Teilen von Altsystemen aufzudecken. Solche Altsysteme sind in der Regel über Jahre gewachsen und wurden ständig mit zumeist undokumentierten Bugfixes, Anpassungen an neue Gegebenheiten und Erweiterungen versorgt, so dass die ursprüng- liche Architektur stark verwässert ist
Um im Zuge von Reengineeringmaßnahmen Refactorings durchführen zu können, muss zuerst anhand der vorliegenden Artefakte (in der Regel dem Quellcode) das Programm verstanden werden. Dazu werden Parser benutzt, die aus den Artefakten Informationen extrahieren und in einem Repository speichern
Zur Speicherung der extrahierten Daten benutzt GUPRO TGraphen, d.h. gerichtete, an- geordnete Graphen, deren Kanten und Knoten typisiert und attributiert sind. Ein solcher Datengraph ist eine Instanz eines T-Graphen-Schemas
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1.1.: Ein einfaches Beispielschema
Das grobgranulare Schema aus Abbildung 1.1 definiert beispielsweise den Knotentyp Function und den Kantentyp FunctionCall. Eine Funktion ist attributiert mit ihrem Namen und der Position ihrer Definition (Dateiname und Zeile), ein Funktionsaufruf ist attributiert mit seiner Position
Abbildung in dieser Leseprobe nicht enthalten
1.1. Programmverstehen mit GUPRO
Der in Abbildung 1.2 angegebene Datengraph genügt diesem Schema. Er beschreibt, dass eine Funktion a(), die in der Datei file.c ab Zeile 106 definiert wird, in der Zeile 113 eine andere Funktion b() aufruft, welche in der Datei misc.c ab Zeile 444 definiert wird
Um Anfragen an solche Datengraphen stellen zu können, wurde die Sprache GREQL ent- wickelt. In ihr formulierte Anfragen werden von einem Parser in einen Syntaxgraphen transformiert, welcher dann von einem Optimierer optimiert werden kann, um letztlich durch den Auswerter ausgewertet zu werden. Das Anfrageergebnis kann dann dem Be- nutzer präsentiert werden. Abbildung 1.3 verdeutlicht diesen Datenfluss
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1.3.: Der Datenfluss bei GUPRO
Bei der Anfrageoptimierung unterscheidet man zwischen einer online- und einer offline- Verwendung. Bei der online-Verwendung hat der Optimierer neben dem Syntaxgraphen der Anfrage auch den Datengraphen und Schemainformationen zur Verfügung. Mit die- sen zusätzlichen Informationen kann eine gezieltere Optimierung vorgenommen werden. Jedoch darf die Optimierung nicht beliebig lange dauern, da in der Regel ein Benutzer die Anfrage über eine graphische Oberfläche gestellt hat und auf das Ergebnis wartet
Bei der offline-Verwendung werden Anfragen ohne Kenntnis des Datengraphen mit dem Ziel optimiert, die optimierten Anfragen zu speichern und erst später an einem Datengra- phen auszuwerten. Hier darf die Optimierung länger dauern, allerdings sind die Möglich- keiten aufgrund der fehlenden Informationen aus dem Datengraphen beschränkt
1.2. Die nächste Generation von GUPRO
Da die alte in C++ geschriebene GREQL-Implementation samt der meisten zugehöri- gen Tools und Komponenten im GUPRO-Umfeld nicht mehr heutigen softwaretechni- schen Ansprüchen genügen und nur schwer wartbar und erweiterbar sind, wurden in den letzten anderthalb Jahren umfangreiche Redesigns und Reimplementationen bestehender Altkomponenten in Java gestartet
So entwickelte Steffen Kahle im Rahmen seiner Diplomarbeit eine moderne Version der Klassenbibliothek für TGraphen namens JGRALAB. Diese erlaubt es dem Benutzer TGraphen zu erzeugen, zu manipulieren und zu traversieren. Zudem stellt sie eine objekt- orientierte Zugriffsschicht zur Verfügung, die automatisch aus einem gegebenen Schema generiert wird. Sie ermöglicht es direkt mit Instanzen der im Schema spezifizierten Kno- ten und Kanten anstatt der “Rohklassen” Vertex und Edge zu arbeiten
Katrin Marchewka ([Mar06]) entwarf eine neue GREQL-Sprachversion (GREQL2) und implementierte einen Parser für diese. GREQL2 unterstützt alle Features der Vorgän- gerversion und bringt noch einige Neuerungen mit sich. So unterstützt der Parser bei- spielsweise jetzt zusätzlich zu regulären Pfadausdrücken die von Tim Steffens in [Ste05] beschriebenen kontextfreien Pfadausdrücke
Zuletzt entwickelte Daniel Bildhauer in seiner Diplomarbeit ([Bil06]) einen GREQL2- Auswerter, welcher eine Anfrage, gegeben als GREQL2-Syntaxgraph, an einem gege- benen Datengraph auswertet und das Ergebnis als Objekt des ebenfalls in dieser Arbeit entwickelten, generischen Containerformats JValue liefert
Die einzige noch fehlende Kernkomponente ist der Optimierer, der in der vorliegenden Diplomarbeit entwickelt werden soll
2. Grundlagen
Dieses Kapitel führt in alle Grundlagen ein, die zum Verständnis der späteren Kapitel notwendig sind
Dazu wird zuerst die Sprache GREQL2 anhand eines Beispiels eingeführt, worauf sich weitere Abschnitte zum Sprachschema und der Auswertung von GREQL2-Anfragen anschließen
Zuletzt wird noch ein Blick über den Tellerrand geworfen und die An- frageoptimierung in relationalen Datenbanksystemen erläutert
2.1. Die Anfragesprache GREQL
In diesem Abschnitt soll die Anfragesprache GREQL2 anhand eines einfachen Beispiels vorgestellt werden. Damit es auch ohne GRALAB-Vorkenntnisse nachvollziehbar ist, wird zunächst ein anschauliches Schema in Form einer vereinfachten Straßenkarte eingeführt
2.1.1. Das Beispielschema RoadMap
Als Beispiel soll eine einfache Straßenkarte dienen. Das Schema ist in Abbildung 2.1 visualisiert
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.1.: Das RoadMap-Schema
Die Definition mittels des JGRALAB-Formates TG ist in Listing 2.1 zu finden
In einer Straßenkarte (RoadMap) existieren zwei verschiedene Arten von Knoten (Junc- tion): Zum einen gibt es Kreuzungen (Intersection) und zum anderen gibt es Städte (City). Das Attribut roundabout gibt an, ob eine Kreuzung ein Kreisverkehr ist. Das Attribut population gibt die Einwohnerzahl einer Stadt an
Das Schlüsselwort abstract vor Junction bestimmt, dass es keine direkten Junction- Instanzen geben darf, sondern nur Instanzen von nichtabstrakten Subklassen. Sowohl Kreuzungen als auch Städte haben ein Namensattribut name, welches direkt in der Va- terklasse Junction deklariert wird. Der Einfachheit halber wird angenommen, dass alle Knoten einen eindeutigen Namen haben
Knoten, also Kreuzungen und Städte, werden durch Kanten verbunden. In einer Straßen- karte sind das Straßen (Street). Jede Straße hat einen Namen (name) und eine Länge (length). Im Schema verbindet eine Straße immer genau zwei Knoten. So wird eine reale Straße wie die B42 durch mehrere Abschnitte vom Typ Street modelliert. Ein Spe- zialfall einer Straße ist eine Autobahn (Highway), welche als zusätzliche Information die Anzahl der Spuren (lanes) trägt
2.1. Die Anfragesprache GREQL2
Abbildung in dieser Leseprobe nicht enthalten
Listing 2.1: Das RoadMap-Schema
2.1.2. Die Beispielinstanz des RoadMap-Schemas
Die konkrete Instanz dieses Schemas, anhand derer die Beispielanfragen ausgewertet wer- den, ist eine einfache Straßenkarte des Gebietes von Koblenz bis in den hohen Westerwald (Abb. 2.2, Seite 22)
Die Repräsentation als TGraph ist in Abbildung 2.3 auf Seite 23 zu sehen
Im Kontext von JGRALAB unterscheidet man zwischen Klasse und Typ. Der Knoten v7 gehört zur Klasse Intersection, aber ebenso zu deren Superklasse Junction. Eben- so gehört die Kante e6 zur Klasse Highway als auch zu deren Vaterklasse Street. Der JGRALAB-Klassenbegriff gleicht also jenem der objektorientierten Programmierung. Im Gegensatz dazu hat jeder Knoten oder jede Kante genau einen Typ, welcher gleich seiner speziellsten Klassenzugehörigkeit ist. Der Typ von v7 ist also Intersection, der Typ von e6 ist Highway
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.2.: Die Straßenkarte von Koblenz bis in den hohen Westerwald
2.1.3. Zwei exemplarische GREQL2-Anfragen
Die Anfrage aus Listing 2.2 gibt alle Knoten (Junction) des Graphen zusammen mit dem jeweiligen Typ des Knotens aus, für die gilt, dass sie mit dem Stadtknoten mit Namen Montabaur direkt verbunden sind
Abbildung in dieser Leseprobe nicht enthalten
Listing 2.2: An Montabaur angrenzende Knoten
Eine einfache GREQL-Query besteht aus einem sogenannten FWR-Ausdruck, wobei FWR für From-With-Report steht
Im from-Teil werden lokale Variablen deklariert. Im Beispiel wird also eine Variable junction der Knotenklasse (man beachte das V für Vertex) Junction deklariert und eine Variable montabaur der Knotenklasse City
Bei der Auswertung wird die Variable junction nacheinander an alle Knoten gebun- den, welche einer der Subklassen Intersection oder City angehören. Die Variable montabaur wird für jede Belegung von junction nacheinander an alle City-Knoten gebunden. Das liegt daran, dass junction außen und montabaur innen deklariert ist, was semantisch zwei geschachtelten Schleifen entspricht
2.1. Die Anfragesprache GREQL2
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.3.: Die TGraphrepräsentation der Straßenkarte
Es folgt ein optionaler with-Teil, der ein Prädikat enthält, welches die Werte der dekla- rierten Variablen erfüllen müssen. In oben genanntem Beispiel muss das Namensattribut der Variable montabaur den Wert “Montabaur” haben, und die Knoten montabaur und junction müssen über eine beliebige Kante verbunden sein. Dies wird durch den regu- lären Pfadausdruck in Zeile 4 von Listing 2.2 erreicht
Ein regulärer Pfadausdruck lässt sich nach Behling [Beh97] und Marchewka [Mar06] induktiv wie folgt definieren:
Definition 1. Eine einfache Pfadbeschreibung besteht aus einem Kantensymbol (−− >,
< −− oder < − >), welchem optional ein in geschweifte Klammern eingeschlossener Kantentypbezeichner folgt
Sind p1 und p2 Pfadbeschreibungen, so auch
- die Sequenz p1p
- die Iterationen p∗ (beliebig oft) und p+ (einmal oder öfter)
1
- die Alternative p1 | p
- die Option [p1]
24 2. Grundlagen
- die Zielknotenrestriktion p1 & VertexType
- die Klammerung (p1)
- die Potenz pn
- die transponierte Pfadbeschreibung pT
- die Startknotenrestriktion VertexType & p
- die Kantenpfadbeschreibung p1 − −anEdge− > p
- die Zwischenknotenrestriktion p1 aNode&{Expression} p
Ein Pfad ist eine alternierende Folge von Kanten und Knoten
Die report-Klausel bestimmt, welche Ausdrücke in die Ergebnismultimenge aufgenom- men werden. Im Beispiel aus Listing 2.2 besteht diese aus dem Knoten, welcher in der Form id: Typ ausgegeben wird, und seinem Namen
Ein FWR-Ausdruck wird durch das Schlüsselwort end abgeschlossen. Das Ergebnis der Auswertung der Query ist:
{v7: Intersection, Autobahndreieck Dernbach (A3/A48)}
{v2: City, Langenhahn}
{v5: City, Neuhaeusel}
Ein Vergleich mit Abbildung 2.3 auf Seite 23 zeigt, dass die gefundenen drei Knoten tat- sächlich die einzigen direkt mit Montabaur verbunden Knoten sind
Zuletzt soll noch eine etwas komplexere Anfrage betrachtet werden. Um diese zu ver- stehen, müssen zusätzlich zu den regulären Pfadausdrücken noch Pfadsysteme eingeführt werden
Ein Pfadsystem wird nach Berg [Ber03] durch einen Anfangsknoten v und einen regu- lären Pfadausdruck α bestimmt. In ihm ist zu jedem von v über einen α-förmigen Pfad erreichbaren Knoten genau ein Pfad enthalten. Im allgemeinen kann es mehrere solche Pfade geben
Die GREQL2-Anfrage aus Listing 2.3 berechnet einen Weg von Rennerod nach Koblenz mit Zwischenstation Hachenburg
In den Zeilen eins bis drei werden dazu Variablen der Klasse City deklariert. Sie werden ohne Optimierung nacheinander an alle möglichen Städtekombinationen gebunden, aber nur wenn der Ausdruck in den Zeilen vier bis sechs zu true evaluiert, wird der report- Teil ausgewertet. In diesem wird der gefundene Pfad ausgegeben
In Zeile 7 wird der Pfad von Rennerod über Hachenburg nach Koblenz berechnet. Da- zu wird zuerst ein Pfadsystem mit Anfangsknoten ren erzeugt, welches zu jedem von ren über hab erreichbaren Knoten genau einen Pfad enthält. Da die Variablen ren, hab und kob bereits im with-Teil geeignet eingeschränkt wurden, extrahiert die Funktion
2.1. Die Anfragesprache GREQL2
Abbildung in dieser Leseprobe nicht enthalten
Listing 2.3: Die Suche nach einer mögliche Route von Rennerod nach Koblenz mit Zwi- schenstation Hachenburg
extractPath() einen Pfad, der tatsächlich von Rennerod über Hachenburg noch Ko- blenz führt. Hierbei ist wichtig zu beachten, dass die Pfade in einem Pfadsystem keines- falls die kürzesten sein müssen. Im allgemeinen ist nicht einmal Zyklenfreiheit garan- tiert
Das Anfrageergebnis ist
v1: City ---e1: Street-> v2: City ---e3: Street->
v3: City ---e4: Street-> v5: City ---e5: Street-> v6: City
In Abbildung 2.3 auf Seite 23 kann abgelesen werden, dass der gefundene Weg von Ren- nerod über Langenhahn nach Montabaur führt. Von dort aus geht es über Neuhäusel nach Koblenz
2.2. Das GREQL2-Schema
Wie bereits erwähnt, erzeugt der GREQL2-Parser beim Lesen einer Anfrage einen ab- strakten Syntaxgraphen, welcher die interne TGraphen-Repräsentation der Anfrage dar- stellt und dem GREQL2-Schema genügt. Dieses ist ausführlich in Katrin Marchewkas Diplomarbeit [Mar06] beschrieben, so dass hier nur eine kurze Einführung anhand des Beispiels in Listing 2.4 gegeben wird
Abbildung in dieser Leseprobe nicht enthalten
Listing 2.4: Die Anfrage zur Bestimmung aller Straßen
Man kann sehen, dass lokale Variablen einer Kantenklasse mit E für Edge deklariert wer- den. Da kein with-Teil angegeben wurde, wird jeder an die Variable street gebunde- ne Wert in die Ergebnismultimenge aufgenommen. reportBag ist gleichbedeutend mit report, jedoch erlaubt letzteres noch die Angabe von Spaltennamen, die hier ohnehin nicht verwendet werden. Will man statt einer Multimenge, die Duplikate enthalten darf, lieber eine Menge als Ergebnis haben, so kann man dies in der Anfrage durch reportSet zum Ausdruck bringen
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.4.: Der Syntaxgraph der Kantenanfrage
Der Syntaxgraph der Anfrage aus Listing 2.4 ist in Abbildung 2.4 angegeben
Das Wurzelelement einer GREQL-Query ist immer ein Knoten des Typs Greql2Expres- sion
Der FWR-Ausdruck wird als BagComprehension-Knoten v6 modelliert.
Die Variablendeklarationen im from-Teil werden durch einen über eine isCompDeclOf-Kante verbundenen Declaration-Knoten, welcher beliebig viele SimpleDeclaration-Knoten enthält, repräsentiert.
Im Beispiel wird nur eine Variable street deklariert. Sie wird an Kanten (E im Anfragetextbzw. EdgeSetExpression im Syntaxgraphen) gebunden und wird durch ihreKlassenzugehörigkeit eingeschränkt (isTypeRestrOf). Diese muss Street oder eineUnterklasse davon (type = false) sein. Bei type = true könnten nur Kanten vom TypStreet an die Variable street gebunden werden, nicht aber Kanten vom Typ Highway.Mit excluded = true lässt sich die Bedeutung invertieren: street ließe sich dann nuran Kanten, die gerade nicht der Klasse Street angehören, binden. Im Beispielgraphenaus Abbildung 2.3 auf Seite 23 träfe das jedoch auf keine Kante zu, so dass das Auswertungsergebnisdie leere Menge wäre.
Die Gestalt der einzelnen Ergebnisse, die durch die reportBag-Klausel bzw. den entsprechendenBagComprehension-Knoten zusammengefasst werden, wird durch den durch eineisCompResultDefOf-Kante verbundenen Ausdruck bestimmt. Da im Beispiel sowohldie String-Repräsentation der Kante als auch der Kantenname ausgegeben werden sollen,muss mittels einer TupleConstruction ein Tupel erzeugt werden. Das erste Elementist der Wert der Variable street an sich, das zweite Element ist das Resultat der Funktionsanwendung(FunctionApplication) street.getValue(“name”), das denWert desAttributs name des an die Variable street gebundenen Elements liefert.
Der Vollständigkeit halber soll auch hier das Auswertungsergebnis der Anfrage angegebenwerden.
{e6: Highway , A3}
{e4: Street , B49}
{e2: Street , B414}
{e3: Street , B255}
{e1: Street , B255}
{e7: Highway , A48}
{e5: Street , B49}
Auch hier lässt sich die Korrektheit wieder leicht anhand Abbildung 2.3 auf Seite 23verifizieren.
2.3. Der GREQL2-Auswerter
In diesem Abschnitt wird die Funktionsweise des GREQL2-Auswerters beschrieben, da nur dann Aussagen über Optimierungsmöglichkeiten gemacht werden können.
Der Auswerter muss eine Funktion GreqlSyntaxgraph×Datengraph→JValue berechnen. Er bekommt also eine GREQL-Anfrage in Form eines Syntaxgraphen und den Datengraphen, auf welchen sich die Anfrage bezieht. Dann wertet er die Anfrage auf dem Datengraphen aus und liefert das Ergebnis als Objekt des generischen Containerformats JValue.
Das ist wie folgt implementiert: VertexEvaluator ist die Vaterklasse von über fünfzig weiteren Auswerterklassen, die spezialisiert für die einzelnen Knotentypen sind. Diese heißen TEvaluator, wenn T der Name eines Knotentyps ist. VertexEvaluator selbst ist abstrakt und definiert eine Methode evaluate(), die das Ergebnis der Auswertung des Knotens als JValue liefert und von allen Subklassen geeignet implementiert werden muss. Zusätzlich enthält VertexEvaluator eine statische Factory-Methode
VertexEvaluator createVertexEvaluator (Vertex vertex ,
GreqlEvaluator eval),
die mittels Reflection anhand des Typs von vertex den passenden VertexEvaluator für diesen Knoten erzeugt.
Im ersten Auswertungsschritt wird über alle Knoten des Syntaxgraphen iteriert. Für jeden Knoten wird mit createVertexEvaluator() ein passender VertexEvaluator erzeugt und als temporäres Attribut des Knotens gespeichert.
Die eigentliche Auswertung wird dann durch Aufruf der evaluate()-Methode des Auswerterobjekts des Wurzelknotens Greql2Expression gestartet. Dessen Auswerter, der Greql2ExpressionEvaluator, ermittelt nun die VertexEvaluator-Objekte der Kindknoten und ruft bei jenen die getResult()-Methode auf, welche entweder evaluate() aufruft oder ein bereits berechnetes und zwischengespeichertes Ergebnis zurückgibt. Dies wird rekursiv bis zu den Blättern des Syntaxgraphen fortgeführt, und jeder Nicht-Blatt- Knoten kombiniert die Ergebnisse seiner Kindknoten entsprechend seiner Semantik.
Um den Berechnungsaufwand möglichst gering zu halten, erfolgt die Auswertung falls möglich nach dem Prinzip der lazy evaluation (verzögerte Auswertung). Das heißt, dass Teilergebnisse nur dann (neu) berechnet werden, wenn sie in einer anderen Berechnung benötigt werden.
Da die Funktionen der GREQL-Funktionsbibliothek aber als Klassen mit einer eval- uate()-Methode definiert sind, welche die Funktionsargumente als Parameter vom Typ JValue erhält, kann dieses Prinzip bei der Auswertung von FunctionApplication- Knoten nicht eingesetzt werden. So werden beim Funktionsaufruf and(A, B) die Ausdrücke A und B vor der Funktionsanwendung and() ausgewertet, obwohl die Berechnung des Ergebnisses von B unnötig ist, falls A bereits zu false ausgewertet wurde. Bei der Auswertung von GREQL2-Funktionen handelt es sich also um eager evaluation (strikte Auswertung).
Das Ergebnis einer Knoten-Auswertung wird als temporäres Attribut des entsprechendenVertexEvaluator-Elements gespeichert. Wird danach erneut getResult() aufgerufen,so wird das zwischengespeicherte Ergebnis geliefert. Der Auswerter speichert zu jederVariable eine Liste von VertexEvaluator-Objekten, deren Ergebnisse von dieser Variablebeeinflusst werden. Bei jeder Variableniteration werden die dadurch ungültig werdendenTeilergebnisse gelöscht und somit eine Neuberechnung veranlasst.
Dies soll am Beispiel aus Listing 2.5 verdeutlicht werden.
Abbildung in dieser Leseprobe nicht enthalten
Listing 2.5: Ein Primzahlbeispiel
In der Anfrage werden a, b und c nacheinander an die Belegungen (7, 7, 7), (7, 7, 8), ..., (20, 20, 19) bis (20, 20, 20) gebunden. Dabei wird zuerst die innerste Variable c inkrementiert, dann b und zuletzt die äußerste Variable a. Da jede der Variablen 14 verschiedene Werte annehmen kann, gibt es insgesamt 143 = 2744 Belegungen, für die der with-Teil evaluiert werden muss.
Wie bereits erwähnt, sind in GREQL2 alle Operatoren wie das logische and oder equals als Funktion implementiert, was zur Folge hat, dass alle Parameter ausgewertet werden müssen. Der with-Teil der Anfrage in äquivalenter Präfix-Notation ist:
and(isPrime(a), and(equals(a, b), equals(b, c)))
Das Ergebnis von isPrime(a) wird nur 14 mal berechnet, da a nur 14 mal den Wert wechselt. Die restlichen 2730 mal liefert getResult() des entsprechenden Function- ApplicationEvaluator-Objekts das zwischengespeicherte Ergebnis der letzten Neuberechnung.
Das Resultat der Funktionsanwendung equals(a, b), welches in obiger Anfrage in der Infixnotation a = b geschrieben wurde, wird nur 196 mal neu berechnet, weil b nur nach jeweils 14 Iterationsschritten an einen neuen Wert gebunden wird. Der zweite Vergleich equals(b, c) wird immer komplett neu berechnet, da sich der Wert von c nach jedem Iterationsschritt ändert.
Damit müssen auch beide and-Funktionsanwendungen bei jedem Iterationsschritt erneut berechnet werden. Die folgende Tabelle fasst die Anzahl der Neuberechnungen der jeweiligen Ausdrücke noch einmal zusammen.
Abbildung in dieser Leseprobe nicht enthalten
Das Ergebnis der Anfrage ist die Menge aller Dreiertupel gleicher Primzahlen zwischen 7 und 20.
{11, 11, 11}
{17, 17, 17}
{19, 19, 19}
{7, 7, 7}
{13, 13, 13}
Im folgenden Abschnitt wird der Themenbereich rund um GREQL2 kurzzeitig verlassen und ein Einblick in die Optimierung von Anfragen in relationalen Datenbanksystemen gegeben.
2.4. Die Anfrageoptimierung in relational Datenbankensystemen
Gemäß [Vos04] unterteilt sich die Anfrageverarbeitung in relationalen Datenbanksystemen in vier Phasen.
1. In der Vorverarbeitung wird der als Anfrage in einer deklarativen Hochsprache wie SQL vorliegende Ausdruck in eine interne, prozedurale Form der Relationenalgebra umgeformt und Views durch ihre Definitionen ersetzt.
2. Danach erfolgt die High-Level- oder algebraische Optimierung, bei der Äquivalenzumformungen auf den Ausdruck angewendet werden.
3. Bei der Low-Level-Optimierung wird zum bereits optimierten Ausdruck ein möglichst kostenminimaler Ausführungsplan (query execution plan, QEP) erzeugt.
4. In der Anfrage-Ausführung wird zuletzt der im vorangegangenen Schritt gewählte QEP ausgeführt und das Anfrageergebnis berechnet.
Ziel der Anfrageoptimierung der Schritte 2 und 3 ist, einen Anfrageausdruck vor der Ausführung in einen äquivalenten Ausdruck umzuformen, dessen Ergebnis mit dem der Originalanfrage übereinstimmt, die Ausführungskosten jedoch geringer sind.
Dabei können die Kostenarten vielfältig und für jede Datenbank und jeden Einsatzzweck verschieden gewichtet sein. Einige Faktoren sind zum Beispiel
- die Wartezeit für den Benutzer,
- die tatsächlich verbrauchte CPU-Zeit,
- der Speicherverbrauch,
- die Anzahl von I/O-Operationen, insbesondere von Sekundärspeicherzugriffen,
- der gesamte Ressourcenverbrauch und eventuell auch
- der benötigte Energieverbrauch.
In den folgenden Abschnitten werden die beiden Optimierungsschritte 2 und 3 etwas genauer erläutert.
2.4.1. Die algebraische Optimierung
In der algebraischen Optimierung wird ein in der Relationenalgebra vorliegender Ausdruck in mehreren Schritten in einen äquivalenten Ausdruck, der allerdings kosteneffizienter zu berechnen ist, umgeformt.
Vossen liefert in [Vos04] folgende Äquivalenz-Definition.
Definition 2. Es sei D = (R, .); E und E′ seien Ausdrücke aus RA. E und E′ heißen
äquivalent, i. Z. E ≈ E′, falls gilt: (∀d ∈ Dat(R)) vE(d) = vE′(d)
Zwei Ausdrücke E und E′ der Relationenalgebra RA heißen also äquivalent, falls sie bei jeder Auswertung bezüglich jedes aktuellen Zustands d über dem gegebenen Datenbankschema D das gleiche Ergebnis liefern.
Die Ausdrücke liegen dabei als Baum vor, wobei die Blätter die Operanden, die inneren Knoten Operationen und die Kanten den Datenfluss repräsentieren. Zur Optimierung wird insbesondere versucht die Zwischenergebnisse der Auswertung zu verkleinern indem Selektionen und Projektionen möglichst weit nach unten im Baum gezogen und so möglichst früh angewendet werden.
Eine von Vossen beschriebene Heuristik zur Durchführung der algebraischen Optimierung
umfasst zum Beispiel die folgenden Schritte:
1. Zerlege Selektionsoperationen, deren Bedingung eine Konjunktion von elementaren Bedingungen ist, in eine Folge von Selektionsoperationen. Damit können die Selektionen in späteren Schritten separat behandelt werden.
2. Schiebe Selektionen vorbei an anderen Operationen so weit wie möglich nach unten im Anfragebaum.
3. Nimmt man an, dass der Anfragebaum von links nach rechts ausgewertet wird, so rearrangiere die Blätter des Baums derart, dass jene, die mit den restriktivsten Selektionsoperationen verbunden sind, am weitesten links stehen.
4. Im letzten Schritt zerlege Projektionen und verschiebe sie im Baum so weit wie möglich nach unten.
Hierbei muss darauf geachtet werden, dass keine Join-Attribute, die später benötigt werden, durch Projektionen entfernt werden, was den Verbund zu einem teuren
kartesischen Produkt degenerieren würde.
Zuletzt kann sich eine Suche nach identischen Teilausdrücken anschließen, mit dem Ziel, diese zu verschmelzen und so nur einmal auszuwerten.
2.4.2. Die Low-Level-Optimierung
Bei der Low-Level-Optimierung geht es um die Erzeugung eines möglichst effizienten Ausführungsplans. Während die algebraische Optimierung auf der sogenannten logischen Algebra, also dem Datenmodell des Systems (z.B. Relationenalgebra) arbeitet, benutzt die Low-Level-Optimierung zur Formulierung von QEPs die physische Algebra. Diese stellt systemspezifische Operatoren bereit, die jene der logischen Algebra implementieren. Somit können hier Implementierungsdetails berücksichtigt werden.
Hierbei gibt es drei wesentliche Aspekte:
1. die Umformung eines Ausdrucks der logischen Algebra in einen Ausführungsplan
2. eine Suchstrategie, die beschreibt, wie zu einem gegebenen QEP weitere alternative QEPs erzeugt werden können
3. eine Kostenfunktion, mit der sich die einzelnen Ausführungspläne bewerten lassen
Bei den Suchstrategien gibt es zum einen die vollständige Suche (z.B. Tiefensuche oder Breitensuche), die aus einem initialen QEP alle möglichen Alternativ-QEPs erzeugt und bewertet. Nur bei vollständiger Suche kann der Fund eines optimalen Ausführungsplans garantiert werden, jedoch ist der Kostenaufwand dazu immens. Zum anderen existieren Heuristiken, die meistens zwar einen suboptimalen QEP liefern, dafür aber hinreichend schnell sind. In der Regel ist man vor allem an der Vermeidung eines besonders schlechten als am Fund des optimalen Ausführungsplans interessiert, so dass der Einsatz von Heuristiken ausreichend ist.
Zur Bewertung alternativer Ausführungspläne zwecks Selektion des Besten, hat die Kostenfunktion die Aufgabe, die gegebenen QEPs einer möglichst realistischen und effizienten Kostenabschätzung zu unterziehen. Hierbei können alle bereits am Anfang dieses Abschnitts erwähnten Faktoren wie CPU-Zeit oder die Anzahl von I/O-Operationen eingehen. Wurde zwischen den verschiedenen alternativen Ausführungsplänen der laut Kostenfunktion effizienteste gewählt, wird dieser zur Ausführung gebracht.
2.4.3. Die Optimierung in Datenbanken und GREQL2
Bei der Anfrageauswertung in Datenbanksystemen entfallen große Teile der Kosten auf Zugriffe auf den Hintergrundspeicher oder die Generierung von Dateien zur Speicherung von Zwischenergebnissen. Die Bibliothek JGRALAB hält den Datengraphen, auf dem eine Anfrage ausgewertet werden soll, komplett im Hauptspeicher. Daher können solche Kosten vernachlässigt werden, und der Fokus liegt auf den reinen Berechnungskosten.
3. Die Arbeitsweise des GREQL1-Optimierers
Dieses Kapitel beleuchtet die Arbeitsweise des GREQL1-Optimierers von David Polock ([Pol97]). Dieser hat die gleiche Zielsetzung wie der zu entwickelnde GREQL2-Optimierer, nämlich die Umformung des Syntaxgraphen der Anfrage derart, dass das Auswertungsergebnis der optimierten und der Originalanfrage gleich sind, jedoch die Auswertungszeit der optimierten Anfrage stark verringert wird. Die Gliederung wurde von Polocks Arbeit übernommen.
Zuerst wird beschrieben, wie der GREQL1-Optimierer die Mehrfachberechnung gleicher Teilausdrücke in Anfragen vermeidet.
Danach wird die Bewertungsfunktion vorgestellt, mit welcher der Optimierer abschätzt, ob eine Umformung des Syntaxgraphen die Auswertung beschleunigt.
Zuletzt werden alle Transformationen, die der GREQL1-Optimierer auf den Syntaxgraphen anwenden kann, beschrieben.
[...]
1 Generic Understanding of PROgrams,http://www.gupro.de
- Arbeit zitieren
- Tassilo Horn (Autor:in), 2008, Ein Optimierer für GReQL2, München, GRIN Verlag, https://www.grin.com/document/111912
