The schema flexibility of database management systems is often seen as an advantage, because it makes it easy to store all kinds of diferent data. Schema-less database systems (such as JSON or graph databases) allow structurally diferent data to be stored in the same database. It also allows storing diferent variants of data or data evolving over time. However, their use is much more complicated compared to relational data. In this paper, we show the impact of heterogeneity on two data processing steps: query execution and evolution operations including their composition and data transformation. From this, we will derive three proposals: (i) storing data with a partial schema management, (ii) vertical partitioning, and (iii) the usage of multi-model databases. In all cases, regular and irregular parts are distinguished in order to mitigate these efects of heterogeneity.
For a long time, the relational data model [
The benefits of these systems (XML, JSON and graph databases) were highly valued because
they can store all kinds of data. The disadvantages are equally obvious: when using schema-less
or schema-flexible databases, all structural variants of the data must be considered in all database
components and also their downstream applications that access the database. This leads to
additional challenges in a lot of database tasks. Significant efort was put into solving challenges
arising from the flexible schema imposed by NoSQL databases, e.g. schema design [
When thinking about optimizing schema modifications, we had an initial presumption that
Schema Modification Operators (SMOs) similar to those suggested in [
Applying these SMOs (add & rename) to a JSON document, they are translated into data migration operations. Because of schema-lessness, i.e., the lack of schema, we have to consider the diferent variants of datasets. Figure 1 represents this example for an entity type Students and the properties institution and university. Here, we see that the step-wise execution of the two SMOs add and rename produces a diferent output than a composed execution. This means that the composition rule does not hold for heterogeneous datasets.
{ "id": 1, The example shows that { """"ifpfdira"rom:sfitel1sy,nsainmoaenm""e::":""As"ntSnucedh"em,nitd"t"}, add institution="UaRd"d+urneinvearmseitiny=s"tUiRt"ution to university { """"""""iuffppffdnairrai"imroomr:visffiselteelt1ryssy,snssninaiinatamooamymennme"e"""e"":::":=::""""""Ass"AUSnttSnRcnuucn"heddhem"eem"}i,nni,dttdt""t",,",, itanhl weNapyoosSsQshiLbavileditayttoaobfcaoshenesstiedwreoer"university" = "UR" } geneity. In this paper, we { """""iffpidairn"mros:isftltei1yst,nsunaitamoimenoe""n"::"::"""Ms"SatFcruhhidGuae"l"nz,t}"", add institution="UaRd"d+urneinvearmseitiny=s"tUiRt"ution to university {{ """"""""iipuffffddrnaiia""oimrrm::fvissieelttl11sryy,,ssnniinaanotammanymeem""e""e:"::"=::"""s""AA"tFSnnSuhcnncdGheehe"m""mni,,it}dd"tt,"",, eeprxroeegsceeunnteitoittnyhetahinmrdopuaegcvhtoolqufutheioernty"""piurnnosiftveiestrsusitioitnoy"n":"="=s"t"UuFRdh"eGn"}t,", operations including their composition based on our
Figure 1: Composition of two SMOs on a heterogeneous dataset experiences.
We will use four diferent heterogeneity classes (HCs) , ranging from very regular (HC1) to very irregular (HC4) (see Section 2). We will show how database subtasks have to be adapted to these heterogeneity classes in Section 3. We start by querying heterogeneous data and show why it can deliver unwanted results. Next, we define the semantics of database evolution operations for the diferent HCs. Then, we describe why the composition of evolution operations becomes more complicated the higher the heterogeneity level. Finally, we briefly explain data transformation and query rewriting for the diferent heterogeneity classes. Based on these observations, we propose diferent data storage solutions for hybrid data consisting of homogeneous and heterogeneous parts (Section 4). Finally, we close with some ideas for future work.
Due to the inherent schema of NoSQL data, we can distinguish diferent levels of heterogeneity.
Data can be present in a completely homogeneous structure where each entity consists of the
same properties. However, it is also possible for properties to only occur in some entities. In
this case, the properties are considered as optional and the entities of the entity type are called
heterogeneous. We introduced four heterogeneity classes (HCs) which influence the complexity
of SMOs [
HC1: All entities of a database are homogeneous which means they have the same implicit structure.
Note: In the case of multi-type operations, i.e., using data from two entity types, only 1:1 or 1:n relationships occur without dangling tuples.
HC2: Multi-type operations with 1:1 and 1:n relationships can create dangling tuples, i.e., join operations with datasets without a join partner.
HC3: Multi-type operations with n:1 and n:m relationships can create dangling tuples. HC4: Databases can contain entities with diferent structures, i.e., two entities from the same entity type can have diferent properties. Note: This heterogeneity class is the most lfexible one. Every possible variant of the data must be considered in all operations.
If we do not have further information, we always have to assume HC4 because there are neither schema constraints nor semantic constraints which can be guaranteed. In contrast, if HC1 can be assumed, querying and evolving databases is much easier. In Section 3, we will demonstrate these two cases.
When databases are stored without a fixed schema, they can vary structurally from entity to entity. Also, checking for semantic constraints is not part of the data insertion process. Thus, in database management systems containing foreign key references, so-called dangling tuples can occur. In this section, we will briefly outline a few cases that illustrate the impact of structural heterogeneity and dangling tuples when using or querying data.
Using and Querying Homogeneous and Heterogeneous Data To demonstrate the efects of heterogeneity, let’s look at a concrete example implemented in MongoDB1. As seen in Figure 3, the university database contains entities with diferent structures. For instance, the attributes cId and courseId of the Student document with "id":2 both describe identical attributes, 1 MongoDB: https://www.mongodb.com/ { "pid": 1, "name": "Schmidt", "profession": "student", "university": "UR", "courses": [{ "cId": "MEI-M01", "semester": "SoSe_22“ }]} { "id": 2, "name": "Schulz", "institution": "UR", "courses": [ { "cId": "MEI-M01" }, { “cId": "MEI-M05“ }]}
Student { "id": 3, "name":"Huber", "profession":"student", "institution": "UR" } { "cId": "MEI-M01", "title": "Java", "ECTS": 6 } { “courseId": "MEI-M05", "title": "Python" }
Course but have diferent property 2 names. Another case of heterogeneity is the optionality of the attribute profession. There is also a lack of courses in Student with "id":3. All in all, the database can be classified as HC4 following the taxonomy defined in Section 2. db.getCollection("Student").find(
{ institution: "UR" } ) db.Student.aggregate([{ $lookup: { from: "Course", localField: "courses.cId", foreignField: "cId", as: "courses"} }]) Query 1: Querying the Student documents with institution="UR" (in MongoDB)
Query 2: Joining the collections Student and Course by property cId (in MongoDB) Example 1: Query 1 filters all Students by the condition institution="UR". The results, shown in Query result 2, contains the Student documents with "id":2 and "id":3. Due to variation in the attribute names (institution or university), the Student document with "pid":1 is not in the result. Users unaware of the heterogeneity in their data could expect an output of all three entities. { id: 2, name: "Schulz", institution: "UR", courses: [ { cId: "MEI-M01" }, { cId: "MEI-M05" }]} Query result 1: Results of Query 1 { id: 3, name: "Huber", profession: "student", institution: "UR" } Example 2: Query 2 shows a join between the Student and Course documents. It yields one course for Student documents each with "pid":1 and "id":2. This is a result of performing the lookup function which corresponds to a left outer join with the condition Student. courses.cId = Course.cId. Additionally, the Student document with "id":2 contains a second course with "cId":"MEI-M05". This attribute has no joining partner in the Course document. Because of the incorrect attribute name, courseId represents a dangling tuple. 2 Attributes and properties are used interchangeably as they describe the same element in diferent database management systems.
The result of the join between Student and Course documents are summarized in the Query
result 2. In this result, the Student document with "id":3 has a courses attribute containing
"courseId":"MEI-M05". This unexpected result is caused by the structural heterogeneity of
the Course document. The lookup function sets the value of the localField (in our example
the Student document with "id":3) and the foreignField (the Course document with
cId) to NULL. In the query execution, both values are NULL [
To avoid this unwanted efect and address the problem of missing values being set to NULL, one could introduce a match stage before executing the lookup function. This filters for Student documents containing a courses attribute and is implemented in MongoDB as follows: $match:{"courses":{"$exists":true,"$ne":[]}}}. { pid: 1, name: "Schmidt", profession: "student", institution: "UR", courses: [{ cId: "MEI-M01", title: "Java",
ECTS: 6 }]} Query result 2: Results of Query 2 { id: 2, name: "Schulz", institution: "UR", courses: [{ cId: "MEI-M01", title: "Java", ECTS: 6 }]} { id: 3, name: "Huber", profession: "student", institution: "UR", courses: [{ title: "Python", courseId: "MEI-M05" }]}
Both example queries show cases where schema and integrity constraints cannot be guaranteed and HC4 must be assumed. This leads to individual documents not being found by the queries; concretely: the Student document with "pid":1 in Query 1 or the Course document with "courseId":"MEI-M05" in Query 2. This is the case for both divergent property names and dangling tuples. The heterogeneity of the data must be considered not only in queries, but also in evolution. In the following, we will emphasize the dificulties heterogeneity brings in this context.
Semantics of Evolution Operations In databases which are used over a long time, evolution
operations like add, delete, rename, move, copy, split and merge must be performed. These
operations are suggested in several approaches for relational databases [
The HCs of the data afect how complex the evolution operations become. This heterogeneity classes hold for all schema-less databases. In the following, we define them for JSON database. If we can start from data in HC1 (regular, relational-like data, no dangling tuple), an operation add is defined as follows:
HC1: add . = ∀ ∈ : {..} − → {.., ”” : ””}.
It specifies that a new property with value is added to all entities of entity type . For a
detailed definition, we refer to [
If we execute the same operation on a dataset in HC4, we need to distinguish two cases: HC4: add . = : {︃ ∈ : ∈/ : {.., ”” : ””, ..} →− { .., ”” : ””, ..}, {..} →− { .., ”” : ””}.
The attribute can either already exist in the entity or not. Therefore, both cases must be considered. There are two diferent semantics of the operation: overwrite and ignore. In case a property is present and we are adding a property with the same key, then overwrite — as the name already says — overwrites the value in the database. When following the ignore semantics, the operation would be rejected keeping the previous value. In the definition of add . in HC4 from above, the ignore semantics is given.
In a similar way, we define a rename operation. Whereas in HC1 only one case sufices, for HC4 we have to distinguish four cases:
HC1: rename . to
∀ ∈ : {.., ”” : ””, ..} − → {.., ”” : ””, ..}.
⎪⎧⎪ ∈ ∧ ∈/ : {.., ”” : ””, ..} →− { .., ”” : ””, ..},
⎪⎪⎪⎪⎪ ∈ ∧ ∈ : {.., ”” : ””, ”” : ””..}
HC4: rename . to : ⎨⎪⎪ →− { .., ”” : ””, ”” : ””, ..},
⎪⎪ ∈/ ∧ ∈ : {.., ”” : ””, ..} →− { .., ”” : ””, ..},
⎪
⎪⎪⎪⎪⎪ ∈/ ∧ ∈/ : {..} →− { ..}.
⎪
⎩
We want to mention that the definition for HC1 corresponds to the first case of the definition
for HC4. Again, we difer between the ignore and overwrite semantics. In the definition of
rename . to . in HC4 from above, the ignore semantics is used which avoids overwriting
already available properties. For using overwrite, which is overwriting the already available
properties, the definition of rename . to has to be adapted. For details we refer to [
Most evolution approaches also ofer so-called multi-type operations like move, copy, split, and merge for a complex restructuring. Here, we also see large diferences in the definitions of semantics for diferent heterogeneity classes. We pick the move operation for HC1 and HC4 as an example. We define move 1. to 2. where 1.1 = 2.2 for HC1: ∀ ∈ 1, ∀ ∈ 2 : : {.., ”” : ””, ”1” : ””, ..}, : {.., ”2” : ””, ..} →− : {.., ”1” : ””, ..}, : {.., ”” : ””, ”2” : ””, ..}.
The definition of the move operation also looks a lot more complex when assuming the datasets are in HC4. Following are the diferent cases to be considered: • ∈ vs. ∈/ • 1 ∈ vs. 1 ∈/ • ∈ vs. ∈/ • 2 ∈ vs. 2 ∈/ Combining these conditions, 24 = 16 diferent cases are resulting. All cases where a join condition is not valid that means (1 ∈/ ∨ 2 ∈/ ) do not need to be considered furthermore. We only have to distinguish and define four diferent cases in the semantics for the move operation: • ( ∈ , ∈ , 1 ∈ , 2 ∈ ), • ( ∈ , ∈/ , 1 ∈ , 2 ∈ ), • ( ̸∈ , ∈ , 1 ∈ , 2 ∈ ), • ( ∈/ , ∈/ , 1 ∈ , 2 ∈ ).
For the definition of all evolution operations in all heterogeneity classes, we again refer to [
We can distinguish three abstract classes for compositions: (i) adding and renaming can be composed to a modified add operation, (ii) several rename operations can be combined, and (iii) rename operations followed by a delete can be composed to a modified delete operation.
In case we can assume HC1, the composed operations (right-hand side in the equations
of Figure 4) have the same efect as a step-wise execution (left-hand side). Data migration
operations are generated for each evolution operation. Consequently, reducing the number of
these evolution operations significantly improves performance . Let’s assume a NoSQL database
with 10000 entities and five evolution operations. In the step-wise execution, we have to apply
the data migration operations on 5 · 10000 entities. If we combine the operations into two
evolution operations, then we need to perform the corresponding data migration operations
on only 2 · 10000 entities. In [
In [
The postconditions define the conditions that hold after the execution of the evolution operation. When applying several evolution operations, these conditions define the status of the dataset after each operation execution. They are needed to determine how evolution operations can be combined. Otherwise, i.e., in heterogeneity classes other than HC1, no composition is possible and the evolution operations have to be applied step-wise instead.
If we do not apply preconditions in the composition, we have to assume HC4. Thus, all structural variants has to be defined in the composition. We want to explain this for the following evolution operations: →− move 1. to 2 on 1. = 2. + rename 2. to
move 1. to 2. on 1. = 2..
In the prior paragraph, we have defined the move operation and the rename operation for HC4. For both operations, we distinguished four cases. If we compose both operations then we have to define 4 · 4 = 16 cases. We want to mention that besides the large efort to define all cases separately, a composition is not possible in all cases. This short example shows how high the efort for composition is in HC4.
ered in all database tasks. Two further examples focus on the transformation of heterogeneous data into other formats and query rewriting.
Data transformation has to consider all variants of the data. We assume that the database has
heterogeneous structures in the source. If we define a mapping between source and target format,
the transformations must be defined for all variants. For instance, if we use the local as view
(LaV) approach — originally developed in [
If we assume data in diferent formats, we have to use query rewriting. This is necessary
either in case of versioned databases or in data integration where we query against the global
schema and translate the queries into the structure of the local schemas. For both tasks, the
number of diferent cases that have to be defined depends on the heterogeneity class [
In summary, as expected, all database tasks are more complex to perform for heterogeneous
databases. Nevertheless, we cannot avoid heterogeneity; in countless applications, it is visible
that not all data is structured in a regular way. And finally, the various developments of
schemaless database management systems show this need. How can one now manage this balancing
act between regular and irregular data? Our conclusion from the application examples listed in
this article is very simple: we propose hybrid methods storing a maximum amount of data under
schema control. For the rest of the data, we need the ability to store irregular data. Several
applications following this hybrid approach have been presented in literature. They deal with
the conjunction of relational databases with document stores [
These hybrid approaches can be implemented in three diferent ways (see Figure 5): (a) within one NoSQL or graph database with partial schema control, (b) as a set of connected NoSQL or graph databases (some with schema control and the others without), or (c) in a multi-model database combining one relational database and NoSQL databases.
like JSON and graph database systems added the opportunity to check schema constraints
(visualized in Figure 5(a)). A prominent example is MongoDB where users can specify a JSON
schema for a specific MongoDB collection [
Neo4J – as an example for a graph database – follows a similar approach, making it possible to generate a partial schema control by defining an individual schema. Cypher ofers existence, type, and uniqueness constraints, which are available for properties of either nodes or relationships.
JSON schema
JSON documents (a) JSON documents with partial schema control
JSON schema
JSON documents JSON documents
JSON documents
JSON documents
JSON documents
JSON JSON documents documents (b) JSON documents, the central (c) Multi-model database: relational documents under schema control database with JSON databases
Vertical partitioning
Furthermore, key constraints can be defined for whole entities such as nodes or relations [
Constraints can be used to avoid heterogeneity of data. In Figure 6 a Neo4J example is
shown. Here, a key constraint constraint_student on the Student nodes with properties
id, name, profession and institution is defined. The graph is based on the dataset of
Figure 3. When violating the constraint, an error message is generated. In Neo4J the command
SHOW CONSTRAINTS can be used to show all defined constraints.
Connected JSON or Graph databases. In this storage method, we propose vertical
partitioning, i.e., the splitting of attributes into groups and the distribution of these groups into
diferent tables [
When looking at Figure 6, one example for this approach would be to save essential information of a Student node as displayed in the constraint called constraint_student under schema control matching the kernel. Additional optional information for each Student node (e.g., a photo or her credit points) would be stored separately in the graph database. Multi-model database. The storage method visualized in Figure 5(c) is quite similar to the previous one. Instead of storing the regular parts in a NoSQL database under schema control (see Figure 5(b)), a relational database is used. This relational database has the built-in feature schema-first which guarantees schema constraints and ofers the opportunity to define further semantic constraints. Similarly to the approach shown in Figure 5(b), the heterogeneous parts are kept in JSON or graph databases. The connections between the datasets are realized by references or other inter-model linkage constraints.
In recent years, the need to store heterogeneous data has become increasingly apparent. This resulted in the development of diferent generations of database systems that allow the heterogeneity of data (XML, JSON and graph databases). However, we conclude that one should keep these heterogeneous parts as small as possible and store everything else relationally. With such an approach, we can achieve a balance in data storage between the desirability of regularly storing large chunks of homogeneous data and the need to store heterogeneous data externally.
NoSQL databases like wide-column stores (Cassandra [
In the past, reverse engineering approaches have been developed to derive the structures
[
Another interesting research direction is the consideration of hybrid databases in schema optimization. The challenge is to distinguish between data that is better suited to be stored in relational databases and data you are better of storing in nonrelational databases. Here, diferent factors like storage size or query performance have to be considered.
The 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 grant no. 385808805.