copyrightbox

# Enhanced Inversion of Schema Evolution with Provenance

Tanja Auge<EMAIL_ADDRESS>University of RostockRostockGermany and
Andreas Heuer<EMAIL_ADDRESS>University of
RostockRostockGermany

###### Abstract.

Long-term data-driven studies have become indispensable in many areas of
science. Often, the data formats, structures and semantics of data change over
time, the data sets evolve. Therefore, studies over several decades in
particular have to consider changing database schemas. The evolution of these
databases lead at some point to a large number of schemas, which have to be
stored and managed, costly and time-consuming. However, in the sense of
reproducibility of research data each database version must be reconstructable
with little effort. So a previously published result can be validated and
reproduced at any time.

Nevertheless, in many cases, such an evolution can not be fully reconstructed.
This article classifies the 15 most frequently used schema modification
operators and defines the associated inverses for each operation. For avoiding
an information loss, it furthermore defines which additional provenance
information have to be stored. We define four classes dealing with dangling
tuples, duplicates and provenance-invariant operators. Each class will be
presented by one representative.

By using and extending the theory of schema mappings and their inverses for
queries, data analysis, why-provenance, and schema evolution, we are able to
combine data analysis applications with provenance under evolving database
structures, in order to enable the reproducibility of scientific results over
longer periods of time. While most of the inverses of schema mappings used for
analysis or evolution are not exact, but only quasi-inverses, adding
provenance information enables us to reconstruct a sub-database of research
data that is sufficient to guarantee reproducibility.

Chase-Inverses, Schema Evolution, Data Provenance, Research Data Management,
Reproducibility

##  1\. Introduction

Research institutions all around the world produce huge amounts of research
data, which have to be managed by research data management. This includes
collecting, evaluating, analyzing, archiving, and publishing the original or
processed research data as well as the results of (data) analyses, theoretical
considerations, or other scientific investigations. In this paper we are
focusing on structured data, represented as a relational database, generated
in scientific experiments, measurement series or always-on sensors.

The presentation and publication of research results increasingly requires
publishing the corresponding research data, which ensures the findability,
accessibility, inter-operability, and re-usability in the sense of FAIR-
Principles111https://www.go-fair.org/. FAIR does not require the publication
of all source data. It is sufficient to specify the source tuples necessary
for the calculation of a specific research result. To perform this
calculation, we use the so-called Chase algorithm supplemented with provenance
information such as witness bases (BKT01, ), provenance polynomials (GKT07, )
and/or additional side tables.

The Chase is a procedure that modifies a database instance $I$ by
incorporating a set of dependencies $\Sigma$ represented as (s-t) tgds or
egds. Originally developed for database design and semantic query
optimization, the Chase nowadays is also used for database applications such
as data exchange, data integration or answering queries using views.
Formulated as schema mapping $\mathcal{M}=(I,J,Q)$ using s-t tgds, i.e. a
dependency from one database $I$ into a second database $J$, the Chase can
process database queries $Q$. This is equivalent to a mapping from red to
green in Figure 1. Thus, the Chase can be used for evaluating conjunctive
queries or simple SQL queries, such as SELECT n,m FROM F,S WHERE F.m=S.m. We
call these queries against the research data evaluation queries.

Figure 1. Chasing evaluation queries and evolution mappings

In addition, the Chase can be used for inverting queries. For this, we choose
$J$ as database instance and the inverse evaluation query $Q^{-1}$ as schema
mapping $\mathcal{M}^{\ast}=(J,I,Q^{-1})$ formalized as s-t tgd like before.
Running both evaluation query and inversion in sequence, this results in a
Chase&Backchase process (DPT99, ). Here the Backchase phase corresponds to a
second Chase phase with the Chase result of the first phase as input. However,
the result
$I^{\ast}=\textsc{Chase}_{\mathcal{M}^{\ast}}(\textsc{Chase}_{\mathcal{M}}(I))$
after applying Chase&Backchase to $I$, $I^{\ast}$ may not be equal to $I$. In
general, $I^{\ast}$ is a subset of $I$, called (minimal) sub-database
(highlighted in red, Figure 1). The corresponding inverse, calculated with the
Chase is called Chase-inverse. Such inverses are not necessarily exact and
unique. They are so-called pseudo-inverse functions of different granularity
(FKPT11, ; AH18b, ).

In research data management, not only the data is changing (e.g. by adding
results of new experiments), but also the data’s schemas. Changing schemas
often results in freezing the entire research database to be able to perform
the evaluation queries used so far. However, this can be time-consuming,
expensive and leads to a dramatically increasing amount of data to be
archived. Formulating a schema evolution $E$ as a schema mapping by s-t tgds
allows processing it by the Chase just like the evaluation queries before. The
composition of inverse evolution steps and original evaluation queries now
enables the reconstruction of research data for changing database structures,
summarized in Figure 1.

At first glance, choosing the Chase algorithm may seem a bit unusual, but the
choice has some significant benefits:

  1. (1)

Both schema evolution and simple evaluation queries can be interpreted as
schema mappings and processed with the Chase algorithm (FKPT11, ). So, both
mappings can be treated with the same theory.

  2. (2)

An elaborated theory about quasi-inverses of schema mappings as well as their
composition already exists (FKPT08, ; FKPT11, ).

  3. (3)

An examination of different types of inverses of the evaluation queries can be
found in (AH18b, ). It can be improved by additional provenance information.
This allows the reconstruction of lost null tuples and duplicates, as well as
the replacement of null values by concrete values.

Interpreting evolution and evaluation as schema mapping and processing by
Chase&Backchase enables the reconstruction of a research result even in the
presence of changing database structures (see Figure 1). For this, an
evolution mapping, represented as schema modification operator, an evaluation
query as well as the two inverses are formulated as s-t tgds. The Chase
calculates the query result, which is then processed by the Backchase. This
provides the (minimal) sub-database in question (highlighted in red).

The inverse type can be used to determine how much and what part of the
original data can be recovered without additional effort. In (AH18b, ) the
Chase-inverse types of 14 typical evaluation operators were specified with and
without using data provenance. Provenance deals with the traceability of a
result back to its original, possibly physical object. In the case of data
provenance, we are interested in where a result tuple comes from, why and how
it is calculated. In (AH18b, ), it is observed that provenance improves the
inverse types in about half of the cases.

In this article, we will perform this analysis for the evolution. For this
purpose, we are looking at 15 schema modification operators, which are
particularly common in practice (CMZ08, ; CMTZ08, ; AMJFH20, ; GZ12, ; WN11, ;
QLS13, ), and verify their invertibility. Then we improve the inverse type
again by adding provenance. This again improves about half of the cases. Other
approaches for combining schema evolution and provenance are given in (GAMH10,
) and (GZ12, ). In total, we identify four classes of invertibility. For each
class we consider one representative in more detail (see Table 2).

### Structure of the Article

To determine the relevant original tuples, we use the Chase algorithm not only
for processing an evaluation query but also for evolution, see Section 3. For
this purpose, in Section 4, we divide schema modification operators into four
classes and examine five representatives with respect to their Chase-inverses
with and without additional provenance information. Before that, in Section 2,
we introduce the necessary definitions regarding Chase and data provenance.

##  2\. Basics and Related Work

This article combines Chase, inverse schema mappings and data provenance from
different areas of database theory. We introduce the most important terms
here, further details can be found in the respective literature.

### Chase

The Chase algorithm is a technique used in a number of data management tasks
like data exchange, data cleaning or answering queries using views. Its wide
range of applicability can be attributed to the fact that Chase generalizes
well. Generally speaking, it incorporates a set of dependencies $\ast$ into a
given object $\bigcirc$ – usually an instance or a query. Only condition: The
dependencies must be representable as (s-t) tgds and egds.

A source-to-target tuple generating dependency (s-t tgd) is a formula of the
form $\forall x:(\phi(x)\rightarrow\exists y:\psi(x,y))$, with $x$,$y$ tuples
of variables, and $\phi(x)$, $\psi(x,y)$ are conjunctions of atoms, called
body and head. It can be seen as inter-database dependency, representing a
constraint within a database. An intra-database dependency is called tuple
generating dependency (tgd). A dependency with equality atoms in the head
equality generating dependency (egd).

In the case of instances, chasing (s-t) tgds create new tuples and chasing
egds clean the database by replacing null values (by other null values or
constants). So, the Chased database satisfies all dependencies of $\ast$. We
use the Chase to process schema evolution. Thus, we deal with inter-database
mapping and can restrict ourselves to s-t tgds in the following. Since chasing
s-t tgds always terminates, we refer to (BKT17, ; GMS12, ) for further
explanations about Chase variants and termination criteria.

Table 1. Sufficient and necessary conditions of Chase-inverses, based on
(FKPT11, ; AH18b, )

Chase-inverse | sufficient condition | necessary condition
---|---|---
exact ($=$) | $I=I^{\ast}$ | $I^{\ast}=I$
classical ($\equiv$) | $=$ |  $\exists$ homomorphism $h$ : $I^{\ast}\rightarrow I$, $\exists$ homomorphism $h^{\prime}$ : $I\rightarrow I^{\ast}$
tp-relaxed $(\preccurlyeq_{\textrm{tp}})$ | $=$ |  $\exists$ homomorphism $h$ : $I^{\ast}\rightarrow I$, $\mid I^{\ast}\mid=\mid I\mid$, $I^{\ast}\leftrightarrow_{\mathcal{M}}I$
relaxed ($\preccurlyeq$) |  $\preccurlyeq_{\textrm{tp}}$ or $\equiv$ |  $\exists$ homomorphism $h$: $I^{\ast}\rightarrow I$, $I^{\ast}\leftrightarrow_{\mathcal{M}}I$
result equivalent ($\leftrightarrow$) | $\preccurlyeq$ | $I^{\ast}\leftrightarrow_{\mathcal{M}}I$

### Chase-inverse functions

Let $I$ and $J$ be two database instances before and after applying the Chase,
i.e. $J=\textsc{Chase}(I)$. A Chase-inverse is a function from $J$ to
$I^{\ast}$, which applies the Chase algorithm to $J$ with $I^{\ast}$ section
of $I$. $I^{\ast}$ is a section of $I$ (short: $I^{\ast}\preccurlyeq I$) iff a
homomorphism $h:I^{\ast}\rightarrow I$ exists, whereby constants are mapped to
constants and null values are mapped to constants or (other) null values
(AH18b, ). Chase-inverse functions belong to the quasi-inverse functions.
Formally, we call $g:I^{\ast}\rightarrow I$ a quasi-inverse function to
$f:I\rightarrow J$ iff $I^{\ast}\preccurlyeq I$ and $f\circ g\circ f=f$
(FKPT08, ). This means that quasi-inverse functions usually recover the
original data only partially. In the case of Chase five inverse types are
distinguish: exact, classical, relaxed (FKPT11, ), tuple-preserving relaxed
and result equivalent (AH18b, ). The sufficient and necessary conditions of
the different Chase-inverse types can be seen in Table 1.

For this, let $\mathcal{M}$ be a schema mapping, $I$ and $I^{\ast}$ two
database instances with
$I^{\ast}=\textsc{Chase}_{\mathcal{M}^{\ast}}(\textsc{Chase}_{\mathcal{M}}(I)).$
$I^{\ast}$ is called sub-database of $I$. A schema mapping $\mathcal{M}$ can
be formalized as a triple $(S_{t},S_{t+1},\Sigma)$ with $S_{t}$ source schema,
$S_{t+1}$ target schema and $\Sigma$ set of dependencies that specify the
relationship between $S_{t}$ and $S_{t+1}$. The affiliated inverse mapping is
defined as $\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$. The star ∗
symbolizes that the inverse function $\mathcal{M}^{\ast}$ may not be exact or
unique. Again it is a quasi-inverse function.

While an exact Chase-inverse ($=$) reconstructs the original database instance
$I$, i.e. $I^{\ast}=I$, the classical Chase-inverse ($\equiv$) only returns an
instance $I^{\ast}$, which is equivalent to the original database instance
$I$, i.e. $I^{\ast}$ and $I$ are equal except for isomorphism. The relaxed
Chase-inverse ($\preccurlyeq$) does not require an equivalent relationship
between the original instance $I$ and the recovered instance $I^{\ast}$, but
data exchange equivalence (short: ${I\leftrightarrow_{\mathcal{M}}I^{\ast}}$)
and the existence of a homomorphism between $I^{\ast}$ and $I$ (FKPT08, ).

To preserve the number of tuples, the definition of relaxed Chase-inverse is
extended (AH18b, ). The corresponding function, called tp-relaxed Chase-
inverse ($\preccurlyeq_{\textrm{tp}}$), additionally requires
$\mid\\!I^{\ast}\\!\mid=\mid\\!I\\!\mid$. In contrast, a weakened definition
is the result equivalent Chase-inverse ($\leftrightarrow$), which only
satisfies data exchange equivalence, i.e.
$\textsc{Chase}_{\mathcal{M}}(I)\equiv\textsc{Chase}_{\mathcal{M}}(I^{\ast})$.

As studied in (AH18b, ), evaluation queries formalised as s-t tgds and applied
by Chase are classified as exact, (tp-)relaxed or result equivalent depending
on query under consideration. The addition of provenance information like
provenance polynomials (GT17, ) and (minimal) witness basis (BKT01, ) allows
the specification of stronger Chase-inverses than without. For example, in the
case of projection or union, a stronger Chase-inverse can be constructed by
using provenance. For other operations, such as selection, the inverse type
can not be improved despite additional information.

### Chase&Backchase

A schema mapping can be processed using the Chase and be inverted using the
Backchase (DPT99, ). The Chase phase computes a modified instance $J$
generated from $I$ by applying the Chase using a schema mapping
$\mathcal{M}=(S_{t},S_{t+1},\Sigma)$. After that, the Backchase phase computes
an instance $I^{\ast}$ by applying the Chase to $J$ using a schema mapping
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$:

$I^{\ast}=\underbrace{\textsc{Chase}_{\mathcal{M}^{\ast}}(J)}_{\textsc{Backchase}}=\textsc{Chase}_{\mathcal{M}^{\ast}}(\underbrace{\textsc{Chase}_{\mathcal{M}}(I)}_{\textsc{Chase}}).$

The calculated instance $I^{\ast}$ can, but must not be sub-database of $I$,
short $I^{\ast}\preccurlyeq I$. This depends on the inverse type defined
above.

### Data Provenance

Depending on the authors (see (HDL17, ) or (PRSA18, )), a distinction is made
between different types of provenance. These include data provenance, workflow
provenance and metadata provenance. The questions to be answered depend on the
provenance type and can be answered in different ways. In this article, we
will focus on data provenance.

Let be $I$ database instance and $Q$ query. Data provenance describes (1)
where a result tuple $r\in Q(I)$ does come from, (2) why and (3) how $r$
exists in the result $Q(I)$. This can be answered extensively by specifying
concrete tuples and database values, intensionally by characterizing a set of
database values (Mot89, ) or query-based by query transformation (BHT14, ). We
consider only extensional answers.

The so-called why-provenance (BKT01, ) specifies a witness basis that
identifies the tuples involved in the calculation of $r$. This tuple-based
basis contains all ids necessary for reconstructing $r$. How-provenance, on
the other hand, uses provenance polynomials (GT17, ; Sel17, ) to explain how a
result tuple $r$ is calculated. The polynomials are defined by a commutative
semi-ring $(\mathbb{N}[X],+,\cdot,0,1)$ with $+$ for union and projection, as
well as $\cdot$ for natural join (GKT07, ). If we are simply interested in
identifying ID or relation name of the tuples involved, we choose where-
provenance. It is the weakest of the three provenance questions, but is
already sufficient in many cases.

### Schema Evolution

Schema evolution deals with the problem of maintaining schema and
functionality of a software system considering a changing data structure. It
can be addressed by so-called Schema Modification Operators (SMOs) that
support semantic conversion of columns, column concatenation/splitting and
other schema modifications. Common operators in the case of research data
management include ADD Column and MERGE Column as well as SPLIT Column
(AMJFH20, ). Other applications are described in (QLS13, ; WN11, ). For
initial approaches to combining schema evolution and provenance, see (GAMH10,
) and (CMZ08, ).

##  3\. SMOs and their Chase-inverses

Especially in the case of long-term data-driven studies, the specification of
source data may become a problem. Therefore, we process not only the
evaluation but also the evolution by the Chase&Back-chase and extend it with
data provenance. For this, we classify the 15 most frequently used schema
modification operators (SMOs) and divide them into four classes. We define the
associated inverses for each operation and examine it with additional
provenance information. While the first class includes all operators with an
exact inverse, i.e. the operators are provenance-invariant, the second and
third class deal with dangling tuples and duplicates. The remaining operators
we summarize in Class IV.

### Chase&Backchase

Evaluation queries and schema evolution can be defined as schema mappings. Let
be $S_{t}$, $S_{t+1}$ two database schemas and $\Sigma$, $\Sigma^{-1}$ two
sets of dependencies, whereby $\Sigma$ corresponds to an evaluation query $Q$
and $\Sigma^{-1}$ corresponds to an schema modification operator. Then the
evolution $E$ can be formalized as schema mapping
$\mathcal{M}=(S_{t},S_{t+1},\Sigma)$ and its corresponding inverse $E^{-1}$ as
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$. Let further be $I(S_{t})$
and $J(S_{t+1})$ two database instances. Then the Chase&Backchase calculates a
(minimal) sub-database

$I^{\ast}(S_{t})=\textsc{Chase}_{\mathcal{M}^{\ast}}(J(S_{t+1}))=\textsc{Chase}_{\mathcal{M}^{\ast}}(\textsc{Chase}_{\mathcal{M}}(I(S_{t})))$

(highlighted red in Figure 2). If we are not interested in processing the
entire instance $J$, we can alternatively process a subset $J^{\ast}\subset J$
in the Backchase (highlighted in blue). For simplicity, we will use $J$ in the
following. In summary, we state: Evolution is processed by the Chase in the
so-called Chase phase. The Backchase phase corresponds to the inversion of the
evolution.

Since we allow quasi-inverse functions to invert the evolution, we symbolize
the inverse mapping by ∗. The exact inverse mapping of $f$ used for merging
and splitting, on the other hand, is denoted by $f^{-1}$, which we consider as
additional provenance information.

Figure 2. Inverting schema evolution

### Schema Modification Operators

The atomic schema changes during an evolution can be represented by so-called
schema modification operators. Based on (CMZ08, ; CMTZ08, ; AMJFH20, ; GZ12, ;
WN11, ; QLS13, ) and more we define 15 frequently used operators, summarized
in Table 3. Some publications also speak of a sixteenth operator NOP, which
performs no action but namespace management.

Each operator has an associated (quasi-)inverse function. The invertibility of
an operator corresponds to the existence of a perfect or quasi-inverse and its
uniqueness. ADD Column, MERGE Column, RENAME Column, SPLIT Column, CREATE
Table, PARTITION Table, RENAME Table and NOP has a unique quasi-inverse
function. According to (CMZ08, ), DROP Table, COPY Table, MERGE Table and DROP
Column have one or more quasi-inverses. Our studies show that the SMO
formalization as s-t tgds always has a unique (quasi-)inverse. Therefore,
another inverse can exist only in the case of a second s-t tgd formalization.
However, this only applies to COPY Table and DECOMPOSE Table (see Table 3).

Table 2. SMOs with exact ${(=)}$, tp-relaxed $(\preccurlyeq_{\textrm{tp}})$,
relaxed ${(\preccurlyeq)}$ or result equivalent ${(\leftrightarrow)}$ Chase-
inverse extended by provenance (highlighted in orange); dangling tuples are
highlighted in magenta and duplicates in cyan

|  | Without Provenance | With Provenance
---|---|---|---
SMO | $\Sigma$ |  Type | $\Sigma^{-1}$ |  Type | $\Sigma^{-1}$ | Provenance
COPY Table | $R(a,b,c)\rightarrow R^{\prime}(a,b,c)\wedge V(a,b,c)$ | $=$ | $R^{\prime}(a,b,c)\wedge V(a,b,c)\rightarrow R(a,b,c)$ | $=$ | $R^{\prime}(a,b,c)\wedge V(a,b,c)\rightarrow R(a,b,c)$ |
| $R(a,b,c)\rightarrow R^{\prime}(a,b,c)$ | $=$ | $R^{\prime}(a,b,c)\rightarrow R(a,b,c)$ | $=$ | $R^{\prime}(a,b,c)\rightarrow R(a,b,c)$ |
| $R(a,b,c)\rightarrow V(a,b,c)$ |  | $V(a,b,c)\rightarrow R(a,b,c)$ |  | $V(a,b,c)\rightarrow R(a,b,c)$ |
JOIN Table | $R(a,b)\wedge V(a,c)\rightarrow T(a,b,c)$ | $=$ | $T(a,b,c)\rightarrow R(a,b)\wedge V(a,c)$ | $=$ | $T(a,b,c)\rightarrow R(a,b)\wedge V(a,c)$ |
|  | $\boldsymbol{\preccurlyeq}$ | $T(a,b,c)\rightarrow R(a,b)\wedge V(a,c)$ | $\preccurlyeq$ | $T(a,b,c)\rightarrow R(a,b)\wedge V(a,c)$ |  why, how
|  |  |  | ${\color[rgb]{1,.5,0}=}$ | $T(a,b,c)\rightarrow R(a,b)\wedge V(a,c)$ |  why, how
|  |  |  |  | \+ reconstruction of lost tuples | \+ side table
MERGE Table |  $R(a,b,c)\rightarrow T(a,b,c)$, | $\leftrightarrow$ |  $T(a,b,c)\rightarrow R(a,b,c)$, | $=$ |  $T(a,b,c)\rightarrow R(a,b,c)$, |  why, how
| $V(a,b,c)\rightarrow T(a,b,c)$ |  | $T(a,b,c)\rightarrow V(a,b,c)$ |  | $T(a,b,c)\rightarrow V(a,b,c)$ |
|  |  |  |  | \+ restriction to tuples of $R$ resp. $V$ |
MERGE Column | $R(a,b,c)\rightarrow T(a,f(b,c))$ | $\preccurlyeq_{\textrm{tp}}$ | $T(a,g)\rightarrow\exists D,E:R(a,D,E)$ | $\preccurlyeq_{\textrm{tp}}$ | $T(a,g)\rightarrow\exists D,E:R(a,D,E)$ |
|  | $\boldsymbol{\preccurlyeq}$ | $T(a,b)\rightarrow\exists D,E:R(a,D,E)$ | $\preccurlyeq_{\textrm{tp}}$ | $T(a,g)\rightarrow\exists D,E:R(a,D,E)$ |  why, how
|  |  |  |  | \+ reconstruction of lost tuples (duplicates) |
|  |  |  | $=$ | $T(a,g)\rightarrow R(a,f^{-1}(g,c),c)$ |  why, how
|  |  |  |  | \+ reconstruction of lost attribute values |  \+ inverse of $f$
|  |  |  |  |  | \+ side table
|  |  |  | $\boldsymbol{=}$ | $T(a,f(b,c))\rightarrow R(a,f^{-1}(g,c),c)$ |  why, how
|  |  |  |  | \+ reconstruction of lost tuples (duplicates) |  \+ inverse of $f$
|  |  |  |  | \+ reconstruction of lost attribute values | \+ side table

All operators can be easily formalized as set of one or at most two s-t tgds.
Similar to our formalization is for example the formalization of (CMZ08, ).
However, there is a crucial difference in the interpretation of MERGE Table.
The authors define this operator by $R(a,b,c)\rightarrow T(a,b,c)$,
$R(a,b,c)\rightarrow V(a,b,c)$ with associated inverse $T(a,b,c)\vee
V(a,b,c)\rightarrow R(a,b,c)$. Since Chase-inverses are not defined for
disjunctive embedded dependency, we consider only s-t tgds. However, the
information loss of using a s-t tgd here can be compensated by adding
additional provenance information.

Table 3. Schema modification operators with corresponding inverse and class

SMO | description | inverse | class
---|---|---|---
COPY Table | creates a duplicate of an existing table | DROP Table | I
|  | MERGE Table |
CREATE Table | introduces a new, empty table | DROP Table | I
DECOMPOSE Table | decomposes a source table into two tables without changing the data stored inside | ADD Column | III
|  | JOIN Table |
DROP Table | removes an existing table | CREATE Table | IV
JOIN Table | combines two tuples from different tables | DECOMPOSE Table | II
MERGE Table | takes two source tables and creates a new table that stores their union | PARTITION Table | IV
PARTITION Table | distributes tuples into two newly created tables according to the specified condition | MERGE Table | I
RENAME Table | changes a table name | RENAME Table | I
ADD Column | introduces a new column with values created by a user-defined constant or function | DROP Column | I
COPY Column | copies a column to another table according to the join condition | DROP Column | I
DROP Column | removes an existing column from a table | ADD Column | III
MERGE Column | sequence of ADD Column and DROP Column using a user-defined function | SPLIT Column | III
MOVE Column | same like COPY Column, but the original column is deleted | MOVE Column | II, III
RENAME Column | changes the name of a column | RENAME Column | I
SPLIT Column | sequence of ADD Column and DROP Column using a user-defined function | MERGE Column | III
NOP | nothing happens | NOP | I

Some operators such as PARTITION Table, COPY Column and MOVE Column require
special conditions $\textsf{cond}_{A}$, which give restrictions on the
attributes. The corresponding s-t tgds are restricted to constant and
attribute selection $\sigma_{A_{i}\theta c}$ or rather $\sigma_{A_{i}\theta
A_{j}}$ with $\theta\in\\{<,\leq,=,\geq,>\\}$. Other conditions can be
formalized using additional side tables.

Side tables contain attribute values required for the reconstruction of the
(minimal) sub-database defined above. Each tuple is a restriction of a source
tuple $t$ and is uniquely identified by its ID $r_{t}$. This ID is not used as
a key, but as additional provenance information. Thus, side tables always
exist only in association with a witness basis or a provenance polynomial.

### Inverse Types

Adding Provenance may improve the inverse type. However, in many cases this is
not necessary at all. Thus, about half of the operators already guarantee an
exact Chase inverse without requiring additional information. The associated
operators – COPY Table, CREATE Table, PARTITION Table, RENAME Table, ADD
Column, COPY Column and RENAME Column plus NOP group together to form Class I.
In the case of the remaining operators, additional provenance causes an
improvement of the inverse type.

To cover the scope of Chase-inverse types as well as their provenance
extensions, and to cover special cases such as dangling tuples and duplicates,
we focus our analyses here on COPY Table (Class I), JOIN Table (Class II),
MERGE Table (Class IV) and MERGE Column (Class III). The results are
summarized in Table 2. Each operator as well as its associated inverse is
formalized as schema mapping $\mathcal{M}=(S_{t},S_{t+1},\Sigma)$ respectively
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$ with $\Sigma$ (column 2) and
$\Sigma^{-1}$ (columns 4 and 6) sets of s-t tgds. The inverse types are
summarized in column 3 and 5. The last three columns describe the facts
including additional provenance.

Splitting, merging or deleting columns often creates lost tuples. Tuples can
also be eliminated when joining tables. Thus, we distinguish two cases:
duplicates (Table 2, highlighted in cyan) and dangling tuples (highlighted in
magenta). Duplicates are generated by the operators DECOMPOSE Table, DROP
Column, MERGE Column, MOVE Column and SPIT Column. They are summarized in
Class III. Since MOVE Column may produce dangling tuples as well as
duplicates, this operator is also part of Class II, along with JOIN Table.
Except for DROP Table and PARTITION Table, all operators are thus assigned to
one of the classes 1 to 3. These form class IV, the class of further
operators.

As seen in Table 2, the formalization of some operators as set of s-t tgds is
not always unique. Thus, COPY Table, DECOMPOSE Table, ADD Column and COPY
Column can be represented in two different ways. The choice of the
representation influences the resulting Chase-inverse type as well as type of
the underlying dependencies. Even additional provenance information may affect
the type.

### Inverse Types using Provenance

Reconstructing lost attribute values in JOIN Table provides an exact Chase-
inverse instead of a relaxed inverse, whereas the restriction to the relevant
tuples in MERGE Table provides an exact Chase-inverse instead of a result-
equivalent. Also, in the case of MERGE Column, additional provenance
information can be used to improve the Chase-inverses significantly. Knowing
the witness bases or provenance polynomials allows the reconstruction of
duplicates. If we also know the inverse of function $f$ and store lost
attribute values in a separate side table, it is also possible to specify an
exact Chase inverse. Thus, provenance enables, among other things, the
reconstruction of lost tuples (duplicates) and attribute values.

All in all, we obtain four classes: Class I contains all operators whose
inverse type does not change due to additional provenance information. The
operators of Class II and Class III deal with dangling tuples or duplicates.
Here additional witness basis, provenance polynomials and side tables are
indispensable. The remaining two operators are summarized in Class IV. The
results of Table 2 are described in detail in Section 4.

### Composition of several SMOs

Since the SMOs operate independently within a sequence, we can determine the
inverses in isolation from each other. So, the inverse mapping of composition

$\mathcal{M}^{\ast}=(\mathcal{M}_{1}\circ...\circ\mathcal{M}_{n})^{-1}=\mathcal{M}^{\ast}_{n}\circ...\circ\mathcal{M}^{\ast}_{1}$

results in a composition of the inverse sub-operations
$\mathcal{M}^{\ast}_{1},...,\mathcal{M}^{\ast}_{n}$. Thus, the inverse type of
$\mathcal{M}^{\ast}$ corresponds to the type of the weakest partial inverse
$\mathcal{M}^{\ast}_{i}$. If no inverse exists for one of the partial
operations $\mathcal{M}_{i}$, neither for its composition
$\mathcal{M}=\mathcal{M}_{1}\circ...\circ\mathcal{M}_{n}$.

For example, MERGE Column is defined as a sequence of ADD Column and DROP
Column operators. DROP Column has a (tp-)relaxed Chase-inverse depends on
whether duplicates exist and additional provenance is used. ADD Column, on the
other hand, always has an exact Chase-inverse. So, the inverse type of MERGE
Column corresponds to the inverse type of DROP Column. This results in tp-
relaxed inverse with additional provenance and a relaxed inverse without.
Adding side tables we can define an exact Chase-inverse, such as summarized in
Table 2. Same applies for SPLIT Column and other user-defined operators.

$R$: | id | name |  |  $V$: | name | subject |
---|---|---|---|---|---|---|---
| 1 | Alice | $r_{1}$ |  | Alice | Math | $s_{1}$
| $\boldsymbol{2}$ | $\boldsymbol{Bob}$ | $r_{2}$ |  | Alice | IT | $s_{2}$
$\scriptstyle{\textsc{Chase}_{\mathcal{M}}}$ $T$: | id | name | subject |
---|---|---|---|---
| 1 | Alice | Math | $r_{1}\cdot s_{1}$
| 1 | Alice | IT | $r_{1}\cdot s_{2}$

\+  id name $\boldsymbol{2}$ $\boldsymbol{Bob}$ $r_{2}$
$\scriptstyle{\textsc{Chase}_{\mathcal{M}^{\ast}}}$ $R$: id name $V$: name
subject 1 Alice Alice Math 2 Bob Alice IT

Figure 3. JOIN Table with dangling tuple (highlighted in magenta); extended by
provenance (highlighted in orange) and side table (highlighted in gray)

### Similarities to Query Evaluation

Processed by the Chase schema modification and evaluation queries have similar
characteristics. MERGE Table, for example, corresponds to union $\cup$,
PARTITION Table to constant or attribute selection $\sigma_{A_{i}\theta c}$
respectively $\sigma_{A_{i}\theta A_{j}}$, and JOIN Table refers to the
natural join $\bowtie$. It follows that the inverse types match those of
(AH18b, ). In the case of evaluation queries, about half of the inverses can
be improved by additional provenance information. The same is true for
evolution. In both cases, the (tp)-relaxed Chase-inverse dominates. However,
an exact Chase-inverse occurs considerably more frequently in evolution than
in evaluation query inversion, see Table 2 and (AH18b, ).

##  4\. The four Classes of SMOs

The most common scheme modifications can be summarized in 15 schema
modification operators (SMOs). Some operators have an exact inverse function,
but the majority does not. Their inverses are quasi-inverses of the types
(tp-)relaxed ($\preccurlyeq_{\textrm{tp}}$) or result equivalent
($\leftrightarrow$). Remedy here is the addition of provenance, which improves
this Chase-inverse type in many cases. For this we distinguish four different
classes of SMOs: provenance invariant (Class I), dangling tuples (Class II),
duplicates (Class III), and special SMOs (Class IV). We will examine the four
classes one by one. For this, we formulate generally valid Lemmas, one for
each class. Each class is presented by one representative.

Let be $R$, $V$ and $T$ three relations over the attributes id, name and
subject. The concrete schemas are given directly in the respective proof. Let
further be $r_{i}$ tuple ID of $i$-th tuple, $w_{j}$ witness basis and $p_{j}$
provenance polynomial. For a source instance $I$,
$J=\textsc{Chase}_{\mathcal{M}^{\ast}}(I)$ is called evaluation result and
$I^{\ast}=\textsc{Chase}_{\mathcal{M}^{\ast}}(J)=\textsc{Chase}_{\mathcal{M}^{\ast}}(\textsc{Chase}_{\mathcal{M}}((I))$
(minimal) sub-database of $I$.

### Class I: Provenance Invariant

Adding provenance does not always change the Chase-inverse type. This affects
about half of the classified evolution operations. Specifically, these include
the SMOs COPY Table, CREATE Table, PARTITION Table and RENAME Table as well as
ADD Column, COPY Column and RENAME Column. All SMOs of this class have an
exact Chase-invers.

###### Lemma 4.0.

Let $\mathcal{M}=(S_{t},S_{t+1},\Sigma)$ be a schema mapping of Class I. Then
the corresponding inverse function
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{\ast})$ is always an exact or
relaxed Chase-inverse independent of additional provenance information.

###### Proof.

W.l.o.g. we will prove the statement for COPY Table. This SMO can be
formalized in two different ways. It can be represented both as one or as a
set of two s-t tgds. Here we consider the first case. Let
$\mathcal{M}=(S_{t},S_{t+1},\Sigma)$ and
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$ be two schema mapping with

$\displaystyle\Sigma$ $\displaystyle=$ $\displaystyle\\{R(a,b,c)\rightarrow
R^{\prime}(a,b,c)\wedge V(a,b,c)\\},$ $\displaystyle\Sigma^{-1}$
$\displaystyle=$ $\displaystyle\\{R^{\prime}(a,b,c)\wedge V(a,b,c)\rightarrow
R(a,b,c)\\}$

that formalizes Copy Column and its inverse mapping. W.l.o.g. let $R$ and $V$
each be restricted to three attributes. Let further
$I=\\{R(x_{i_{1}},x_{i_{2}},x_{i_{3}})\bigm{|}i\in\mathbb{N}\\}$ be an
arbitrarily chosen source instance. Chasing $\mathcal{M}^{\ast}$ after chasing
$\mathcal{M}$ yields:

$\displaystyle I^{\ast}$ $\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{-1}}(\textsc{Chase}_{\mathcal{M}}(I))$
$\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{-1}}(\textsc{Chase}_{\mathcal{M}}(\\{R(x_{i_{1}},x_{i_{2}},x_{i_{3}})\bigm{|}i\in\mathbb{N}\\}))$
$\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{-1}}(\\{R^{\prime}(x_{i_{1}},x_{i_{2}},x_{i_{3}}),V(x_{i_{1}},x_{i_{2}},x_{i_{3}})\bigm{|}i\in\mathbb{N}\\})$
$\displaystyle=$
$\displaystyle\\{R(x_{i_{1}},x_{i_{2}},x_{i_{3}})\bigm{|}i\in\mathbb{N}\\}$
$\displaystyle=$ $\displaystyle I$

Thus, we have no loss of information and obtain an exact Chase-inverse. Since
we can already guarantee an exact inverse, adding provenance, i.e. additional
witness bases or provenance polynomials over the source IDs, is not necessary
here. We do not receive any additional or necessary information from it. ∎

In addition to COPY table, COPY Column can also be formalized in two different
ways. In both cases an exact Chase-inverse can be specified. For all other
SMOs of Class I only one formalization exists, witch guarantees an exact Chase
inverse with and without using additional provenance.

### Class II: Dangling Tuples

Depending on the source instance, dangling tuples may occur. In this case an
exact Chase-inverse can not be guaranteed. Also, the addition of witness bases
and provenance polynomials may not be sufficient in some cases. However, if we
note the lost tuples in so-called side tables, we can also specify exact
Chase-inverses. This concerns the SMOs JOIN table and MOVE Column.

###### Lemma 4.0.

Let $\mathcal{M}=(S_{t},S_{t+1},\Sigma)$ be a schema mapping of Class II. Then
the corresponding inverse function
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{\ast})$ is exact if we do not have
dangling tuples. However, if such tuples are present, the Chase-inverse can be
defined as result equivalent or relaxed. By using provenance as well as
additional side tables, we can specify an exact Chase inverse, too.

We will take a closer look at JOIN Table. For this, let be
$\mathcal{M}=(S_{t},S_{t+1},\Sigma)$ and
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$ two schema mappings with

$\displaystyle\Sigma$ $\displaystyle=$ $\displaystyle\\{R(a,b)\wedge
V(c,d)\wedge b=d\rightarrow T(a,b,c)\\},$ $\displaystyle\Sigma^{-1}$
$\displaystyle=$ $\displaystyle\\{T(a,b,c)\rightarrow R(a,b)\wedge
V(c,d)\wedge b=d\\}.$

Let further be $R(\texttt{id},\texttt{name})$,
$V(\texttt{name},\texttt{subject})$ and
$T(\texttt{id},\texttt{name},\texttt{sub-}$ $\texttt{ject})$ three relations
with an arbitrarily chosen source instance. Chasing $\mathcal{M}$ after
chasing $\mathcal{M}^{\ast}$ returns

$\displaystyle I^{\ast}$ $\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{\ast}}(\textsc{Chase}_{\mathcal{M}}(I))$
$\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{\ast}}(\textsc{Chase}_{\mathcal{M}}(\\{R(1,\textrm{Alice}),R(2,\textrm{Bob}),$
$\displaystyle\quad
V(\textrm{Alice},\textrm{Math}),V(\textrm{Alice},\textrm{IT})\\}))$
$\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{\ast}}(\\{T(1,\textrm{Alice},\textrm{Math}),T(1,\textrm{Alice},\textrm{IT})\\})$
$\displaystyle=$
$\displaystyle\\{R(1,\textrm{Alice}),V(\textrm{Alice},\textrm{Math}),V(\textrm{Alice},\textrm{IT})\\}$
$\displaystyle\preccurlyeq$ $\displaystyle I$

$R$: | name | $\texttt{mod}_{1}$ | $\texttt{mod}_{2}$ |
---|---|---|---|---
| Alice | 1.7 | 3.3 | $r_{1}$
| Bob | 2.0 | 2.7 | $r_{2}$
| Alice | 3.0 | $2.0$ | $s_{3}$
$\scriptstyle{\textsc{Chase}_{\mathcal{M}}}$ $T$: | name | f($\texttt{mod}_{1}$,$\texttt{mod}_{2}$) |
---|---|---|---
| Alice | 5.0 | $r_{1}+r_{3}$
| Bob | 4.7 | $r_{2}$
$\scriptstyle{\textsc{Chase}_{\mathcal{M}^{\ast}}}$ $R$: | name | $\texttt{mod}_{1}$ | $\texttt{mod}_{2}$
---|---|---|---
| Alice | $\eta_{1}$ | $\eta_{2}$
| Bob | $\eta_{3}$ | $\eta_{4}$
| ~~Alice~~ | ~~$\eta_{5}$~~ | ~~$\eta_{6}$~~

(a) Inverse without knowing $f^{-1}$

$R$: | name | $\texttt{mod}_{1}$ | $\texttt{mod}_{2}$ |
---|---|---|---|---
| Alice | 1.7 | 3.3 | $r_{1}$
| Bob | 2.0 | 2.7 | $r_{2}$
| Alice | 3.0 | 2.0 | $s_{3}$
$\scriptstyle{\textsc{Chase}_{\mathcal{M}}}$ $T$: | name | f($\texttt{mod}_{1}$,$\texttt{mod}_{2}$) |
---|---|---|---
| Alice | 5.0 | $r_{1}+r_{3}$
| Bob | 4.7 | $r_{2}$

\+  $\texttt{mod}_{2}$ 3.3 2.7 2.0 $r_{1}$ $r_{2}$ $r_{3}$
$\scriptstyle{\textsc{Chase}_{\mathcal{M}^{\ast}}}$ $R$: name
$\texttt{mod}_{1}$ $\texttt{mod}_{2}$ Alice 1.7 3.3 Bob 2.0 2.7 Alice 3.0 2.0

(b) Inverse including $f^{-1}$

Figure 4. MERGE Column using different Chase-inverses $\mathcal{M}^{\ast}$;
extended by provenance (highlighted in orange) and side table (highlighted in
gray)

Like shown in Figure 3, dangling tuple (highlighted in magenta) can be
problematic here. Lost tuples like $(2,\textrm{Bob})$ can not be reconstructed
in the (minimal) sub-database $I^{\ast}$. In this case, we merely reconstruct
a subset of the source instance $I$ and record a result-equivalent Chase-
inverse. However, if there are no dangling tuples, an exact Chase-inverse can
be guaranteed.

Adding witness basiss or provenance polynomials (highlighted in orange) does
not change the Chase-inverse type. These do not provide any additional
information for us. However, if we additionally store the dangling tuple
$r_{2}$ in an external side table (highlighted in gray), it can be added back
to the reconstructed instance $I^{\ast}$. Summarized we can guarantee an exact
Chase-inverse, because:

$\displaystyle I^{\ast}$ $\displaystyle=$
$\displaystyle\\{R(1,\textrm{Alice}),S(\textrm{Alice},\textrm{Math}),V(\textrm{Alice},\textrm{IT})\\}\cup\\{R(2,\textrm{Bob})\\}$
$\displaystyle=$ $\displaystyle I.$

MOVE Column may contain duplicates in addition to dangling tuple. The
corresponding SMO can be formulated in two different ways. It is the only SMO
in our study that does not have a Chase-inverse in every case.

### Class III: Duplicates

The presence of duplicates typically permits only the specification of a
relaxed Chase-inverse. SMOs belonging to this class are DROP Column, MERGE
Column, SPLIT Column and DECOMPOSE Table. An improvement of the inverse type
is only possible by adding provenance information. In some cases even an exact
Chase-inverse can be guaranteed.

$R$: | id | name | subject |  |  |  $V$: | id | name | subject |
---|---|---|---|---|---|---|---|---|---|---
| 1 | Alice | Math | $r_{1}$ |  |  | 2 | Bob | IT | $s_{1}$
| 1 | Alice | IT | $r_{2}$ |  |  | 1 | Alice | IT | $s_{2}$
$\scriptstyle{\textsc{Chase}_{\mathcal{M}}}$ $T$: | id | name | subject |
---|---|---|---|---
| 1 | Alice | Math | $r_{1}+s_{1}$
| 2 | Bob | IT | $r_{2}$
| 1 | Alice | IT | $s_{2}$
$\scriptstyle{\textsc{Chase}_{\mathcal{M}^{\ast}}}$ $R$: | id | name | subject |  |  $V$: | id | name | subject
---|---|---|---|---|---|---|---|---
| 1 | Alice | Math |  |  | 1 | Alice | Math
| ~~2~~ | ~~Bob~~ | ~~IT~~ |  |  | 2 | Bob | IT
| 1 | Alice | IT |  |  | ~~1~~ | ~~Alice~~ | ~~IT~~

Figure 5. MERGE Table extended by provenance (highlighted in orange)

###### Lemma 4.0.

Let $\mathcal{M}=(S_{t},S_{t+1},\Sigma)$ be a schema mapping of Class III.
Then the corresponding Chase-inverse
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$ is (tp-)relaxed, depending on
the existence of duplicates. By adding provenance information and side tables,
the Chase-inverse type can be defined as tp-relaxed or exact.

###### Proof.

Let $\mathcal{M}=(S_{t},S_{t+1},\Sigma)$ and
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$ be two schema mappings with

$\displaystyle\Sigma$ $\displaystyle=$ $\displaystyle\\{R(a,b,c)\rightarrow
T(a,f(b,c))\\},$ $\displaystyle\Sigma^{-1}$ $\displaystyle=$
$\displaystyle\\{T(a,g)\rightarrow\exists D,E:R(a,D,E)\\}$

formalizing MERGE Column and its associated inverse mapping. W.l.o.g. let $R$
be restricted to three and $T$ to two attributes. Let further $f$ be any MERGE
function,
$I=\\{R(x_{i_{1}},x_{i_{2}},x_{i_{3}})_{r_{i}}\bigm{|}i\in\mathbb{N}$ $\wedge\
f(x_{j_{2}},x_{j_{3}})=f(x_{k_{2}},x_{k_{3}})\wedge\ r_{i}\textrm{ is tuple
identifier}\\}$ an instance with tuple identifier $r_{i}$ and duplicate in
$t_{j}$ and $t_{k}$. Let $w_{j}$ be witness basis of duplicate $r_{j}$ with
$w_{j}=w_{k}=\\{\\{r_{j}\\},\\{r_{k}\\}\\}$. So, $w_{j}$ contains two sets of
tuple identifiers, so-called witnesses. A witness, here $\\{r_{j}\\}$ and
$\\{r_{k}\\}$, holds all tuple IDs needed for reconstructing one tuple. Two
witnesses represent a duplicate. Chasing $\mathcal{M}^{\ast}$ after chasing
$\mathcal{M}$ then returns

$\displaystyle I^{\ast}$ $\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{\ast}}(\textsc{Chase}_{\mathcal{M}}(I))$
$\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{\ast}}(\\{T(x_{i_{1}},f(x_{i_{2}},x_{i_{3}}))_{w_{i}}\bigm{|}i\in\mathbb{N}$
$\displaystyle\quad\wedge\ f(x_{j_{2}},x_{j_{3}})=f(x_{k_{2}},x_{k_{3}})\\}$
$\displaystyle\quad\wedge\ w_{i}\textrm{ witness basis with
}w_{j}=w_{k}=\\{\\{r_{j}\\},\\{r_{k}\\}\\})$ $\displaystyle=$
$\displaystyle\\{R(x_{i_{1}},\eta_{i_{2}},\eta_{i_{3}})\bigm{|}i\in\mathbb{N}\wedge\
\eta_{j_{2}}=\eta_{k_{2}},\eta_{j_{3}}=\eta_{k_{3}}\\}$
$\displaystyle\preccurlyeq_{\textrm{(tp)}}$ $\displaystyle I.$

Due to the existence quantifiers, the inverse s-t tgd always generates two new
null values $\eta_{i_{2}}$ and $\eta_{i_{3}}$. Thus, the attribute values
processed in $f$ can not be recovered. Due to the duplicate $t_{j}=t_{k}$, the
reconstructed instance $I^{\ast}$ contains less tuples than the original
instance $I$. The inverse $\mathcal{M}^{\ast}$ is thus relaxed without and tp-
relaxed with existing duplicates. Adding provenance guarantees an tp-relaxed
Chase-inverse. In this case, $\eta_{j_{2}}\neq\eta_{j_{3}}$ as well as
$\eta_{k_{2}}\neq\eta_{k_{3}}$ holds.

Let alternatively be $\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$ inverse
mapping with

$\displaystyle\Sigma^{-1}$ $\displaystyle=$
$\displaystyle\\{T(a,b))\rightarrow R(a,f^{-1}(a,f^{-1}(g,c),c\\}.$

This formalization can only be used in combination with provenance, since
polynomials, side tables and the knowledge of $f^{-1}$ are necessary here.
Then chasing $\mathcal{M}^{\ast}$ after chasing $\mathcal{M}$ returns

$\displaystyle I^{\ast}$ $\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{\ast}}(\textsc{Chase}_{\mathcal{M}}(I))$
$\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{\ast}}(\\{T(x_{i_{1}},f(x_{i_{2}},x_{i_{3}}))_{p_{i}}\bigm{|}i\in\mathbb{N}$
$\displaystyle\quad\wedge\ f\textrm{ invertible function}$
$\displaystyle\quad\wedge\ p_{i}\textrm{ provenance polynomial with
}p_{j}=p_{k}=r_{k}+r_{k}\\}$ $\displaystyle\quad\wedge\
f(x_{j_{2}},x_{j_{3}})=f(x_{k_{2}},x_{k_{3}})\\}$ $\displaystyle\cup\
\\{(x_{i_{3}})_{r_{i}}\bigm{|}i\in\mathbb{N}\wedge\ r_{i}\ \textrm{tuple
identifier}\\})$ $\displaystyle=$
$\displaystyle\\{R(x_{i_{1}},f^{-1}(f(x_{i_{2}},x_{i_{3}}),x_{i_{1}})_{\mid_{x_{i_{2}}}},f^{-1}(f(x_{i_{2}},x_{i_{3}}),x_{i_{1}})_{\mid_{x_{i_{3}}}})\bigm{|}$
$\displaystyle\quad i\in\mathbb{N}\wedge\
f(x_{j_{2}},x_{j_{3}})=f(x_{k_{2}},x_{k_{3}})\\}$ $\displaystyle=$
$\displaystyle\\{R(x_{i_{1}},x_{x_{2}},x_{i_{3}})\bigm{|}i\in\mathbb{N}\\}$
$\displaystyle=$ $\displaystyle I.$

Let be $p_{i}$ provenance polynomial and $a_{i_{j}}$ element of the side table
$\\{(x_{i_{3}})_{r_{i}}\bigm{|}i\in\mathbb{N}\wedge\ r_{i}\ \textrm{tuple
identifier}\\}$. Then $x_{i_{2}}$ can be recalculated from
$f^{-1}(g,x_{i_{3}})$ as follows:

  * •

attribute values $g$ and $x_{i_{3}}$ are explicitly contained in
$J=\textsc{Chase}_{\mathcal{M}}(I)$;

  * •

inverse function $f^{-1}$ is given after precondition;

  * •

attribute value $x_{i_{3}}$ can be read from the side table using $p_{i}$.

Also duplicates can be reconstructed using this additional information.
Overall an exact Chase-inverse can be guaranteed. ∎

Figure 4 shows the situation above in a concrete example. Let be $R$ a
student-table where the points of the two passed modules should be summarized.
The inverse without knowing $f^{-1}$ yields a relaxed Chase-inverse (see
Figure 4(a)). However, the duplicate $(\textrm{Alice},5.0)$ in $T$ can be
reconstructed using additional provenance information, here a provenance
polynomial (highlighted in orange). Adding a sustainable side even allows the
definition of a exact Chase-inverse if $f^{-1}$ is known (see Figure 4(b)).
Proving the other SMOs of Class III is quite similar.

### Class IV: Special SMOs

Almost all SMOs can be assigned to Classes 1 to 3. Only MERGE Table and DROP
Table remain. These contain neither dangling tuple (see Class II) nor
duplicates (see Class III). In contrast to Class I, however, adding provenance
improves the inverse type in both cases.

###### Lemma 4.0.

The SMO MERGE Table has a result equivalent Chase-inverse. Adding provenance
information, the Chase-inverse type can be defined as exact.

The unification of two tables $R$ and $V$ can be formalized as schema mapping
$\mathcal{M}$ with inverse mapping
$\mathcal{M}^{\ast}=(S_{t+1},S_{t},\Sigma^{-1})$,

$\displaystyle\Sigma$ $\displaystyle=$ $\displaystyle\\{R(a,b,c)\rightarrow
T(a,b,c),V(a,b,c)\rightarrow T(a,b,c)\\},$ $\displaystyle\Sigma^{-1}$
$\displaystyle=$ $\displaystyle\\{T(a,b,c)\rightarrow
R(a,b,c),T(a,b,c)\rightarrow V(a,b,c)\\}.$

Let further be $R$, $S$ and $T$ three relations with an arbitrarily chosen
source instance $I$. Chasing $\mathcal{M}^{\ast}$ after chasing $\mathcal{M}$
then yields

$\displaystyle I^{\ast}$ $\displaystyle=$
$\displaystyle\textsc{Chase}_{\mathcal{M}^{\ast}}(\textsc{Chase}_{\mathcal{M}}(I))=\textsc{Chase}_{\mathcal{M}^{\ast}}(J)\neq
I,$

whereby $I^{\ast}$ may contain more tuples than $I$, since
$\mathcal{M}^{\ast}$ preserves all existing tuples like
$(2,\textrm{Bob},\textrm{IT})$ and $(1,\textrm{Alice},\textrm{IT})$ in Figure
5, which are not originally contained in $R$ and $T$, respectively.

However, the redundant tuples in $I^{\ast}$ can be identified and deleted by
using how-provenance (highlighted orange in Figure 5). Knowing the tuples used
for calculating $J$, allows us to reassign the tuples to their source
relations. We can thus reconstruct the source instance error-free and
guarantee an exact Chase-inverse. It is not significant how exactly the result
is produced. It is sufficient to know which tuple ids are involved in the
generation of $(2,\textrm{Bob},\textrm{IT})$ or
$(1,\textrm{Alice},\textrm{IT})$. A generalized witness basis or witness list
is sufficient, too.

###### Lemma 4.0.

The SMO DROP Table has a relaxed Chase-inverse. Adding provenance information
the Chase-inverse type can be defined as tp-relaxed.

## Conclusion

Especially for long-term data-driven studies, changing databases lead at some
point to a large number of schemas. However, in the sense of reproducibility
of research data each database version must be reconstructable with little
effort. Nevertheless, in many cases, such an evolution can not be fully
reconstructed.

This article classified the 15 most frequently used schema modification
operators and defined the associated inverses for each operation. For avoiding
an information loss, it furthermore defined which additional provenance
information have to be stored. All in all, we define four classes dealing with
dangling tuples, duplicates and provenance-invariant operators.

By using and extending the theory of schema mappings and their inverses for
queries, we are able to combine data analysis applications with provenance
under evolving database structures, thus enabling the reproducibility of
scientific results over longer periods of time.

## References

  * (1) T. Auge and A. Heuer: The Theory behind Minimizing Research Data: Result equivalent Chase-inverse Mappings. LWDA, CEUR Workshop Proceedings, vol. 2191, CEUR-WS.org, pp.1–12, 2018.
  * (2) T. Auge, E. Manthey, S. Jürgensmann, S. Feistel and A. Heuer: Schema Evolution and Reproducibility of Long-term Hydrographic Data Sets at the IOW. LWDA, CEUR Workshop Proceedings, vol. 2738, CEUR-WS.org, pp.258–269, 2020.
  * (3) N. Bidoit, M. Herschel and K. Tzompanaki: Query-Based Why-Not Provenance with NedExplain. EDBT, OpenProceedings.org, pp.145–156, 2014.
  * (4) P. Buneman, S. Khanna and W. C. Tan: Why and Where: A Characterization of Data Provenance. ICDT, Lecture Notes in Computer Science, vol. 1973, Springer, pp.316–330, 2001.
  * (5) M. Benedikt, G. Konstantinidis, G. Mecca, B. Motik, P. Papotti, D. Santoro and E. Tsamoura: Benchmarking the Chase. PODS, ACM, pp.37–52, 2017.
  * (6) C. Curino, H. J. Moon, L. Tanca and C. Zaniolo: Schema Evolution in Wikipedia – Toward a Web Information System Benchmark. ICEIS (1), pp.323–332, 2008.
  * (7) C. Curino, H. J. Moon and C. Zaniolo: Graceful database schema evolution: the PRISM workbench. Proc. VLDB Endow., 1(1), pp.761–772, 2008.
  * (8) A. Deutsch, L. Popa and V. Tannen: Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB, Morgan Kaufmann, pp.459–470, 1999.
  * (9) R. Fagin, P. G. Kolaitis, L. Popa and W. C. Tan: Quasi-inverses of schema mappings. ACM Trans. Database Syst., 33(2), pp.11:1–11:52, 2008
  * (10) R. Fagin, P. G. Kolaitis, L. Popa and W. C. Tan: Schema Mapping Evolution Through Composition and Inversion. Schema Matching and Mapping, Data-Centric Systems and Applications, Springer, pp.191–222, 2011.
  * (11) B. Glavic, G. Alonso, R. J. Miller and L. M. Haas: TRAMP: Understanding the Behavior of Schema Mappings through Provenance. Proc. VLDB Endow., 3(1), pp.1314–1325, 2010.
  * (12) T. J. Green, G. Karvounarakis and V. Tannen: Provenance semirings. PODS, ACM, pp.31–40, 2007.
  * (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 and V Tannen: The Semiring Framework for Database Provenance. PODS, ACM, pp.93–99, 2017.
  * (15) S. Gao and C. Zaniolo: Provenance Management in Databases Under Schema Evolution. TaPP, USENIX Association, 2012.
  * (16) M. Herschel, R. Diestelkämper, and H. Ben Lahmar: A survey on provenance: What for? What form? What from? VLDB J., 26(6), pp.881-906, 2017.
  * (17) A. Motro: Using Integrity Constraints to Provide Intensional Answers to Relational Queries. VLDB, Morgan Kaufmann, pp.237–246, 1989.
  * (18) B. Pérez, J. Rubio, and C. Sáenz-Adán: A systematic review of provenance systems. Knowl. Inf. Syst., 3(57), pp.495-543, 2018.
  * (19) D. Qiu, B. Li and Z. Su: An empirical analysis of the co-evolution of schema and code in database applications. ESEC/SIGSOFT FSE, ACM, pp.125–135, 2013.
  * (20) P. Senellart: Provenance and Probabilities in Relational Databases. SIGMOD Rec., 46(4), pp.5–15, 2017.
  * (21) S. Wu and I. Neamtiu: Schema evolution analysis for embedded databases. ICDE Workshops, IEEE Computer Society, pp.151–156, 2011.