Master Thesis MSTR-2019-39

BibliographySchweizer, Markus: Speichern und Visualisieren von Struktureller Provenance.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 39 (2019).
73 pages, german.
Abstract

Die zunehmende Digitalisierung führt zu einem enormen Wachstum an heterogenen Datenmengen. Entsprechend komplexer und undurchsichtiger werden Datenbankanfragen. Daher bedarf es skalierbarer Techniken, um Entwicklern Zusammenhänge zwischen Analyseschritten und Datenmanipulationen leichter nachvollziehen lassen zu können. Data Provenance beschreibt den Verlauf einzelner Datenelemente auf Tupel-Ebene in datenverarbeitenden Prozessen. Somit können Manipulationen einzelner Daten Schritt für Schritt innerhalb einer Datenbankanfrage nachvollzogen werden. Pebble, eine am Lehrstuhl entwickelte Provenance Lösung für Apache Spark, erweitert den Data Provenance Ansatz um Strukturelle Provenance: Mit ihr ist es möglich, gezielt mit geschachtelten Daten zu arbeiten und somit nicht nur auf Tupel-Ebene, sondern durch das Ansprechen einzelner Attribute mittels Tree-Pattern innerhalb geschachtelter Daten zu arbeiten. Dies ermöglicht ein noch genaueres Zurückverfolgen von Daten, welches nicht nur auf Tupel-Ebene stattfindet, sondern auf den entsprechend ausgewählten geschachtelten Teildaten. Somit können beispielsweise Elemente innerhalb einer Liste gezielt angesprochen und verfolgt werden. Das Sammeln von Data Provenance geschieht entweder lazy und damit zur Anfrage der Data Provenance, oder eager und wird bereits während der Programmausführung gesammelt. Pebble bietet bereits einen lazy-Ansatz. Im Rahmen dieser Arbeit wird Pebble um den eager-Ansatz erweitert. Dafür werden zwei Ansätze zum eager-Caching der Data Provenance verfolgt und vorgestellt. In beiden Ansätzen geht es um ein effizientes Speichern der gesammelten Data Provenance. Ebenfalls wird ein Algorithmus entwickelt, welcher Teildaten aus geschachtelten Ergebnismengen zurück bis zu den Eingabedaten verfolgt. Zusätzlich wird eine Visualisierung der von Pebble gesammelten Data Provenance entwickelt. Diese Visualisierung veranschaulicht den Verlauf der Datenbankanfrage sowie den Einfluss der vom Nutzer gewählten Tree-Pattern auf das Zurückverfolgen gezielt ausgewählter, geschachtelter Daten. Abschließend gibt es eine Evaluation, welche den neuen eager-Ansatz dem lazy-Ansatz gegenüberstellt und diese Ansätze auf Laufzeiten und Speicherbedarf testet. Dabei wird deutlich, dass ein Backward-Tracing mit eager-Ansatz bei komplexeren Datenbankanfragen nur einen Bruchteil der Ausführungszeit des lazy-Ansatzes benötigt, mit zunehmender zu speichernder Datengröße jedoch an Vorsprung verliert. Dies lässt sich darauf zurückführen, dass Apache Spark mit der Zeit beginnt, Daten aus dem Cache auf das Dateisystem zu schreiben, und das Einlesen dieser Daten dann wesentlich mehr Zeit benötigt.

Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Data Engineering
Superviser(s)Herschel, Prof. Melanie; Diestelkämper, Ralf
Entry dateAugust 12, 2019
   Publ. Computer Science