Das hier vorgestellte Verfahren ermöglicht die Analyse der Data Provenance von beliebigen SQL-Queries. Von der ebenfalls hier skizzierten Implementierung des Verfahrens werden unter anderem unterstützt: Subqueries, Aggregierungen, rekursive Queries und Window Functions. Eingabequeries werden zunächst in eine imperative Programmiersprache übersetzt. Der Programmcode wird mit einem neuen Verfahren analysiert, das auf bekannte Techniken aus dem Bereich der Programmanalyse aufbaut: Program Slicing, Kontrollflussanalyse und abstrakte Interpretation. Dadurch erhält man eine Berechnung von Where- und Why-Provenance auf der Granularitätsebene einzelner Tabellenzellen.
Data provenance, SQL, program analysis
Wir stellen einen neuen Ansatz für die Analyse der Data
Provenance [
Die theoretische Anwendbarkeit auf beliebige Queries wird dadurch erreicht, dass wir Eingabequeries zuerst in eine imperative (Turing-vollständige) Programmiersprache überset1.1
2.
Im Folgenden werden zwei Beispiel-Queries und die Ergebnisse der mit unserer Implementierung durchgeführten Provenance-Analyse vorgestellt. Die erste Query greift ein Beispiel aus der Literatur auf und die zweite wurde gewählt, um die Mächtigkeit unseres Ansatzes zu demonstrieren. agencies
name based_in phone t1 BayTours San Francisco 415-1200 t2 HarborCruz Santa Cruz 831-3000 externaltours
name destination type t3 BayTours San Francisco cable car t4 BayTours Santa Cruz bus t5 BayTours Santa Cruz boat t6 BayTours Monterey boat t7 HarborCruz Monterey boat t8 HarborCruz Carmel train price $50 $100 $250 $400 $200 $90
mit ti bezeichnet.
SELECT e.name, a.phone FROM agencies AS a,
externaltours AS e WHERE a.name = e.name AND e.type = b’oat’ output
name phone HarborCruz 831-3000 BayTours 415-1200 BayTours 1 415-1200 2 (a) SFW-Query (b) Ergebnis
2.1
Diese Beispiel-Query stammt aus [
Zelle 1 ist hier als Where-abhängig von t5: BayTours markiert. Ein Blick auf die SQL-Query (SELECT e.name) bestätigt dieses Ergebnis: denn hier werden Werte aus der Eingabetabelle ins Resultat kopiert. Dies entspricht den Kriterien von Where-Provenance, wie wir sie in Abschnitt 1 angegeben haben.
Die Markierungen zeigen außerdem Why-Abhängigkeiten von t1: BayTours , t5: BayTours und t5: boat . Diese drei Werte werden im WHERE-Teil der SQL-Query für die Joinund Filterkriterien benutzt.
1 und 2 zeigen, dass die wertemäßig nicht unterscheidbaren BayTours und BayTours anhand ihrer jeweiligen Provenance (t5 oder t6) unterscheidbar werden.
3 veranschaulicht, dass Data Provenance entgegen der wörtlichen Bedeutung auch in Vorwärts-Richtung funktioniert. Die Farbmarkierungen besagen, dass t1: 415-1200 mit zwei Werten von der Ausgabetabelle auf Werteebene zusammenhängt. Konkret wird hier die Telefonnummer zwei Mal kopiert. 2.2
Die hier vorgestellte Provenance-Analyse einer rekursiven Query ist nach dem Wissen der Autoren mit keiner anderen existierenden Implementierung möglich. Die Query besteht auch aus einer Anzahl von Funktionsaufrufen. Interessante Ausschnitte des Ergebnisses unserer Provenance-Analyse werden erneut mit farbigen Markierungen dargestellt.
Abbildung 3(a) zeigt die Eingaberelationen. compounds enthält chemische Summenformeln und ihre Bezeichnungen. In Tabelle fsm ist ein endlicher Automat codiert, der die Syntax dieser Formeln überprüfen kann.
Die SQL-Query in Abbildung 3(b) führt diesen Automaten aus. Da alle Formeln in compounds parallel verarbeitet werden, existieren mehrere Automaten parallel. In jedem Schritt eines Automaten wird das erste Zeichen einer Formel abgeschnitten und der entsprechende Zustandsübergang durchgeführt. Aktueller Zustand und “Restformel” sind in der Tabelle run gespeichert, die bei jedem Schritt der Automaten neu berechnet wird. In Abbildung 3(c) sind zwei Versionen von run abgebildet: direkt nach der Initialisierung (step: 0) und nach drei Schritten (step: 3). Wenn die Formeln vollständig verzehrt sind, beendet sich der rekursive Teil der Query. Als Endresultat werden die Ableitungsschritte für citrate (siehe Abbildung 3(d)) zurückgegeben.
Die Where-Provenance von 4 zeigt an, von welchen Werten O73- abgeleitet wurde. Dazu zählt erst einmal die vollständige Summenformel t9: C6H5O73- . Aber auch alle Zwischenzustände werden von der Analyse erfasst, wie anhand der Markierungen in Abbildung 3(c) zu erkennen ist.
Die interessantesten Why-Abhängigkeiten von 4 sind innerhalb der Tupel t12 und t13 zu finden. Das sind nämlich gerade die Kanten des Automaten, die besucht wurden, um O73- abzuleiten. compounds compound t9 citrate t11 hydronium HC36HO1+2O6 t10 glucose formula
C6H5O73t12 t13 t14 t15 t16 t17 t18 fsm source 0 1 1 1 2 2 3
labels A..Za..z A..Za..z0..9 0..9 +0..9 +A..Za..z target final 1 false 1 true 2 true 3 true 2 false 3 false 1 true
WITH RECURSIVE run(compound, step, state, formula) AS (
SELECT compound, 0, 0, formula FROM compounds UNION ALL SELECT this.compound, this.step + 1 AS step, edge.target AS state, right(this.formula, -1) AS formula FROM run AS this,
fsm AS edge WHERE length(this.formula) > 0 AND this.state = edge.source AND strpos(edge.labels,
left(this.formula, 1)) > 0 ) SELECT r.step, r.state, r.formula FROM run AS r WHERE r.compound = c’itrate’ run compound step state formula citrate 0 0 C6H5O73glucose 0 50 C6H12O6 hydronium 0 0 H3O+ . .
.
run compound step state formula citrate 3 1 5O73glucose 3 1 12O6 hydronium 3 1 + output step state formula 0 0 C6H5O731 1 6H5O732 1 H5O733 1 5O734 1 O735 1 73- 4 6 1 37 2 8 3 1 def query(agencies , externaltours ): 2 #FROM clause: read source tables 3 rows = [] 4 for tupVar2 in agencies: 5 for tupVar3 in externaltours: 6 rs = {"tupVar2": tupVar2 , 7 "tupVar3": tupVar3 , 8 "tmp": {}, 9 } 10 rows.append(rs) 11 #WHERE clause: compute where predicate 12 rowIdx = 0 13 while rowIdx < len(rows): 14 rs = rows[rowIdx] 15 col4 = rs["tupVar2"]["name"] 16 col5 = rs["tupVar3"]["name"] 17 res6 = col4 == col5 18 col7 = rs["tupVar3"]["type"] 19 val8 = "boat" 20 res9 = col7 == val8 21 res10 = res6 and res9 22 rs["tmp"]["where"] = res10 23 rowIdx = rowIdx + 1 24 #WHERE clause: apply where predicate 25 filtered = [] 26 for rs in rows: 27 if rs["tmp"]["where"]: 28 filtered.append(rs) 29 rows = filtered 30 #SELECT clause: compute result columns 31 rowIdx = 0 32 while rowIdx < len(rows): 33 rs = rows[rowIdx] 34 col11 = rs["tupVar3"]["name"] 35 col12 = rs["tupVar2"]["phone"] 36 rs["tmp"]["eval0"] = col11 37 rs["tmp"]["eval1"] = col12 38 rowIdx = rowIdx + 1 39 #SELECT clause: assemble result table 40 ship = [] 41 for rs in rows: 42 row = {} 43 row["name"] = rs["tmp"]["eval0"] 44 row["phone"] = rs["tmp"]["eval1"] 45 ship.append(row) 46 return ship
Zuletzt wird mit 5 noch die Einsicht transportiert, dass die Schrittzahl des Automaten keinerlei Einfluss auf die Ableitung von citrate hat. Die Markierungen zeigen lediglich eine Where-Provenance zwischen den Schritten 0 bis 8 an, die auf das Inkrementieren zurückzuführen ist. Es gibt keine Why-Provenance, das heißt keine (versehentliche) Beeinflussung des Endresultats durch die Schrittzählung.
Die zu analysierenden SQL-Queries werden in unserer Implementierung zunächst in Python-Programme übersetzt. Python hat als Zwischensprache den Vorteil, sehr leichtgewichtig und daher für die weitere Analyse gut zugänglich
zu sein. Es wird außerdem von Kooperationspartnern eingesetzt. Ein Nachteil von Python ist die schlechtere Performance (gegenüber Sprachen wie C). Es gibt jedoch keinen Hinderungsgrund, die mit Hilfe von Python erarbeiteten Techniken der Provenance-Analyse nicht auf andere Sprachen wie LLVM zu übertragen.
Damit würden wir einem aktuellen Forschungstrend in der
Datenbank-Community folgen, SQL nicht länger mit dem
Volcano-Iterator-Model zu implementieren, sondern Queries
just-in-time zu kompilieren (siehe [
Aus Platzgründen wird der von uns verwendete Übersetzer nur anhand eines Beispiels vorgestellt. Listing 1 zeigt, wie die Übersetzung von Query 2(a) aussieht. Je Query oder Sub-Query wird eine eigene Python-Funktion erzeugt. Die Argumente und Rückgabewerte sind Tabellen, die in Python als Listen von Dictionaries implementiert sind. Die SQL-Klauseln einer Query werden in eine Reihenfolge gebracht, die eine Berechnung im imperativen Paradigma erlaubt: SFW wird beispielsweise zu FWS.
Wie in Abbildung 4 dargestellt, teilt sich die ProvenanceAnalyse im Wesentlichen auf zwei Schritte auf: 1 Kontrollflussanalyse (dynamisch, zur Laufzeit) und 2 abstrakte Interpretation (statisch, zur Kompilierzeit).
Die Kontrollflussanalyse ist dafür zuständig, alle für den Kontrollfluss benötigten Prädikate zu bestimmen und deren Werte zu speichern. Beispielsweise würde bei der Ausführung einer if-Anweisung die zugehörige Kontrollflussinformation darin bestehen, ob entweder der if- oder der elseRumpf ausgeführt wird. Die Information kann durch einen einzelnen booleschen Wert codiert werden.
In Phase 2 findet die eigentliche Provenance-Analyse statt. Hier wird das Kontrollfluss-Log benutzt, um den tatsächlichen Ausführungspfad nachvollziehen zu können, den das Programm zur Laufzeit genommen hat.
In Abschnitt 4.1 wird die Motivation für die soeben skizzierte Struktur geschildert sowie ein Bezug zu Ergebnissen der theoretischen Informatik hergestellt, die einer Programmanalyse harte Grenzen setzt. Abschnitt 5 erläutert die beiden Analyseschritte genauer sowie deren Implementierung in Python.
Eine rein statische Provenance-Analyse ist im Allgemeinen für Python-Programme nicht möglich, denn Python ist eine Turing-vollständige Programmiersprache. Der Satz von Rice besagt, dass nicht-triviale Laufzeiteigenschaften (wie Data Provenance) für allgemeine Turing-Maschinen nicht algorithmisch entscheidbar sind.
Um den Konsequenzen des Satzes von Rice zu entgehen, ändert dieses Verfahren die Voraussetzungen. Wie in Abbildung 4 dargestellt, wird der zur Laufzeit aufgezeichnete Kontrollfluss an die abstrakte Interpretation übergeben. Zu Kontrollflussanweisungen zählen unter anderem if- und while-Anweisungen. Für diese Konstrukte besteht das zugehörige Kontrollfluss-Log lediglich aus einer Folge von booleschen Werten: • Wird entweder if oder else ausgeführt? • Wird der Rumpf von while (nochmal) ausgeführt oder wird die Schleife beendet?
Dieses Log steht also während der statischen Analyse zur Verfügung. Das heißt, die statische Analyse weiß für jedes if x:, ob es in Wirklichkeit entweder ein if True: oder if False: ist - je nachdem, ob True oder False im Log steht.
Mit dem Kontrollfluss-Log findet deshalb eine Linearisierung des Python-Programms statt. Die Abfolge der Anweisungen im Programm ist statisch festgelegt, weil der Kontrollfluss festgelegt ist. Kontrollfluss-Konstrukte verhalten sich nun transparent und im einfachsten Fall besteht die restliche Analyse des Programms nur noch darin, Zuweisungen an Variablen zu betrachten.
Dadurch liegt in 2 keine Turing-Vollständigkeit mehr vor. Der Satz von Rice gilt nicht mehr und eine ProvenanceAnalyse ist (quasi-statisch) möglich.
Das Beispiel in Abschnitt 5 wird das verdeutlichen. 4.2
Als Granularität (oder level of detail) wird in [
Orthogonal dazu wollen wir den Begriff Auflösung verwenden, um damit die Größe der Programmfragmente zu bezeichnen, für die am Ende der Analyse eine Data Provenane ausgegeben wird.
Beispielsweise könnte es in einer niedrigen Auflösung so sein, dass das Programm nur als Ganzes analysiert wird. Das heißt, die Data Provenance bezieht sich gerade auf die Ein/Ausgabedaten des Programms selbst und zeigt an, wie die Ausgabedaten von den Eingabedaten abhängig sind. Eine andere Variante bestünde darin, für jeden einzelnen Ausdruck in diesem Programm eine Data Provenance auszugeben. Das heißt, für einen Ausdruck wie b+c wird als Ergebnis die Abhängigkeit von den Einzelwerten b sowie c ausgegeben. Hier ist die Auflösung sehr hoch.
Von uns wurde als Auflösung die Ebene von Funktionsaufrufen benutzerdefinierter Funktionen gewählt. Im Ergebnis der Provenance-Analyse sind deshalb die Parameter und Rückgabewerte von Funktionsaufrufen aufgeführt sowie die dazugehörende Data Provenance.
Als Grundlage für die Implementierung der ProvenanceAnalyse dient CPython in Version 3.4. Dabei handelt es sich um die stabile und zum Zeitpunkt des Schreibens dieses Artikels aktuelle Referenzimplementation von Python. Intern übersetzt sie Quelltext in Bytecode, der anschließend in der zugehörigen virtuellen Maschine (VM) ausgeführt wird. Als Zwischenschritt während der Übersetzung erzeugt CPython einen Abstract Syntax Tree (AST), auf dessen Basis wir das Analyseverfahren implementiert haben.
In Abbildung 5 ist dargestellt, wie die einzelnen PythonKomponenten zusammenarbeiten. Mit weißem Hintergrund dargestellt sind die ein/ausgehenden Datensätze (Relationen) sowie der Python Programmcode, der analysiert wer
den soll. Grau hinterlegt sind Komponenten der CPythonImplementierung selbst, die unmodifiziert verwendet werden. In schwarz ist, was wir zusätzlich implementiert haben.
Während der Analyse wird das zu einem AST kompilierte Eingabeprogramm zwei Mal verarbeitet. In Schritt 1 wird es zunächst instrumentiert. Dabei werden zusätzliche Python-Anweisungen eingefügt, die einerseits die vorhandene Funktionalität nicht verändern und andererseits für das Schreiben des Kontrollfluss-Log zuständig sind. Das so modifizierte Programm wird zu Bytecode kompiliert und anschließend mit der VM ausgeführt. Während der Ausführung werden Eingabe/Ausgabedaten gelesen/geschrieben sowie das Kontrollfluss-Log produziert. Schritt 1 wird in Abschnitt 5.1 genauer beschrieben.
In Schritt 2 wird das unmodifizierte (nicht instrumentierte) Eingabeprogramm erneut hergenommen und mit Hilfe des Kontrollfluss-Logs die eigentliche Provenance-Analyse durchgeführt. Eine genaue Beschreibung dieses Teils folgt in Abschnitt 5.2. Bemerkenswert ist, dass hier keine Eingabedaten benötigt werden. Die abstrakte Interpretation findet auf symbolischer Ebene statt, das heißt es wird lediglich ermittelt, wie die im Programm benutzten Variablen voneinander abhängig sind. Dies genügt, um sowohl Why- als auch Where-Provenance zu berechnen. 5.1
Allgemein gesprochen müssen diejenigen Sprachkonstrukte instrumentiert werden, deren Verhalten bezüglich Data Provenance sich nicht durch rein statische Analyse bestimmen lässt. Bisher instrumentieren wir zwei Kategorien von Sprachkonstrukten: (i) Kontrollfluss und (ii) Indexzugriff.
Listing 2 zeigt ein bereits instrumentiertes Programmfragment, das je ein Beispiel für beide Fälle enthält. Die Funktion dow() erhält als Argumente den Wochentag als Zahlenwert (num = 0...6) und eine Liste mit Namen von Wochentagen. Sie liefert eine String-Repräsentation zurück. Sie unterstützt außerdem zwei verschiedene Datumsformate: Wochenbeginn am Montag (fmt = True) oder am Sonntag (fmt = False). 6
Nachdem die Kontrollfluss-Logs erzeugt worden sind, kann jetzt die eigentliche Ableitung der Data Provenance stattfinden. Dazu werden wie in Abbildung 5 dargestellt, lediglich das Eingabeprogramm zusammen mit den Logs verwendet. Daten sind an dieser Phase nicht beteiligt. Dementsprechend werden auch keine Berechnungen von Werten ausgeführt, was Systemressourcen spart.
Die abstrakte Interpretation wird durchgeführt, indem alle Anweisungen des Programms in derselben Reihenfolge nachvollzogen werden, in der sie auch zur Laufzeit ausgeführt wurden. Die richtige Reihenfolge einzuhalten ist dank des aufgezeichneten Kontrollflusses sehr einfach. Immer dann, wenn eine Kontrollflussentscheidung benötigt wird (zum Beispiel: if- oder else-Block ausführen), kann diese Information im Kontrollfluss-Log nachgeschlagen werden.
Where-Provenance.
Während die Anweisungen nacheinander interpretiert wer1 days = [(),(),() , 2 () ,() ,() ,()] 3 def dow(num , fmt , days ): 4 if fmt: #fmt: True 5 pos = (num +()) % () 6 else: 7 pos = num 8 res = days[pos] #pos: 5 9 return res 10 dow((), (), days) #returns: ()
den, wird eine Variablenumgebung gepflegt und mit jeder interpretierten Anweisung gegebenenfalls aktualisiert. Die Umgebung beinhaltet alle derzeit sichtbaren Variablen zusammen mit ihren jeweiligen Abhängigkeiten von den Eingabedaten.
Der Aufbau dieser Umgebung ist ein inkrementeller Prozess. Jede Zuweisung einer Variablen, wie zum Beispiel in a = b, wird eine entsprechende Aktualisierung der Umgebung nach sich ziehen. In diesem Beispiel müssten alle Abhängigkeiten von b nach a kopiert werden.
Auf diese Weise wird die Umgebung ständig aktuell gehalten und referenziert in ihren Abhängigkeiten stets die Eingabedaten. Am Ende der Analyse braucht nur noch die gewünschte Variable, zum Beispiel res, in der Umgebung nachgeschlagen zu werden.
Why-Provenance.
Die Ausführung von Anweisungen in einem if- oder elseRumpf sind abhängig vom zugehörigen Prädikat des if/elseKonstrukts. Diese Abhängigkeit modellieren wir als WhyProvenance.
In der Analyse wird dazu eine Menge an Abhängigkeiten gepflegt, die dem Kontrollfluss selbst zugeordnet ist. Bei Eintritt in den Rumpf einer if-Anweisung wird dem Kontrollfluss eine Abhängigkeit vom Prädikat dieser if-Anweisung zugeordnet. Allen Zuweisungen, die in diesem Rumpf ausgeführt werden, werden dann wiederum die Abhängigkeiten des Kontrollflusses in Form von Why-Provenance hinzugefügt.
Nachdem der if-Rumpf abgearbeitet ist, werden die Abhängigkeiten des Kontrollflusses wieder zurückgesetzt. Ob if- oder else-Rumpf ausgeführt werden, macht hier keinen Unterschied: in beiden Fällen gilt dasselbe Prädikat. Die Interpretation von Schleifen funktioniert analog.
Beispiel-Analyse.
In Listing 3 ist abgedruckt, wie sich das aus dem Instrumentierungsschritt bereits bekannte Programmfragment in Schritt 2 der Provenance-Analyse darstellen würde. Alle vorkommenden atomaren Werte sind durch () ersetzt worden. Code in dieser Form wird nicht erzeugt, doch das Listing veranschaulicht, auf welcher Basis die abstrakte Interpretation arbeitet.
Anhand dieses Beispiels wird nun dargestellt, wie die Ableitung der Data Provenance funktioniert. Das Ergebnis dieser Analyse besteht gemäß der gewählten Granularität und Auflösung (siehe Abschnitt 4.2) darin, wie die Variable res von den Funktionsparametern abhängig ist.
Um die Analyse zu initialisieren, werden die in den Funk
3 (dow()) num: 7e fmt: 8e 4 (if fmt:) 8y num: 7e fmt: 8e 5 (pos=) 8y num: 7e fmt: 8e pos: 8y, 7e 8 (res=) num: 7e fmt: 8e pos: 8y, 7e res: 8y, 7y, 5e
Wir versprechen uns eine Performanceverbesserung von dieser neuen Implementierung.
Als weitere Implementierung ist LLVM geplant, um
mittels [
Habitat [