Chapter 3: NoSQL

Distributed Information Systems

Spring Semester 2026

Prof. Dr. Heiko Schuldt

Dr. Marco Vogt
What does NoSQL mean?

NoSQL: Not only SQL

Non-relational databases
No schema: dynamically add new attributes
to individual records

[Link]

Distributed Information Systems – Spring 2026 – NoSQL 2

Unstructured Data is the Norm

According to Gartner, 80 to 90% of the world’s data today is unstructured!

Source: [Link]

Distributed Information Systems – Spring 2026 – NoSQL 3

A few days ago on LinkedIn

Source: [Link]

Distributed Information Systems – Spring 2026 – NoSQL 4

What does NoSQL mean?

NoSQL: Not only SQL Inherently distributed

Non-relational databases − Data replication
− Data partitioning
No schema: dynamically add new attributes
to individual records Highly scalable for (very) large volumes of data
− Horizontal scalability

Simple interface
− No full-fledged declarative query language
− No joins

Relaxed consistency
− No ACID
− (BASE)
Distributed Information Systems – Spring 2026 – NoSQL 5
Objectives of Chapter 3

− In the last decade, data management has

seen significant changes, with new types of You will …
systems that have been introduced − … get to know the different types of
− Essentially, these NoSQL databases NoSQL systems, their advantages and
abandon the idea of having a dedicated disadvantages,
relational schema − … understand the different levels of
executions guarantees NoSQL systems
− This brings a large degree of flexibility provide,
NoSQL systems have in contrast to
traditional relational databases, but it also − … learn about the trade-off between basic
comes with disadvantages and restrictions properties in distributed data management

Distributed Information Systems – Spring 2026 – NoSQL 6

NoSQL Systems

Several types of alternatives to relational database systems:

− Key-value Stores
▪ Simple data model (“schema-less schema”)

− Wide-Column Stores
▪ Data is organized into column families with flexible schema

− Document Stores
▪ Structure of data is specified via XML or JSON

− Graph Stores
▪ Systems tailored to graph structures (nodes, edges) and graph algorithms

Distributed Information Systems – Spring 2026 – NoSQL 7

Store vs Database

The terms store and database are often used interchangeably, but the difference usually comes down
to emphasis and context.

“Store” tends to highlight the system's role in persisting data, especially in specialized or simplified
systems that focus on particular access patterns

“Database” implies a more full-featured system with comprehensive data management

capabilities.

In the NoSQL world, many systems are referred to as stores to stress their optimized, schema-flexible
nature, even though they provide many of the functions typically associated with databases.

Distributed Information Systems – Spring 2026 – NoSQL 8

Overview of Chapter 3

3.1 Key-Value Stores

3.2 Wide-Column Stores
3.3 Document Stores
3.4 Graph Stores
3.5 RDF and Triple Stores
3.6 In-Memory Databases
3.7 Polystore & PolyDBMS
3.8 Distributed Data Management in the Cloud: CAP and Consistency

Distributed Information Systems – Spring 2026 – NoSQL 9

Key-Value Stores …

A key-value store is based on a simple data model that consists of

− A unique key
− An additional value, which is basically a BLOB. This BLOB might have an internal structure and
different key/value pairs might have differently structured BLOBs.
It is the application‘s task to properly interpret the contents in the BLOB
→ it is a “schemaless database”

Key Value
K1 42 2016-02-29 105.71

K2 'Miller'

K3 2 'Smith' 'Basel' 42 X'120332828474292' 0.0

K4 7 5 'ID' 5

K5 2016-02-28 10:28:32 2016-03-01 12:03:56 [Link]

Distributed Information Systems – Spring 2026 – NoSQL 10

… Key-Value Stores

Operations in Key-Value Stores

− get(key)returns the key-value pair specified by the key
− put(key, value) stores the key-value pair identified by the key.
If it already exists, the value will be overwritten
− delete(key) removes the key-value pair specified by the key from the database

Key-value stores are not suitable when …

− References between data have to be maintained (and referential integrity needs to be enforced)
− Applications / users need to „search by data“ instead of „search by key“, i.e., when the contents
of the value are used to retrieve key-value pairs as the value has to be interpreted by the
application.

Distributed Information Systems – Spring 2026 – NoSQL 11

Key-Value Stores: Applications

Sample use cases for key-value store databases

− Web applications: user sessions and user preferences

▪ Key: user ID

− In-memory data caching: joint caching of heterogeneous objects

▪ Key: object ID

− Real-time recommendations and advertising: collect user-specific recommendations

▪ Key: user ID

− etc.

Distributed Information Systems – Spring 2026 – NoSQL 12

Key-Value Stores: Meet the Players

Examples of key-value stores

− DynamoDB (Amazon), [Link]
− Berkeley DB, [Link]
de/database/technologies/related/[Link]
− memcached, [Link]
− LevelDB (Google), [Link]
− redis, [Link]
− riak, [Link]
− Voldemort (LinkedIn), [Link]
− … and many more …

Distributed Information Systems – Spring 2026 – NoSQL 13

Overview of Chapter 3

3.1 Key-Value Stores

3.2 Wide-Column Stores
3.3 Document Stores
3.4 Graph Stores
3.5 RDF and Triple Stores
3.6 In-Memory Databases
3.7 Polystore & PolyDBMS
3.8 Distributed Data Management in the Cloud: CAP and Consistency

Distributed Information Systems – Spring 2026 – NoSQL 14

Row Stores

Customers
− Relational databases use “Row
ID Name City Balance Discount
Stores”
01 Legrand Geneva -1‘080,00 0.10
Database 02 Marty Basel -8‘00,00 0.20

− Store entire tuples on database pages 03 Frei Basel 0,00 0,10

pages 04 Janvier Geneva 0,00 0,10

05 Rossi Lugano 0,00 0,05
06 Meier Zurich -3‘800,00 0,05
− Optimized for Online Transaction 07 Hürlimann Lucerne -100,00 0,05
Processing (OLTP) applications 08 Schmid Lausanne -2‘235,00 0,10
09 McAllen Zurich -550,00 0,00
▪ Write or read complete tuples
10 Lacroix Geneva -31‘000,00 0,20
… … … … …

Distributed Information Systems – Spring 2026 – NoSQL 15

Column Stores (Not Wide-Column!)

Columns stores are optimized for

applications that are characterized by … Customers

− … long, complex read transactions that ID Name City Balance Discount

01 Legrand Geneva -1‘080,00 0.10
do not request full tuples (Online
02 Marty Basel -8‘00,00 0.20
Analytical Processing, OLAP)
03 Frei Basel 0,00 0,10
− … and rather few update operations 04 Janvier Geneva 0,00 0,10
05 Rossi Lugano 0,00 0,05
06 Meier Zurich -3‘800,00 0,05
07 Hürlimann Lucerne -100,00 0,05
08 Schmid Lausanne -2‘235,00 0,10
09 McAllen Zurich -550,00 0,00
Database 10 Lacroix Geneva -31‘000,00 0,20
pages … … … … …

Distributed Information Systems – Spring 2026 – NoSQL 16

Example: C-Store

− C-Store is an example of a Column Store system

Writeable Store (WS)
− Writeable Store: allows arbitrary insert and update operations
− Read-Optimized Store: the only write operation supported is a Tuple Mover
batch update, initiated by the Writeable store
(= lazy replication)
Read-optimized Store (RS)
− Tuple Mover: executes batch update
− Relational model as logical data model, SQL at the interface
− Physical storage: Projections of single (or multiple) attributes

Distributed Information Systems – Spring 2026 – NoSQL 17

C-Store: Read-Optimized Store …

Single attributes can be stored several times in the read-optimized store (in different projections)
− For each projection, there is a Sort Key (the attribute according to which the projection is sorted)
− Each projection is horizontally partitioned into several segments.
− Each segment is characterized by a Segment Identifier (SID).
This means that each segments encompasses an interval of the Sort Key.
Logical Physical Projection P1 Sort key
representation representation
SID Name Dept
1
Table Employees
Segments
Name Age Dept Salary
2 Key range
Sort key Sort key
3
P2 Name Salary P3
Age Salary

Distributed Information Systems – Spring 2026 – NoSQL 18

… C-Store: Read-Optimized Store

− The entries (or values) of each segment are characterized by a Storage Key (SK)

− The link to other attributes of the same tuple is done via specialized Join Indexes

− Assumption: P1 (M segments) and P2 (N segments) are projections of the same relation (table)
▪ A Join Index then consists of M tables (one per segment of P1)
▪ An entry in the Join Index of P1 for segment SP1 contains for each entry of SP1 a link to the
corresponding entries in projection P2
▪ This link consists of the segment identifier (SID) and the Storage Key (SK) within the segment
▪ Join Indexes thus only establish a unidirectional link between projections

Distributed Information Systems – Spring 2026 – NoSQL 19

C-Store: Join Index

…
Segment SP1,i: ith segment of Projection P1 SP2,j
Name Salary
SP1,i Name SK Dept
1
2
3
4
5

…
SP2,j+2
Name Salary
Join Index for Segment SP1,i
SID SK
… …
… …
… …
SP2, j 3

…
SP2, j+2 1

Distributed Information Systems – Spring 2026 – NoSQL 20

Typical Applications for Column Stores

Data Warehousing: Read-heavy analytical queries across large datasets

Business Intelligence & Reporting: Generating aggregated insights and reports

OLAP (Online Analytical Processing): Complex, ad-hoc queries on historical data

Distributed Information Systems – Spring 2026 – NoSQL 21

Column Stores: Meet the Players

Vertica: Commercial implementation of C-Store, [Link]

SAP IQ (formerly Sybase IQ): First commercial column store system

[Link]

MonetDB: Research prototype, CWI Amsterdam, [Link]

… and many more systems (both open source and commercial)

Distributed Information Systems – Spring 2026 – NoSQL 22

Wide-Column Stores

Keys Columns
Each row can have a varying set of
columns
Phone Mail
Alice
+41 71 .. alice@gm..
Similar to column stores, data is
stored column-oriented Mail Address Fax
Bob
alice@gm.. Weg 1 +41 61 2 ..

Address Fax
Olivia
Weg 5 +41 63 5 ..

Distributed Information Systems – Spring 2026 – NoSQL 23

Example: Google BigTable …

BigTable, a wide-column store, is a distributed storage system for managing structured data that is
designed to scale to a very large size (up to petabytes) across thousands of commodity servers
− Developed by Google and used by over sixty of their products and projects (Web Indexing, Google
Earth, Google Finance, Personalized Search)

These applications place very different demands in terms of:

− Data size: from URL to web page to satellite images (Billions of URLs, many versions/page –
20KB/page)
− Latency requirements: from throughput-oriented batch-processing jobs to real-time data serving
− Deployment: from a handful to thousand of servers
− Very high read/write rates (millions of operations per second)
− Efficient scans over all or interesting subset of data (crawled data, anchors, ...)
− Examined data changes over time, e.g., contents of a web page over multiple crawls

Distributed Information Systems – Spring 2026 – NoSQL 24

… Google BigTable …

Rows:
− Each row identified by a row key

Columns:
− Column family: column name which might appear multiple times in a row
− Column key: combination of column family and qualifier

Multiple versions:
− Under a column key, several versions of the associated value (enriched with a timestamp that
indicates their validity) can be stored
− Materialize the evolution of the value over time

Distributed Information Systems – Spring 2026 – NoSQL 25

… Google BigTable …

Column Family

row key content anchor:[Link] … anchor:[Link]

… … … … … … …

[Link] <html>.. T1 “CNN” T9 “[Link]” T11

<html>.. T2 … …
<html>.. T3
<html>.. T4

<html>.. T5

…
…
… … … … … … …

Timestamps
value
Distributed Information Systems – Spring 2026 – NoSQL 26
… Google BigTable

Large tables broken into tablets at row boundaries

− Tablet holds contiguous range of rows
− Aim for 100 MB to 200 MB of data per tablet
− Fine-grained load balancing:
▪ Migrate tablets away from overloaded machine
▪ Master makes load balancing decisions

Distributed Information Systems – Spring 2026 – NoSQL 27

Typical Applications for Wide-Column Stores

Internet of Things (IoT) Data: High-velocity, large-scale sensor and telemetry data

Real-Time Analytics: Applications requiring immediate insights from distributed data

Large-Scale Logging & Event Tracking: High-volume logs and monitoring data

Distributed Information Systems – Spring 2026 – NoSQL 28

Column Stores: Meet the Players

BigTable (Google): The original wide-column design, [Link]

Apache HBase: Open-Source clone of BigTable, [Link]

Apache Cassandra (originated at Facebook): combines key/value stores and more sophisticated
schemas, [Link]

ScyllaDB: High-performance, Cassandra-compatible system [Link]

… and many more systems (both open source and commercial)

Distributed Information Systems – Spring 2026 – NoSQL 29

Overview of Chapter 3

3.1 Key-Value Stores

3.2 Wide-Column Stores
3.3 Document Stores
3.4 Graph Stores
3.5 RDF and Triple Stores
3.6 In-Memory Databases
3.7 Polystore & PolyDBMS
3.8 Distributed Data Management in the Cloud: CAP and Consistency

Distributed Information Systems – Spring 2026 – NoSQL 30

Document Databases

From a conceptual point of view, document databases are in between relational DBMS and key/value
stores
− Each record (= document) is associated with a unique key
− In contrast to a key/value-store, the value (document) has an inherent structure which is specified
either via JSON or XML
− JSON or XML documents can be nested

Distributed Information Systems – Spring 2026 – NoSQL 31

JSON

JSON: supports two types of elements Example:

{
− object: set of key/value pairs; value can "firstName" : "Ronald",
be of type string, number, object, or array
"lastName" : "Rump",
(which means that nesting is allowed)
"age" : 78,
− array: list of values "address" :
{
"street" : "Rump Tower Street",
"number" : 1,
"city" : "New York City",
"zip" : "01234"
},
"telephone" : [05678, 01987, 00105]
}

Distributed Information Systems – Spring 2026 – NoSQL 32

XML

XML documents consist of elements which Example:

are delimited by tags <A> element </A> <person>
− Tags may be nested, but must not overlap <firstName>Ronald</firstName>
<lastName>Rump</lastName>
− Tags may contain attributes, e.g., <A <age>78</age>
attribute name="value“ ...> </A> <address>
<street>Rump Tower Street</street>
<number>1</number>
<city>New York City</city>
<zip>01234</zip>
</address>
<phoneWork>05678</phoneWork>
<phoneHome>01987</phoneHome>
<phoneMobile>00105</phoneMobile>
</person>

Distributed Information Systems – Spring 2026 – NoSQL 33

Document Databases

Document databases add a unique ID to the Example:

JSON or XML document. {
"id" : "person91238323",
"firstName" : "Ronald",
→ Documents can be retrieved via this ID
"lastName" : "Rump",
"age" : 78,
"address" :
{
"street" : "Rump Tower Street",
"number" : 1,
"city" : "New York City",
"zip" : "01234"
},
"telephone" : [05678, 01987, 00105]
}

Distributed Information Systems – Spring 2026 – NoSQL 34

Document Databases vs. Key/Value Stores

In contrast to key/value stores, document stores also provide an API or query language that allow to
retrieve documents based on their content (and structure)
− Example: select all documents where a particular object has a given value
− These APIs or query languages are proprietary and depend on the type of documents
(and their representation) supported

Distributed Information Systems – Spring 2026 – NoSQL 35

Document Databases: Applications

Sample use cases for document store databases

− Text documents: store and query text collections
− Metadata management: manage descriptive metadata to any type of data collections
− Interoperability: structure and store documents needed for exchange between systems
− etc.

Distributed Information Systems – Spring 2026 – NoSQL 36

Document Databases: Meet the Players

Examples for document databases

− Couchbase, [Link]
− CouchDB, [Link]
− MongoDB, [Link]
− OrientDB, [Link]

− … and many more …

Distributed Information Systems – Spring 2026 – NoSQL 37

Overview of Chapter 3

3.1 Key-Value Stores

3.2 Wide-Column Stores
3.3 Document Stores
3.4 Graph Stores
3.5 RDF and Triple Stores
3.6 In-Memory Databases
3.7 Polystore & PolyDBMS
3.8 Distributed Data Management in the Cloud: CAP and Consistency

Distributed Information Systems – Spring 2026 – NoSQL 38

Graph Databases

− Graphs are well suited data structures to manage networked information

− Applications using such networked information usually rely on very special and sophisticated
queries, such as
▪ Determine transitive dependencies (e.g., friends-of-friends)
▪ Decide whether two elements (nodes) are connected
▪ Determine the shortest path between two elements (e.g., navigation systems)
▪…
− Relational schemas provide only limited support for such queries
− Graph databases store graphs natively and provide better query support

Distributed Information Systems – Spring 2026 – NoSQL 39

 Self-Study

Graph Databases – Recap from Algorithms & Data Structures

Basics: a graph G = (V, E) consists of

− A set V of vertices (nodes)
− A set E of edges connecting two vertices from V with e = {vi, vk}. An edge can be
▪ Directed (edge can be traversed only in one direction). In this case, one node is the source, the
other one the target. In e = (vi, vk), node vi is source and node vk is target; or
▪ Undirected (edge traversal in any direction)

Distributed Information Systems – Spring 2026 – NoSQL 40

 Self-Study

Graph Databases – Recap from Algorithms & Data Structures

A graph is called
− Directed graph if it contains only directed edges
− Undirected graph if it contains only undirected edges
− Multigraph if it may contain several edges between the same two nodes
− Complete if it contains all possible edges

Two nodes are called adjacent if they are connected via an edge; an edge is incident to a node
if it is connected to that node

Distributed Information Systems – Spring 2026 – NoSQL 41

 Self-Study

Examples of graphs …

(Simple) Undirected Graph

− Each edge is represented by a set including two nodes: e1 v2 e2
e = {vi, vk} = {vk, vi}
v1 v3
e3
− With |V| = n, a graph may contain up to
n n (n−1)
= edges
2 2

(Simple) Directed Graph

v2
− Each edge is represented by an ordered tuple, e1 e2
e = (vi, vk) ≠ (vk, vi) e3
v1 v3
e4
− With |V| = n, a graph may contain up to n ∙ (n-1) edges
(without “self edges”)

Distributed Information Systems – Spring 2026 – NoSQL 42

 Self-Study

… Examples of graphs …

Undirected Multigraph
v2
− Each edge is represented by a set including two nodes e1 e2
e3
v1 v3
− The edge set E is a multiset of such edges
e4

Directed Multigraph
v2
• The edge set E is a multiset of tuples e1 e2
e3
v1 v3
e4
e5

Distributed Information Systems – Spring 2026 – NoSQL 43

 Self-Study

… Examples of graphs

Weighted Graphs
− Each edge ei has an associated weight wi
(e.g., cost, distance, capacity, etc.)
e1: w1 v2 e : w
2 2
− Edge weights are independent of the type of graph v1
e3: w3
v3
(directed / undirected) and the multiplicity of edges e4: w4

− Example: weighted simple directed graph

Distributed Information Systems – Spring 2026 – NoSQL 44

 Self-Study

Examples of graph algorithms ...

− Cycle detection (directed graphs)

▪ find a path along edges where start and end node is the same

− Eulerian path
▪ Traverse a graph by visiting each edge exactly once
▪ Start node and end node do not need to be the same

− Eulerian cycle
▪ Each edge has to be traversed exactly once
▪ Start node and end node are the same

− Hamiltonian path
▪ Each node has to be visited exactly once
(not all edges have to be traversed)

Distributed Information Systems – Spring 2026 – NoSQL 45

 Self-Study

… Examples of graph algorithms …

− Hamiltonian cycle
▪ Each node has to be visited exactly once
(start and end node are the same)

− Spanning Tree
▪ Find a subset of the edges of E (from a start node = root)
that forms a tree and that visits each node

− Shortest path
▪ Minimal number of edges between two nodes
(alternative: minimal weight on path from start to end node)

Distributed Information Systems – Spring 2026 – NoSQL 46

 Self-Study

… Examples of graph algorithms

− Depth-first search (DFS)

▪ Traversal of a graph from a given start node
▪ Explores as far as possible all nodes’ direct neighbors
before backtracking

− Breadth-first search (BFS)

▪ Traversal of a graph from a given start node
▪ Explores all direct neighbors of a node first, before
moving to the next level neighbors

Distributed Information Systems – Spring 2026 – NoSQL 47

 Self-Study

Graph Data Structure: Edge List

− A graph is stored as a set of nodes V and a set of edges E

− E is
▪ Set of sets for undirected graphs
▪ Set of tuples for directed graphs
▪ Multiset of sets / tuples for multigraphs
− Advantages
▪ Insertion / deletion of nodes and edges
▪ Simple queries asking for all edges or all nodes
− Disadvantages
▪ No or not adequate support for more sophisticated queries (i.e., find particular node or edge, find
path, etc.)

Distributed Information Systems – Spring 2026 – NoSQL 48

 Self-Study

Graph Data Structure: Adjacency Matrix

− With |V| = n, the adjacency matrix A is an (n × n) matrix where

v2
0 if there is no edge e1 e2
− 𝑎𝑖,𝑘 = ൞1 if there is an edge v1 v3
e3
𝑛 for multiple edges

− For undirected graphs, the matrix is symmetric v1 v2 v 3

v1 0 1 1
− Advantages v2 1 0 1
▪ Lookup for an edge (either by its source or target node) v3 1 1 0
▪ Insertion of new edge (if source and target nodes already exist)
− Disadvantages
▪ Insertion of node requires extension of matrix
▪ Search for neighbors requires scan of complete column
▪ Large storage overhead, in particular for large, sparse graphs
Distributed Information Systems – Spring 2026 – NoSQL 49
 Self-Study

Graph Data Structure: Incidence Matrix

− With |V| = n and |E| = m, the incidence matrix B is an (n × m) matrix where

the rows represent the vertices and the columns the edges and
e1 v2
0 if node and edge are not connected e2
− 𝑏𝑖,𝑘 =ቊ e3
1 if node and edge are connected v1 v3
e4
− For directed graphs, the source node is marked with -1,
the target node with +1 e1 e2 e3 e4

− Advantages v1 -1 0 -1 1
v2 1 1 0 0
▪ Only existing edges are stored (no empty column) v3 0 -1 1 -1

− Disadvantages
▪ Insertion of nodes / edges costly (extension of matrix)
▪ Search for neighbors requires costly scans
▪ Large storage overhead
Distributed Information Systems – Spring 2026 – NoSQL 50
 Self-Study

Graph Data Structure: Adjacency List

− Stores vertex set V and for each vi ∈ V, a linked list that contains
the neighbors of vi (adjacent nodes)
v2
▪ For directed graphs, the list only contains nodes connected e1 e2
e3
via outgoing edges v1 v3
e4
▪ For multigraphs, nodes may occur several times in a linked list
e5
− Advantages
v1 v2 v3
▪ Insertion of vertices and edges v2
▪ Lookup of neighbors v3 v2 v1 v1

− Disadvantages
▪ Checking existence of particular edge
(especially for a given target node)

Distributed Information Systems – Spring 2026 – NoSQL 51

 Self-Study

Graph Data Structure: Incidence List

− Stores vertex set V and for each vi ∈ V, a linked list that contains
all the incident edges of vi
e1 v2 e2
▪ For directed graphs, only outgoing edges e3
are stored in the incident list v1 v3
e4
− Advantages
▪ Insertion of vertices and edges v1 e1: v2 e3: v3 e4: v3
▪ Lookup of neighbors v2 e1: v1 e2: v3
v3 e2: v2 e3: v1 e4: v1
− Disadvantages
▪ Checking existence of particular edge for a given target node

Distributed Information Systems – Spring 2026 – NoSQL 52

(Labeled) Property Graph Model …

− Most graph databases support directed multigraphs

− In addition to the basic graph structure, further information is stored
▪ inside the nodes and Type: Person
Attributes:
▪ inside the edges Name: String
Age: Integer
− Nodes and edges are typed; labels denote the type name
− Type definition specifies a set of attributes. Each attribute consists of
▪ a name Type: knows
Source node: Person
▪ a value, taken from a given domain Target node: Person
Attributes:
▪ name:value pairs are also called properties, since: Date
therefore, these graphs are called property graphs

Distributed Information Systems – Spring 2026 – NoSQL 53

 Self-Study

… (Labeled) Property Graph Model …

A property graph P is a labeled and attributed multigraph with identifiers where

P = (V, E, LV, LE, ID) with
− V is a set of nodes
− E is a set of edges
− LV is a set of node labels (type names for nodes). For each l ∈ LV there is a type definition
t = (l, A) with A being a set of attribute definitions; each a ∈ A is an attribute definition with
a = (attributename, domain)
− LE is a set of edge labels (type names for edges). For each l’ ∈ LE there is a type definition
t’ = (l’, A’, sourcetype, targettype) with A’ being a set of attribute definitions so that each a’ ∈ A’ is
an attribute definition with a’ = (attributename, domain), sourcetype ⊆ LV and targettype ⊆ LV
− ID is a set of unique identifiers (for nodes and edges)

Distributed Information Systems – Spring 2026 – NoSQL 54

… (Labeled) Property Graph Model

Example of a property graph (from a highly simplified social network)

ID: 1
Label: Person
Name: Alice
Age: 42

ID: 4 ID: 8
Label: knows Label: knows
since: 2009-08-07 ID: 5
Label: knows since: 2017-03-28
since: 2009-08-07

ID: 6, Label: knows

since: 2014-03-21
ID: 2 ID: 3
Label: Person Label: Person
Name: Bob ID: 7 Name: Charlie
Age: 27 Label: dislikes Age: 55

Distributed Information Systems – Spring 2026 – NoSQL 55

 Self-Study

Advanced Graph Models

Hypergraphs are graphs with hyperedges

− A “normal” edge corresponds to a two-element subset of V (source and target)
− An undirected hyperedge eh = {vi, vk, …, vr} ⊆ V consists of a set of nodes
− A directed hyperedge eh = ({vi, …, vr}, {vs, …, vz}) is a tuple consisting of two sets of nodes where
▪ {vi, …, vr} ⊆ V are the source nodes (source set) and
▪ {vs, …, vz} ⊆ V are the target nodes (target set)
▪ The cardinalities of both sets may differ

Nested Graphs are graphs with hypernodes

− A “normal” node is atomic
− A hypernode (recursively) contains an entire graph

Distributed Information Systems – Spring 2026 – NoSQL 56

Graph Databases in Practice: Neo4J

Neo4J ([Link]
− Based on Labeled Property Graph Model
− Edges are called “relationships”
− Provides ACID transactions
− Indexing for node and edge properties based on the Apache Lucene text search engine library
− Declarative query language Cypher (search for nodes or traverse a graph)

Distributed Information Systems – Spring 2026 – NoSQL 57

Cypher Overview …

“Mimick” elements of the data model in the query language (“ASCII art”)

Different ways to refer to nodes (variable:label)

− (p) represents a node with node variable p
− () anonymous node (no label or variable), can refer to any node in the DB
− (p:Person) using node variable p and node label Person
− (:Technology) no variable, node label Technology

Distributed Information Systems – Spring 2026 – NoSQL 58

… Cypher Overview …

Different ways to refer to edges, [variable:relationship_type]

− --> and <-- are used for directed edges (anonymous relationships)

− -- is used for undirected relationships (in the DB, a direction must be specified;
the -- edges are only used for query purposes “don’t care”)

− [rel] are relationship variables, [:likes] are relationship types

− Relationship names and/or types are inserted in [] in between the relationship arrow;
for instance –[:likes]-> refers to the :likes relationship between two nodes

Distributed Information Systems – Spring 2026 – NoSQL 59

… Cypher Overview …

Node or relationship properties

− In order to select nodes or relationships, the desired values of properties can be specified
within {} inside the node () or relationship [] specification

− Examples:
▪ Node property: (p:Person {name: 'Alice'})
▪ Relationship property: -[rel:IS_FRIENDS_WITH {since: 2018}]->

Node and relationship expressions can be combined to form graph patterns

(corresponds to the traversal of subgraphs)
− Example:
(p:Person {name: 'Alice'})-[rel:LIKES]->(g:Technology {type: 'GraphDBs'})

Distributed Information Systems – Spring 2026 – NoSQL 60

… Cypher Overview

Cypher queries have a dedicated structure given. The most important clauses are:
MATCH
▪ specifies an existing node, relationship, label, property, or pattern in the database
▪ It corresponds to a graph traversal to be considered in the query
▪ It can be compared to the SELECT clause in SQL
WHERE
▪ (optional) specifies additional filters
RETURN
▪ specifies the values or results (nodes/relationships/properties/patterns) a query should return
▪ It is not required for write operations but it is needed for reads

More details and full reference available at: [Link]

Distributed Information Systems – Spring 2026 – NoSQL 61

Cypher Example
ID: 1
Label: Person
Name: Alice
Age: 42
Example: Search all people Alice knows
ID: 4 ID: 8
Label: knows Label: knows
since: 2009-08-07 ID: 5
Label: knows since: 2017-03-28
since: 2009-08-07

ID: 6, Label: knows

since: 2014-03-21
ID: 2 ID: 3
Label: Person Label: Person
Name: Bob ID: 7 Name: Charlie
Age: 27 Label: dislikes Age: 55

Distributed Information Systems – Spring 2026 – NoSQL 62

Cypher Example
ID: 1
Label: Person
Name: Alice
Age: 42
Example: Search all people Alice knows
ID: 4 ID: 8
Label: knows Label: knows
since: 2009-08-07 ID: 5
Label: knows since: 2017-03-28
since: 2009-08-07

ID: 6, Label: knows

since: 2014-03-21
ID: 2 ID: 3
Label: Person Label: Person
Name: Bob ID: 7 Name: Charlie
Age: 27 Label: dislikes Age: 55

MATCH (:Person {name: "Alice"})-[:KNOWS]->(p:Person)

RETURN p

Distributed Information Systems – Spring 2026 – NoSQL 63

Cypher Example
ID: 1
Label: Person
Name: Alice
Age: 42
Example: Which people know Bob?
ID: 4 ID: 8
Label: knows Label: knows
since: 2009-08-07 ID: 5
Label: knows since: 2017-03-28
since: 2009-08-07

ID: 6, Label: knows

since: 2014-03-21
ID: 2 ID: 3
Label: Person Label: Person
Name: Bob ID: 7 Name: Charlie
Age: 27 Label: dislikes Age: 55

Distributed Information Systems – Spring 2026 – NoSQL 64

Cypher Example
ID: 1
Label: Person
Name: Alice
Age: 42
Example: Which people know Bob?
ID: 4 ID: 8
Label: knows Label: knows
since: 2009-08-07 ID: 5
Label: knows since: 2017-03-28
since: 2009-08-07

ID: 6, Label: knows

since: 2014-03-21
ID: 2 ID: 3
Label: Person Label: Person
Name: Bob ID: 7 Name: Charlie
Age: 27 Label: dislikes Age: 55

MATCH (p:Person)-[:KNOWS]->(:Person {name: "Bob"})

RETURN p

Distributed Information Systems – Spring 2026 – NoSQL 65

Cypher Example
ID: 1
Label: Person
Name: Alice
Age: 42
Example: Which people are mutual friends
ID: 4 ID: 8
of Alice and Bob? Label: knows
ID: 5 Label: knows
since: 2009-08-07 since: 2017-03-28
Label: knows
since: 2009-08-07

ID: 6, Label: knows

since: 2014-03-21
ID: 2 ID: 3
Label: Person Label: Person
Name: Bob ID: 7 Name: Charlie
Age: 27 Label: dislikes Age: 55

Distributed Information Systems – Spring 2026 – NoSQL 66

Cypher Example
ID: 1
Label: Person
Name: Alice
Age: 42
Example: Which people are mutual friends
ID: 4 ID: 8
of Alice and Bob? Label: knows
ID: 5 Label: knows
since: 2009-08-07 since: 2017-03-28
Label: knows
since: 2009-08-07

ID: 6, Label: knows

since: 2014-03-21
ID: 2 ID: 3
Label: Person Label: Person
Name: Bob ID: 7 Name: Charlie
Age: 27 Label: dislikes Age: 55

MATCH (:Person {name: "Alice"})-[:KNOWS]->(f:Person)<-[:KNOWS]-(:Person {name: "Bob"})

RETURN f

Distributed Information Systems – Spring 2026 – NoSQL 67

Graph Databases: Applications

Sample use cases for graph databases

− Social networks: manage individuals and their relationships
− Spatial information: manage maps and associated road networks
− Bioinformatics: manage biological structures and their relationships
− etc.

Distributed Information Systems – Spring 2026 – NoSQL 68

Graph Databases: Meet the Players

− Neo4j ([Link]

− HyperGraphDB ([Link]
▪ Supports hypergraphs

− OrientDB ([Link]
▪ Combined document database and graph database

− … and many more …

Distributed Information Systems – Spring 2026 – NoSQL 69

Overview of Chapter 3

3.1 Key-Value Stores

3.2 Wide-Column Stores
3.3 Document Stores
3.4 Graph Stores
3.5 RDF and Triple Stores
3.6 In-Memory Databases
3.7 Polystore & PolyDBMS
3.8 Distributed Data Management in the Cloud: CAP and Consistency

Distributed Information Systems – Spring 2026 – NoSQL 70

Resource Description Framework (RDF)

− The Resource Description Framework (RDF) provides a simple language to capture knowledge
▪ In short: the purpose of RDF is to provide the mechanisms to specify data “about” something,
i.e., about arbitrary resources
▪ Self-descriptive data

− The development of RDF has been motivated by several uses, including:

▪ Machine-processable information: to allow data to be processed outside the particular
environment in which it was created
▪ Linked Open Data: providing information about (web) resources and their interdependencies

Distributed Information Systems – Spring 2026 – NoSQL 71

RDF: Resources and Literals

− RDF allows describing resources by specifying the properties of resources

− Resources are identified via a URI

▪ e.g., documents, images, video clips, or services
▪ Resources are not necessarily restricted to the web but could also represent people, social
entities, physical objects

− Resources map conceptually to entities or to sets of entities

− Literals (basic values) represent elements of concrete domains

▪ Expressed as string (lexical value) that maps to an element of a concrete domain (String, Number,
Date, …)

Distributed Information Systems – Spring 2026 – NoSQL 72

RDF: Structure

− An RDF document is a collection of statements

− Each statement is expressed as a triple consisting of
▪ Subject (this is a resource, in RDF terminology)
▪ Predicate (which is also identified by a URI)
▪ Object (this can be either a resource or a literal)
− A statement makes an assertion about its subject, namely that its subject is related to the object
through its predicate

predicate(subject, object)

Distributed Information Systems – Spring 2026 – NoSQL 73

RDF Graph

RDF graph representation:

− Subject
− Predicate
− Literal

Subject Object_A
Predicate_1

Object_B
Predicate_2

Therefore, RDF is a kind of graph data model

Distributed Information Systems – Spring 2026 – NoSQL 74

RDF Graph

RDF graph representation:

− Subject
− Predicate
− Literal

Subject Object_A Predicate_1(Subject, Object_A)

Predicate_1

Object_B Predicate_2(Subject, Object_B)

Predicate_2

Therefore, RDF is a kind of graph data model

Distributed Information Systems – Spring 2026 – NoSQL 75

RDF: Example

− Resources: phil101
Immanuel Kant
…
− Literals: 'Critique of Pure Reason'
‘Königsberg’
…
− Statements: hasTitle(phil101, 'Critique of Pure Reason')
teaches(Immanuel Kant, phil101)
bornIn(Immanuel Kant, ‘Königsberg’)
…
RDF Property Graph

Distributed Information Systems – Spring 2026 – NoSQL 76

RDF: Example

− Resources: phil101
Immanuel Kant
…
− Literals: 'Critique of Pure Reason'
‘Königsberg’
…
− Statements: hasTitle(phil101, 'Critique of Pure Reason')
teaches(Immanuel Kant, phil101)
bornIn(Immanuel Kant, ‘Königsberg’)
…
RDF bornIn Property Graph
Immanuel
Königsberg
Kant
teaches
phil101 Critique of
hasTitle Pure Reason

Distributed Information Systems – Spring 2026 – NoSQL 77

RDF: Example

− Resources: phil101
Immanuel Kant
…
− Literals: 'Critique of Pure Reason'
‘Königsberg’
…
− Statements: hasTitle(phil101, 'Critique of Pure Reason')
teaches(Immanuel Kant, phil101)
bornIn(Immanuel Kant, ‘Königsberg’)
…
RDF bornIn Property Graph
Immanuel
Königsberg Person
Kant Course

teaches name:
“Immanuel Kant”
teaches courseId: phil101

phil101 Critique of bornIn:

title: “Critique of
Pure Reason”
hasTitle Pure Reason “Königsberg”

Distributed Information Systems – Spring 2026 – NoSQL 78

Triple Stores Databases

− A triple store is a dedicated (graph) database that only supports RDF triples
▪ There are native triple stores …
▪ … and triple stores built upon relational databases, graph databases, or document databases

− If triples are named (named triples), systems are called quad stores

− With the advent of graph databases, triple stores have lost their importance

Distributed Information Systems – Spring 2026 – NoSQL 79

Overview of Chapter 3

3.1 Key-Value Stores

3.2 Wide-Column Stores
3.3 Document Stores
3.4 Graph Stores
3.5 RDF and Triple Stores
3.6 In-Memory Databases
3.7 Polystore & PolyDBMS
3.8 Distributed Data Management in the Cloud: CAP and Consistency

Distributed Information Systems – Spring 2026 – NoSQL 80

In-Memory Databases

Database servers with large-scale main memory can keep an entire database in transient memory
− Hence, main memory is the primary storage location for data
− The performance (read and write) is significantly higher than in databases with persistent storage on
HDDs or SSDs.
− A, C, and I of ACID can be provided without problems
− But: durability (D) cannot be provided without additional mechanisms

In-memory data management is orthogonal to all database types that have been introduced
before:
− Can be applied to relational systems as well as to all other forms of NoSQL databases
− Typically, systems are hybrid: they can operate only in main memory or they are able to store
data on disk

Distributed Information Systems – Spring 2026 – NoSQL 81

In-Memory Databases: Durability

In order to make sure that in-memory databases survive system crashes, they need to support one of
the following:
− Snapshots: the system periodically stores a snapshot of the entire database. After a system crash,
all changes since the last snapshot will be lost.
− Logging: transaction logs are stored persistently on disk (either based on an initial system state or
in combination with periodical snapshots). During recovery, the log has to be re-played.
− Replication: the in-memory database is replicated to other in-memory servers

Distributed Information Systems – Spring 2026 – NoSQL 82

Overview of Chapter 3

3.1 Key-Value Stores

3.2 Wide-Column Stores
3.3 Document Stores
3.4 Graph Stores
3.5 RDF and Triple Stores
3.6 In-Memory Databases
3.7 Polystore & PolyDBMS
3.8 Distributed Data Management in the Cloud: CAP and Consistency

Distributed Information Systems – Spring 2026 – NoSQL 83

Polystores …

Polyglot programming
− Applications can be written in different programming languages
− Each language is used for an aspect for which it is particularly well suited
→ This has advantages compared to a solution based on only one language
Polyglot persistence
− Adoption of the polyglot programming concept for databases
− Instead of a “One-Size-Fits-All” database for an entire application, polyglot persistence considers
a combination of different databases (data models / storage technologies / query language)
→ Select the best data management solution for a certain (sub-)set of an application’s data
Multistore database
− Provides a common user interface and a common query language on top of heterogeneous
database systems

Distributed Information Systems – Spring 2026 – NoSQL 84

… Polystores …

In most cases, there is no sharp distinction between

− Different NoSQL systems: e.g., document stores are also Key/Value stores
− Different data formats: e.g., structured and unstructured
− Different application workloads: e.g., may encompass OLTP or OLAP

No One-Size-Fits-All
− There is not a single system that jointly supports all types of applications
− Even for concrete applications, it is sometimes impossible to select a database / storage system

Distributed Information Systems – Spring 2026 – NoSQL 85

… Polystores …

− Combine polyglot persistence and multistores (i.e., combine different databases in one system)
− Different storage technologies (main memory, SSD, spinning disk)
− Data replication (in different data formats / models)
− Decision per query where to route a request
− Logical database consisting of several physical databases

Distributed Information Systems – Spring 2026 – NoSQL 86

… Polystores

Polystore

K/V Store RDBMS Column Store Graph DB

Distributed Information Systems – Spring 2026 – NoSQL 87

Polystores: Meet the Players

− Polypheny: research prototype and commercial product emerging from the DBIS group of the
University of Basel ([Link]
− BigDAWG ([Link]
− … and others

Distributed Information Systems – Spring 2026 – NoSQL 88

Problem: Polystores are typically read-only

− Polystores are intended as an alternative for Data Warehouses

− The most recent data can be read without first integrating the data into a Data Warehouse
− Perfect tool for data analytics

However, there is also a solution that supports write queries: PolyDBMS

Distributed Information Systems – Spring 2026 – NoSQL 89

PolyDBMS: Overview

− Heterogenous data stores to store data and

execute queries

− Replication and partitioning of data across multiple

underlying data stores

PolyDBMS
− Data can be placed on a heterogenous set of data
stores

− A logical schema that can be queried through all

query interfaces

− Queries might be decomposed and pushed down

to different engines

Distributed Information Systems – Spring 2026 – NoSQL 90

Problem: Independence of Storage Configuration

The Problem The result of a query must be independent of

− Data stores do not have the same set of features − how and where the data is physically stored
and capabilities − by which engine it has been processed
− Especially problematic with data modification
queries The available query languages, operations and
functions must not depend on the physical storage of
Example: Day of Week (DoW) the data.
Function that takes a timestamp and returns an
integer
PostgreSQL: 0-6, Sunday is 0
Oracle: 1-7, Sunday is 1
Only observable difference between storage
The solution configurations should be the execution time
− Integrate an execution engine into the PolyDBMS
itself
− This engine is able to execute all queries

Distributed Information Systems – Spring 2026 – NoSQL 91

PolyDBMS: Different Kinds of Schemas
Exposed Schema
− Building blocks are defined by the query
language
− Making semantic concepts from other data
models available

Distributed Information Systems – Spring 2026 – NoSQL 92

PolyDBMS: Different Kinds of Schemas
Exposed Schema
− Building blocks are defined by the query
language
− Making semantic concepts from other data
models available

Physical Schema
− Building blocks are defined by the data store
− Storing data for efficient querying
− Utilizing features of the data store

Distributed Information Systems – Spring 2026 – NoSQL 93

PolyDBMS: Different Kinds of Schemas
Exposed Schema
− Building blocks are defined by the query
language
− Making semantic concepts from other data
models available

Logical Schema
− The central schema of the PolyDBMS
− Building blocks from all supported data
models
− Enabling cross-model queries

Physical Schema
− Building blocks are defined by the data store
− Storing data for efficient querying
− Utilizing features of the data store

Distributed Information Systems – Spring 2026 – NoSQL 94

PolyDBMS: Namespaces

The logical schema S is a set of namespaces N:

𝑆 ∶= 𝑁1 , 𝑁2 , … , 𝑁𝑚 with 𝑚 ∈ ℕ

− Every namespace has a unique name and is

of a specific data model

− This model defines the available set of

schema building blocks

Distributed Information Systems – Spring 2026 – NoSQL 95

Example: Exposed Schema …

Example: An application using an SQL

<c u s t o m e r,
(relational) query interface needs to access a <k n o w s>
vip>
namespace with the data model graph. id: 55
name: Hanna
𝑁 𝐿𝑃𝐺 ≔ name, 𝐺 address: Basel <c u s t o m e r >
𝑁 𝑅𝐸𝐿 ≔ name, 𝑇1 , … , 𝑇𝑛 with 𝑛 ∈ ℕ id: 285
name: Bob
𝐿𝑃𝐺 𝑅𝐸𝐿 <k n o w s> address: Liestal
𝑁 ⟼𝑁

<c u s t o m e r >
Map node labels as tables and mimic id: 96
the concept of join tables name: Alice
address:
Hölstein

Distributed Information Systems – Spring 2026 – NoSQL 96

 customer
Example: LPG ⟼ Relational id properties labels
55 name: Hanna, address: Basel customer, vip
285 name: Bob, address: Liestal customer
96 name: Alice, address: Hölstein customer

<c u s t o m e r, vip
vip> <k n o w s>
id properties labels
id: 55
55 name: Hanna, address: Basel customer, vip
name: Hanna
address: Basel <c u s t o m e r > customer->customer
id: 285 src tgt properties labels
name: Bob
55 285 knows
<k n o w s > address: Liestal
96 55 knows

customer->vip
<c u s t o m e r >
id: 96 src tgt properties labels

name: Alice 96 55 knows

address: vip->customer
Hölstein
src tgt properties labels
55 285 knows

Distributed Information Systems – Spring 2026 – NoSQL 97

Example: LPG ⟼ Relational

𝑁 𝐿𝑃𝐺 ≔ name, 𝐺
𝑁 𝑅𝐸𝐿 ≔ name, 𝑇1 , … , 𝑇𝑛 with 𝑛 ∈ ℕ

𝑁 𝐿𝑃𝐺 ⟼ 𝑁 𝑅𝐸𝐿

name, 𝐺 ⟼ 𝜋1 𝑁 𝐿𝑃𝐺 , ntab 𝜋2 𝑁 𝐿𝑃𝐺 ∪ etab 𝜋2 𝑁 𝐿𝑃𝐺

ntab 𝐺 ≔ 𝑥, id, props, labels 𝑥 ∈ labelsOf 𝐺

ntab etab
etab 𝐺 ≔ 𝑥→𝑦, src, tgt, props, labels 𝑥, 𝑦 ∈ labelsOf 𝐺

→ There are similar mappings for the other pairs

of data models and for mapping to the physical
schema

Distributed Information Systems – Spring 2026 – NoSQL 98

Implementation of a PolyDBMS: Polypheny

− Polypheny is an open-source system originating from the

University of Basel.

− It supports the Relational, Document, and LPG data models.

− It combines the advantages and performance optimizations of

multiple domain specific database systems

− It has support for write queries and transactions (depending on

the configuration) providing full ACID guarantees.

Distributed Information Systems – Spring 2026 – NoSQL 99

Overview of Chapter 3

3.1 Key-Value Stores

3.2 Wide-Column Stores
3.3 Document Stores
3.4 Graph Stores
3.5 RDF and Triple Stores
3.6 In-Memory Databases
3.7 Polystore & PolyDBMS
3.8 Distributed Data Management in the Cloud: CAP and Consistency

Distributed Information Systems – Spring 2026 – NoSQL 100

Data Management in the Cloud

Distributed Information Systems – Spring 2026 – NoSQL 101

Data Management in the Cloud: Basics

− Cloud Computing Revisited: The Cloud from a Consumer‘s Perspective

− Establish service level agreements with Cloud providers (quality of service, QoS)
▪ e.g., Availability
− Elasticity: dynamically request additional resources for peak loads
▪ e.g., Scalability

010110101001010100101110101101

Distributed Information Systems – Spring 2026 – NoSQL 102

The Cloud from a Provider’s Perspective

− Have enough spare resources to guarantee elastic behavior

▪ How to maximize capacity utilization?
− Multi-tenancy
▪ Support different tenants with completely different requirements in the same system
− Quality of Service guarantees; for data, this includes
▪ Replication (software, data), constrained by CAP Theorem (details later)
▪ Performance / latency
− Cloud data management
▪ How to provide read operations with different semantics (up-to-date data, stale data)
▪ Long-term preservation and archiving
− Some of these aspects are not convincingly solved but are still subject to intensive research
Distributed Information Systems – Spring 2026 – NoSQL 103
Different Levels of Consistency …

Strong consistency (eager replication)

− Each update forces all replicas to be updated
− Afterwards, all accesses return the new value
− But: limited availability between 1st and last write
operation

Weak consistency (lazy replication)

− Update needs to be acknowledged only once
− Full availability
− Inconsistent system state during convergence period
(inconsistency window)

Distributed Information Systems – Spring 2026 – NoSQL 104

Cloud Data Management – Requirements

Tolerance to network partitions

− If a connection to a computer / rack / datacenter / continent fails,
the disconnected partitions must continue to work
− Clients in the same partition do not even realize the partitioning

Availability
− For the client, the system (even though it might be distributed) looks
like one physical system and should be usable / accessible anytime
− Solution: redundancy & replication

Consistency
− The more replicas, the more difficult to keep consistency
− When enforcing consistency, the system is no longer highly available
Distributed Information Systems – Spring 2026 – NoSQL 105
CAP Theorem …

− Only two of the three requirements Consistency, Availability, tolerance to network Partitions
can be met at the same time (has been formally proven)

− General assumption: network partitions cannot be influenced by the Cloud providers

→ Trade-off between availability and consistency

Consistency Availability
− Cloud providers can choose to either weaken
− Availability, or
− Consistency
Network
partitioning
tolerance

Distributed Information Systems – Spring 2026 – NoSQL 106

… CAP Theorem

If there is
[Link]
no partition

Consistency Availability
impos-
sible

x = 42 x? 42 no Partition no
availability Tolerance consistency

Distributed Information Systems – Spring 2026 – NoSQL 107

CAP Theorem: General Discussion …

Data Replication (Foundations of Distributed Systems) revisited: Assume we have a distributed

system with replicated data and let …
− N be the number of nodes that store a replica of the data
− W be the number of “write replicas”, i.e, replicas that need to acknowledge the receipt of the
update before the update completes
− R be the number of “read replicas”, i.e., replicas hat are contacted when a data object is
accessed through a read operation

Distributed Information Systems – Spring 2026 – NoSQL 108

CAP Theorem: General Discussion …

Depending on N, W, and R, a system has the following characteristics

− W+R > N (and W > N/2)
In this case, the write set and the read set always overlap and one can guarantee strong
consistency

− R+W=N (or, even worse, R+W < N)

In this case, consistency cannot be guaranteed as one cannot make sure that the most recent data
is read.
→ This is also known as weak consistency or eventual consistency

Distributed Information Systems – Spring 2026 – NoSQL 109

CAP Theorem: Examples …

− Primary backup DBMS with synchronous − Asynchronous replication

replication
− Fault tolerant and optimized for writes
− Fault tolerant and optimized for reads
− N=2, W=R=1
− N=W=2, R=1

write write read write read

Client 1 Client 2 Client 1 Client 2

− What if the system cannot write to W nodes? − Consistency cannot be guaranteed

→ Failure (impacting availability)

Distributed Information Systems – Spring 2026 – NoSQL 112

… CAP Theorem: Examples …

Usually, high availability in distributed storage systems means N > 2.

In most cases, N = 3 (triplication)

− Systems with an exclusive focus on fault-tolerance: N=3, with W=2 and R=2

− Systems that aim at supporting high read loads: N = 3 or even higher

(in the area of up to hundreds of nodes in special applications), R = 1

− Systems that aim at providing a high degree of consistency: W=N,

even though this may decrease the success probability of the write

− Systems that aim at providing a high degree of fault-tolerance, but not consistency:
N=3, W=1 (master node), and rely on a lazy technique to update the other replicas

− … and many more different combinations

Distributed Information Systems – Spring 2026 – NoSQL 113

… CAP Theorem: Examples

Concrete values of N, W and R depend on what property needs to be optimized

− R=1 and W=N optimizes the read case

− W=1 and R=N optimize for a very fast write. But:

▪ Durability is not guaranteed in the presence of failures
▪ If W ≤ N/2 there is the possibility of conflicting writes because write sets do not overlap
(quorum is not reached)

Distributed Information Systems – Spring 2026 – NoSQL 114

Different Flavors of (Strong) Consistency

Sequential Consistency
− This corresponds to the serializability criterion in databases (conflict-preserving serializability,
CPSR), i.e., the equivalence to some serial execution
→ highest form of consistency

Causal Consistency
− Writes that are causally related must be seen in the same order.
− At the same time, writes (especially from the same transaction) that are not causally related may be
executed in different orders on different sites

Distributed Information Systems – Spring 2026 – NoSQL 115

Different Flavors of (Weak) Consistency …

Monotonic Read Consistency

− Once a system has returned a particular record to a client, further queries of the same client
will only return versions that are at least as fresh as the previously returned one

Monotonic Write Consistency

− If a particular client changes some data item two (or several) times, then the system has to make
sure that the writes happen internally in exactly the same order

Read-your-Write Consistency
− A system guarantees that, once a record has been updated, any attempt to read the record
will return the updated value

Distributed Information Systems – Spring 2026 – NoSQL 116

… Different Flavors of (Weak) Consistency

Writes-follows-reads Consistency
− A write operation on object x following a read on x by the same transaction is guaranteed to take
place on the same or more recent version of x that was read

Session Consistency
− Read-your-Write consistency, where the property is only limited to the lifetime of a client session

Distributed Information Systems – Spring 2026 – NoSQL 117

Eventual Consistency …

Eventual consistency is a form of weak consistency

− Guarantee: if no further updates are made during convergence, all accesses will eventually
see the new value
− Supported (exclusively) by most Cloud providers
→ They might return inconsistent data!

Distributed Information Systems – Spring 2026 – NoSQL 118

ACID vs. BASE

From database transactions, we know the ACID guarantees

− Atomicity
− Consistency
− Isolation
− Durability

Most Cloud providers rather provide much softer and blurrier guarantees (because of the CAP
theorem): BASE
− Basically Available: the system is available most of the time, but may occasionally be down
− Soft state: information (state) the user puts into a system will eventually go away if this information
is not maintained (i.e., information will expire unless it is refreshed) – in contrast to the D in ACID
− Eventual consistency: weak consistency, see before; – in contrast to the I in ACID

Distributed Information Systems – Spring 2026 – NoSQL 120

Availability vs. Consistency: Cost-based Data Management

• availability
• performance
• inconsistency costs • consistency costs

no consistency eventual consistency strong consistency

Current research: model that takes into account:

− Actual and predicted workload
− Costs of necessary resources: consistency costs
− Costs for dealing with inconsistencies
− User requirements: performance, availability
− Available budget
− Dynamically select and adapt protocols for distributed data management

Distributed Information Systems – Spring 2026 – NoSQL 121

CAP in the Non-Failure Case: PACELC

− CAP essentially deals with failures

− In the non-failure case, there is a trade-off between consistency and latency

▪ The higher the consistency level, the higher the latency
▪ The lower the consistency level, the better the overall performance (low latency)

− This is also known as PACELC

▪ PAC: a permutation of CAP
▪ ELC: Else Latency vs. Consistency

Distributed Information Systems – Spring 2026 – NoSQL 122

More on Latency

Latency matters!
− Amazon found every 100ms of latency cost them 1% in sales
− Google found an extra 0.5 seconds in search page generation time dropped traffic by 20%
− A broker could lose $4 million in revenues per millisecond if their electronic trading platform is
5 milliseconds behind the competition

Distributed Information Systems – Spring 2026 – NoSQL 123

Further Reading

[Aba 12] Daniel Abadi: Consistency Tradeoffs in Modern Distributed Database System Design:
CAP is Only Part of the Story. IEEE Computer 45(2): 37-42, 2012.

[AFG+ 09] M. Armbrust, A. Fox, R. Griffith, A. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin,
I. Stoica, M. Zaharia. Above the Clouds: A Berkeley View of Cloud Computing. Tech. Report UC
Berkeley, 2009.
[Bre 00] E. Brewer: Towards robust distributed systems. In: Proc. PODC 2000.

[EFH+ 11] S. Edlich, A. Friedland, J. Hampe, B. Brauer, M. Brückner: NoSQL – Einstieg in die Welt
nichtrelationaler Web 2.0 Datenbanken. Hanser, 2011.
[GL 02] S. Gilbert, N. Lynch: Brewer's conjecture and the feasibility of consistent, available, partition-tolerant
web services. SIGACT News 33(2): 51-59, 2002

[SF13] P. Sadalage, M. Fowler: NoSQL Distilled. Addison-Wesley, 2013.

[Wie 15] L. Wiese: Advanced Data Management – for SQL, NoSQL, Cloud and Distributed Databases.
De Gruyter, 2015

Distributed Information Systems – Spring 2026 – NoSQL 124

Questions?