Graph-Algorithmen und die Hypergraph-Anfragesprache GrafL

Graph-Algorithms and the Hypegraph Query Language GrafL

Student

  • André Gember

Gutachter

  • Andreas Heuer 
  • Holger Meyer 

Betreuer / Ansprechpartner

  • Holger Meyer

Typ der Arbeit

  • Bachelorarbeit

Charakter der Arbeit

  • Erarbeitung State-of-the-Art
  • Konzeption
  • Prototypische Implementierung

Vorkenntnisse

  • Datenbanken
  • Graphen und Algorithmen

Beschreibung

Im Zentrum der Untersuchungen des ISEBEL-Projektes stehen Glaubenssysteme, speziell im Bereich der Legenden. Dazu werden drei Sammlungen namhafter Erzählforscher wie Evald Tang Kristensen in Dänemark, Richard Wossidlo zu Mecklenburg und niederländischer Sammler und Forscher aufbereitet, zusammengeführt und mit Graph-Mining-Techniken [1] auf gemeinsame, wiederkehrende Muster untersucht. Diese Muster beschreiben, wie etwa Legenden entstehen, wie sie weitergegeben werden, sich entwickeln und in welchem kulturellem Umfeld dies geschieht.

Die Inhalte des Wossidlo-Archivs, die Feldforschungsbelege, Auszüge der Korrespondenzen Wossidlos mit einem umfangreichen Beiträgernetzwerk, Verweise auf publizierte Werke zu den einzelnen Bereichen des täglichen Lebens und weiterer Kollektionen, liegen in digitalisierter Form vor. Das WossiDiA-System [2] verwendet zur Speicherung gerichtete, typisierte Hypergraphen [3].

Um typische Fragestellungen der Erzählforschung effizient und effektiv zu unterstützen, soll dem Anwendungsentwickler eine Hypergraph-basierte Anfragesprache zur Verfügung gestellt werden. Dazu ist der State-of-the-Art in diesem Bereich eingehend zu untersuchen und darzustellen. Beispiele für solche Anfragesprachen sind Apache TinkerPop‘s graph traversal language, Gremlin, und TinkerPop-kompatible Systeme wie Apache Spark GraphX, die auch in Rahmen des ISEBEL-Projektes und WossiDiA eingesetzt werden. Hydra.PowerGraph verfügt mit GrafL über eine eigene Anfragesprache, die speziell auf Hypegraphstrukturen ausgerichtet ist.

Dabei steht im Rahmen der Bachelorarbeit nicht so sehr der Umfang der Anfragesprache und der damit verbundenen Anfragemöglichkeiten, sondern vielmehr die Ausgestaltung der Schnittstelle zum Graphdatenbanksystem. Dazu sind vorrangig Ansätze wie RESTful APIs und Web-Service-Schnittstellen, die einen Programmiersprachen-unabhängigen Zugriff erlauben, zu untersuchen.

Am Beispiel einfacher, bereits vorhandener Graphoperationen wie Filteroperationen (klassische Werteselektion für Knoten, Strukturselektion für Graphen (etwa nach Kanten-, Link- sowie Knotentypen) und die Anwendunge existierender Graph-Algorithmen (K- Nachbarschaft, K-Shortest Path, ...) ist eine Schnittstelle zu konzipieren und prototypisch zu implementieren. Anfrageergebnisse werden in Hydra.PowerGraph typischerweise als Hypergraphen, d.h. als Menge von Hyperkanten, zurückgegeben. Die Form der Ergebnis- Vermittlung ist neu zu konzipieren. Dazu sind flexible Datenrepräsentationsformen der Ergebnisgraphen auf Basis bekannter Formate (XML, JSON, ...) zu wählen, die die Darstellung von Ranking Score-Werten, eine Portionierung oder ein inkrementelles Nachladen erlauben.

Die prototypische Implementierung soll auf der existierenden REST-API aufbauen und eine Client-seitige Testsuite aus dem Hydra.Maps-Projekt zur Verifikation verwenden.

Arbeitsschritte

  • Recherche, Aufbereitung und Klassifikation existierender Ansätze für Graph- Anfrageschnittstellen und APIs; Darstellung des State-of-the-Art

  • Untersuchung der Übertragbarkeit existierender Schnittstellen auf Hypergraphstrukturen

  • Kritische Bewertung der existierenden Frameworks und der existierenden REST-API für das WossiDiA-System

  • Neukonzeption der API und deren prototypische Umsetzung

  • Demonstration der Tauglichkeit anhand ausgewählter Fragestellungen auf dem WossiDiA-Datensatz und aus dem Hydra.Maps-Projekt

Literatur

  • Aggarwal,CharuC.,Wang,Haixun(Eds.):ManagingandMiningGraphData. Springer, 2010.

  • Meyer,Holger,Alf-ChristianSchering,andAndreasHeuer."TheHydra.PowerGraph System." Datenbank-Spektrum (2017): 1-17.

  • HolgerMeyer,Alf-ChristianScheringandChristophSchmitt,WossiDiA---TheDigital Wossidlo Archive, in: Holger Meyer, Christoph Schmitt, Thomas Jansen and Alf- Christian Schering (Hrsg.), Corpora ethnographica online --- Strategien der Digitalisierung kultureller Archive und ihrer Präsentation im Internet, Volume 5 of Rostocker Beiträge zur Volkskunde und Kulturgeschichte, Waxmann, 2014, 61–84.

  • Angles,Renzoetal:G-CORE:ACoreforFutureGraphQueryLanguages.SIGMOD Conference 2018: 1421-1432.

  • Angles,Renzo,andFedericoMezaandFranciscoMoya:Supportingpropertygraphs in apache giraph. CLEI 2016: 1-12.

  • Holzschuher,Florian,andRenéPeinl."Performanceofgraphquerylanguages: comparison of cypher, gremlin and native access in Neo4j." Proceedings of the Joint EDBT/ICDT 2013 Workshops. ACM, 2013.

  • Hartig,Olaf,andJorgePérez."AninitialanalysisofFacebook’sGraphQLlanguage." AMW 2017 11th Alberto Mendelzon International Workshop on Foundations of Data Management and the Web, Montevideo, Uruguay, June 7-9, 2017.. Vol. 1912. Juan Reutter, Divesh Srivastava, 2017.

  • Eizinger,Thomas."APIDesigninDistributedSystems:AComparisonbetween GraphQL and REST." (2017).

  • Xin,ReynoldS.,etal."Graphx:Unifyingdata-parallelandgraph-parallelanalytics."arXiv preprint arXiv:1402.2394 (2014).