=Paper=
{{Paper
|id=Vol-2454/paper_19
|storemode=property
|title=Keeping NoSQL Databases Up to Date – Semantics of Evolution Operations and their Impact on Data Quality
|pdfUrl=https://ceur-ws.org/Vol-2454/paper_19.pdf
|volume=Vol-2454
|authors=Mark Lukas Möller,Meike Klettke,Uta Störl
|dblpUrl=https://dblp.org/rec/conf/lwa/MollerKS19
}}
==Keeping NoSQL Databases Up to Date – Semantics of Evolution Operations and their Impact on Data Quality==
https://ceur-ws.org/Vol-2454/paper_19.pdf
Keeping NoSQL Databases up to date –
Semantics of Evolution Operations and their
Impact on Data Quality
Mark Lukas Möller1 , Meike Klettke1 , and Uta Störl2?
1
University of Rostock, Rostock, Germany
{mark.moeller2,meike.klettke}@uni-rostock.de
2
Darmstadt University of Applied Sciences, Darmstadt, Germany
uta.stoerl@h-da.de
Abstract. Evolving a NoSQL database schema regularly involves mi-
grating datasets into new schema versions. NoSQL databases store data-
sets in different heterogeneity levels (HCs) that can be characterized
by their degree of regularity and cardinality of various entity types. In
this article, we present the semantics of NoSQL evolution operations
and their corresponding data migration operations while distinguishing
different NoSQL HCs. One use-case of NoSQL evolution operations is
improvement of actuality and completeness of data which is especially
relevant in terms of the ever-expanding volume of data.
Keywords: NoSQL Schema Evolution · Schema Evolution Operation ·
Data Heterogeneity Classes · Data Quality
1 Introduction
In agile software development environments source code is changed frequently
which also can include changes of the data in a database. In order to deal with
schema changes, schema evolution operations adapt the data to the new struc-
ture. While for relational databases schema evolution has been studied in detail
in the past [13], these approaches cannot be directly transferred to NoSQL since
characteristics like data heterogeneity have to be taken into account.
The majority of NoSQL database systems can be used for storing datasets
with different characteristics:
1. No or limited schema control: In NoSQL, neither schema information nor
semantical constraints have to be defined before the actual storing of the
datasets. Thus, datasets with different structures can be stored even within
the same collection and may lead to heterogeneous data.
2. Regularity of data: Oftentimes NoSQL databases are generated by appli-
cations or object mappers resulting in data structures that are checked in
?
Copyright c 2019 for this paper by its authors. Use permitted under Creative Com-
mons License Attribution 4.0 International (CC BY 4.0).
2 ML. Möller, M. Klettke, U. Störl
terms of data consistency. In these cases, well-structured data is stored in
NoSQL databases that at least have an implicit schema.
3. Versioned datasets: In other applications, regular datasets are generated
with a certain structure, yet this structure changes frequently over time.
Consequently, the NoSQL database becomes heterogeneous since it contains
datasets in different versions within the same collection.
In all datasets that are used over long periods of time, we have to enable their
evolution. In order to transform pre-existing stored data into a new structure,
efficient schema evolution operations are required that can cope with problems
of heterogeneity and cardinalities and that update and cleanse the data to ensure
a high level of data quality.
De
d let
Ad e
A4 D4
m:n 4
3 A1 D1
Cardinalities
n:1 C1 R1
C2
C3 M1
e
C4 R4
nam
n) ity
Cop
e o o-
1:n
e v e go s
u
en ter
sio ne
M2
er re
ctu us g he
y
Re
1:1 1 2 M3
o -
t
ne o
sa l He
gehom
M4
(in r a
no yes
m
Dangling Tuples
ru
M ove
St
(a) Three dimensions of the four (b) Heterogeneity Classes of the
NoSQL HCs Evolution Operations
Fig. 1. NoSQL Heterogeneity Classes
First, we are introducing different degrees of NoSQL heterogeneity. Fig-
ure 1(a) visualizes the three dimensions that have to be considered. The first
dimension (x-axis in Figure 1(a)) describes the existence of dangling tuples. Our
evolution language includes two multi-type operations, move and copy. Both op-
erations specify matching conditions between entities. In this context, dangling
tuples are termed as entities without a matching partner regarding a multi-type
operation.
The second dimension describes the cardinalities between kinds that are af-
fected by multi-type operations. Becauses NoSQL databases do not check seman-
tic constraints in advance, it is required to differentiate whether all properties
have a matching partner or dangling tuples exist. If matching partners exist, it
is important to determine the number of partners - referred to as cardinality.
The last dimension regards the heterogeneity of entities of the same version.
Here we distinguish between datasets in which all entities of the same version
have homogeneous or heterogeneous structures (z-axis in Figure 1(a)). We derive
different heterogeneity classes (HCs) per schema evolution operations, starting
Keeping NoSQL Databases up to date 3
from the most structured datasets and 1:1 cardinalities up to unstructured data-
sets and arbitrary cardinalities.
HC1: In this class, the operation affects datasets in the same or different struc-
tural versions (e.g., when lazy migration approaches are used), yet all data-
sets in the same version have exactly the same structure. Multi-type opera-
tions presume 1:1 cardinalities only and there are no dangling tuples allowed
between two kinds of matching conditions.
HC2: The second class extends HC1 by 1:n cardinalities. Therefore, it is re-
quired to deal with dangling tuples.
HC3: The third class encompasses HC2 with arbitrary cardinalities. Additional
strategies are required for determining property values of entities affected by
multi-entity operations with n:m cardinalities.
HC4: The fourth class represents NoSQL databases that can have different
structures within the same version. Consequently, optional properties can
occur that may be available in some entities of a concrete version and missing
in other entities of the same version.
A schema evolution operation against a NoSQL database must be able to cope
with all variants of input datasets. The article makes the following contribution.
– We have already introduced four different heterogeneity classes (HC1-HC4)
for NoSQL. Based on these heterogeneity classes, we define the operational
semantics and data migration for a NoSQL evolution language in Section 3.
We show that for certain HCs the evolution operations can be simplified.
– We discuss the impact on schema evolution operations on the data quality in
Section 4, namely data actuality, data completeness, and data consistency.
2 Foundations
Our NoSQL evolution language contains three single-type operations, add, delete
and rename, and two multi-type operations, move and copy. The operations are
defined for the evolution of the schema and entailed data migration operations
can be derived. The schema evolution and data migration operations are used to
bring entities into the latest structural version. Firstly, we introduce the semantic
foundations.
Data with an equal or similar set of properties is called a an entity-type or a
kind. A kind named A consists of a schema and of a set of entities and is defined
as KA = (SA , EA ).
The schema SA is defined as a set of property-names, SA = {A1 , . . . , An }. The
set of entities EA of KA over the schema SA is defined as EA := {e1 , . . . , em }
whereby m represents the number of entities and where each entity ei in EA
consists of up to n properties (also referred to as attributes) called aij with
i ∈ (1, . . . , m) and j ∈ (1, . . . , n). Formally, ei = {aij | j ∈ {1, . . . n}}.
Here, i represents the index for the i-th entity of EA and j is the j-th property
of the corresponding entity. Each property aij consists of a property name and
and a property value: aij = (Aij : vij ) ∈ SAi × DAi , whereby SAi ⊆ SA and
DAi ⊆ DA . Here, SAi × DAi represents the domain of the property.
4 ML. Möller, M. Klettke, U. Störl
Example. To illustrate the definitions, let us consider an example for the
representation of a subset of a research project database which stores informa-
tion about research stations, the name of the funder of the project, and the bud-
get. The kind is called project and is defined as Kproject = {Sproject , Eproject },
whereby Sproject = {”p id”, ”station name”, ”funder”, ”budget”}. Eproject is the set
of entities that contains two entities (e1 and e2 ) of the kind project. A valid set
of data Eproject is:
Eproject = {
{("p_id": 1), ("station_name": "Ocean"), ("funder": "DFG"), ("budget": "5 Mil")},
{("p_id": 2), ("station_name": "Baltic Sea")}
}
For the evolution operations, it is required to check whether an entity contains
a property with a certain name, regardless of its value. Because properties are
stored as a tuple and not as a set, the operator ∈∗ is defined which evaluates if
there is a property available for a given entity or not. For this purpose, we define
a projection operation that projects onto the property name: πA := SAi ×DAi →
SAi with (Aij , vij ) 7→ Aij . Based on this projection, the ∈∗ operator is defined.
X ∈∗ ei :⇔ ∃aij ∈ ei : X ∈ πA (aij ), and X ∈∗ EA :⇔ ∀ei ∈ EA : X ∈∗ ei .
Reconsider the previous example. Here, ”station name” ∈∗ e1 is True while
”location” ∈∗ e2 is False.
The Dot-Notation is introduced for reading the value of a given property
name and is particularly needed in order to express matching conditions for
multi-entity operations. The following notation is introduced:
∀X ∈∗ ei : ei .X := πv (aij ) with πv := SAi × DAi → DAi with (Aij , vij ) 7→ vij .
In the example, e1 .station name evaluates to ”Ocean”and e2 .station name eval-
uates to ”Baltic Sea”, while e1 .location throws an exception.
Due to migration and encompassed different schema versions, the same kind
is inspected at different points in time. For this, a notation of a version is intro-
duced in the form of in square brackets. For instance, SA[10] = {A1 , . . . , An }[10]
describes the schema of kind A at schema version 10. In the abstract notation
for the evolution and migration operation, [vA ] and [vB ] is used for the version
information of the kinds KA and KB .
Generally, SA can be derived by iterating over all entities of EA and collect all
attribute names. Nevertheless, SA is stored as well to support a query rewriting
approach presented in [9].
3 Semantics of the Evolution Operations
In this section, we define the semantics of the evolution operations on regular
structures and structured datasets, and we will extend them to irregular struc-
tures and heterogeneous datasets. The evolution operations were introduced for
the first time as EBNF and as a NoSQL programming language in [14] and since
that time continously extended. The chosen evolution operations add, rename,
delete, move and copy represent a set of frequent schema evolution operations
Keeping NoSQL Databases up to date 5
in open source applications (c.f. [3]). The effort for data migration increases ac-
cordingly to the HC. In order to define the concrete heterogeneity classes, pre-
and postconditions are used to determine the regularity of the data. The pre-
and postconditions are inspired by the Hoare triple. These conditions are compa-
rable with the concept of design by contract. Operations are only executed if the
preconditions are fulfilled, otherwise they will be rejected. After the execution
of an operation, the postconditions are guaranteed.
Hereafter we define the single-type operation add and the multi-type opera-
tion move. The semantics for the complete evolution language is given in [10].
3.1 Heterogeneity Class 1
Operations in HC1 assumes that in a dataset all entities of a kind have the same
schema within the same schema version. Hence, there is no possibility to have
datasets with optional properties. For multi-type operations, this class can only
cope with matches of 1:1 cardinalities.
Each of the operations evolves the schema and migrates the entities into the
new version. On the instance level, the operation modifies the data structure
and updates affected instances. The effects of the evolution operations have to
be defined on the schema level and the instance level. Evolution operations are
defined as rules whereby the left side of a rule describes the schema/instances
before the operation while the right side describes the schema/instances after
the operation. All rules consist of a precondition which needs to hold before the
operation. If the condition is not fulfilled, the operation is not executed. The
postconditions are fulfilled after the operation and will become important for
the chaining of operations and for the examination of Data the Quality.
The Add Operation This operation adds a property to all entities of a kind.
The operation specifies the kind, the new property name and additionally, the
default property value. In HC1, the add operation is defined as:
B add A.X = d
precond : {X 6∈ SA[vA ] }
SA (A1 , . . . , An )[vA ] → SA (X, A1 , . . . , An )[vA +1]
∀ei ∈ EA : (ei (a1 , . . . , an )[vA ] → ei ((X : d), a1 , . . . , an )[vA +1] )
postcond : {X ∈ SA[vA +1] }
First, the operation verifies that the precondition is fulfilled which states that
the name of the property is not allowed to be available in the schema of KA in the
version vA . The second line describes the schema evolution of KA . In version vA ,
schema SA consists of n properties A1 , . . . , An . After the operation in version
vA + 1, the schema consists of n + 1 properties including the added property
named X. The third line describes the instance level modification of each entity
of KA . Each entity consists of the properties a1 to an and additionally the new
property (X : d) whereby X is the name of the added property and d is the
6 ML. Möller, M. Klettke, U. Störl
default value. After the modification of the schema and the entity migration,
the postcondition holds which states that property name X is part of SA in
version vA + 1. As a variant of the given semantics, it is possible to add a
property without default value: add A.X. In this case, the property (X : ⊥) is
added whereby ⊥ represents a Null value.
The Move Operation The multi-type operation move transfers a property
from the entities of one kind (termed as source kind ) to entities of a different
kind (termed as target kind ). To execute a multi-type operation, a matching
condition between both kind is mandatory. In HC1, the matching cardinality is
assumed as 1:1, which entails bijectivity so that every entity of the source kind
has exactly one match with an entity of the target kind, and vice versa. This
also presumes that the value of the matching condition is unique for each entity
and there is neither an entity on the source side nor on the target side that does
not have a matching partner. Consequently, multi-entity operations in HC1 are
restricted to kinds with the same amount of entities.
In HC1, the semantics of the move operation is defined as follows:
B move A.X To B.Z where A.K = B.F
precond : {X ∈ SA[vA ] , Z 6∈ SB[vB ] }
SA (X, K, A3 , . . . , An )[vA ] → SA (K, A3 , . . . , An )[vA +1]
SB (F, B2 , . . . , Bm )[vB ] → SB (Z, F, B2 , . . . , Bm )[vB +1]
∀ei ∈ EA , ej ∈ EB , ei .K = ej .F :
(ei ((X : x), (K : k), ai3 , . . . , ain )[vA ] ∧ ej ((F : k), bj2 , . . . , bjm )[vB ]
→ ei ((K : k), ai3 , . . . , ain )[vA +1] ∧ ej ((Z : x), (F : k), bj2 , . . . , bjm )[vB +1] )
postcond : {X ∈
/ SA[vA +1] , Z ∈ SB[vB +1] }
Beside the matching condition, the source and target kinds as well as the
property names are specified. Here, these are KA with the property X and KB
with property Z. The move operations implicitly realizes a rename operation if
the property names of the source and target kinds are different. In the where
clause, the matching condition is explicitly specified.
Before the operation, SA of KA contains the property name X, while SB of
the KB does not. On the schema level, it is apparent that the moved property
X is not present anymore in SA after the operation execution. Instead, SB
now contains Z. During the operation, all entities ei and ej are modified. The
property (X : x) is not present anymore in any entity of KA while (Z : x)
is part of each entity of KB . The same symbol x on the left and on the right
hand side of the rule indicate the same property value – the value is transferred
without a modification from the source kind to the target by the operation. The
matching condition between both kinds is represented by the same property
value k ((K : k) for ei and (F : k) for ej ) as well.
Keeping NoSQL Databases up to date 7
3.2 Heterogeneity Classes 2 and 3
In heterogeneity classes 2 and 3, we assume structurally homogeneous data
within the same version, however, cardinalities are extended to 1:n in HC2 and
to m:n in HC3. Thus, it is necessary to deal with dangling tuples and multi
matches. Since HC2 and HC3 are inherited in HC4 in terms of their character-
istics, we will explain the properties and challenges of these HCs in the next
section. Furthermore, both HCs are discussed in detail in [10].
3.3 Heterogeneity Class 4
Evolution operations in HC4 cover the most complicated NoSQL databases con-
sidering all structural variants. In this HC, schema heterogeneity and multi-
entity operation of arbitrary cardinalities are included.
An example for challenges in HC4 is given in Figure 2. Here, an add operation
is executed and affects two entities of Kproject . For the property value of funder
of the entity with the id : 2 it is required to decide whether the value of funder is
either overwritten with the default value or preserved. The semantics is extended
by introducing the additional keywords overwrite and ignore for implementing
conflict resolution strategies.
For heterogeneous data, it is required to denote optionality in the semantics,
especially in the preconditions, since it is not known whether a certain property
occurs in all entities of a kind. Optional properties are labeled with a question
?
mark. For example, X ∈ SA states that X is an optional property in the schema
of kind A and can or cannot appear in an entity. This requires to deal with
both cases in the semantics. On the schema level, the notation SA (X?) is used
analogously.
The Add operation The definition of the add operation is given below. Here,
the overwrite approach is used which adds the property and the specified default
value to entities without that property. For entities that already contain the
property before of the operation, their affected property values are overwritten
by the operation’s default value.
In contrast to HC1, it is distinguished between the global conditions which
hold for the schema and all entities affected by the evolution operation, and case
conditions which only hold for a subset of the entities affected by the operation.
project project
{ id : 1, { id : 1,
1.1 } 2.1 funder : "M-V"
}
{ id : 2, { id : 2,
1.2 funder : "DFG" 2.2 funder : ?
} }
add project.funder = "M-V"
Fig. 2. Execution of the add operation on heterogeneous data in HC4
8 ML. Möller, M. Klettke, U. Störl
The definition of the evolution operation is divided into two cases: The first
case defines the operation for all datasets in which X is not available. A property
named X is added with the default value d. The second case defines the operation
for the datasets that already contain X. The existing value of the property X
is overwritten with the default value d. Analogously to HC1, this operation also
can be defined without a default value.
Please note that in HC4 all properties are considered as optional that do not
directly affect the operation (here: A2 , . . . , An ). For an improved readability, the
denotation for optionality is only given for properties that are affected by the
evolution operation (here: X).
B add overwrite A.X = d
?
global precond : {X ∈ SA }
SA (X?, A2 , . . . , An )[vt ] → SA (X, A2 , . . . , An )[vt+1 ]
∀ei ∈ EA[vt ] :
case precond : {X 6∈∗ ei[vt ] }
ei (ai2 , . . . , ain )[vt ]
case : X 6∈∗ ei[vt ]
→ ei ((X : d), ai2 , . . . , ain )[vt+1 ]
case postcond : {X ∈∗ ei[vt+1 ] }
case precond : {X ∈∗ ei[vt ] }
ei ((X : x), ai2 , . . . , ain )[vt ]
case : X ∈∗ ei[vt ]
→ ei ((X : d), ai2 , . . . , ain )[vt+1 ]
case postcond : {X ∈∗ ei[vt+1 ] }
global postcond : {X ∈ SA[vt+1 ] }
The Move Operation The definition of the move operation is more difficult
because it has to be defined for two kinds (source and target). It is necessary
to cope with both heterogeneity and arbitrary cardinalities in the semantics,
whereby even 1:1 matches entail complex problems. Let us extend the introduced
example by a second kind called metadata which at least consists of a prop-
erty called m id. Some entities of Kmetadata contain the property station name
as well. The database administrator wants to evolve the database schema by
moving station name from Kmetadata to Kproject . Since project consists of the
property station name as well, determining the property value is not trivial. Fig-
ure 3 depicts the cases that can occur with a matching cardinality of 1:1 for the
move operation in HC4. The first match describes the case where station name is
available in the corresponding entity of Kmetadata , but not in Kproject , and can
be moved easily. The second case describes where station name is not available
in Kmetadata yet in Kproject . For both introduced conflict resolution strategies
the pre-existing value for station name is preserved. The third case describes the
Keeping NoSQL Databases up to date 9
metadata project
{ m_id : 1, { p_id : 1
m1 station_name : "Ocean" p1 }
} move metadata.station_name
{ m_id : 2 to project.station_name { p_id : 2,
m2 } where metadata.m_id = project.p_id p2 station_name : "Baltic Sea"
}
{ m_id : 3 { p_id : 3
m3 } p3 }
{ m_id : 4, { p_id : 4,
m4 station_name : "West Coast" p4 station_name : "Oregon-3"
} }
Fig. 3. Emerging cases of the move operation with 1:1 matching cardinalities and
heterogeneous data
case that station name is neither available in Kmetadata nor in Kproject , here, a
property with an empty value will be introduced. The last case delineates that
station name is part of both entities. For the last case, the value of station name
depends on the conflict resolution strategy. All cases are required to be handled
by the semantics of the move operation in HC4.
On the schema level, it is established that the operation datetimestamp is
removed from the source kind, while the property datetimestamp is contained in
the target kind.
For all entities of the source kind without a matching partner, the property
is removed and for all entities of the target kind without a matching partner the
entity is assigned with a property of a Null value.
The formal semantics of the move overwrite operation for HC4 is given in
the Appendix of this paper. The semantics of all other single-type and multi-
type operations of the NoSQL evolution language and their different conflict
resolution approaches are described in [10].
4 Increased Data Quality through Schema Evolution
Quality of data entails several characteristics such as data completeness, data
actuality, and data consistency (c.f. [17]). Schema evolution can be applied for
refreshing the datasets and in parallel increasing the data quality and in some
cases decreasing the HC. Both will be sketched in the following.
Data Actuality The main focus of the evolution lies on updating datasets and
migrating them into the latest version. In our previous work, we have introduced
methods for an eager data migration (immediately after introducing a new ver-
sion), lazy migration (on demand, if datasets are accessed) or by using hybrid
strategies [6], [8]. In all cases, datasets are transformed into the actual schema
version. This enables that legacy datasets can be updated, transformed into the
current structure and guarantees data actuality.
10 ML. Möller, M. Klettke, U. Störl
Data Completeness and Data Consistency The NoSQL evolution opera-
tions presented in this paper never increase the heterogeneity of the databases.
After execution data migration operations the databases always remain in the
same HC as the source datasets. Even further, the operations can be used to in-
crease regularity and completeness of the NoSQL databases, and in some cases to
reduce the heterogeneity class and so improve the data quality. In the following
we will present this in more detail for the heterogeneity classes.
Reconsidering the given semantics, it is evident that data in heterogeneity
class 1 or 2 always remain in this class due to the restrictions of the pre- and
postconditions, the heterogeneity and the matching conditions. For both HCs
there are no optional properties and operations always affect all entities of a kind.
Concluding, it is impossible to transform data without optional properties into
schema-heterogeneous data. For multi-type operations with the same matching
condition, the cardinality remains the same, even for chained operations.
In HC3, the same argumentation holds for optional properties. Regarding
cardinalities, data in HC3 also remains in this HC for two multi-entity oper-
ations with the same matching condition. Nevertheless, the conflict resolution
approaches provide an advantage. Consider two kinds with a n:1 relation (en-
compassed in HC3), e.g. two entities of Kmetadata (caused by duplicates) belong
to a single entity of Kproject . Selecting data from both kinds using a join oper-
ation normally returns two result rows. By evolving the database and moving
all properties from the entities of Kmetadata to Kproject using overwrite or ig-
nore results in a concrete property value for all properties moved to the entity
of Kproject . Nevertheless, depending on the application, it might be a downside
that for both strategies because a subset of property values is lost after the move
or copy operation. A better solution can be the generation of an array of values
to collect the values of all matching partners while decreasing heterogeneity.
For data in HC4, it can be possible to transform this data into lower het-
erogeneity classes. Only HC4 copes with optional properties. Consider Kproject
from the example on page 4 where the only optional property budget is not exis-
tent in each entity. After an add operation (with an arbitrary conflict resolution
approach) on Kproject , all entities have a homogeneous schema. Hence, evolution
operations can be used this way in order to increase the schema-homogeneity of
NoSQL datasets.
5 Related Work
The main aspect of this paper deals with the semantics for NoSQL schema
evolution operations and data migration for different heterogeneity classes. Ad-
ditionally, we presented the impact of evolution operations on data quality. In
this section, we present approaches and concepts related to ours.
In [7], the authors present an approach for schema mapping. Similar to our
semantics, a mapping consists of a source and a target schema, and a set of for-
mulas of some logic over both schemas. The used formalism to describe database
dependencies are Tuple-generating dependencies (TGDs) (see also [12], [1]).
Keeping NoSQL Databases up to date 11
In [5], several schema versions are being maintained within a single relational
database. In that publication a language for bidirectional schema evolution and
forwards and backwards delta code generation is defined to support multiple
versions of an application while maintaining only one database with co-existing
schema versions.
Schildgen presents in [15] the language NotaQL to transform NoSQL data
and uses this language to overcome different kinds of heterogeneity.
Data quality is a long studied field in relational database theory and covers
a broad field of characteristics, such as data homogeneity, data correctness, and
data completeness. An overview of data integration steps and tools in practice
is given in [4]. Naumann describes in [11] research directions and challenges of
data quality and classifies different data profiling subtasks. The aspects of the
duplicate elimination/coping redundancy can be part of a data cleansing pro-
cess (c.f. [2]). Our presented semantics eliminates multiple values for properties
that are affected by schema evolution operations by using the overwrite or ignore
approach. This avoids a duplication of records with only one different property
value. In contrast to other data cleansing approaches, we are focusing on trans-
formation of NoSQL dataset into the current version and in parallel increasing
the regularity of the databases. The transformation process is described by the
evolution operations.
In our research project Darwin [16], we realized the evolution for MongoDB,
Cassandra and CouchDB for the single- and multi-type operations in HC1 and
HC2.
6 Summary and Future Work
In agile development environments, data structures are often changed which
necessitates the definition of schema evolution operations. For efficient schema
evolution, schema evolution operations were defined that take the characteristics
of NoSQL data, such as data heterogeneity, into account.
In this article, we introduced NoSQL heterogeneity classes which relate to
the complexity of operations. We presented as a subset of our schema evolu-
tion language the semantics for the single-type operation add and the multi-type
move for different HCs. We have shown the complexity of the operations in dif-
ferent heterogeneity classes and why evolving the schema allows to improve data
quality under certain conditions. Storing completely unstructured and hetero-
geneous data is very uncommon, even in the NoSQL world – applications often
require a certain schema for reading and processing data. Hence, datasets are
stored homogeneously. Data in higher heterogeneity classes require sophisticated
evolution and migration operations. In this article, we have shown that the pre-
sented semantics is able to migrate into a lower heterogeneity class when certain
requirements are met.
In the future, we plan to extend the semantics by introducing further schema
evolution operations. The current operations have been chosen due to an analysis
of schema changes in open-source applications like Wikipedia (c.f. [3]). Further
12 ML. Möller, M. Klettke, U. Störl
operations such as split and merge are possible and useful as well. We plan
to estimate and benchmark the impact of schema heterogeneity and low data
quality for various scenarios, such as schema evolution or query rewriting in
environments where data is lazily migrated as examined in [9].
Acknowledgements This article is published in the scope of the project
“NoSQL Schema Evolution und Big Data Migration at Scale” which is funded
by the Deutsche Forschungsgemeinschaft (DFG) under the number 385808805. A
special thanks goes to Stefanie Scherzinger, Andrea Hillenbrand, Dennis Marten,
Tanja Auge, and Hannes Grunert for their support, comments on this work, and
several discussions. We thank all reviewers for their constructive feedback.
References
1. Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley
(1995), http://webdam.inria.fr/Alice/
2. Bench-Capon, T.J.M., Soda, G., Tjoa, A.M. (eds.): DEXA ’99, Florence, Italy,
Proc. LNCS, vol. 1677. Springer (1999)
3. Curino, C., Moon, H.J., Tanca, L., Zaniolo, C.: Schema Evolution in Wikipedia -
Toward a Web Information System Benchmark. In: Proc. ICEIS’08 (2008)
4. Haas, L.M.: Beauty and the beast: The theory and practice of information inte-
gration. In: ICDT. Springer LNCS, vol. 4353, pp. 28–43. Springer (2007)
5. Herrmann, K., Voigt, H., Rausch, J., et al.: Living in Parallel Realities — Co-
Existing Schema Versions with a Bidirectional Database Evolution Language. In:
Proc. SIGMOD (2017)
6. Klettke, M., Störl, U., Shenavai, M., et al.: NoSQL Schema Evolution and Big Data
Migration at Scale. In: IEEE Big Data 2016, Washington DC. IEEE (2016)
7. Kolaitis, P.G.: Schema mappings, data exchange, and metadata management. In:
PODS. pp. 61–75. ACM (2005)
8. Möller, M.L.: Datenevolutions- und Migrationsstrategien in NoSQL-Datenbanken.
In: Grundlagen von Datenbanken. CEUR Workshop Proc., vol. 2126 (2018)
9. Möller, M.L., Klettke, M., Hillebrand, A., et al.: Query Rewriting for Continuously
Evolving NoSQL Databases (2019), accepted for ER2019, Salvador, Brazil
10. Möller, M.L., Klettke, M., Störl, U.: Formal Semantics of NoSQL Evolution Opera-
tions under different Heterogeneity Levels (2018), Tech. Report, Rostock University
11. Naumann, F.: Data profiling revisited. SIGMOD Record 42(4), 40–49 (2013)
12. Pichler, R., Skritek, S.: The Complexity of Evaluating Tuple Generating Depen-
dencies. In: ICDT 2011, Uppsala, 2011. ACM (2011)
13. Roddick, J.F.: Schema Evolution in Database Systems - An Annotated Bibliogra-
phy. SIGMOD record 21(4), 35–40 (1992)
14. Scherzinger, S., Klettke, M., Störl, U.: Managing schema evolution in nosql data
stores. Proc. DBPL CoRR, abs/1308.0514, abs/1308.0514 (2013)
15. Schildgen, J., Deßloch, S.: Heterogenität überwinden mit der Datentransforma-
tionssprache NotaQL. Datenbank-Spektrum 16(1), 5–15 (Mar 2016)
16. Störl, U., Müller, D., Tekleab, A., et al.: Curating variational data in application
development. In: ICDE. pp. 1605–1608. IEEE Computer Society (2018)
17. Strong, D.M., Lee, Y.W., Wang, R.Y.: Data Quality in Context. Commun. ACM
40(5), 103–110 (1997)
Keeping NoSQL Databases up to date 13
A Appendix
Move Overwrite Semantics in Heterogeneity Class 4
B move overwrite A.X to B.Z where A.K = B.F
? ?
global precond : {X ∈ SA[va ] , Z ∈ SB[vb ] }
SA (X?, K?, A3 ?, . . . , An ?)[va ] → SA (K?, A3 ?, . . . , An ?)[va +1]
SB (F ?, B2 ?, . . . , Bm ?)[vb ] → SB (Z, F ?, B2 ?, . . . , Bm ?)[vb +1]
∀ei ∈ EA , ej ∈ EB , ei .K = ej .F :
∗ ∗
case precond : {X ∈ ei[va ] ∧ Z ∈ / ej[vb ] }
(e ((X : x), (K : k), a , . . . , a )
i i i
[va ]
3 n
∗
∧ ej ((F : k), bj2 , . . . , bjm )[vb ]
case : Z ∈ / ej[vb ]
→ ei ((X : x), (K : k), ai3 , . . . , ain )[va ]
∧ ej ((Z : x), (F : k), bj2 , . . . , bjm )[vb ] )
∗ ∗
case postcond : {X ∈ ei[va ] ∧ Z ∈ ej[vb ] }
∗ ∗
{X ∈ ∧ ∈ ej[vb ] }
case precond : e Z
i[v a ]
(ei ((X : x), (K : k), ai3 , . . . , ain )[va ]
∗
case : X ∈ ei[va ]
∗
∧ ej ((Z : z), (F : k), bj2 , . . . , bjm )[vb ]
case : Z ∈ ej[vb ]
→ ei ((X : x), (K : k), ai3 , . . . , ain )[va ]
∧ ej ((Z : x), (F : k), bj2 , . . . , bjm )[vb ] )
∗ ∗
case postcond : {X ∈ ei[va ] ∧ Z ∈ ej[vb ] }
ei ((X : x), (K : k), ai3 , . . . , ain )[va ]
→ ei ((K : k), ai3 , . . . , ain )[va +1]
e → ej[vb +1]
j[vb ]
∗ ∗
case postcond : {X ∈ / ei[va +1] ∧ Z ∈ ej[vb +1] }
∗ ∗
case precond : {X ∈ / ei[va ] ∧ Z ∈ ej[vb ] }
(ei ((K : k), ai3 , . . . , ain )[va ]
∗
∧ ej ((Z : z), (F : k), bj2 , . . . , bjm )[vb ]
case : Z ∈ e
j[vb ]
→ ei ((K : k), ai3 , . . . , ain )[va ]
∧ ej ((Z : z), (F : k), bj2 , . . . , bjm )[vb ] )
∗ ∗
case postcond : {X ∈ / ei[va ] ∧ Z ∈ ej[vb ] }
∗ ∗
case precond : {X ∈ / ei[va ] ∧ Z ∈ / ej[vb ] }
∗
case : X ∈/ ei[va ] (ei ((K : k), ai3 , . . . , ain )[va ]
∗
∧ ej ((F : k), bj2 , . . . , bjm )[vb ]
case : Z ∈ / ej[vb ]
→ ei ((K : k), ai3 , . . . , ain )[va ]
x ∧ ej ((Z : ⊥), (F : k), bj2 , . . . , bjm )[vb ] )
∗ ∗
case postcond : {X ∈ / ei[va ] ∧ Z ∈ ej[vb ] }
e → e
i[va ]
i[va +1]
ej[vb ] → ej[vb +1]
∗ ∗
case postcond : {X ∈ / ei[va +1] ∧ Z ∈ ej[vb +1] }
(∀ei ∈ EA :6 ∃ej ∈ EB : ei .K = ej .F ) ∨ (∀ej ∈ EB 6 ∃ei ∈ EA : ej .F = ei .K) :
(ei ((X : x), (K : k), ai3 , . . . , ain )[va ] → ei ((K : k), ai3 , . . . , ain )[va +1] )
(ei ((K : k), ai3 , . . . , ain )[va ] → ei ((K : k), ai3 , . . . , ain )[va +1] )
(ej ((Z : z), (F : k), bj2 , . . . , bjm )[vb ] → ej ((Z : z), (F : k), bj2 , . . . , bjm )[vb +1] )
(ej ((F : k), bj2 , . . . , bjm )[vb ] → ej ((Z : ⊥), (F : k), bj2 , . . . , bjm )[vb +1] )
global postcond : {X ∈
/ SA[va +1] , Z ∈ SB[vb +1] }