Information Systems [Data Management Systems]: Data Provenance; Information Systems [Information Integration]: Data Exchange CHASE-Algorithmus, Data Provenance, Schema-Evolution, Daten-Evolution, CHASE-Inverse, Ergebnisaquivalenz 1.

Unter dem Begri Provenance Management versteht man die Ruckverfolgbarkeit eines Anfrageergebnisses bis zu den relevanten Originaldaten [4]. Dies beinhaltet sowohl die Originaldaten an sich (where-Provenance) als auch den zuruckgelegten Weg (why- und how-Provenance).

Anwendung ndet diese Fragestellung etwa im Forschungsdatenmanagement. Das Ziel besteht hierbei in der Verfolgung und Archivierung von Daten, die bei wissenschaftlichen Projekten, Experimenten oder Beobachtungen erfasst worden sind. Der Weg von der Datenerhebung bis zur Publikation soll so nachvollziehbar, rekonstruierbar und replizierbar gehalten werden. Da die Forschungsdatenbank sich standig andert und somit eine bitemporale Datenbank [ 18 ] darstellt, muss die Evolution von Daten und Schemata mit dem Provenance Management zusammenspielen. Leider werden bisher die Data-Provenance-Forschungen immer auf einer festen Datenbank durchgefuhrt. Zwei Forschungsziele des Projektes bestehen daher in der Berechnung einer minimalen Teildatenbank der Original-Forschungsdatenbank sowie der Vereinheitlichung von Provenance und Evolution.

Berechnung einer minimalen Teildatenbank: Die berechnete minimale Teildatenbank soll die Ergebnisse der Auswertungsanfrage unter verschiedenen Randbedingungen rekonstruieren konnen, etwa:

Die Tupelanzahl der Originalrelation bleibt erhalten. Die Teildatenbank kann homomorph auf das Original abgebildet werden.

Konkret stellt sich die Frage, welche zusatzlichen Informationen bei archiviertem Ergebnis und gemerkter Auswertungsanfrage fur die Rekonstruktion der minimalen Teildatenbank benotigt werden. Reicht es, eine minimale Zeugenmenge aufzuheben (why -Provenance, [ 6 ]) und/oder die zugehorigen Provenance-Polynome zu berechnen (how -Provenance, [ 14 ])? Oder ist es notwendig, ganze Tupel bzw. Datenbankausschnitte direkt zu speichern?

Die Berechnung einer inversen Anfrage Q 1, mit deren Hilfe die gesuchte minimale Teildatenbank bestimmt werden soll, ist abhangig vom Typ der Originalanfrage Q sowie allen zusatzlich gemerkten Informationen. So kann fur die Projektion etwa eine ergebnisaquivalente CHASE-Inverse [3], fur die , K(S2)

A Projektion ohne Duplikateliminierung eine relaxte CHASEInverse und fur die Kopie eine exakte CHASE-Inverse [ 12 ] angegeben werden (siehe Tabelle 4). Die in den Randbedingungen geforderte Homomorphie ist eine sehr starke Eigenschaft, welche im Verlauf weiterer Untersuchungen gezielt abgeschwacht werden soll. Ein erster Ansatz ist die De nition ergebnisaquivalenter CHASE-Inversen (siehe Abschnitt 3.3). Diese vernachlassigen die Homomorphie ganzlich, was wiederum zu einem starken Informationsverlust fuhren kann. So konnen ganze (vielleicht fur andere Anfragen notwendige) Tupel verloren gehen, welche bei der Verwendung einer relaxten CHASE-Inversen zumindest als Nulltupel noch erhalten blieben. Andere Ansatze fuhren beispielsweise Konzepthierarchien oder eine Vergroberung der Datenbankbestande ein, wie es etwa fur intensionale Provenance-Antworten notwendig ist [ 22 ].

Vereinheitlichung von Provenance und Evolution: Bisherige Provenance-Anfragen Qprov (where-, why - und how Provenance) erfolgen stets auf einer gegebenen festen Datenbank S1 sowie einer Auswertungs-Anfrage Q. Die Kombination von Provenance mit Schema- und Daten-Evolution soll die Auswertung von Provenance-Anfragen bei sich andernden Daten und Schemata ermoglichen (siehe Abbildung 1). Mit Hilfe der Inversenbildung E 1 kann wiederum, (falls moglich) der neue Datenbankbestand J in das alte Schema Das mittels CHASE berechnete Auswertungsergebnis (siehe Abschnitt 3.1) soll daher in einem zweiten Schritt, dem BACKCHASE, um eine inverse Provenance-Anfrage Q0prov erweitert werden.

Formal: Nach der Schemaevolution E : S1 ! S3 kann die Anfrage Q0 als Komposition der ursprunglichen Anfrage Q sowie der inversen Evolution E 1 direkt berechnet werden: Q0(J (S3)) = (E 1

Q)(J (S3)) = Q(I(S1)): Die neue Provenanceanfrage Q0prov ergibt sich analog als

Q0prov(K (S2)) = (Qprov E)(K (S2)): Es genugt daher, sich eine der beiden minimalen Teildatenbanken I (S1) oder J (S3) zu merken. Die jeweils andere lasst sich mit Hilfe der Inversen leicht berechnen. Im Forschungsdatenmanagement entspricht K dabei stets der gesamten Ergebnisdatenbank K, d.h. K = K. Allgemeine Provenance-Anfragen konnen auch auf Teilmengen dieser Ergebnisdatenbank sowie konkreten Tupeln gestellt werden.

Die Universitat Rostock vereint ihre Forschungen zum Thema Provenance Management im Projekt METIS in PArADISE [ 17 ]. Konkret beschaftigt sich dieses Projekt mit Provenance Management bei der Auswertung von Sensordatenmengen fur die Entwicklung von Assistenzsystemen.

METIS : Das Langzeitprojekt METIS (Management, Evolution, Transformation und Integration von Schemata) vereint die Verfahren zur Integration, Transformation und Evolution von Daten. Auch die Frage der Datenherkunft wird in diesem Projekt untersucht.

PArADISE : In der Projektgruppe PArADISE (Privacy AwaRe Assistive Distributed Information System Environment) werden Techniken zur Auswertung von gro en Mengen von Sensordaten entwickelt.

Eine Anwendung von METIS in PArADISE im Bereich des Forschungsdatenmanagements wird zusammen mit dem Leibniz-Institut fur Ostseeforschung in Warnemunde (IOW) entwickelt (siehe [ 5 ]). Die Notwendigkeit zur Integration von Provenance- und Evolutions-Fragestellungen wurde gerade in dieser Kooperation geboren.

Im Rest dieses Beitrages werden wir die Formalisierung der Auswertungsanfragen und ihrer Inversen mit Hilfe des CHASE einfuhren sowie fur einfache Auswertungsanfragen verschiedene Typen von Inversen angeben. Die Formalisierung der Techniken uber den CHASE soll uns gerade ermoglichen, die Ergebnisse der Schema-Evolutions-Theorie, der Theorie des Datenaustausches und der Data Provenance zu vereinheitlichen.

Die Idee unserer Arbeit basiert auf der Kombination dreier verschiedenen Grundtechniken.

Provenance: Die Grundlage fur unsere Provenance-Analysen bildet [ 16 ] mit einem allgemeinen U berblick uber die Begri sbildungen sowie die verschiedenen Klassi zierungen von Provenance-Anfragen (why , where, how und why not ). Die Konstruktion von (minimalen) Zeugenbasen und ProvenancePolynomen zur Beantwortung der why - bzw. how -Provenance basieren auf den Techniken aus [ 6 ] und [ 1, 14, 15 ]. Die Ubertragung der Problematik auf die Spieltheorie wird in [ 19 ] zur Analyse der why not -Provenance benutzt.

CHASE: Leider werden Provenance-Anfragen derzeit nur auf festen Datenbanken benutzt. Um die Technik mit der Evolution von Schemata und Daten kombinieren zu konnen, wollen wir die Auswertungs-Anfragen Q sowie die ProvenanceAnfragen Qprov mit Hilfe von s-t tgds und egds (siehe unten) darstellen und mit Hilfe des CHASE konzeptuell umsetzen. Seine ursprungliche Anwendung hat der CHASE im Datenbankentwurf [ 20 ], der auf den Tableaude nitionen in [1] basiert. Der CHASE wurde dann spater vor allem fur die Transformation von Datenbanken im Bereich der Datenintegration, des Datenaustausches und der Schema-Evolution benutzt. In diesen Fallen dient der CHASE dann zur Darstellung von Schemabbildungen.

Schemaabbildungen und inverse Abbildungen. Fagin et al. beschaftigen sich in ihren Arbeiten [ 9, 12 ] ausfuhrlich mit der De nition des CHASE-Algorithmus fur s-t tgds und egds sowie der Konstruktion von CHASE-inversen Schemaabbildungen [ 10, 11 ]. Eine Implementierung des CHASE fur diesen Anwendungsfall liefert etwa die Software Llunatic [ 13 ]. In [ 8 ] wurden diese Techniken auch fur die Schema-Evolution verwendet. Die Nutzung inverser Schemaabbildungen fur das Provenance Management, speziell fur Provenance-Anfragen, ist bisher noch nicht vorgenommen worden.

Die Bearbeitung der beiden oben vorgestellten Forschungsziele soll durch die Kombination der gerade vorgestellten Tabelle 1: APS-Relation mit zugehorigen Tupelidenti katoren t1 und t2 Techniken erfolgen, (1) dem CHASE-Algorithmus zur Auswertung von Anfragen, (2) der Ermittlung von why - und how -Provenance und (3) der Berechnung von CHASE-inversen Abbildungen zur Rekonstruktion einer minimalen Teilmenge der Originaldatenbank. 3.1

Der CHASE ist ein in der Datenbanktheorie universell einsetzbares Werkzeug. Es ndet Anwendung etwa bei der Darstellung von Abhangigkeiten innerhalb einer Datenbank oder eines relationenalgebraischen Ausdrucks, der Implikation von Abhangigkeiten, dem Aquivalenznachweis von Datenbankschemata unter gegebenen Abhangigkeiten sowie der Behandlung (Ersetzung oder Sauberung) von Nullwerten in Datenbanken. Die Idee dieses Algorithmus kann dabei wie folgt zusammengefasst werden: Fur ein Objekt und eine Menge von Abhangigkeiten ? (beispielsweise eine Menge von FDs und JDs) arbeitet der CHASE die Abhangigkeiten ? in das Objekt ein, sodass ? implizit in enthalten ist, und somit die Abhangigkeiten nicht verletzt. Bildhaft ergibt sich:

chase?( ) = ? :

Seine ursprungliche Anwendung hat der CHASE im Datenbankentwurf [ 20 ], der auf den Tableaude nitionen in [1] basiert. Der CHASE kann aber nicht nur mit FDs und JDs (?) auf Tableaus ( ), sondern auch mit tgds/s-t tgds und egds (?) auf Datenbanken ( ) de niert werden. Dies beschreiben unter Anderem Fagin et al. in [ 12, 9 ].

Eine tuple-generating dependency (tgd) ist eine Sequenz der Form

8x : ( (x) ! 9y : (x; y)) mit Konjunktionen (x) und (x; y) von Atomen aus x bzw. x und y. Ist (x) eine Konjunktion von Atomen uber einem Quellschema S und (x; y) eine Konjunktion von Atomen uber einem Zielschema T , so hei t eine solche Sequenz auch source-to-target tuple-generating dependency (s-t tgd). Eine equality-generating dependency (egd) ist fur zwei Variablen x1; x2 aus x de niert durch

8x : ( (x) ! (x1 = x2)):

Der CHASE einer Instanz I uber einer Abhangigkeitsmenge ist schlie lich eine (endliche oder unendliche) Sequenz von tgd- und egd-Regeln, welche neue Tupel erzeugen oder (markierte) Nullwerte durch Konstanten bzw. (markierte) Nullwerte mit kleinerem Index ersetzen kann.

Zur Veranschaulichung des CHASE sei exemplarisch die Datenbank einer Universitat gegeben. Diese enthalt unter Anderem eine Relation mit den Namen, Studiengangen und Matrikelnummern ihrer Studenten sowie eine weitere Relation, welche alle abgeschlossenen Abschlussarbeiten listet. Die zugehorigen Schemata sind de niert

STUD(Matrikelnummer, Name, Studiengang) und

AA(ID, Titel, Vertiefung, Matrikelnummer, Note). Die Relation APS mit dem Schema

APS(ID, Titel, Matrikelnummer, Studiengang), welche die Abschlussarbeiten pro Studiengang zusammenfasst, soll nun in die Relationen AA und STUD migriert werden. Hierzu seien folgende Abhangigkeiten gegeben (eine s-t tgd, eine tgd sowie eine egd):

ST = f 1 : APS(i; t; m; s)

! 9N; V; G : STUD(m; N; s) ^ AA(i; t; V; m; G)g T = f 2 : AA(i; t; v; m; g) ! 9 N; S : STUD(m; N; S);

3 : STUD(m; n1; s) ^ STUD(m; n2; s) ! n1 = n2g Der CHASE liefert nun, angewandt auf den Datenbestand aus Tabelle 1, nach Integration der s-t tgd 1 die Tupelmenge I0 = fSTUD(4711, N1, Informatik), AA(1234, Big Data, V1, 4711, G1), STUD(4711, N2, Informatik),

AA(2467, Provenance, V2, 4711, G2)g mit den (markierten) Nullwerten N1; N2; V1; V2; G1 und G2. Bevor 2 sowie 3 eingearbeitet werden, muss gepruft werden, ob I0 die Abhangigkeiten aus T bereits erfullt, d.h. I0 j= T. In diesem Fall ware ein weiterer CHASE-Schritt, also die Anwendung einer tgd- oder egd-Regel, nicht mehr notwendig und der CHASE selbst erfolgreich. Die tgd 2 ist bereits erfullt, sodass die Eliminierung uber ussiger Nullwerte | das sogenannte cleaning | mittels 3 bereits die Ergebnisinstanz I00 = fSTUD(4711, N1, Informatik),

AA(1234, Big Data, V1, 4711, G1),

AA(2467, Provenance, V2, 4711, G2)g liefert. Implementiert ist diese Art des CHASE etwa in der Software Llunatic [ 13 ]. 3.2

Typischerweise werden vier Provenance-Anfragen und vier Provenance-Antworten (siehe Tabelle 2) unterschieden [ 16 ]. Die ersten drei Anfragen konnen dabei bzgl. ihres Informationsgehaltes ( ) geordnet werden: where why how : Mit anderen Worten, aus dem Ergebnis der how -Provenance konnen die why - sowie die where-Provenance abgeleitet werden. Gleiches gilt fur die why - und where-Provenance (siehe Abbildung 2). Der formale Beweis fur die Reduktion der why auf die how -Provenance kann in [ 7 ] nachgelesen werden. Die why not -Anfrage kann in diese "Informationskette\ nicht eingeordnet werden, da sie, anders als die why -, where- oder how -Anfrage keine extensionale, sondern eine anfrage- oder modi kationsbasierte Antwort liefert.

Die how -Provenance einer Anfrage Q kann als ProvenancePolynom [ 14, 2, 15 ], die why -Provenance in Form von (minimalen) Zeugenbasen [ 6 ] und die where-Provenance als Liste where-Provenance (Tabellenname)

APS h why-Provenance how-Provenance (Zeugenbasis) (Polynom) fft1g; ft2g; ft1; t2gg (t1 (t1 + t2)) + (t2 (t1 + t2))

h

Exakte, klassische und relaxte CHASE-Inverse sind spezielle Formen von inversen Abbildungen [ 12 ]. Erstmalig formuliert wurden inverse Schemaabbildungen von Fagin [ 10 ]. Er de niert die Inverse einer Schemaabbildung M : S1 ! S2 als eine Schemaabbildung M : S2 ! S1, deren Komposition M M der Identitatsabbildung entspricht.

Inverse Abbildungen nden etwa bei der Schemaevolution Anwendung. Wahrend eine exakte CHASE-Inverse stets die Originaldatenbank rekonstruiert, liefert die klassische CHASE-Inverse nur ein zur Originaldatenbank aquivalentes Ergebnis. Kann eine Inverse nicht angegeben bzw. de niert werden, wird aber dennoch eine Art inverse Abbildung benotigt, kann auf die sogenannte Quasi-Inverse zuruckgegri en werden [ 11 ]. Sie liefert nicht mehr die Quellinstanz selbst, dafur aber eine hierzu aquivalente Instanz oder zumindest eine aquivalente Teilinstanz.

Fur eine Anfrage Q und eine Quellinstanz I liefert der CHASE eine Ergebnisinstanz K = chaseM(I), wenn gilt: Q wird als Schemaabbildung M = (S1; S2; 1) mit Quell- und Zielschema S1 und S2 sowie einer Menge von Abhangigkeiten 1 aufgefasst;

Im Forschungsdatenmanagement soll neben der Auswertungsanfrage und dem -ergebnis selbst auch der verwendete Ausschnitt der Originaldatenbank archiviert werden. Falls sich die Daten oder das Schema der Forschungsdatenbank hau g verandern, musste man nach jeder auf dem Datenbestand vorgenommenen Auswertung die Originaldatenbank einfrieren\ und sichern. Um dies zu vermeiden, berechnen "wir mit Hilfe von Provenance-Management-Techniken die minimale Teildatenbank, die gesichert werden muss, um das Anfrageergebnis wieder erzeugen zu konnen. Dazu haben wir Techniken der why - und how -Provenance mit der Theorie der inversen Schema-Abbildungen fur Datenintegration und Datenaustausch kombiniert. Basis fur die Transformationen auf den Daten zur Evolution von Schema und Daten als auch fur die Transformation, die die Auswertungsanfrage darstellt, ist der CHASE. Damit konnen wir drei verschiedene Teilgebiete der Theorie zusammenfuhren.

In diesem Beitrag haben wir erste konkrete Teilergebnisse zur Klassi zierung von inversen Anfragen bei der Berechnung der why -Provenance vorgestellt: Die Berechnung der Inversen nur mit Hilfe von Ergebnis und Auswertungsanfrage, die Bestimmung der Inversen mit Hilfe zusatzlicher ProvenanceInformationen (Provenance-Polynome der how -Provenance) sowie die De nition eines Datenbankausschnitts, der homomorph auf die Originaldatenbank abgebildet werden kann.

[2] Y. Amsterdamer, D. Deutch und V. Tannen. \Provenance for Aggregate Queries". In: PODS. ACM, 2011, S. 153{164.