Der BACKCHASE zur Unterstützung von Data Provenance und Schema-Evolution

Abstract

Der CHASE-Algorithmus ist ein Multifunktionswerkzeug der Datenbankforschung. Ursprunglich fur die Optimierung des Datenbankentwurfs genutzt, wird er heutzutage auch fur den Datenaustausch und Data-Cleaning verwendet und kann ebenfalls genutzt werden, um Anfragen zu optimieren. Fur einige Anwendungen reicht eine CHASE-Phase alleine jedoch nicht aus. Teilweise wird eine Nachbearbeitung, eine sogenannte BACKCHASE-Phase, benotigt. Dies ist beispielsweise der Fall, wenn Auswertungen zum Zweck der Ruckverfolgbarkeit (Provenance) invertiert werden sollen. In dieser Arbeit fassen wir zusammen, wie der Ansatz des CHASE und BACKCHASE verwendet werden kann, um die Why-Provenance von Anfragen unter Schema-Evolution zu gewahrleisten.

KURZFASSUNG

MOTIVATION

2. 2.1

STAND DER FORSCHUNG

CHASE & BACKCHASE

Der CHASE-Algorithmus ging aus der Datenbankforschung als Werkzeug zum Schlussfolgern mit Integritatsbedingungen hervor. Dabei wird eine Menge von Abhangigkeiten , der CHASE-Parameter, auf ein CHASE-Objekt d angewandt und erweitert dies durch Forward-Chaining so, dass d dem CHASE-Parameter genugt [ 5 ]. Grundlegend werden zwei Arten von Abhangigkeiten, die equality-generating dependencies (EGDs) und tuple-generating dependencies (TGDs), unterschieden [ 13 ]. Eine EGD stellt die Gleichheit bestimmter Werte sicher und ist eine Formel der Form

8~x : F (~x) ! x1 = x2: Hierbei ist ~x ein Variablenvektor mit x1; :::; xn als Komponenten. F ist eine Konjunktion von Pradikaten der Form Ri(~x), wobei Ri Relationenschemata des Datenbankschemas sind. TGDs hingegen rufen die Generierung neuer Tupel hervor und sind Formeln der Form 8~x : F1(~x) ! 9~y : F2(~x; ~y): Hierbei muss in F1 jede Komponente aus ~x mindestens einmal vorkommen. Eine besondere Form von TGDs sind sourceto-target-TGDs (s-t-TGDs). Bei ihnen ist der Rumpf (linke Seite der Abhangigkeit) uber einem Quellschema S und der Kopf (rechte Seite) uber einem Zielschema S0 de niert. Durch die Beschrankung auf Konjunktionen von Pradikaten, betrachten wir im Folgenden nur Anfragen und Evolutionsoperationen, die ausschlie lich als Konjunktionen darstellbar sind. Disjunktionen lassen sich spatestens in der BACKCHASE-Phase nach der Invertierung nicht ohne Zusatzinformationen (Zeugenbasis einzelner Tupel) verarbeiten. Bei der Anwendung des CHASE (siehe Algorithmus 1) wird dann im CHASE-Objekt nach Mustern des Rumpfes jeder Abhangigkeit gesucht. Ein solcher Trigger ist aktiv, falls der Kopf seiner entsprechenden Abhangigkeit noch nicht im CHASE-Objekt erfullt ist. Da sich diverse Bedingungen als Algorithmus 1: Standard-CHASE auf CHASE-Objekt d if ist aktiv then if hat Form 8~x : F1(~x) ! 9~y : F2(~x; ~y) then

Nimm Kopf von in d auf else if hat Form 8~x : F (~x) ! x1 = x2 then if x1; x2 sind Konstanten und x1 6= x2 then

CHASE schlagt fehl else if x2 ist Konstante then

x1 x2 else x2

x1 EGDs bzw. TGDs formulieren lassen und die Berechnung deren Implikation auf Instanzen oder Anfragen verschiedene Ziele erfullen kann, ist der CHASE vielseitig einsetzbar. So lassen sich unter anderem (1) Datenmigrationen als s-tTGDs fur den CHASE auf einer Datenbankinstanz formulieren [ 10 ], (2) Data-Cleaning-Probleme durch Anwendung des CHASE auf einer Datenbankinstanz mit bestimmten EGDs zur Bereinigung losen [ 12 ], (3) Anfragen durch Sichten beantworten, indem man den CHASE mit den Sichtde nitionen auf der Anfrage als CHASE-Objekt ausfuhrt [ 9 ], sowie (4) Anfragen semantisch optimieren, indem man Integritatsbedingungen als CHASE-Parameter in die Anfrage einarbeitet [ 15 ].

Fur die Anwendungsfalle (3) und (4) reicht eine einzelne CHASE-Phase jedoch nicht aus. Die CHASE-Phase berechnet hier ein Zwischenergebnis, welches fur die BACKCHASEPhase, in diesem Fall eine zweite Anwendung des CHASE mit modi zierten Abhangigkeiten, verwendet wird [ 9 ]. Die BACKCHASE-Phase muss aber nicht zwingend eine zweite CHASE-Phase sein [ 16 ]. Je nach Anwendungsfall konnen auch hier verschiedene Techniken Ansatz nden.

In Abbildung 1 zeigen wir schematisch den Einsatz des BACKCHASE fur die Anwendungsfalle (3) und (4): Im Anwendungsfall (3) wird eine Anfrage Q an Basisrelationen einer Datenbanken um Zugri e auf verwendbare Sichten angereichert, die CHASE-Parameter enthalten dann die Sichtde nitionen. Die BACKCHASE-Phase minimiert nun diese erweiterte Anfrage und schrankt sie (falls moglich) ausschlie lich auf Zugri e uber die Sichtrelationen ein (Anfrage Q0). In der BACKCHASE-Phase wird der CHASE mit inversen Sichtde nitionen angewendet [ 9 ]. Im Anwendungsfall 4 werden Integritatsbedingungen als CHASE-Parameter in Q'

CHASE BACKCHASE

CHASE-Ergebnis

CHASE(Q)

Abbildung 1: CHASE und BACKCHASE die Anfrage Q eingearbeitet. Die BACKCHASE-Phase minimiert dann diese Anfrage, indem sie uber ussige Operationen (etwa Verbunde) eliminiert. In diesem Anwendungsfall ist die BACKCHASE-Phase ein durch homomorphe Abbildungen der Anfrage gesteuerter, aquivalenzerhaltender Reduktionsprozess [ 15 ]. Die BACKCHASE-Phase wurde fur die Anwendungsfalle (1) und (2) bisher nicht benotigt. Wir werden sie in Abschnitt 3 aber einfuhren. Hier wollen wir das Anfrageergebnis einer Anfrage, verstanden als Datenbanktransformation wie in (1), mit Hilfe der Why-Provenance auf die minimale Zeugenbasis, also die relevanten Originaltupel aus der Datenbank, zuruckfuhren. Der Schritt der Why-Provenance wird durch eine erweiterte inverse Anfrage dargestellt, die wir als BACKCHASE-Phase verstehen. Analog werden wir eine Schema-Evolution als eine Datenbanktransformation wie in (1) verstehen. Um die neue Datenbank nach der Evolution in die alte Darstellung vor der Evolution ruckrechnen zu konnen, mussen wir auch hier die Evolution in einer BACKCHASE-Phase invertieren. 2.2

Data Provenance

Die Provenance beschaftigt sich mit der Frage nach dem Ursprung von Daten. Insbesondere ist dies fur die Nachvollziehbarkeit von wissenschaftlichen Auswertungen interessant. Hauptsachlich unterscheidet man drei Abstraktionsstufen der Provenance, Where-, Why- und How-Provenance. Diese beschreiben in unterschiedlichem Detailgrad, woher die Ergebnisdaten stammen. Dies reicht von der Benennung der Datenquellen (Where), also den Relationen und Datenbankschemata [ 7 ], uber die Angabe der beteiligten Tupel (Why), einer sogenannten Zeugenbasis [ 6 ], bis zu ProvenancePolynomen (How) [ 14 ], welche aussagen, wie die beteiligten Tupel kombiniert wurden.

Der CHASE kann genutzt werden, um ein Anfrageergebnis zu berechnen. Hierzu formuliert man die Anfrage als s-t-TGD und wendet sie mittels des CHASE auf die entsprechende Datenbankinstanz an. Aus dem Anfrageergebnis lassen sich die beteiligten Tupel errechnen, indem man die Inverse der Auswertung bildet. Hierzu fuhrt man den CHASE auf der Ergebnisrelation mit der invertierten s-t-TGD der Anfrage aus. Je nach Art der Anfrage konnen sich unterschiedliche Arten von Inversen ergeben, welche mittels zusatzlicher Provenance-Annotationen noch verbessert werden konnen [ 2, 11 ]. Ziel ist es, eine moglichst genaue CHASEInverse zu erhalten, auch wenn Anfragen in der Regel verlustbehaftet sind und sich somit nicht jede Information rekonstruieren lasst. 2.3

Schema-Evolution

Die Evolution eines Datenbankschemas ist der U bergang von einer Schemaversion in eine neue. Diese sind durch A nderungen im Anwendungsgebiet begrundet, z. B. neue relevante Informationen, die zuvor nicht erhoben wurden, oder neue Anforderungen an die Anwendung [ 17 ]. Deshalb reichen die moglichen Operationen wahrend einer Evolution vom simplen Hinzufugen eines neuen Attributs bis hin zu komplexen Berechnungen neuer Werte. Auch Evolutionsoperationen lassen sich als s-t-TGDs und EGDs darstellen. Hierbei ist das Quellschema die aktuelle Schemaversion und das Zielschema die Folgeversion. Sowohl Anfragen als auch Schema-Evolution liegen die Basisoperationen Selektion (Attribut gleich Attribut und Attribut gleich Konstante), Projektion, Verbund und die Umbenennung von Relationen und Attributen zugrunde. In beiden Fallen interessieren uns die CHASE-Inversen [ 11 ]. Diese drucken den Grad des Informationsverlustes aus, wenn wir versuchen, die Originalinstanz aus dem CHASE-Ergebnis durch Invertierung der Abhangigkeiten zu rekonstruieren. Dies ist fur unseren Anwendungsfall von gro er Relevanz, da die Berechnung der an der Anfrage beteiligten Tupel und ihrer Attribute Grundlage des in Abschnitt 3 vorgestellten Ansatzes ist. Dafur rekonstruieren wir die Teilinstanz unserer Originaldatenbank, mussen dabei aber darauf achten, dass keines der fur die Anfrage bzw. Evolution relevanten Tupel bei der Rekonstruktion verloren geht. Daher benotigen wir bezuglich der an einer Anfrage bzw. Evolution beteiligten Tupel eine tupelerhaltend-relaxierte Inverse, d. h., dass die durch den BACKCHASE gewonnene Datenbankinstanz auf die Originalinstanz abbildbar ist und die gleiche Tupelzahl besitzt [ 2 ].

NUTZUNG DES BACKCHASE

Zunachst zeigen wir in Unterabschnitt 3.1, wie die oben genannten Basisoperatoren und komplexere Operationen fur Anfragen und Evolutionen als Abhangigkeiten (s-t-TGDs), und somit als Parameter fur den CHASE-Algorithmus, formuliert werden konnen. Wir verwenden hierbei eine Kurzschreibweise, bei der nur existenzquanti zierte Variablen explizit als solche angegeben werden. Die Namen der Variablen entsprechen den Namen der Attribute.

Danach werden wir in Unterabschnitt 3.2 dann die Basis fur den BACKCHASE-Prozess legen, indem wir die Provenance- und Evolutionsschritte uber mehrere Stufen hin invertieren und komponieren. Hierbei mussen wir insbesondere berucksichtigen, dass wir bei der Komposition verschiedener Schritte wertvolle Zwischeninformationen nicht verlieren. Die s-t-TGDs werden hier als Transformationssprache nicht mehr ausreichen, wir mussen auf Konstrukte der Pradikatenlogik zweiter Ordnung (so-TGDs, second-order TGDs) ausweichen [ 11 ]. 3.1

Anfragen und Schema-Evolution als s-t

TGDs

Im Nachfolgenden zeigen wir am Beispiel der Projektion, wie sich Operatoren fur Anfragen und Schema-Evolutionen als s-t-TGDs darstellen lassen. Weitere Details und Operatoren nden sich in [ 19 ].

Die Projektion lasst sich als s-t-TGD formulieren, indem nur die Attribute, auf welche projiziert werden soll, im Kopf der Abhangigkeit vorkommen, z. B.

R(A1; A2; A3; :::; An) ! R0(A1; A2): Da der Standard-CHASE jedoch nur fur aktive Trigger den Kopf der Abhangigkeit in das Ergebnis der Anfrage bzw. Evolution aufnimmt, wird hier eine Duplikateliminierung vorgenommen, die nur eine relaxierte CHASE-Inverse bedeutet [ 2 ]. In Bezug auf die an der Anfrage beteiligten Tupel genugt dies jedoch einer tupel-erhaltend relaxierten Inverse, da Tupel, fur die kein aktiver Trigger existiert, keinen Ein uss auf das Anfrageergebnis haben [ 18 ]. Die Inverse der obigen s-tTGD lautet dann

R0(A1; A2) ! 9A3; :::An : R(A1; A2; A3; :::; An) Im Gegensatz zu Anfragen kann bei der Evolution jedoch noch ein Spezialfall auftreten. Da bei einer Schema-Evolution auch neue Attribute hinzukommen konnen, kann dort auch auf Attribute projiziert werden, die nicht im ursprunglichen Schema vorkommen. Fur die Invertierung sind solche neu hinzugefugten Attribute jedoch unproblematisch, da sie keinen Ein uss auf die aus der Ursprungsrelation stammenden Informationen haben.

Die in [ 19 ] beschriebenen, grundlegenden Operatoren werden in Anfragen und Evolutionsoperationen hau g verknupft und bieten somit die Grundlage der meisten bekannten Operationen zur Schema-Modi kation, die in [ 8 ] vorgestellt wurden. Dabei gilt, dass der weniger genaue Inversentyp dominiert [ 2, 11 ]. Hierbei muss jedoch in einem Fall besonders auf die Projektion geachtet werden. Fur die Auswertung relevante Attribute, z. B. Verbundbedingungen, die nicht im Kopf der TGD vorkommen, mussen besonders markiert werden. Darauf gehen wir spater in diesem Abschnitt genauer ein. Es konnen aber auch komplexere Auswertungen vorkommen, die z. B. Aggregate berechnen oder vollig neue Werte generieren. In diesen Fallen ist der Standard-CHASE nicht ausreichend, um die CHASE- oder BACKCHASE-Phase abzuschlie en. Solche Auswertungen, lassen sich jedoch mit Hilfe von second-order-Abhangigkeiten umsetzen [ 11 ]. Hier konnen Funktionen de niert werden, welche die Generierung neuer Konstanten erlauben. Sind diese selbst nicht invertierbar, werden an den entsprechenden Stellen in der BACKCHASE-Phase Nullwerte generiert. 3.2

Komposition von Provenance- und Evolutionsschritten

Im Folgenden stellen wir einen Ansatz vor, welcher die Berechnung derjenigen Tupel erlaubt, welche nach einer Evolution nicht mehr ausreichend in der nachsten Schemaversion abgebildet werden, um bestimmte Anfragen zu reproduzieren. Hierzu setzen wir voraus, dass alle Tupel eine eindeutig ID (TID) besitzen und die Evolutionsschritte und Anfragen, die reproduzierbar bleiben sollen, gespeichert werden. Beim U bergang wird die Menge der Tupel berechnet, die nach der Evolution nicht mehr fur die Beantwortung der ausgewahlten Anfragen ausreichen. Diese Menge nennen wir im Folgenden IP rov und muss nach der Schema-Evolution zusatzlich aufbewahrt werden.

Dieser Prozess lauft in drei Teilschritten ab. Zunachst berechnen wir mittels des CHASE und BACKCHASE fur jede Anfrage, jeweils durch eine s-t-TGD abgebildet, ihr Ergebnis und die Menge der Tupel, die tatsachlich an der Auswertung beteiligt waren. Diese Mengen nennen wir I0(S). Anschlieend berechnen wir analog die Datenbank in der nachsten Schemaversion (I(S0)), basierend auf den Evolutionsoperationen, die ebenfalls als s-t-TGDs dargestellt werden, sowie die Menge der Tupel J, die nach der Evolution durch Invertierung abbildbar sind. Im letzten Teilschritt suchen wir Abbildungen von Tupeln aus I0(S) in J. Existiert eine solche Abbildung fur ein Tupel, ist es in der nachfolgenden Schemaversion ausreichend abgebildet, um fur die Anfragen verwendet zu werden. Ist dies nicht der Fall, muss es zum Zweck der Reproduzierbarkeit aufbewahrt werden. Provenance der Anfragen. In [ 1 ] wurde vorgestellt, wie eine Anfrage Q0 auf der nachsten Schemaversion S0 nach der Evolution E aussehen muss, um das Ergebnis der ursprunglichen Anfrage Q auf der alten Schemaversion S zu produzieren. Hierzu muss Q0 der Ausfuhrung von Q auf dem alten Datenbestand entsprechen. Es gilt also

Q0(S0) = Q(E 1(S0)): Da CHASEE 1 (S0) jedoch nicht zwangslau g alle Tupel ausreichend wiederherstellt, um die Anfrage Q zu beantworten, mussen dem Ergebnis noch die eingefrorenen Tupel IP rov hinzugefugt werden. So ergibt sich fur den allgemeinen Fall

Q0(S0) = Q(E 1(S0) [ IP rov): Die erste Phase der Berechnung von IP rov identi ziert die beteiligten Tupel fur alle ausgewahlten Anfragen Qi. i=1 n I0(S) = [ CHASEQ 1 (CHASEQi (I)) i Da bei Anfragen oder Evolutionsschritten Attribute, die fur die Berechnung dieser relevant sind, herausprojiziert werden konnen, muss abgesichert werden, dass diese Attribute spater erkannt werden konnen. Da Konstanten bei der Invertierung einer s-t-TGD weiter erhalten bleiben, ist die Selektion A = c unproblematisch. Verbundattribute bzw. Attributvergleiche Ai = Aj, bei denen diese Attribute nicht im Kopf der TGD auftauchen, beein ussen die Auswertung, werden aber nach dem BACKCHASE mit Nullwerten in den entsprechenden Tupeln besetzt. Um diese von Attributen abzuheben, die nicht fur die Auswertung relevant sind, markieren wir Variablen, die im Kopf der invertierten s-t-TGD mehrfach vorkommen aber existenzquanti ziert sind, als besondere Variablen AiP rov. Diese generieren beim CHASE spezielle Nullwerte (Provenance-Nullwerte) jP rov.

Provenance der Schema-Evolution. Anschlie end fuhren wir

die gleiche Berechnung fur die Evolution E durch, um herauszu nden, welche Tupel sich nach der Evolution rekonstruieren lassen.

J = CHASEE 1 (CHASEE(I)) = CHASEE 1 (I(S0)) Hierbei mussen wir Provenance-Nullwerten keine Beachtung schenken, da wir uns nur dafur interessieren, welche Informationen des alten Schemas im neuen erhalten bleiben. Da hier die Evolution berechnet werden soll, bedeutet dies allerdings auch die Berechnung neuer TIDs, falls Tupel nach der Evolution zusammenfallen oder aufgesplittet werden. Im allgemeinen Fall reicht der Standard-CHASE hier nicht aus. Betrachten wir zur Veranschaulichung folgende Beispiele. Das Attribut Z der Relation R auf der Datenbankinstanz I(S) soll nach der Evolution E ebenfalls durch das Attribut Y abgedeckt werden. In diesem Fall werden Tupel aus R aufgesplittet, sodass potenziell neue TIDs notig werden. Berechnet man nun CHASEE(I), ergibt sich die folgende Relation R auf der Datenbankinstanz I(S0).

E : R(tid; x; y; z) ! 9T id2; T id3 : R(T id2; x; y) ^ R(T id3; x; z) Diese Nullwerte mussen nun durch entsprechende Konstanten fur neue TIDs ersetzt werden. Im Falle des Aufsplittens TID 1 2 (b) Relation R auf I(S0) Tabelle 1: Relation R vor und nach Anwendung des CHASE TID 1 2

X 1 1

Y 1 2 (a) Relation R2

TID 1

X 1 (b) Relation Rx

TID von Tupeln kann dies direkt uber second-order-TGDs passieren, die statt Nullwerten uber eine Funktion neue, eindeutige IDs berechnen, z. B. UUIDs. Fallen jedoch auch Tupel zusammen, z. B. weil ein Attribut durch die Evolution entfernt wird, funktioniert dies nicht. Hier konnten redundante Tupel mit unterschiedlichen IDs entstehen. Betrachten wir hierzu folgendes Beispiel der Relation R2 und der Evolution E2.

E2 : R2(tid; x; y) ! 9T id2; T id3 : Rx(T id2; x) ^ Ry(T id3; y) Berechnet man nun CHASEE(I), ergeben sich die in Tabelle 2 dargestellten Relationen Rx und Ry in der nachsten Schemaversion. Hier konnen nicht direkt neue TIDs durch die s-t-TGD der Evolution vergeben werden, da sonst ein zusatzliches Tupel in Rx generiert wird, welches jedoch den gleichen X-Wert tragt. Solche Redundanzen sind nicht erwunscht, sodass in einem Zwischenschritt die Nullwerte durch entsprechende Konstanten ersetzt werden mussen. Des weiteren muss diese Vergabe neuer Konstanten invertierbar sein, damit bei der Invertierung der Evolution auch alte TIDs errechnet werden konnen. Daher bietet es sich an, ein Verzeichnis uber die Provenance der TIDs zu fuhren, aus dem abgelesen werden kann, aus welchen Tupeln (TIDs) der vorherigen Schemaversion die Tupel der neuen Schemaversion gebildet wurden. Dies kann uber eine Hilfstabelle T ID(tidS; tidS0 ) realisiert werden, um welche die Abhangigkeiten fur die Evolution erweitert werden mussen. Erweitern wir E2 um die Nutzung dieser Hilfsrelation, ergibt sich folgende s-t-TGD E3 : R2(tid; x; y) ! 9T id2; T id3 : Rx(T id2; x) ^ Ry(T id3; y) ^T ID(tid; T id2) ^ T ID(tid; T id3): Bevor die Invertierung des Evolutionsschrittes statt ndet, muss nun noch die Cleaning-EGD angewandt werden. Hierfur verwenden wir second-order-EGDs der Form

T ID(tid; tid2) ! tid2 = f (tid2): Dabei ist f eine Funktion, die bei Eingabe eines Nullwertes eine neue TID (z. B. eine UUID), bei Eingabe einer Konstante jedoch diese selbst zuruckgibt. Dies muss fur alle TIDs durchgefuhrt werden. Besonders muss dabei darauf geachtet werden, dass die nummerierten Nullwerte global durch die Konstanten uberschrieben werden.

Berechnung der zu speichernden Tupel. Im nalen Schritt berechnen wir nun IP rov. Hierzu suchen wir die Menge derjenigen Tupel aus I0(S), die sich auf Tupel in J abbilden lassen. Diese Menge nennen wir JM . Ein normaler Nullwert in einem Tupel in I0(S) bedeutet, dass die Auswertung, aus deren BACKCHASE-Phase dieses Tupel stammt, jenes Attribut nicht benotigt. Diese Nullwerte konnen daher beliebig auf Konstanten oder Nullwerte in J abgebildet werden. Anders verhalt sich dies jedoch bei den Provenance-Nullwerten. Da sie an der Auswertung beteiligt sind, durfen diese nur auf Konstanten abgebildet werden. Sonst gehen z. B. Verbundkriterien und damit auch die Reproduzierbarkeit der Anfrage verloren. IP rov ergibt sich dann aus denjenigen Tupeln, die an der Anfrage beteiligt waren, aber nicht in JM sind. Diese Tupel konnen dann in extra Tabellen "eingefroren" werden, sodass sie fur die entsprechenden Anfragen genutzt werden konnen. Weiter muss dazu bekannt sein, welche Anfragen auf welcher Schemaversion gestellt wurden, damit man wei , auf welche Schemaversion zuruckgerechnet werden muss. Zudem mussen auch alle Evolutionsschritte, die Schema S zu S0 transformieren, aufbewahrt werden, damit das Zuruckrechnen auf alte Versionen gelingt. Es ist auch moglich, die Evolutionsschritte zu komponieren und statt mehrerer Evolutionen nur die Kompositionen dieser zu speichern [ 11 ]. Dies verhindert jedoch das Berechnen der zwischenzeitigen Schemaversionen. Im allgemeinen Fall kann auf jeder Schemaversion Si mindestens eine Anfrage gestellt werden, fur welche wir die Reproduzierbarkeit voraussetzen wollen. Speichert man nur die s-t-TGD Ekomp, welche die Evolution von Si 1 uber Si nach Si+1 beschreibt, so ist es nicht mehr moglich Si selbst zu berechnen. Damit kann die Reproduzierbarkeit der Anfrage auf ihrer ursprunglichen Schemaversion nicht mehr gewahrleistet werden. Kommen jedoch Falle vor, bei denen zwischen zwei Schema-Evolution keine derartigen Auswertungen stattfanden, kann die Komposition der Evolutionsoperationen eingesetzt werden, um Zwischenschritte bei zukunftigen Berechnungen einzusparen.

Beispiel. Betrachten wir zur Veranschaulichung folgendes Anwendungsbeispiel. Gegeben sei die folgende Relation in Tabelle 3, sowie die Anfrage

P erson(vo; na; 18; an) ! Q(na; an): Aus Datenschutzgrunden soll das Alter in der nachsten Schemaversion in Altersbereiche eingeteilt werden. Dies geschehe durch folgende Evolutionsoperation

P erson(vo; na; al; an) ! P ersonAnon(vo; na; f (al); an): Der Altersbereich wird durch eine Funktion f bestimmt, welche das Alter in den entsprechenden Bereich (0 5; 6 10; :::) einteilt. Wir vernachlassigen hier die TIDs, da keine der

Vorname

Max Erika Paul

Name

Mustermann Musterfrau Muller

Alter

30 18 18

Anschrift

Parkstra e 3 Schlossallee 7 Hafenstra e 12

Tabelle 3: Person (I(S))

s-t-TGDs zu einem Zusammenfallen oder Aufsplitten von Tupel fuhrt und diese somit nie verandert werden. Zunachst berechnen wir durch den CHASE das Anfrageergebnis Q, welches uns Namen und Anschriften der Personen liefert, die 18 Jahre alt sind (Tabelle 4). Anschlie end fuhren wir den CHASE mit der invertierten Anfrage

Q(na; an) ! 9V o : P erson(V o; na; 18; an)

Name

Musterfrau Muller

Anschrift

Schlossallee 7 Hafenstra e 12

Tabelle 4: Anfrageergebnis Q

auf dem Anfrageergebnis aus und erhalten somit die Menge derjenigen Tupel, die an der Anfrage beteiligt waren (abgebildet in Tabelle 5). Danach berechnen wir I(S0). Hierfur

Vorname

Der hier vorgestellte Ansatz verwendet den CHASE-Algorithmus zur Sicherstellung der Reproduzierbarkeit von Anfragen unter Schema-Evolution. Bekannterweise terminiert der CHASE-Algorithmus im allgemeinem Fall nicht zwingend, wird aber an zwei stellen der Berechnung eingesetzt. Im hier gezeigten Anwendungsfall ist die Terminierung allerdings garantiert. Grund dafur ist, dass in diesen CHASEPhasen Ziel- und Quellschemata strikt getrennt sind, sodass auch neu generierte Werte nicht wahrend der selben CHASE-Anwendung gelesen werden und somit niemals Zyklen entstehen konnen.

Die Berechnung der nachfolgenden Schemaversion schlie t die Berechnung neuer TIDs ein. Da diese stets eindeutig sein mussen, und nachfolgend bei der Ruckrechnung in alte Schemaversionen rekonstruiert werden mussen, schlagen wir vor dies uber eine s-o-Abhangigkeit zu losen, die neue eindeutige Werte (z. B. in Form von UUIDs) liefert. Diese wiederum werden in einer Hilfstabelle abgelegt, um die Invertierung von Abhangigkeiten zu unterstutzen. Dies stellt eine Erweiterung des Standard-CHASE da, welche es erlaubt zur Laufzeit neue Konstanten zu generieren. In unserem Fall ist dies vergleichbar mit einer EGD, deren Kopf neben einer Variable auch eine Konstante enthalt. Diese wird durch eine gesonderte Methode im Programm berechnet und uberpruft die Eingabe auf ihren Typ bezuglich des CHASE. Handelt es sich um eine Konstante, soll diese selbst zuruckgegeben werden (TID bereits generiert). Bei einem Nullwert wird eine neue TID zuruckgegeben, welche fortan in allen Tupeln den entsprechenden Nullwert ersetzt.

AUSBLICK

In diesem Beitrag haben wir einen Ansatz vorgestellt, um mit Hilfe des CHASE Daten zu identi zieren, die durch eine Schema-Evolution nicht ausreichend abgebildet werden, um bestimmte Anfragen zu reproduzieren. Die hier gezeigte Vorgehensweise lie e sich in den Evolutionsprozess einbinden, um nur diejenigen Daten aufzubewahren, welche fur die Reproduzierbarkeit ausgewahlter Anfragen relevant sind. Hierbei haben wir jedoch nur die Schema- und keine Datenevolution betrachtet, sodass der hier vorgestellte Ansatz A nderungen der Daten au erhalb von Schema-Evolution nicht berucksichtigt.

Eine o ene Frage ist weiter, wie mit mehreren SchemaEvolution umgegangen werden kann. Tupel der Schemaversion Si+1, die fur eine ausgewahlte Anfrage Q des Schemas Si relevant sind, mussen auch beim U bergang in die Schemaversion Si+2 ausreichend abgebildet werden, sodass Q immer noch reproduzierbar ist. Der hier vorgestellte Algorithmus bietet dafur keine U berprufung. Die Komposition der Evolutionsoperationen von Schema Si zu Si+2 kann genutzt werden, um dies zu erreichen. Allerdings ist die Berechnung der Kompositionen uber alle Schemaversionen und das U berprufen fur jede gewahlte Anfrage vorheriger Schemaversionen ein gro er Aufwand, welcher bei jeder Evolution betrieben werden muss. Wunschenswert ist eine Variante, welcher das aktuelle Schema genugt, um diese U berprufung der nachsten Evolution durchzufuhren, z. B. durch Annotation entsprechender Tupel und Attribute.

Eine weitergehende Fragestellung ist, wie wir den hier fur einen Anwendungsfall vorgestellten BACKCHASE-Prozess fur verschiedene Anwendungsfalle (in Abschnitt 2 Anwendungsfalle 1 bis 4) vereinheitlichen konnen, da wir alle Anwendungen mit einem einheitlichen CHASE&BACKCHASETool (ChaTEAU, [ 3 ]) unterstutzen wollen.

LITERATUR

References

[1] T. Auge and A. Heuer . Combining Provenance Management and Schema Evolution . In IPAW, volume 11017 of Lecture Notes in Computer Science, pages 222 { 225 . Springer, 2018 .

[2] T. Auge and A. Heuer . The Theory behind Minimizing Research Data: Result equivalent CHASE-inverse Mappings . In LWDA , volume 2191 of CEUR Workshop Proceedings , pages 1 { 12. CEUR-WS.org, 2018 .

[3] T. Auge and A. Heuer . ProSA - using the CHASE for provenance management . In ADBIS , volume 11695 of Lecture Notes in Computer Science, pages 357 { 372 . Springer, 2019 .

[4] T. Auge , E. Manthey , S. Jurgensmann, S. Feistel, and A. Heuer . Schema evolution and reproducibility of long-term hydrographic data sets at the IOW . In LWDA , volume 2738 of CEUR Workshop Proceedings , pages 258 { 269 . CEUR-WS.org, 2020 .

[5] M. Benedikt , G. Konstantinidis, G. Mecca , B. Motik , P. Papotti , D. Santoro , and E. Tsamoura . Benchmarking the Chase . In PODS , pages 37 { 52 . ACM, 2017 .

[6] P. Buneman , S. Khanna , and W. C. Tan . Why and Where: A Characterization of Data Provenance . In ICDT , volume 1973 of Lecture Notes in Computer Science , pages 316 { 330 . Springer, 2001 .

[7] J. Cheney , L. Chiticariu , and W. C. Tan . Provenance in Databases: Why, How, and Where . Found. Trends Databases , 1 ( 4 ): 379 { 474 , 2009 .

[8] C. Curino , H. J. Moon , and C. Zaniolo . Graceful database schema evolution: the PRISM workbench . Proc. VLDB Endow ., 1 ( 1 ): 761 { 772 , 2008 .

[9] A. Deutsch and R. Hull . Provenance-Directed Chase & Backchase . In In Search of Elegance in the Theory and Practice of Computation , volume 8000 of Lecture Notes in Computer Science, pages 227 { 236 . Springer, 2013 .

[10] R. Fagin , P. G. Kolaitis , R. J. Miller , and L. Popa . Data exchange: semantics and query answering . Theor. Comput. Sci. , 336 ( 1 ): 89 { 124 , 2005 .

[11] R. Fagin , P. G. Kolaitis , L. Popa , and W. C. Tan . Schema Mapping Evolution Through Composition and Inversion . In Schema Matching and Mapping, Data-Centric Systems and Applications , pages 191 { 222 . Springer, 2011 .

[12] F. Geerts , G. Mecca, P. Papotti , and D. Santoro . Mapping and cleaning . In ICDE , pages 232 { 243 . IEEE Computer Society, 2014 .

[13] S. Greco , C. Molinaro , and F. Spezzano . Incomplete Data and Data Dependencies in Relational Databases . Synthesis Lectures on Data Management . Morgan & Claypool Publishers, 2012 .

[14] T. J. Green , G. Karvounarakis , and V. Tannen . Provenance semirings . In PODS , pages 31 { 40 . ACM, 2007 .

[15] A. Heuer , G. Saake, and K. Sattler . Datenbanken - Implementierungstechniken, 4. Au age. MITP , 2019 .

[16] M. Meier . The backchase revisited . VLDB J ., 23 ( 3 ): 495 { 516 , 2014 .

[17] M. L. Mo ller, S. Scherzinger, M. Klettke , and U. Sto rl. Why It Is Time for Yet Another Schema Evolution Benchmark - Visionary Paper . In CAiSE Forum , volume 386 of Lecture Notes in Business Information Processing , pages 113 { 125 . Springer, 2020 .

[18] F. Rose . Erweiterung des CHASE-Werkzeugs ChaTEAU um eine BACKCHASE-Phase . Masterarbeit, Universitat Rostock, DBIS, 2020 .

[19] F. Rose and A. Heuer . Der BACKCHASE zur Unterstutzung von Data Provenance und Schema-Evolution . Technical Report CS 02-21 , Institut fur Informatik, Universitat Rostock , 2021 . Langfassung dieses Artikels.