Evolving a NoSQL database schema regularly involves migrating datasets into new schema versions. NoSQL databases store datasets in di erent 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 di erent 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.
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
structure. While for relational databases schema evolution has been studied in detail
in the past [
The majority of NoSQL database systems can be used for storing datasets with di erent characteristics: 1. No or limited schema control: In NoSQL, neither schema information nor semantical constraints have to be de ned before the actual storing of the datasets. Thus, datasets with di erent 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 applications or object mappers resulting in data structures that are checked in ? Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 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 di erent 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, e cient 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.
m:n s e iit n:1 l a n i rad1:n C 3
4 1:1 Dn1aongling Tupylee2ss hogmenoSe-toruushctegutee(rnrianoel-oHsuaemsteegvoerresnioeint)y (a) Three dimensions of the four NoSQL HCs
C o p y
Add
A4
A1 D1 C4 C3 C2 C1 M1 R1
M2 M3 M4
Delete D4
R4 e m a n e
R
Move (b) Heterogeneity Classes of the
Evolution Operations
First, we are introducing di erent degrees of NoSQL heterogeneity. Figure 1(a) visualizes the three dimensions that have to be considered. The rst 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 operations 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 affected by multi-type operations. Becauses NoSQL databases do not check semantic constraints in advance, it is required to di erentiate 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 di erent heterogeneity classes (HCs) per schema evolution operations, starting from the most structured datasets and 1:1 cardinalities up to unstructured datasets and arbitrary cardinalities.
HC1: In this class, the operation a ects datasets in the same or di erent structural versions (e.g., when lazy migration approaches are used), yet all datasets in the same version have exactly the same structure. Multi-type operations 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 required to deal with dangling tuples.
HC3: The third class encompasses HC2 with arbitrary cardinalities. Additional strategies are required for determining property values of entities a ected by multi-entity operations with n:m cardinalities.
HC4: The fourth class represents NoSQL databases that can have di erent 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 di erent heterogeneity classes (HC1-HC4) for NoSQL. Based on these heterogeneity classes, we de ne 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 simpli ed. { We discuss the impact on schema evolution operations on the data quality in
Section 4, namely data actuality, data completeness, and data consistency. 2
Our NoSQL evolution language contains three single-type operations, add, delete and rename, and two multi-type operations, move and copy. The operations are de ned 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 de ned as KA = (SA; EA).
The schema SA is de ned as a set of property-names, SA = fA1; : : : ; Ang. The set of entities EA of KA over the schema SA is de ned as EA := fe1; : : : ; emg 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 2 (1; : : : ; m) and j 2 (1; : : : ; n). Formally, ei = faij j j 2 f1; : : : ngg.
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 ) 2 SAi DAi , whereby SAi SA and DAi DA. Here, SAi DAi represents the domain of the property.
Example. To illustrate the de nitions, let us consider an example for the representation of a subset of a research project database which stores information about research stations, the name of the funder of the project, and the budget. The kind is called project and is de ned as Kproject = fSproject; Eprojectg, whereby Sproject = f"p id"; "station name"; "funder"; "budget"g. 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 2 is de ned which evaluates if there is a property available for a given entity or not. For this purpose, we de ne a projection operation that projects onto the property name: A := SAi DAi ! SAi with (Aij ; vij ) 7! Aij . Based on this projection, the 2 operator is de ned. X 2 ei :, 9aij 2 ei : X 2 A(aij ), and X 2 EA :, 8ei 2 EA : X 2 ei.
Reconsider the previous example. Here, "station name" 2 e1 is True while "location" 2 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: 8X 2 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 evaluates to "Baltic Sea", while e1:location throws an exception.
Due to migration and encompassed di erent schema versions, the same kind
is inspected at di erent points in time. For this, a notation of a version is
introduced in the form of in square brackets. For instance, SA[
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 [
In this section, we de ne the semantics of the evolution operations on regular
structures and structured datasets, and we will extend them to irregular
structures and heterogeneous datasets. The evolution operations were introduced for
the rst time as EBNF and as a NoSQL programming language in [
Hereafter we de ne the single-type operation add and the multi-type
operation move. The semantics for the complete evolution language is given in [
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 modi es the data structure and updates a ected instances. The e ects of the evolution operations have to be de ned on the schema level and the instance level. Evolution operations are de ned 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 ful lled, the operation is not executed. The postconditions are ful lled 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 speci es the kind, the new property name and additionally, the default property value. In HC1, the add operation is de ned as:
B add A.X = d
precond : fX 62 SA[vA]g
SA(A1; : : : ; An)[vA] ! SA(X; A1; : : : ; An)[vA+1] 8ei 2 EA : (ei(a1; : : : ; an)[vA] ! ei((X : d); a1; : : : ; an)[vA+1])
postcond : fX 2 SA[vA+1]g First, the operation veri es that the precondition is ful lled 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 modi cation 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 default value. After the modi cation 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 di erent 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 de ned as follows: B move A.X To B.Z where A.K = B.F
precond : fX 2 SA[vA]; Z 62 SB[vB]g SA(X; K; A3; : : : ; An)[vA] ! SA(K; A3; : : : ; An)[vA+1] SB(F; B2; : : : ; Bm)[vB] ! SB(Z; F; B2; : : : ; Bm)[vB+1]
8ei 2 EA; ej 2 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 : fX 2= SA[vA+1]; Z 2 SB[vB+1]g
Beside the matching condition, the source and target kinds as well as the property names are speci ed. 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 di erent. In the where clause, the matching condition is explicitly speci ed.
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 modi ed. 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 modi cation 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.
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
characteristics, we will explain the properties and challenges of these HCs in the next
section. Furthermore, both HCs are discussed in detail in [
Evolution operations in HC4 cover the most complicated NoSQL databases considering all structural variants. In this HC, schema heterogeneity and multientity operation of arbitrary cardinalities are included.
An example for challenges in HC4 is given in Figure 2. Here, an add operation is executed and a ects 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 con ict 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 2 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 de nition of the add operation is given below. Here, the overwrite approach is used which adds the property and the speci ed default value to entities without that property. For entities that already contain the property before of the operation, their a ected 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 a ected by the evolution operation, and case conditions which only hold for a subset of the entities a ected by the operation. project funder : "DFG : 1, : 2, project : 1, : 2,
? add project.funder = "M-V"
Fig. 2. Execution of the add operation on heterogeneous data in HC4
The de nition of the evolution operation is divided into two cases: The rst case de nes 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 de nes 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 de ned without a default value.
Please note that in HC4 all properties are considered as optional that do not directly a ect the operation (here: A2; : : : ; An). For an improved readability, the denotation for optionality is only given for properties that are a ected by the evolution operation (here: X).
B add overwrite A.X = d 8ei 2 EA[vt] :
global precond : fX 2? SAg
SA(X?; A2; : : : ; An)[vt] ! SA(X; A2; : : : ; An)[vt+1] case : X 62 ei[vt] case : X 2 ei[vt] 8 > > > < > > > : 8 > > > < > > > : case precond : fX 62 ei[vt]g ei(ai2 ; : : : ; ain )[vt] ! ei((X : d); ai2 ; : : : ; ain )[vt+1] case postcond : fX 2 ei[vt+1]g case precond : fX 2 ei[vt]g ei((X : x); ai2 ; : : : ; ain )[vt] ! ei((X : d); ai2 ; : : : ; ain )[vt+1] case postcond : fX 2 ei[vt+1]g global postcond : fX 2 SA[vt+1]g The Move Operation The de nition of the move operation is more di cult because it has to be de ned 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 property 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. Figure 3 depicts the cases that can occur with a matching cardinality of 1:1 for the move operation in HC4. The rst 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 con ict resolution strategies the pre-existing value for station name is preserved. The third case describes the metadata m1 }{ m_id staion_me : "Ocean m2 }{ m_id : 1, : 2 move metadata.station_name
to project.station_name where metadata.m_id = project.p_id : 1 : 2, : 3 : 4, 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 con ict 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
multitype operations of the NoSQL evolution language and their di erent con ict
resolution approaches are described in [
Quality of data entails several characteristics such as data completeness, data
actuality, and data consistency (c.f. [
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 increase 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 a ect 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 operations with the same matching condition. Nevertheless, the con ict resolution approaches provide an advantage. Consider two kinds with a n:1 relation (encompassed 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 operation normally returns two result rows. By evolving the database and moving all properties from the entities of Kmetadata to Kproject using overwrite or ignore 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 heterogeneity classes. Only HC4 copes with optional properties. Consider Kproject from the example on page 4 where the only optional property budget is not existent in each entity. After an add operation (with an arbitrary con ict 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
The main aspect of this paper deals with the semantics for NoSQL schema evolution operations and data migration for di erent heterogeneity classes. Additionally, we presented the impact of evolution operations on data quality. In this section, we present approaches and concepts related to ours.
In [
In [
Schildgen presents in [
Data quality is a long studied eld in relational database theory and covers
a broad eld of characteristics, such as data homogeneity, data correctness, and
data completeness. An overview of data integration steps and tools in practice
is given in [
In our research project Darwin [
In agile development environments, data structures are often changed which necessitates the de nition of schema evolution operations. For e cient schema evolution, schema evolution operations were de ned 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 evolution language the semantics for the single-type operation add and the multi-type move for di erent HCs. We have shown the complexity of the operations in different heterogeneity classes and why evolving the schema allows to improve data quality under certain conditions. Storing completely unstructured and heterogeneous 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 presented 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. [
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.
B move overwrite A.X to B.Z where A.K = B.F SA(X?; K?; A3?; : : : ; An?)[va] ! SA(K?; A3?; : : : ; An?)[va+1]
SB(F ?; B2?; : : : ; Bm?)[vb] ! SB(Z; F ?; B2?; : : : ; Bm?)[vb+1] 8ei 2 EA; ej 2 EB; ei:K = ej :F : 8 8 case precond : fX 2 ei[va] ^ Z 2= ej[vb]g >>>>>>>> >>>>>><> (ei^((eXj ((:Fx):; k(K); b:jk2);;: a:i:3; ;b:jm::);[avbin] )[va] >>>>>>><>>>>>>>>>>>>>>>case : Z 2= ej[vb] 8>>>>>>><>:>>>>>> ccaa(!sseeei^^(epp(eeiXrojj(es(((tc((:XcoZZxon):n::d;xdxz(:)K)):;f;;(f(X(K:FXFk2):::2;kkka)))ei;;;e3ibab[i;vj[jiv:a223a:];;;:]:^::;^:::a:Z::Zi;;;nbba2j)2jim[mnvae)))e[j[][vvvj[vab[bvb]]]b])g]g >>>>>>>>>>>>>>>case : Z 2 ej[vb] >>>>:>>> ca!se^epeioj(s((t(XcZo:n:xdx)):;;(f(KXF ::2kk));;eabi[jiv23a;;]:: ^:::: Z;;ba2jimn))e[[vvja[bv]]b)]g > >> ei((X : x); (K : k); ai3 ; : : : ; ain )[va] > > >>>> ! ei((K : k); ai3 ; : : : ; ain )[va+1] > >>>>:> ceaj[sveb]p!ostecjo[vnbd+:1]fX 2= ei[va+1] ^ Z 2 ej[vb+1]g (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 : fX 2= SA[va+1]; Z 2 SB[vb+1]g