Kurzfassung

Bei Graphdatenbanken basieren deklarative Anfragesprachen in der Regel auf Pattern Matching. Bestehende Arbeiten zu Pattern Matching konzentrieren sich jedoch überwiegend auf eine algorithmische Betrachtung und lassen die Integration in ein Datenbanksystem außen vor. Diese Arbeit adressiert genau diesen Aspekt und konzentriert sich dabei auf das Property-Graph-Datenmodell sowie die am Lehrstuhl entwickelte Hauptspeicherdatenbankplattform ERIS.

Ausgangssituation

In der Verarbeitung großer Datenmengen gewinnen Graphdatenbanken zunehmend an Bedeutung. Dabei werden Daten in Form von Graphen, also in Knoten und Kanten, strukturiert. Häufig lassen sich gerade Zusammenhänge zwischen Entitäten so natürlicher darstellen. Auch zielen heute viele Fragestellungen bei der Auswertung und Verarbeitung von Daten viel mehr auf Zusammenhänge zwischen Entitäten als auf die Entitäten selbst ab und lassen sich so auf graphstrukturierten Daten besser beantworten.
Bei Graphdatenbanken basieren deklarative Anfragesprachen in der Regel auf Pattern Matching, bei dem eine Anfrage als Teilgraphschablone formuliert wird. Pattern Matching ist ein sehr altes deklaratives Anfragekonzept, welches durch seine hohe logische Abstraktion überzeugt, dadurch jedoch sehr anspruchsvoll hinsichtlich einer effizienten Anfrageverarbeitung ist. Pattern Matching ist bereits häufig untersucht wurden. Diese Arbeiten konzentrieren sich jedoch überwiegend auf die algorithmische Betrachtung der Problematik und legen meist ein sehr einfaches Graph Datenmodell (in der Regel ohne Properties) zugrunde. Mit dem inzwischen breitem Interesse an Graphdatenverarbeitung stellt sich die Frage der Umsetzung von Pattern Matching im Kontext eines zeitgemäßen Graph-Datenmodells wie z.B. dem Property-Graph-Modell und aktueller hauptspeicherbasierter Datenbankinfrastruktur neu.

Aufgabenstellung

In dieser Diplomarbeit soll nun die Integration bewährter Pattern-Matching-Algorithmen in moderne Datenbanksysteme anhand des Property-Graph-Datenmodells und der am Lehrstuhl entwickelten Hauptspeicherdatenbankplattform ERIS untersucht werden. Dabei sind folgende Fragestellungen vordergründig zu berücksichtigen:

  • Wie kann ein effizientes Auswerten von nicht-topologischen Werteprädikaten sinnvoll in Pattern-Matching-Algorithmen integriert werden?
  • Wie können Graphen in ERIS physisch, verteilt repräsentiert werden, dass Pattern-Matching effizient darauf arbeiten können?

Als Ergebnis der Untersuchung ist ein Implementierungskonzept für die Realisierung von Pattern Matching auf ERIS zu entwickeln. Mit einer prototypischen Implementierung sollen anschließend in selbstständig konzipierten Experimenten verschieden Implementierungsalternativen untersucht und für das Konzept getroffene Festlegungen evaluiert werden.