Fein-granulare Analyse der Datenherkunft in ausdrucksstarken Anfragen

01.09.2018 bis 31.08.2021

Data Provenance deckt auf, wie Datenbankanfragen Eingabedaten transformieren, filtern, verknüpfen und aggregieren, um das endgültige Resultat zu erhalten. Die heute typische Anfragekomplexität und stetig wachsende Datenvolumina erschweren es, das interne Vorgehen von Anfragen zu verstehen und zu validieren: wo in der Eingabe ist der Ursprung dieses Resultates? Wieso hat die Anfrage diese Teilausgabe erzeugt aber eine andere unterdrückt? Genau wie wurde dieser Resultatwert berechnet und welche Anfragekonstrukte waren an dieser Berechnung beteiligt? Data Provenance beantwortet diese und weitere Fragen, erklärt die Internas (und Fehler) von Anfragen, hilft bei der Einschätzung der Qualität von Daten und schafft Vertrauen in Anfrageergebnisse—unschätzbare Werte für eine datengestützte Wissenschaft und Gesellschaft.

Mittels Provenance verlagern wir den Fokus einer Anfrage von Werten und deren Transformation auf Abhängigkeiten zwischen Ausgabe- und Eingabedaten. Dieser Forschungsantrag baut auf die zentrale Hypothese, dass abstrakte Interpretation den idealen Rahmen bietet, um diese Fokusverlagerung sowohl zu studieren als auch zu implementieren. Abstrakte Interpretation—ein Stil der Programmanalyse, der seit den 1970er Jahren etabliert ist—konzentriert sich auf wenige ausgewählte Aspekte der Programmausführung und ignoriert alle weiteren. In diesem Projekt adaptieren wir diese Ideen, so dass Ein-/Ausgabeabhängigkeiten (anstatt Werten) in Anfragen und Programmen die Hauptrolle einnehmen.

Je komplexer Anfragelogik wird, desto höher ist der Wert von Data Provenance. Wir werden Provenance für fortgeschrittene Anfragekonstrukte und -idiome (wie tiefe Verschachtelung, gleitende Windows, benutzer- sowie vordefinierte Funktionen oder Rekursion) ableiten. Es ist ein Kernziel, tatsächlich praktisch relevante Dialekte von Anfragesprachen—bspw. moderne SQL-Varianten—zu verstehen. Hier zeigen frühere Arbeiten signifikante Restriktionen. Wir bauen auf die Flexibilität abstrakter Interpretation und werden abstrakte Domänen definieren, die Provenance auf mehreren Granularitätsstufen erklären können, bis hin zu individuellen atomaren Werten (z.B. den Zellen einer Tabelle). Weitergehende Änderungen der abstrakten Domänen und der Regeln der Anfrageauswertung werden uns erlauben, neue und notorisch schwierige Arten von Provenance zu untersuchen (etwa die von im Resultat unterdrückten Werten). Abstrakte Interpretation ist sowohl ein mächtiges theoretisches als auch ein praktisches Instrument. Wir werden Letzteres nutzen, um die parallele Ableitung von Provenance für Anfragen über sehr großen Datenmengen und die nahtlose Einbettung von Provenance in Anfrageübersetzer existierender moderner Datenbanksysteme zu realisieren.