Entwurf einer State-of-the-Art Graph-API für Hydra.PowerGraph

Designing a State-of-the-Art Graph-API for Hydra.PowerGraph

Student

  • Simon Leidenbach

Gutachter

  • Andras Heuer
  • Holger Meyer

Betreuer / Ansprechpartner

  • Alf-Christian Schering
  • 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 Anfrageschnittstelle 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, Charu C., Wang, Haixun (Eds.) : Managing and Mining Graph Data. Springer, 2010.
  • Meyer, Holger, Alf-Christian Schering, and Andreas Heuer. "The Hydra. PowerGraph System." Datenbank-Spektrum (2017): 1-17.
  • Holger Meyer, Alf-Christian Schering and Christoph Schmitt, WossiDiA --- The Digital 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, Renzo et al: G-CORE: A Core for Future Graph Query Languages. SIGMOD Conference 2018: 1421-1432.
  • Angles, Renzo, and Federico Meza and Francisco Moya: Supporting property graphs in apache giraph. CLEI 2016: 1-12.
  • Holzschuher, Florian, and René Peinl. "Performance of graph query languages: comparison of cypher, gremlin and native access in Neo4j." Proceedings of the Joint EDBT/ICDT 2013 Workshops. ACM, 2013.
  • Hartig, Olaf, and Jorge Pérez. "An initial analysis of Facebook’s GraphQL language." 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. "API Design in Distributed Systems: A Comparison between GraphQL and REST." (2017).
  • Xin, Reynold S., et al. "Graphx: Unifying data-parallel and graph-parallel analytics." arXiv preprint arXiv:1402.2394 (2014).