Where- und Why-Provenance für syntaktisch reiches SQL durch Kombination von Programmanalysetechniken Tobias Müller Universität Tübingen Tübingen, Deutschland to.mueller@uni-tuebingen.de ABSTRACT zen, das resultierende Programm in eine linearisierte Form Das hier vorgestellte Verfahren ermöglicht die Analyse der (erläutert in Abschnitt 4) umwandeln und anschließend die Data Provenance von beliebigen SQL-Queries. Von der eben- eigentliche Provenance-Analyse durchführen. Dieser von uns falls hier skizzierten Implementierung des Verfahrens wer- entwickelte Ansatz basiert auf dem Prinzip des Program Sli- den unter anderem unterstützt: Subqueries, Aggregierun- cing [10, 3]. gen, rekursive Queries und Window Functions. Eingabeque- Von bisherigen Arbeiten wurde sukzessive der Umfang der ries werden zunächst in eine imperative Programmiersprache analysierbaren SQL-Konstrukte erweitert. Dazu zählen bei- übersetzt. Der Programmcode wird mit einem neuen Verfah- spielsweise geschachtelte Subqueries [6] sowie Aggregierun- ren analysiert, das auf bekannte Techniken aus dem Bereich gen [1]. Mit der in der vorliegenden Arbeit vorgestellten Im- der Programmanalyse aufbaut: Program Slicing, Kontroll- plementierung ist eine Analyse dieser Konstrukte ebenfalls flussanalyse und abstrakte Interpretation. Dadurch erhält möglich. Nach dem Wissensstand der Autoren erlaubt unse- man eine Berechnung von Where- und Why-Provenance auf re Implementierung erstmalig auch die Analyse von Window der Granularitätsebene einzelner Tabellenzellen. Functions und rekursiven Queries. 1.1 Data Provenance Categories and Subject Descriptors Das allgemeine Ziel der Berechnung von Data Provenance F.3.2 [Logics and Meanings of Programs]: Semanti- ist es, den Ursprung und die zurückgelegten Verarbeitungs- cs of Programming Languages—Program analysis; H.2.3 schritte des Resultats von Datenverarbeitung sichtbar zu [Database Management]: Languages—Query Languages; machen. Auf dem Gebiet der relationalen Datenbanken ha- H.2.4 [Database Management]: Systems—Relational Da- ben wir uns konkret mit der Frage beschäftigt, auf welchen tabases Ursprungsdaten (hier: Tabellenzellen) genau das Ergebnis einer SQL-Query beruht. General Terms Seit [2] unterscheidet die wissenschaftliche Literatur zwei Arten von Provenance: Languages • Where-Provenance charakterisiert sowohl eine direkte Abhängigkeit von Werten durch Kopieren sowie zum Keywords Beispiel auch bei Aggregierungen, in denen viele Werte Data provenance, SQL, program analysis zu einem zusammengefasst werden. • Why-Provenance charakterisiert Abhängigkeiten durch Kontrollflussentscheidungen. Diese liegen zum Beispiel 1. EINFÜHRUNG vor, wenn die Existenz eines (Teil-)Ergebnisses von ei- Wir stellen einen neuen Ansatz für die Analyse der Data nem anderen Wert abhängig ist, der als Filterkriterium Provenance [5] von SQL-Queries vor sowie eine prototypi- dient (= Semantik einer WHERE-Klausel in SQL). sche Implementierung davon. Der hier präsentierte Ansatz Basierend auf dem hier vorgestellten Ansatz sowie mit un- erlaubt eine Analyse beliebiger (lesender) SQL-Queries. Die serer prototypischen Implementierung können beide Arten algebraische Ebene wird nicht berührt, wodurch auch keine von Provenance berechnet werden. algebraischen Restriktionen auftreten. Zum Beispiel ist [1] In Abschnitt 2 werden Beispiel-Queries und deren Analy- eingeschränkt auf eine positive relationale Algebra. seergebnisse vorgestellt. Die Abschnitte 3 bis 4 erläutern die Die theoretische Anwendbarkeit auf beliebige Queries wird Grundzüge des Analyseverfahrens. In Abschnitt 5 beschrei- dadurch erreicht, dass wir Eingabequeries zuerst in eine im- ben wir eine konkrete Implementierung. Aus Platzgründen perative (Turing-vollständige) Programmiersprache überset- ist nur eine verkürzte Darstellung möglich. 2. BEISPIEL-QUERIES Im Folgenden werden zwei Beispiel-Queries und die Er- gebnisse der mit unserer Implementierung durchgeführten Provenance-Analyse vorgestellt. Die erste Query greift ein 27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. Beispiel aus der Literatur auf und die zweite wurde gewählt, Copyright is held by the author/owner(s). um die Mächtigkeit unseres Ansatzes zu demonstrieren. 84 agencies 1 und 2 zeigen, dass die wertemäßig nicht unterscheid- name based_in phone baren BayTours und BayTours anhand ihrer jeweiligen t1 BayTours San Francisco 415-1200 Provenance (t5 oder t6 ) unterscheidbar werden. t2 HarborCruz Santa Cruz 831-3000 3 3 veranschaulicht, dass Data Provenance entgegen der externaltours wörtlichen Bedeutung auch in Vorwärts-Richtung funktio- name destination type price niert. Die Farbmarkierungen besagen, dass t1 : 415-1200 t3 BayTours San Francisco cable car $50 mit zwei Werten von der Ausgabetabelle auf Werteebene t4 BayTours Santa Cruz bus $100 zusammenhängt. Konkret wird hier die Telefonnummer zwei t5 BayTours Santa Cruz boat $250 t6 BayTours Monterey boat $400 Mal kopiert. t7 HarborCruz Monterey boat $200 HarborCruz Carmel train $90 t8 2.2 Endlicher Automat Abbildung 1: Bootstouren-Beispiel: Where- und Die hier vorgestellte Provenance-Analyse einer rekursiven Why-Provenance sind markiert mit sowie . Query ist nach dem Wissen der Autoren mit keiner anderen Falls beides zutrifft, wird verwendet. Tupel sind existierenden Implementierung möglich. Die Query besteht mit ti bezeichnet. auch aus einer Anzahl von Funktionsaufrufen. Interessan- output te Ausschnitte des Ergebnisses unserer Provenance-Analyse SELECT e.name, a.phone name phone werden erneut mit farbigen Markierungen dargestellt. FROM agencies AS a, HarborCruz 831-3000 Abbildung 3(a) zeigt die Eingaberelationen. compounds externaltours AS e BayTours 415-1200 enthält chemische Summenformeln und ihre Bezeichnungen. WHERE a.name = e.name BayTours 1 415-1200 AND e.type = ’boat’ In Tabelle fsm ist ein endlicher Automat codiert, der die 2 Syntax dieser Formeln überprüfen kann. (a) SFW-Query (b) Ergebnis Die SQL-Query in Abbildung 3(b) führt diesen Automa- Abbildung 2: Welche Agenturen bieten Bootstouren ten aus. Da alle Formeln in compounds parallel verarbeitet an? werden, existieren mehrere Automaten parallel. In jedem Schritt eines Automaten wird das erste Zeichen einer For- 2.1 Bootstouren mel abgeschnitten und der entsprechende Zustandsübergang Diese Beispiel-Query stammt aus [4] und reproduziert die durchgeführt. Aktueller Zustand und “Restformel” sind in dort gefundene Data Provenance. In Abbildung 1 sind die der Tabelle run gespeichert, die bei jedem Schritt der Au- Eingabetabellen dargestellt: agencies enthält Stammdaten tomaten neu berechnet wird. In Abbildung 3(c) sind zwei von Reiseveranstaltern und externaltours enthält deren Versionen von run abgebildet: direkt nach der Initialisie- angebotene Touren. Die Query in Abbildung 2(a) findet die- rung (step: 0) und nach drei Schritten (step: 3). Wenn die jenigen Veranstalter, die Bootstouren im Angebot haben. Formeln vollständig verzehrt sind, beendet sich der rekursive Die Ausgaberelation steht in Abbildung 2(b). Teil der Query. Als Endresultat werden die Ableitungsschrit- Zelle 1 ist hier als Where-abhängig von t5 : BayTours te für citrate (siehe Abbildung 3(d)) zurückgegeben. markiert. Ein Blick auf die SQL-Query (SELECT e.name) Die Where-Provenance von 4 zeigt an, von welchen Wer- bestätigt dieses Ergebnis: denn hier werden Werte aus der ten O7 3- abgeleitet wurde. Dazu zählt erst einmal die voll- Eingabetabelle ins Resultat kopiert. Dies entspricht den Kri- ständige Summenformel t9 : C6 H5 O7 3- . Aber auch alle Zwi- terien von Where-Provenance, wie wir sie in Abschnitt 1 schenzustände werden von der Analyse erfasst, wie anhand angegeben haben. der Markierungen in Abbildung 3(c) zu erkennen ist. Die Markierungen zeigen außerdem Why-Abhängigkeiten Die interessantesten Why-Abhängigkeiten von 4 sind in- von t1 : BayTours , t5 : BayTours und t5 : boat . Diese drei nerhalb der Tupel t12 und t13 zu finden. Das sind nämlich Werte werden im WHERE-Teil der SQL-Query für die Join- gerade die Kanten des Automaten, die besucht wurden, um und Filterkriterien benutzt. O7 3- abzuleiten. WITH RECURSIVE run(compound, step, state, formula) AS ( SELECT compound, 0, 0, formula FROM compounds compounds UNION ALL compound formula SELECT this.compound, run t9 citrate C6 H5 O7 3- this.step + 1 AS step, compound step state formula edge.target AS state, citrate 0 0 C6 H5 O7 3- output t10 glucose C6 H12 O6 right(this.formula, -1) AS formula t11 hydronium H3 O+ FROM run AS this, glucose 0 50 C6 H12 O6 step state formula fsm AS edge hydronium 0 0 H3 O+ 0 0 C6 H5 O7 3- fsm WHERE length(this.formula) > 0 1 1 6 H5 O7 3- source labels target final AND this.state = edge.source .. 2 1 H5 O7 3- t12 0 A..Za..z 1 false AND strpos(edge.labels, . 3 1 5 O7 3- t13 1 A..Za..z 0.. 9 1 true left(this.formula, 1)) > 0 run 4 1 O7 3- t14 1 0.. 9 2 true ) compound step state formula 5 1 7 3- 4 t15 1 +- 3 true SELECT r.step, r.state, r.formula 3- 3- t16 2 0.. 9 2 false citrate 3 1 5 O7 6 1 FROM run AS r - t17 2 +- 3 false WHERE r.compound = ’citrate’ glucose 3 1 12 O6 7 2 hydronium 3 1 + 8 3 t18 3 A..Za..z 1 true (a) Eingabetabellen (b) Rekursive Query (c) Zwischenergebnisse (d) Ergebnis Abbildung 3: Endlicher Automat, der die Syntax von chemischen Summenformeln überprüft. 85 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 , Abbildung 4: Hauptelemente der Provenance- 7 " tupVar3 ": tupVar3 , Analyse 8 "tmp": {}, 9 } zu sein. Es wird außerdem von Kooperationspartnern einge- 10 rows. append (rs) setzt. Ein Nachteil von Python ist die schlechtere Performan- 11 #WHERE clause : compute where predicate ce (gegenüber Sprachen wie C). Es gibt jedoch keinen Hinde- 12 rowIdx = 0 rungsgrund, die mit Hilfe von Python erarbeiteten Techni- 13 while rowIdx < len(rows ): ken der Provenance-Analyse nicht auf andere Sprachen wie 14 rs = rows[ rowIdx ] LLVM zu übertragen. 15 col4 = rs[" tupVar2 "]["name"] Damit würden wir einem aktuellen Forschungstrend in der 16 col5 = rs[" tupVar3 "]["name"] Datenbank-Community folgen, SQL nicht länger mit dem 17 res6 = col4 == col5 Volcano-Iterator-Model zu implementieren, sondern Queries 18 col7 = rs[" tupVar3 "]["type"] just-in-time zu kompilieren (siehe [9]). 19 val8 = "boat" Aus Platzgründen wird der von uns verwendete Überset- 20 res9 = col7 == val8 zer nur anhand eines Beispiels vorgestellt. Listing 1 zeigt, 21 res10 = res6 and res9 wie die Übersetzung von Query 2(a) aussieht. Je Query oder 22 rs["tmp"][" where "] = res10 Sub-Query wird eine eigene Python-Funktion erzeugt. Die 23 rowIdx = rowIdx + 1 Argumente und Rückgabewerte sind Tabellen, die in Py- 24 # WHERE clause : apply where predicate thon als Listen von Dictionaries implementiert sind. Die 25 filtered = [] SQL-Klauseln einer Query werden in eine Reihenfolge ge- 26 for rs in rows: bracht, die eine Berechnung im imperativen Paradigma er- 27 if rs["tmp"][" where "]: laubt: SFW wird beispielsweise zu FWS. 28 filtered . append (rs) 29 rows = filtered 4. PROVENANCE-ANALYSE 30 # SELECT clause : compute result columns IN ZWEI STUFEN 31 rowIdx = 0 Wie in Abbildung 4 dargestellt, teilt sich die Provenance- 32 while rowIdx < len(rows ): Analyse im Wesentlichen auf zwei Schritte auf: 1 Kontroll- 33 rs = rows[ rowIdx ] flussanalyse (dynamisch, zur Laufzeit) und 2 abstrakte In- 34 col11 = rs[" tupVar3 "]["name"] terpretation (statisch, zur Kompilierzeit). 35 col12 = rs[" tupVar2 "][" phone "] Die Kontrollflussanalyse ist dafür zuständig, alle für den 36 rs["tmp"][" eval0 "] = col11 Kontrollfluss benötigten Prädikate zu bestimmen und deren 37 rs["tmp"][" eval1 "] = col12 Werte zu speichern. Beispielsweise würde bei der Ausfüh- 38 rowIdx = rowIdx + 1 rung einer if-Anweisung die zugehörige Kontrollflussinfor- 39 # SELECT clause : assemble result table mation darin bestehen, ob entweder der if- oder der else- 40 ship = [] Rumpf ausgeführt wird. Die Information kann durch einen 41 for rs in rows: einzelnen booleschen Wert codiert werden. 42 row = {} In Phase 2 findet die eigentliche Provenance-Analyse 43 row["name"] = rs["tmp"][" eval0 "] statt. Hier wird das Kontrollfluss-Log benutzt, um den tat- 44 row[" phone "] = rs["tmp"][" eval1 "] sächlichen Ausführungspfad nachvollziehen zu können, den 45 ship. append (row) das Programm zur Laufzeit genommen hat. 46 return ship In Abschnitt 4.1 wird die Motivation für die soeben skiz- Listing 1: Übersetzung der Bootstouren-Query. Es zierte Struktur geschildert sowie ein Bezug zu Ergebnissen findet (noch) keine Code-Optimierung statt. der theoretischen Informatik hergestellt, die einer Program- manalyse harte Grenzen setzt. Abschnitt 5 erläutert die bei- Zuletzt wird mit 5 noch die Einsicht transportiert, dass den Analyseschritte genauer sowie deren Implementierung in die Schrittzahl des Automaten keinerlei Einfluss auf die Ab- Python. leitung von citrate hat. Die Markierungen zeigen lediglich eine Where-Provenance zwischen den Schritten 0 bis 8 4.1 Linearisierung an, die auf das Inkrementieren zurückzuführen ist. Es gibt Eine rein statische Provenance-Analyse ist im Allgemei- keine Why-Provenance, das heißt keine (versehentliche) Be- nen für Python-Programme nicht möglich, denn Python ist einflussung des Endresultats durch die Schrittzählung. eine Turing-vollständige Programmiersprache. Der Satz von Rice besagt, dass nicht-triviale Laufzeiteigenschaften (wie Data Provenance) für allgemeine Turing-Maschinen nicht al- 3. SQL-ÜBERSETZUNG gorithmisch entscheidbar sind. Die zu analysierenden SQL-Queries werden in unserer Im- Um den Konsequenzen des Satzes von Rice zu entgehen, plementierung zunächst in Python-Programme übersetzt. ändert dieses Verfahren die Voraussetzungen. Wie in Ab- Python hat als Zwischensprache den Vorteil, sehr leichtge- bildung 4 dargestellt, wird der zur Laufzeit aufgezeichne- wichtig und daher für die weitere Analyse gut zugänglich te Kontrollfluss an die abstrakte Interpretation übergeben. 86 Zu Kontrollflussanweisungen zählen unter anderem if- und while-Anweisungen. Für diese Konstrukte besteht das zuge- hörige Kontrollfluss-Log lediglich aus einer Folge von boole- schen 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 je- des 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 Linearisie- rung des Python-Programms statt. Die Abfolge der Anwei- sungen im Programm ist statisch festgelegt, weil der Kon- trollfluss festgelegt ist. Kontrollfluss-Konstrukte verhalten sich nun transparent und im einfachsten Fall besteht die restliche Analyse des Programms nur noch darin, Zuweisun- gen an Variablen zu betrachten. Dadurch liegt in 2 keine Turing-Vollständigkeit mehr vor. Der Satz von Rice gilt nicht mehr und eine Provenance- Analyse ist (quasi-statisch) möglich. Das Beispiel in Abschnitt 5 wird das verdeutlichen. Abbildung 5: Komponenten der Python- 4.2 Granularität und Auflösung Implementierung Als Granularität (oder level of detail) wird in [7] bezeich- den soll. Grau hinterlegt sind Komponenten der CPython- net, was die kleinstmöglichen Datenstrukturen sind, die in Implementierung selbst, die unmodifiziert verwendet wer- einer Provenance-Analyse berücksichtigt werden. Meist sind den. In schwarz ist, was wir zusätzlich implementiert haben. das entweder Tupel oder Tabellenzellen. In dem hier bespro- Während der Analyse wird das zu einem AST kompilier- chenen Ansatz besteht die Granularität in Zellen. te Eingabeprogramm zwei Mal verarbeitet. In Schritt 1 Orthogonal dazu wollen wir den Begriff Auflösung ver- wird es zunächst instrumentiert. Dabei werden zusätzliche wenden, um damit die Größe der Programmfragmente zu Python-Anweisungen eingefügt, die einerseits die vorhan- bezeichnen, für die am Ende der Analyse eine Data Pro- dene Funktionalität nicht verändern und andererseits für venane ausgegeben wird. das Schreiben des Kontrollfluss-Log zuständig sind. Das so Beispielsweise könnte es in einer niedrigen Auflösung so modifizierte Programm wird zu Bytecode kompiliert und sein, dass das Programm nur als Ganzes analysiert wird. anschließend mit der VM ausgeführt. Während der Aus- Das heißt, die Data Provenance bezieht sich gerade auf die führung werden Eingabe/Ausgabedaten gelesen/geschrieben Ein/Ausgabedaten des Programms selbst und zeigt an, wie sowie das Kontrollfluss-Log produziert. Schritt 1 wird in die Ausgabedaten von den Eingabedaten abhängig sind. Ei- Abschnitt 5.1 genauer beschrieben. ne andere Variante bestünde darin, für jeden einzelnen Aus- In Schritt 2 wird das unmodifizierte (nicht instrumen- druck in diesem Programm eine Data Provenance auszuge- tierte) Eingabeprogramm erneut hergenommen und mit Hil- ben. Das heißt, für einen Ausdruck wie b+c wird als Ergebnis fe des Kontrollfluss-Logs die eigentliche Provenance-Analyse die Abhängigkeit von den Einzelwerten b sowie c ausgege- durchgeführt. Eine genaue Beschreibung dieses Teils folgt in ben. Hier ist die Auflösung sehr hoch. Abschnitt 5.2. Bemerkenswert ist, dass hier keine Eingabe- Von uns wurde als Auflösung die Ebene von Funktions- daten benötigt werden. Die abstrakte Interpretation findet aufrufen benutzerdefinierter Funktionen gewählt. Im Ergeb- auf symbolischer Ebene statt, das heißt es wird lediglich nis der Provenance-Analyse sind deshalb die Parameter und ermittelt, wie die im Programm benutzten Variablen von- Rückgabewerte von Funktionsaufrufen aufgeführt sowie die einander abhängig sind. Dies genügt, um sowohl Why- als dazugehörende Data Provenance. auch Where-Provenance zu berechnen. 5. IMPLEMENTIERUNG 5.1 Instrumentierung Als Grundlage für die Implementierung der Provenance- Allgemein gesprochen müssen diejenigen Sprachkonstruk- Analyse dient CPython in Version 3.4. Dabei handelt es sich te instrumentiert werden, deren Verhalten bezüglich Data um die stabile und zum Zeitpunkt des Schreibens dieses Ar- Provenance sich nicht durch rein statische Analyse bestim- tikels aktuelle Referenzimplementation von Python. Intern men lässt. Bisher instrumentieren wir zwei Kategorien von übersetzt sie Quelltext in Bytecode, der anschließend in der Sprachkonstrukten: (i) Kontrollfluss und (ii) Indexzugriff. zugehörigen virtuellen Maschine (VM) ausgeführt wird. Als Listing 2 zeigt ein bereits instrumentiertes Programm- Zwischenschritt während der Übersetzung erzeugt CPython fragment, das je ein Beispiel für beide Fälle enthält. Die einen Abstract Syntax Tree (AST), auf dessen Basis wir das Funktion dow() erhält als Argumente den Wochentag als Analyseverfahren implementiert haben. Zahlenwert (num = 0...6) und eine Liste mit Namen von In Abbildung 5 ist dargestellt, wie die einzelnen Python- Wochentagen. Sie liefert eine String-Repräsentation zurück. Komponenten zusammenarbeiten. Mit weißem Hintergrund Sie unterstützt außerdem zwei verschiedene Datumsforma- dargestellt sind die ein/ausgehenden Datensätze (Relatio- te: Wochenbeginn am Montag (fmt = True) oder am Sonntag nen) sowie der Python Programmcode, der analysiert wer- (fmt = False). 87 1 days = ["Sun","Mon","Tue", 1 days = [() ,() ,() , 2 "Wed","Thu","Fri","Sat"] 2 () ,() ,() ,()] 3 def dow(num , fmt , days ): 3 def dow(num , fmt , days ): 4 if fmt: 4 if fmt: #fmt: True 5 #true: week starts on Monday 5 pos = (num +()) % () 6 logCtrl(True) 6 else: 7 pos = num 7 pos = (num +1) % 7 8 res = days[pos] #pos: 5 8 else: 9 # false : week starts on Sunday 9 return res 10 dow ((), (), days) # returns : () 10 logCtrl(False) 11 pos = num Listing 3: Pseudocode aus Sicht der abstrakten 12 logIdx(pos) Interpretation. 13 res = days[pos] 14 return res den, wird eine Variablenumgebung gepflegt und mit jeder 15 dow (4, True , days) # returns : "Fri" interpretierten Anweisung gegebenenfalls aktualisiert. Die Listing 2: Beispiel für instrumentierten Pro- Umgebung beinhaltet alle derzeit sichtbaren Variablen zu- grammcode. Die Instrumentierungsanweisungen sammen mit ihren jeweiligen Abhängigkeiten von den Ein- gabedaten. sind umrandet . Der Aufbau dieser Umgebung ist ein inkrementeller Pro- Die beiden instrumentierten Anweisungen sind: (i) das zess. Jede Zuweisung einer Variablen, wie zum Beispiel in if/else-Statement und (ii) der Ausdruck days[pos] (Zeile a = b, wird eine entsprechende Aktualisierung der Umge- 13). An beiden Stellen wäre eine rein statische Analyse nicht bung nach sich ziehen. In diesem Beispiel müssten alle Ab- ausreichend. Bei (i) ist nicht bekannt, welcher Rumpf über- hängigkeiten von b nach a kopiert werden. haupt ausgeführt wird und bei (ii) ist unbekannt, auf welches Auf diese Weise wird die Umgebung ständig aktuell ge- Listenelement von days zugegriffen wird. halten und referenziert in ihren Abhängigkeiten stets die Im Gegenzug ist die Data Provenance einer Anweisung wie Eingabedaten. Am Ende der Analyse braucht nur noch die zum Beispiel pos = (num+1) % 7 schon bei statischer Analyse gewünschte Variable, zum Beispiel res, in der Umgebung klar: der Wert von pos ist Where-abhängig von num. In diesem nachgeschlagen zu werden. Fall ist keine Instrumentierung erforderlich. Wird dow() mit den Parametern von Zeile 15 aufgerufen, Why-Provenance. werden folgende Logs produziert: Die Ausführung von Anweisungen in einem if- oder else- • Kontrollfluss: [True] Rumpf sind abhängig vom zugehörigen Prädikat des if/else- • Indices: [5] Konstrukts. Diese Abhängigkeit modellieren wir als Why- In diesem bewusst kurz gehaltenem Beispiel bestehen bei- Provenance. de Logs aus jeweils nur einem Element. Für längere Pro- In der Analyse wird dazu eine Menge an Abhängigkeiten gramme würden weitere Einträge einfach in der Reihenfolge gepflegt, die dem Kontrollfluss selbst zugeordnet ist. Bei Ein- hinzugefügt, in der die Instrumentierungsanweisungen auf- tritt in den Rumpf einer if-Anweisung wird dem Kontroll- gerufen werden. In Schritt 2 werden die Einträge in ge- fluss eine Abhängigkeit vom Prädikat dieser if-Anweisung nau derselben Reihenfolge wieder gelesen. Deshalb braucht zugeordnet. Allen Zuweisungen, die in diesem Rumpf aus- das Log nur sequenziell zu sein. Die Zuordnung eines Log- geführt werden, werden dann wiederum die Abhängigkeiten Eintrags zur zugehörigen Anweisung im analysierten Pro- des Kontrollflusses in Form von Why-Provenance hinzuge- gramm ist implizit gegeben. fügt. Nachdem der if-Rumpf abgearbeitet ist, werden die Ab- 5.2 Abstrakte Interpretation hängigkeiten des Kontrollflusses wieder zurückgesetzt. Ob Nachdem die Kontrollfluss-Logs erzeugt worden sind, kann if- oder else-Rumpf ausgeführt werden, macht hier keinen jetzt die eigentliche Ableitung der Data Provenance stattfin- Unterschied: in beiden Fällen gilt dasselbe Prädikat. Die In- den. Dazu werden wie in Abbildung 5 dargestellt, lediglich terpretation von Schleifen funktioniert analog. das Eingabeprogramm zusammen mit den Logs verwendet. Daten sind an dieser Phase nicht beteiligt. Dementsprechend Beispiel-Analyse. werden auch keine Berechnungen von Werten ausgeführt, In Listing 3 ist abgedruckt, wie sich das aus dem Instru- was Systemressourcen spart. mentierungsschritt bereits bekannte Programmfragment in Die abstrakte Interpretation wird durchgeführt, indem alle Schritt 2 der Provenance-Analyse darstellen würde. Alle Anweisungen des Programms in derselben Reihenfolge nach- vorkommenden atomaren Werte sind durch () ersetzt wor- vollzogen werden, in der sie auch zur Laufzeit ausgeführt den. Code in dieser Form wird nicht erzeugt, doch das Lis- wurden. Die richtige Reihenfolge einzuhalten ist dank des ting veranschaulicht, auf welcher Basis die abstrakte Inter- aufgezeichneten Kontrollflusses sehr einfach. Immer dann, pretation arbeitet. wenn eine Kontrollflussentscheidung benötigt wird (zum Bei- Anhand dieses Beispiels wird nun dargestellt, wie die Ab- spiel: if- oder else-Block ausführen), kann diese Information leitung der Data Provenance funktioniert. Das Ergebnis die- im Kontrollfluss-Log nachgeschlagen werden. ser Analyse besteht gemäß der gewählten Granularität und Auflösung (siehe Abschnitt 4.2) darin, wie die Variable res Where-Provenance. von den Funktionsparametern abhängig ist. Während die Anweisungen nacheinander interpretiert wer- Um die Analyse zu initialisieren, werden die in den Funk- 88 days: [0e , 1e , 2e , 3e , 4e , 5e , 6e ] Abhängigkeiten num: 7e Zeile Kontrollfluss Variablen fmt: 8e Abbildung 6: Initialisierung 3 (dow()) num: 7e fmt: 8e tionsparametern vorkommenden Werte durch künstliche ids 4 (if fmt:) 8y num: 7e repräsentiert. Abbildung 6 zeigt die im Beispiel gewählte fmt: 8e Repräsentation, die aus ansteigenden natürlichen Zahlen be- 5 (pos=) 8y num: 7e steht. Die Variable days ist eine Liste und enthält dement- fmt: 8e sprechend für jedes Listenelement einen anderen Repräsen- pos: 8y , 7e tanten. Das tiefgestellte e soll anzeigen, dass eine Where- 8 (res=) num: 7e Abhängigkeit besteht (= Abhängigkeit vom Wert an die- fmt: 8e ser Stelle). Why-Abhängigkeiten kommen später hinzu und pos: 8y , 7e werden entsprechend durch y gekennzeichnet. res: 8y , 7y , 5e Diese Repräsentanten ersetzen während der abstrakten In- Tabelle 1: Ableitung der Provenance terpretation die tatsächlichen Werte. Am Ende der Analyse von dow() wird die Variable res nicht mit dem Wert "Fri" Wir versprechen uns eine Performanceverbesserung von die- belegt sein, sondern mit einer Menge von Repräsentanten. ser neuen Implementierung. In Tabelle 1 sind die einzelnen Analyseschritte der ab- Als weitere Implementierung ist LLVM geplant, um mit- strakten Interpretation aufgeführt. In der ersten Spalte steht tels [9] kompilierte Queries analysieren zu können. die Zeilennummer des Python-Statements, das soeben inter- Habitat [8] ist ein SQL-Debugger, der eingesetzt wird, um pretiert wurde. Die mittlere Spalte enthält die Abhängigkei- potentiell fehlerhafte Queries direkt auf SQL-Sprachebene ten des Kontrollflusses. Die letzte Spalte zeigt den Inhalt zu untersuchen. Dazu wird die verdächtige Query von Ha- der Variablenumgebung. Um die Übersichtlichkeit zu ver- bitat instrumentiert und vom RDBMS ausgeführt. Die in- bessern, wird hier die Variable days nicht dargestellt. strumentierte Query beobachtet (= zeichnet auf), wie die In Zeile 3 wird die Funktion betreten. Hier findet die In- potentiell fehlerhafte Ergebnisrelation berechnet wird und itialisierung der Datenstrukturen statt, das heißt die ids 0..8 präsentiert dem Benutzer diese Beobachtungen. Bei großen werden vergeben. num, fmt und days sind die Parameter der Eingabetabellen besteht das Problem, dass man vielleicht Funktion und werden der Umgebung hinzugefügt. nur an der Beobachtung der Berechnung eines einzelnen Er- In Zeile 4 beginnt das if/else-Konstrukt. Hier werden gebnistupels interessiert ist, aber auch tausende andere Tu- zunächst die Abhängigkeiten des if/else-Prädikats fmt den pel zusätzlich beobachtet. Um genau die für ein bestimmtes Kontrollfluss-Abhängigkeiten hinzugefügt. Dabei findet eine Ergebnistupel relevanten Eingabetupel herauszufinden, ist Transformation von 8e zu 8y statt. Die Umgebung bleibt Data Provenance genau das richtige Werkzeug. Eine Kom- unverändert. Als dritter Punkt wird das Kontrollfluss-Log bination von diesen beiden Techniken wird von uns ange- gelesen, um festzustellen, ob der if- oder else-Rumpf be- strebt. sucht werden soll. Das Log liefert ein True zurück, also wird eine Analyse des if-Rumpfs durchgeführt. 7. REFERENCES Zeile 5 enthält eine Zuweisung an die Variable pos. Da- [1] Y. Amsterdamer, D. Deutch, and V. Tannen. zu wird zunächst der Ausdruck (num+()) % () analysiert. Die Provenance for Aggregate Queries. In Proc. PODS, beiden () haben hier keine Abhängigkeiten, werden also ein- pages 153–164. ACM, 2011. fach ignoriert. Die Abhängigkeiten von num werden kopiert: [2] P. Buneman, S. Khanna, and W.-C. Tan. Why and 7e . Außerdem werden die Kontrollflussabhängigkeiten über- Where: A Characterization of Data Provenance. In nommen: 8y . Proc. ICDT, pages 316–330. Springer, 2001. Zuletzt findet in Zeile 8 ein Listenzugriff statt. Hier wird [3] J. Cheney. Program Slicing and Data Provenance. das Indices-Log bemüht, das den Index 5 enthält. An 5. IEEE Data Engineering Bulletin, 30(4):22–28, 2007. Stelle von days befindet sich 5e und wird nach res kopiert. [4] J. Cheney, L. Chiticariu, and W.-C. Tan. Provenance Darüber hinaus hat der Index wie auch der Kontrollfluss ei- in Databases: Why, How, and Where. Foundations ne steuernde Funktion. Deshalb wird der Inhalt von pos als and Trends in Databases, 1(4), 2007. Why-Provenance kopiert. Das Ergebnis der Analyse für res ist: [8y , 7y , 5e ], also [5] Y. Cui, J. Widom, and J. Wiener. Tracing the Lineage Where-Abhängigkeit von "Fri" und Why-Abhängigkeit von of View Data in a Warehousing Environment. ACM fmt: True und num: 4. TODS, 25(2), 2000. [6] B. Glavic and G. Alonso. Provenance for Nested Subqueries. In Proc. EDBT, pages 982–993. ACM, 6. ZUSAMMENFASSUNG UND AUSBLICK 2009. Unser hier vorgestellte Ansatz und seine konkrete Im- [7] B. Glavic and K. Dittrich. Data Provenance: A plementierung erweitert die bisherigen Grenzen der Prove- Categorization of Existing Approaches. In BTW, nance-Analyse von SQL. Window Functions und rekursi- volume 7, pages 227–241. Citeseer, 2007. ve Queries sind Bestandteile aktueller DBMS-Implementie- [8] T. Grust and J. Rittinger. Observing SQL Queries in rungen und können von unserem Prototypen analysiert wer- their Natural Habitat. ACM TODS, 38(1), 2013. den. [9] T. Neumann. Efficiently Compiling Efficient Query Derzeit wird im Rahmen einer studentischen Arbeit eine Plans for Modern Hardware. In Proc. VLDB, 2011. zusätzliche Python-Implementierung der hier vorgestellten [10] M. Weiser. Program Slicing. IEEE Transactions on Provenance-Analyse entwickelt. Ihr Merkmal besteht darin, Software Engineering, SE-10(4), 1984. dass sie Bytecode direkt analysiert (statt den Python-AST). 89