zur Startseite

Masterarbeit

Provenance für fehlende Ergebnisse auf geschachtelten Daten in verteilten Systemen
Betreuer M.Sc. Ralf Diestelkämper
Prüfer Prof. Dr. rer. nat. Melanie Herschel
Ende10.04.2019
Beschreibung

DISC (data intensive scalable computing) Systeme werden häufig zur Analyse und Verarbeitung großer Datenmengen genutzt, da sie Datensätze und –ströme in vielen Formaten einfach abfragen und umformen können. Bekannte Vertreter der DISC Systeme sind unter anderem die Systeme Flink, Hadoop, Pig, Hive und Spark. Gerade weil diese Systeme so eine Vielfalt von Datenformaten unterstützen und verteilt sind, ist das Debuggen und Einstellen der Analyseschritte eine wesentliche Herausforderung. Je nach Größe des Datensatzes und der Analyseanfrage ist eine händische Fehlersuche sehr aufwändig und fehleranfällig. Existierende Erweiterungen der oben genannten DISC Systeme haben gezeigt, dass Provenance Lösungen das Debugging solcher Anwendungen erleichtern.

Provenance beschreibt Meta-Informationen, die bei der Ausführung einer Anfrage über das eigentliche Ergebnis hinaus gesammelt werden und den Entstehungsprozess des Ergebnisses beschreiben. Wenn (semi-)strukturierte Daten mit Operatoren verarbeitet werden, deren Semantik überwiegend klar definiert ist, spricht man auch von Data Provenance. Aus diesem Feld stammt auch die (positive) Why-Provenance. Sie beschreibt welche Teile der Eingabe zu welchem Teil der Ausgabe führen.  

Existierende Provenance Lösungen für DISC Systeme, wie beispielsweise RAMP, sammeln ausschließlich positive Why-Provenance. Allerdings beschränken diese sich auf Erklärungen von existierenden Ergebnisdaten. Ihnen fehlt die Fähigkeit erwartete, aber fehlende, Ergebnisse zu erklären (Why-Not Provenance).

Für relationale Daten gibt es bereits Lösungen, die diesen Bereich der Provenance abdecken. Beispiele für Implementationen sind Artemis und Why-Not. Sie unterscheiden sich u.A. in den Arten der Erklärungen, die sie für die fehlenden Tupel in der Anfrage erstellen. Basis dafür ist eine allgemeine Formalisierung der Problemstellung, die von allen Algorithmen verarbeitet werden kann.

Für die, im Vergleich zu relationalen Daten nicht so stark strukturierten, geschachtelten Daten wie XML oder JSON Daten, gibt es bisher keine Why-Not Provenance Lösungen.

Da diese Daten häufig auch in DISC Systemen analysiert werden können, ist das Ziel dieser Arbeit ist die Entwicklung einer Why-Not Provenance Lösung für geschachtelte Daten in DISC Systemen zu erarbeiten.