In research data management and other applications, the primary research data have to be archived for a longer period of time to guarantee the reproducibility of research results. How can we minimize the amount of data to be archived, especially in the case of constantly changing databases or database schemes and permanently performing new evaluations on these data? In this article, we will consider evaluation queries given in an extended relational algebra. For each of the operations, we will decide whether we can compute an inverse mapping to automatically compute a (minimal) subdatabase of the original research database when only the evaluation query and the evaluation result is stored. We will distinguish between different types of inverses from exact inverses to data exchange equivalent inverses. If there is no inverse mapping, especially for aggregation operations, we will derive the necessary provenance information to be able to perform the calculation of this subdatabase. The theory behind this minimization of research data, that has to be archived to guarantee reproducible research, is based on the CHASE&BACKCHASE technique, the theory of schema mappings and their inverses, and the provenance polynomials to be used for how provenance.
In several applications, an extensive amount of data has to be managed, analyzed, stored, and archived due to legal and provenance purposes. In our projects, we consider quite different applications dealing with growing amounts of data, such as research data management with measurement data and sensor data management for smart (assistive) systems aiming at the derivation of activity and intention models by means of Machine Learning algorithms. In all of these cases, the massive amount of primary measurement or sensor data has to be reduced to an important kernel, that has to be archived for a longer period (often ten years, due to legal reasons).
Since the database of research and sensor data and its database schema evolves over time, the researcher or smart system developer is forced to store complete snapshots of the data each time, the database or database schema changes. In most cases, the management of research or sensor data becomes difficult to handle. The problem is, how to calculate the kernel of important data when databases or database schemes are changing. This is the aim of our research project. Which parts of the original database have to be frozen, when evaluations of research data are performed, or when decisions of smart systems have to be recorded? We want to minimize the subdatabase that has to be stored to guarantee the reproducibility of the performed evaluation.
How to automatically compute this minimal subdatabase of the primary data?
Given an evaluation query and the result of the evaluation query, is it possible
to derive the minimal subdatabase simply by an inverse mapping without any
additional annotations of the data and without any need to freeze the original
database? Or do we have to store some additional information, e.g. provenance
polynomials [
Our use case and main application scenario for minimizing research data
is a cooperation of our database research group and the Leibniz Institute for
Baltic Sea Research Warnemuende (IOW). Applications, data, data integration
processes, evaluation queries, and data provenance problems are described in [
In this paper, we want to describe the first step of our research: given an
evaluation query and an evaluation result, does there exist an inverse mapping
that computes a subdatabase of the original database that guarantees the
reproducibility of the result? If there is no such inverse mapping, can we add some
annotations like provenance polynomials to do so? In our case, the evaluation
query is given in an extended relational algebra (adding some basic scalar,
arithmetical operations, grouping, and aggregates to the classical relational algebra).
For the derivation of the inverse mapping, we will adapt the theory of inverse
schema mappings from the areas of data exchange, schema evolution and schema
integration [
In the next section, we will briefly introduce some fundamental definitions and results of the CHASE&BACKCHASE process, as well as schema mappings and their inverses. In Section 3, we introduce new types of inverse mappings, the tuple preserving relaxed CHASE-inverse and the result equivalent CHASEinverse. In Section 4, we will determine the possible types of inverses that can be computed for a specific operator of the extended relational algebra. 2
The idea of our work is based on the combination of three different basic
techniques: CHASE&BACKCHASE, CHASE-inverse schema mappings and data
provenance. In this paper, we will introduce the first two of these. For a more
detailed introduction into the state of the art in data provenance, we refer to
[
The CHASE is a tool universally applicable in database theory. It is used, for example, to incorporate dependencies within a database or a relational algebra expression, to implicate dependencies, to verify the equivalence of database schemas under given dependencies, and to handle (replace or clean) null values in databases. The idea of this algorithm can be summarized as follows: For a CHASE object and a CHASE parameter ∗ (in most cases: a set of dependencies), the CHASE incorporates ∗ into the object , so that ∗ is implicitly contained in , and thus satisfies the dependencies in ∗. The result can be presented as: chase∗( ) = ∗ .
The CHASE has its original application in database design [
For a query Q and a source instance I, the CHASE returns a result instance K = chaseM(I) if the following holds: – Q is defined as a schema mapping M = (S1, S2, Σ) with source and target schemas S1 and S2 and a set of dependencies Σ describing the semantics of the query; – I is the source instance in S1; – K is target instance in S2.
These dependencies can be tgds or s-t tgds and egds. A tuple-generating dependency (tgd) is a sequence of the form
∀x : (φ(x) → ∃y : ψ(x, y)) with conjunctions φ(x) and ψ(x, y) of atoms from x and x and y respectively1. If φ(x) is a conjunction of atoms over a source scheme S and ψ(x, y) a conjunction 1 x and y are vectors of variables x1, x2, . . . or y1, y2, . . . of atoms over a target scheme T , such a sequence is also called source-to-target tuple-generating dependency (s-t tgd). An equality-generating dependency (egd) is for two variables x1, x2 from x defined by
∀x : (φ(x) → (x1 = x2)).
The CHASE&BACKCHASE is an algorithm for rewriting queries using views
while exploiting integrity constraints. It was introduced in [
A schema mapping M is a triple (S1, S2, Σ), consisting of a source schema S1,
a target schema S2 and a set of dependencies Σ that specifies the relationship
between the source and target schema. CHASE-inverses are a special form of
schema mappings [
Inverse mappings are used in schema evolution, for example. While an exact
CHASE-inverse always reconstructs the original database, the classical
CHASEinverse only returns an instance I∗ which is equivalent to the original database
instance I, i.e. I∗ and I are equal except for the homomorphic mapping of
marked null values to other marked null values or attribute values. The relaxed
CHASE-inverse is another version of the CHASE-inverse [
Given an original research database over database schema S1 and an evaluation query Q, we now want to derive the result of the (why or how ) provenance query Qprov either as some type of inverse of Q or, if not possible, by use of provenance information. To calculate this minimal subdatabase of the original research database, that has to be archived to guarantee the reproducibility of the evaluations, we will use – st-tgds for the basic operations of the extended relational algebra, to be used to express the evaluation query Q, – the CHASE to formally evaluate Q on the original database instance I, to produce the result instance K, – the BACKCHASE step to formally evaluate the provenance query Qprov, i.e. some kind of inverse mapping, to determine the minimal subdatabase I∗ of I (or an equivalent data set) that we will call recovered instance, – and the different types of inverses of mappings (see Section 3) to determine whether this inverse can be calculated with or without additional annotations like provenance polynomials (see Subsection 4.3).
The complete process is defined in [
Tuple preserving relaxed and result equivalent
CHASE-inverse
The relaxed CHASE-inverse is a weakening of the classical CHASE-inverse. It
does not require an equivalence relationship between the source instance and the
recovered instance I∗, but data exchange equivalence [
To preserve the number of tuples of the original database we extend the definition of the relaxed CHASE-inverse and we call it tuple preserving relaxed CHASEinverse (tp-relaxed). This sharpens the character of the relaxed CHASE-inverse. In the opposite, a weakened definition is a schema mapping M = (S1, S2, Σ), called result equivalent CHASE-inverse, with regard to M (short: I ↔M K), where the data exchange equivalence is valid for two instances I and K over S, i.e. chaseM(I) ≡ chaseM(K). The result equivalent CHASE-inverse only requires result equivalence and no additional homomorphism from I∗ to I and is therefore the weakest CHASE-inverse. Overall, this results in the reduction: result equivalent relaxed tp-relaxed exact.
This reduction forms the sufficient condition for the existence of a CHASEinverse. The necessary condition follows from the respective definition of the CHASE-inverse. Table 1 summarizes these conditions.
If the recovered instance I∗ contains tuples with (marked) null values whose remaining attribute values match the attribute values of a tuple of the source instance I (for example (1, 3, 5) ∈ I and (1, 3, n1) ∈ I∗), then I∗ is called section of the instance I (short: I∗ I). In other words, there is a homomorphism h that maps the tuples from I∗ to the tuples from I. For the above example, 1 7→ 1, 3 7→ 3 and n1 7→ 5 applies. If I∗ contains no (marked) null values and all tuples from I∗ are also tuples in I, we write I∗ ⊆ I.
With these types of inverses, CHASE-inverse schema mappings can now be found for almost all basic operations of the extended algebra, we use for
CHASE-inverse Sufficient condition Necessary condition Exact - I∗ = I Classical Exact CHASE-inverse I∗ ≡ I Tp-relaxed Exact CHASE-inverse I∗ I, | I∗ |=| I | Relaxed Tp-relaxed CHASE-inverse I∗ I
Result equivalent Relaxed CHASE-inverse I∗ ↔M I the evaluation queries in research data management or the Machine Learning algorithms in smart, sensor-based systems. 4
Basic operations and CHASE-inverse schema mappings In this paper we discuss the following problems: Is there an inverse mapping for an evaluation query and an evaluation result that calculates a sub-database of the original database and that guarantees the reproducibility of the result? And, if there is no such inverse mapping, can we add some annotations like provenance polynomials to do so? Therefore we neglect the homomorphy demanded by R. Fagin and define the so-called result equivalent CHASE-inverse. On the other hand we extend the definition of relaxed CHASE-inverse with the additional property that the number of tuples has to be equal in the source and the result instance. For almost each of the relational basic operations one of the four CHASE-inverse types can be detected now. For this purpose, the respective operation is formulated as s-t tgd and processed using the CHASE&BACKCHASE method. By composing the basic operations, CHASE-inverse mappings can also be found for general evaluation queries such as SQL-implementations of Machine Learning algorithms. 4.1
The basic operations of the extended relational algebra (copy, renaming,
projection, natural join, selection, set operations and also arithmetic operations) can
be written as s-t tgds based on their representations in Datalog. For aggregation
and grouping, we refer to [
The recovered instance I∗ = chaseM∗ (K) = chaseM∗ (chaseM(I)) is thus the result of a query Qprov on the result instance K. I∗ contains whole tuples from I or tuples restricted to certain attributes of the source schema (and filled with (marked) null values).
Copy:
r(a1, a2, a3) → r(a1, a2, a3) r(a1, a2, a3) → r(a1, a3) r1(a1, a2) ∧ r2(a2, a3) → r(a1, a2, a3) ∃c ∈ dom(A1) : r(a1, a2) ∧ a1θc → r(a1, a2) with θ ∈ {<, ≤, =, 6=, ≥, >}
The second CHASE application is used here to “mapping back” the result
instance K to the source instance I. However, this is usually only partially
successful, so that an additional recovered instance I∗ must be introduced, which
is then compared with the source instance. This phase can be interpreted as the
BACKCHASE phase. The idea of the CHASE&BACKCHASE method is based
on the idea of Deutsch et al. [
The existence of an exact CHASE-inverse (=) can only be proven for a few relational operations such as copy or one-variable arithmetic operations. While no CHASE-inverse can be found for the selection for inequality and the set difference (xxx), most operations are tp-relaxed ( tp), relaxed ( ) or result equivalent CHASE-inverses (↔).
I(S1):
The addition of provenance information allows the specification of stronger
CHASE-inverse schema mappings than without (see Table 2, column 4). The
provenance polynomials and (minimal) witness bases required for this correspond
to the definitions in [
The situation is different for aggregate functions SUM and AVG. For illustration we consider the schema S1, consisting of the attributes id, module and grade. The evaluation query Q performs the aggregation of the attribute grade. Without using data provenance, one tuple (m1, n1, 1.725) is generated, which stores the aggregated value AVG(grade) (see also Figure 2). A result equivalent CHASEinverse exists. By using provenance information, the exact CHASE-inverse can only be defined for the aggregated attribute grade itself. Therefore, the used provenance polynomial is calculated as t = 1.3⊗t1+K2.3⊗t2+K1.0⊗t3+K2.3⊗t4 . Ret1+Kt2+Kt3+Kt4 lated to the whole relation, there just can be specified a tp-relaxed CHASE-inverse mapping. In order to guarantee an exact CHASE-inverse in this case, the relation K0(S20) must be stored too (gray box in Figure 3), in addition to the evaluation query Q = AVG(grade), the result database K(S2) and the provenance polynomial t. The gray colored records of the recovered instance I∗ are no longer null values, but can be specified concretely.
I(S1):
This additional side table K0 is, however, in many cases not necessary or desired, for example due to data privacy aspects. A concrete traceability of the recovered result is already possible with the CHASE-inverse mapping shown in Figure 3 without the gray extension K0. In this case the id and module numbers have to be replaced by null values. The s-t tgds for this operation (aggregation with provenance polynomials) looks like
R(id, module, grade) → Rresult(f (grade)) with f (x) = AVG(x) for the CHASE and
Rresult(avg grade) → ∃ ID, Module : R(ID, Module, grade) for the BACKCHASE step, where the grade can concretely be calculated from the result attribute value of avg grade and the provenance polynomial t.
An explicit specification of the respective inverse M∗ is also possible. Thus, the CHASE-inverse can be the identity mapping, renaming, projection, selection, the null value extension in Ai and null tuple generation, the reconstruction of lost attribute values Ai and the reconstruction of lost tuples. For relaxed schema mappings one of the above inverse always exists. The inverse can even be specified explicitly for the following operations: The natural join, one-variable arithmetic operations (multiplication, division, addition, and subtraction) as well as the renaming can be inverted by the projection, the inverse arithmetic operations (division, multiplication, subtraction, and addition, resp.) and the renaming. The inverse schema mapping of a result equivalent schema mapping is already the identity. All realizations are represented in the third and fifth column of Table 2. In the case of aggregation, i.e. M = AVG(Ai), this means for the inverse mapping M∗ the reconstruction of the lost attribute value Ai and the null value extension in Aj with i 6= j.
For grouping, we have to distinguish three cases: an inverse type of relaxed ( ) for MIN and MAX and tp-relaxed ( tp) for COUNT. For SUM and AVG there exists a result equivalent CHASE-inverse (↔) or an exact CHASEinverse (=) with and without using provenance information. For the inverse M∗ this results in the identity mapping, the generation of null tuples, the null value extension in Ai and the reconstruction of lost tuples and concrete attribute values Ai (see Table 2, column 3 and 5). 4.4
For the composition M = M1 ◦ ... ◦ Mn of operations, the inverse mapping M∗ = (M1 ◦ ... ◦ Mn)−1 = M∗n ◦ ... ◦ M2∗ ◦ M1∗ results in a composition of the inverse suboperations M1∗, ..., M∗n. The type of the CHASE-inverse M∗ thus corresponds to the type of the weakest partial inverse Mi∗ with i = 1, ..., n. If there are no CHASE-inverses to the suboperations Mi (i = 1, ..., n), there is also no CHASE-inverse to the schema mapping M.
We use such a composition to implement more complex evaluation queries on research data such as Machine Learning algorithms, e.g. the Hidden Markov model. This model is one of the best-known machine learning algorithms. It describes a stochastic model in which a system is modeled by a Markov chain — a kind of “memory protocol” — with unobserved states. The future development of the process therefore depends only on the last observed state, but not on the previous states.
Based on the representation of the Hidden Markov model in the form of SQL
statements [
In this paper, we investigated whether an inverse mapping exists for an evaluation query and an evaluation result, which calculates a subdatabase of the original database that guarantees the reproducibility of the result. For this purpose we have defined new CHASE-inverses and determined the possible types of inverses that can be computed for a specific operator of the extended algebra. In some cases, we used additional annotations like provenance polynomials. In Table 2, we have shown in which cases these additional annotations are necessary.
m m A tc
o o j in ru fr f
r
o o ll n it it u io c c
e e n s j j i i
m m
A A o o j in in fr f
r
A
A t s s ceeavnn ?IsreevnMiitteynd iganβmAi← iltseeeoxnnu rsceonA+i itttreaobun itttreaobun iitteynd iitteynd xxx xxx iltsceeon iitteynd xxx iitseeoxnnn ltreeeagnpu ilftttrsaoob itseeeoxnn ilftttrsaoob itseeeoxnn iitteynd rceonA+i ltseandup :///+− o l u n n l i j i j f a
o v
o l c l
e u r n p t − , + { rov In an lau lau on on
re v v o o P ll ll it it t u u c c
e e u n n j j o p e t s = = = x p t ↔ ↔ ↔= ) ) ) ) / ) ∈ itreaonpM()R (())rAAij←R (())rAiR .()(r/1122RR (())rcθAiR (())rθAAijR i,tθhw<{∈≤ (())rcA=i6R (())rAA=ij6R ()(r1122∪RR ()(r1122∩RR ()(r1122−RR (())rAXAiR ((rTOUNAiR (())rUMAiR (())rVGAiR (()r;)(FAGijjR i)tθθhαwR O r β π r σ σ σ σ r r r M C S A γ ( r Table 2: Basic operations and their exact (=), tp-relaxed ( tp), relaxed ( ) or result equivalent( )CHASE-inversewithrestrictiontotheattributeAi forCOUNT,SUM ↔ and AVG