NoSQL and the idea of scaling up and out Databases

What lies beyond Relational

Prof. Yannis Velegrakis

Utrecht University

[Link]@[Link]
[Link]
Disclaimer:
Slides courtesy of
- Martin Fowler
- Michalis Petropoulos
- Bill Howie
- Yannis Velegrakis
3
4
5
The Need for Data Storage

6
How do we store data?

7
Why would I want a database?
What problem do they solve?

1. Sharing
Support concurrent access by multiple readers and writers
2. Data Model Enforcement
Make sure all applications see clean, organized data
3. Scale
Work with datasets too large to fit in memory
4. Flexibility
Use the data in new, unanticipated ways

8
How do we store data?

ANNOTATIONSUMMARY-COMBINEDORFANNOTATION16_Phaeo_genome
###query length COG hit #1 e-value #1 identity #1 score #1 hit length #1 description #1
chr_4[480001-580000].287 4500
chr_4[560001-660000].1 3556
chr_9[400001-500000].503 4211 COG4547 2.00E-04 19 44.6 620 Cobalamin biosynthesis protein CobT (nicotinate-mononucleotide:5, 6-dimethylbenz
chr_9[320001-420000].548 2833 COG5406 2.00E-04 38 43.9 1001 Nucleosome binding factor SPN, SPT16 subunit
chr_27[320001-404298].20 3991 COG4547 5.00E-05 18 46.2 620 Cobalamin biosynthesis protein CobT (nicotinate-mononucleotide:5, 6-dimethylbenz
chr_26[320001-420000].378 3963 COG5099 5.00E-05 17 46.2 777 RNA-binding protein of the Puf family, translational repressor
chr_26[400001-441226].196 2949 COG5099 2.00E-04 17 43.9 777 RNA-binding protein of the Puf family, translational repressor
chr_24[160001-260000].65 3542
chr_5[720001-820000].339 3141 COG5099 4.00E-09 20 59.3 777 RNA-binding protein of the Puf family, translational repressor
chr_9[160001-260000].243 3002 COG5077 1.00E-25 26 114 1089 Ubiquitin carboxyl-terminal hydrolase
chr_12[720001-820000].86 2895 COG5032 2.00E-09 30 60.5 2105 Phosphatidylinositol kinase and protein kinases of the PI-3 kinase family
What is the data model? chr_12[800001-900000].109
chr_11[1-100000].70
1463
2886
COG5032 1.00E-09 30 60.1 2105 Phosphatidylinositol kinase and protein kinases of the PI-3 kinase family

chr_11[80001-180000].100 1523

9
What is a Data Model?

Three components:
1. Structures
2. Constraints
3. Operations

10
Examples

1. Structures
n rows and columns?
n nodes and edges?
n key-value pairs?
n a sequence of bytes?
2. Constraints
n all rows must have the same number of columns
n all values in one column must have the same type
n a child cannot have two parents
3. Operations
n find the value of key x
n find the rows where column “lastname” is “Jordan”
n get the next N bytes

11
 Database: A collection of information
organized to afford efficient retrieval

Historical Example: Network Databases

Orderer
Customer

Screw
Contact Rep

Nut

Washer

12
Historical Example: Hierarchical Databases

Customer Contact Rep

Orderer Screw
Orderer Nut
master
Washer
detail
Works great if you want to find all
orders for a particular customer. Screw

But what if you want to find all Nut

Customers who ordered a Nail?
Nail

detail
13
Relational Databases (Codd 1970)

• Everything is a table
• Every row in a table has the same columns
• Relationships are implicit: no pointers

Course Student Id Student Id Student Name

CSE 344 223… 223… Jane
CSE 344 244… 244… Joe
CSE 514 255.. 255.. Susan
CSE 514 244…

14
Impedance Mismatch
1980
Rise of the Relational Databases

1990

2000

2010
1980

1990

Rise of the Object Databases

2000

2010
1980

1990

Relational Dominance
2000

2010
The Need for Integration

20
Data Warehouse Architecture

€ 2 OLAP / Decision Support

Users Applications Data Cubes / Data Mining

ETL Tools
Relational Database
(Warehouse) (Extract-Transform-Load)

Data Cleaning

Data Data Data

Source Source Source

22
Virtual Integration Architecture

Design-Time

€
End Users
2
Applications

Sources can be:

Global • Relational DBs
Schema
• Excel Files
Schema
Mappings
• Web Sites
• Web Services

Local Local Local

Data Data Data
Schema Schema Schema
Source Source Source

23
Data Management: The Old Model

24
Data Analytics: The New Model

Extracting Value from Data

Analytics

25
 Real Life Data Use Cases

l Education
n Correlate academic effectiveness with various factors
l Healthcare
n Preventive & Personalized
l Urban Planning
n Fusion of high fidelity geographical data
l Intelligent Transportation
n Analysis and visualization of live and detailed road network data
l Environmental Modeling
n Sensor Networks

26
Real Life Data Use Cases

l Energy Saving
n Unveiling Patterns of Use
l Financial Systemic Risk Analysis
n Analyze contracts and relationships among entities
l Security
n Social Networks, Financial Transactions, Transportation
l • Computer Security
n Log Info, Data Transfers and Transactions
l Democracy
n Citizens understand how the government operates

27
The Need for Scaling Up

28
Machine Generated Data

Internet Users

Employees / Data Engineers

More
Big Data

29
30
31
32
1980

1990

2000

2010 NoSQL
The Birth of NoSQL

40
Data Model
 Aggregate Oriented

Key Value Document Oriented

Humans think in graphs

• We understand better things by matching them to things that we know.

• And the things we know … are in the form of graphs
Graphs capture naturally heterogeneous data

• No specific schema
• Shows how different parts connect to each other.
• Hard to model with relational joins
• Very important for more informative insights

69
The property Graph Model
name: Jo
Nodes age: 26
Represent Oblects
name:Mary
Can be labeled marriedTo age: 28
in: 2005
Relationships
Relate Nodes
Have a label (used as a type)

live
Have direction

sIn
Properties
<Name: value> pairs
Describe characteristics in: New York
builtIn: 2007
Can be on nodes or on edges

70
Graph Data: Social Networks

Facebook social graph

4-degrees of separation [Backstrom-Boldi-Rosa-Ugander-Vigna, 2011]
71
A file system for Clusters

73
A Data Center

74
A Container style Data Center

A google data center

may contain
45 containers which is
~60,000 servers

75
The Need for Concistency … or Not

76
ACID

• ACID
– Atomic – Each transaction is either properly carried out or the process halts
and the database reverts back to the state before the transaction started.
This ensures that all data in the database is valid.
– Consistent – A processed transaction will never endanger the structural
integrity of the database.
– Isolated – Transactions cannot compromise the integrity of other
transactions by interacting with them while they are still in progress.
– Durable – The data related to the completed transaction will persist even in
the cases of network or power outages. If a transaction fails, it will not
impact the manipulated data.

77
BASE

• Base
– Basically Available – Rather than enforcing immediate consistency, BASE-
modelled NoSQL databases will ensure availability of data by spreading and
replicating it across the nodes of the database cluster.
– Soft State – Due to the lack of immediate consistency, data values may
change over time. The BASE model breaks off with the concept of a
database which enforces its own consistency, delegating that responsibility
to developers.
– Eventually Consistent – The fact that BASE does not enforce immediate
consistency does not mean that it never achieves it. However, until it does,
data reads are still possible (even though they might not reflect the reality).

78
BASE

• RDBMS = ACID
• NoSQL = BASE (Well …. almost)

79
The Effect of Replication

86
The Effect of Replication

Nick Mary

87
The Effect of Replication

Nick Mary

88
The Effect of Replication

X
Nick Mary

89
The Effect of Replication

X X X
Nick Mary

Consistency Guaranteed

90
The Effect of Replication

X
Nick Mary

Availability Guaranteed

91
l Consistency
n Do all applications see all the same data?
l Availability
n If some nodes fail, does everything still work?
l Partitioning
n If your nodes can’t talk to each other, does everything still work?

92
 Partition Tolerance

Consistency
CAP Theorem [Brewer 2000, Lynch 2002]

You cannot have Availability

them all.

93
93
 Consistency

Partition Tolerance OR

Availability

94
 Consistency

Partition Tolerance OR

Availability
Response Time

95
Megastore
Spanner
Accumulo

src: Shashank Tiwari

Large Language Models

l Treat Tables or other structures as documents.

l Train the model
l Ask Natural Language Queries

l Challenges:
l Formality of the Language (Deterministric Query Answering)
l Performance

97
Thank you.