Introduction to Computer Science

William Hsu
Department of Computer Science and Engineering
National Taiwan Ocean University
Chapter 9: Database Systems
supplementary - noSQL
You can have data without information, but you cannot have information without data.
Daniel Keys Moran
Data is a precious thing and will last longer than the systems themselves.
Tim Berners-Lee
Types of Data
› Data can be broadly classified into four types:
– Structured Data:
› Have a predefined model, which organizes data into a form that is
relatively easy to store, process, retrieve
and manage
› E.g., relational data

– Unstructured Data:
› Opposite of structured data
› E.g., Flat binary files containing text, video or audio
› Note: data is not completely devoid of a structure (e.g., an audio
file may still have an encoding structure and some metadata
associated with it)
Types of Data
› Data can be broadly classified into four types:
– Dynamic Data:
› Data that changes relatively frequently
› E.g., office documents and transactional entries in a financial
database

– Static Data:
› Opposite of dynamic data
› E.g., Medical imaging data from MRI or CT scans
Why Classifying Data?
› Segmenting data into one of the following 4 quadrants can
help in designing and developing a pertaining storage
solution
Dynamic Static
Unstructured

Media Production, Media Archive,

eCAD, mCAD, Office Broadcast, Medical
Docs Imaging
Structured

Transaction Systems,
BI, Data Warehousing
ERP, CRM

› Relational databases are usually used for structured data

› File systems or NoSQL databases can be used for (static),

unstructured data (more on these later)
Scaling Traditional Databases
› Traditional RDBMSs can be either scaled:
– Vertically (or Up)
› Can be achieved by hardware upgrades (e.g., faster CPU, more
memory, or larger disk)
› Limited by the amount of CPU, RAM and disk that can be
configured on a single machine

– Horizontally (or Out)

› Can be achieved by adding more machines
› Requires database sharding and probably replication
› Limited by the Read-to-Write ratio and communication overhead
Why Sharding Data?
› Data is typically sharded (or striped) to allow for
concurrent/parallel accesses

Input data: A large file

Machine 1 Machine 2 Machine 3

Chunk1 of input data Chunk3 of input data Chunk5 of input data

Chunk2 of input data Chunk4 of input data Chunk5 of input data

E.g., Chunks 1, 3 and 5 can be accessed in parallel

Amdahl’s Law
› How much faster will a parallel program run?
– Suppose that the sequential execution of a program takes 𝑇𝑇1
time units and the parallel execution on 𝑝𝑝 processors/machines
takes 𝑇𝑇𝑝𝑝 time units

– Suppose that out of the entire execution of the program, 𝑠𝑠

fraction of it is not parallelizable while 1 − 𝑠𝑠 fraction is
parallelizable

– Then the speedup (Amdahl’s formula):

8
 Amdahl’s Law: An Example
› Suppose that:
– 80% of your program can be parallelized
– 4 machines are used to run your parallel version of
the program

› The speedup you can get according to Amdahl’s law is:

Although you use 4 processors you cannot get a speedup

more than 2.5 times!
9
 Real Vs. Actual Cases
› Amdahl’s argument is too simplified
› In reality, communication overhead and potential
workload imbalance exist upon running parallel
programs
20 80 20 80
Serial Serial

Parallel 20 20 Parallel 20 20
Process 1 Process 1

Process 2 Process 2

Cannot be parallelized
Process 3 Process 3
Cannot be parallelized Can be parallelized

Process 4 Process 4 Communication overhead

Can be parallelized
Load Unbalance
1. Parallel Speed-up: An Ideal Case 2. Parallel Speed-up: An Actual Case
Some Guidelines
› Here are some guidelines to effectively benefit
from parallelization:
– Maximize the fraction of your program that can be parallelized
– Balance the workload of parallel processes
– Minimize the time spent for communication

11
Why Replicating Data?
› Replicating data across servers helps in:
– Avoiding performance bottlenecks
– Avoiding single point of failures
– And, hence, enhancing scalability and availability
Why Replicating Data?
› Replicating data across servers helps in:
– Avoiding performance bottlenecks
– Avoiding single point of failures
– And, hence, enhancing scalability and availability

Main Server

Replicated Servers
But, Consistency Becomes a Challenge
› An example:
– In an e-commerce application, the bank database has been
replicated across two servers
– Maintaining consistency of replicated data is a challenge

Event 1 = Add $1000 Event 2 = Add interest of 5%

1 2

Bal=2000
Bal=2100
Bal=1000 4 3 Bal=1000
Bal=1050
Bal=2050

Replicated Database
 The Two-Phase Commit Protocol
› The two-phase commit protocol (2PC) can be used to
ensure atomicity and consistency
Phase I: Voting
VOTE_REQUEST
VOTE_COMMIT

Participant 1 Database Server 1

VOTE_REQUEST

VOTE_COMMIT

Coordinator Participant 2 Database Server 2

VOTE_COMMIT
VOTE_REQUEST

Participant 3 Database Server 3

 The Two-Phase Commit Protocol
› The two-phase commit protocol (2PC) can be used to
ensure atomicity and consistency
Phase II: Commit
GLOBAL_COMMIT LOCAL_COMMIT

Participant 1 Database Server 1

GLOBAL_COMMIT LOCAL_COMMIT

Coordinator Participant 2 Database Server 2

GLOBAL_COMMIT LOCAL_COMMIT

“Strict” consistency,
which limits scalability! Participant 3 Database Server 3
 The CAP Theorem
› The limitations of distributed databases can be described
in the so called the CAP theorem
– Consistency: every node always sees the same data at any given
instance (i.e., strict consistency)
– Availability: the system continues to operate, even if nodes in a
cluster crash, or some hardware or software parts are down due
to upgrades
– Partition Tolerance: the system continues to operate in the
presence of network partitions

CAP theorem: any distributed database with shared data, can have at
most two of the three desirable properties, C, A or P
The CAP Theorem (Cont’d)
› Let us assume two nodes on opposite sides of a
network partition:

› Availability + Partition Tolerance forfeit Consistency

› Consistency + Partition Tolerance entails that one side
of the partition must act as if it is unavailable, thus
forfeiting Availability
› Consistency + Availability is only possible if there is no
network partition, thereby forfeiting Partition Tolerance
Large-Scale Databases
› When companies such as Google and Amazon were
designing large-scale databases, 24/7 Availability was a
key
– A few minutes of downtime means lost revenue
› When horizontally scaling databases to 1000s of
machines, the likelihood of a node or a network failure
increases tremendously
› Therefore, in order to have strong guarantees on
Availability and Partition Tolerance, they had to
sacrifice “strict” Consistency (implied by the CAP
theorem)
Trading-Off Consistency
› Maintaining consistency should balance between the
strictness of consistency versus availability/scalability
– Good-enough consistency depends on your application
Trading-Off Consistency
› Maintaining consistency should balance between the
strictness of consistency versus availability/scalability
– Good-enough consistency depends on your application

Loose Consistency Strict Consistency

Easier to implement, Generally hard to implement, and

and is efficient is inefficient
The BASE Properties
› The CAP theorem proves that it is impossible to
guarantee strict Consistency and Availability while
being able to tolerate network partitions
› This resulted in databases with relaxed ACID
guarantees
› In particular, such databases apply the BASE properties:
– Basically Available: the system guarantees Availability
– Soft-State: the state of the system may change over time
– Eventual Consistency: the system will eventually
become consistent
Eventual Consistency
› A database is termed as Eventually Consistent if:
– All replicas will gradually become consistent in the absence of
updates
Eventual Consistency
› A database is termed as Eventually Consistent if:
– All replicas will gradually become consistent in the absence of
updates

Webpage-A
Webpage-A Webpage-A

Event: Update
Webpage-A Webpage-A
Webpage-A

Webpage-A
Eventual Consistency:
A Main Challenge
› But, what if the client accesses the data from different
replicas?

Webpage-A
Webpage-A Webpage-A

Event: Update
Webpage-A Webpage-A
Webpage-A

Webpage-A

Protocols like Read Your Own Writes (RYOW) can be

applied!
NoSQL Databases
› To this end, a new class of databases emerged, which
mainly follow the BASE properties
– These were dubbed as NoSQL databases
– E.g., Amazon’s Dynamo and Google’s Bigtable

› Main characteristics of NoSQL databases include:

– No strict schema requirements
– No strict adherence to ACID properties
– Consistency is traded in favor of Availability
 Types of NoSQL Databases
› Here is a limited taxonomy of NoSQL databases:

NoSQL Databases

Document Graph Key-Value Columnar

Stores Databases Stores Databases
Document Stores
› Documents are stored in some standard format or
encoding (e.g., XML, JSON, PDF or Office Documents)
– These are typically referred to as Binary Large Objects
(BLOBs)

› Documents can be indexed

– This allows document stores to outperform traditional file
systems

› E.g., MongoDB and CouchDB (both can be queried

using MapReduce)
 Types of NoSQL Databases
› Here is a limited taxonomy of NoSQL databases:

NoSQL Databases

Document Graph Key-Value Columnar

Stores Databases Stores Databases
Graph Databases
› Data are represented as vertices and edges
Id: 2
Name: Bob
Age: 22

Id: 1
Name:
Alice
Age: 18

Id: 3
Name:
Chess
Type:
Group

› Graph databases are powerful for graph-like queries (e.g., find the shortest path
between two elements)

› E.g., Neo4j and VertexDB

 Types of NoSQL Databases
› Here is a limited taxonomy of NoSQL databases:

NoSQL Databases

Document Graph Key-Value Columnar

Stores Databases Stores Databases
Key-Value Stores
› Keys are mapped to (possibly) more complex value
(e.g., lists)

› Keys can be stored in a hash table and can be distributed

easily

› Such stores typically support regular CRUD (create,

read, update, and delete) operations
– That is, no joins and aggregate functions

› E.g., Amazon DynamoDB and Apache Cassandra

 Types of NoSQL Databases
› Here is a limited taxonomy of NoSQL databases:

NoSQL Databases

Document Graph Key-Value Columnar

Stores Databases Stores Databases
 Columnar Databases
› Columnar databases are a hybrid of RDBMSs and Key-
Value stores
– Values are stored in groups of zero or more columns, but in
Column-Order (as opposed to Row-Order)
Record 1 Column A Column A = Group A

Alice 3 25 Bob Alice Bob Carol Alice Bob Carol

4 19 Carol 0 3 4 0 25 3 25 4 19
45 19 45 0 45
Column Family {B, C}
Row-Order Columnar (or Column-Order) Columnar with Locality Groups

– Values are queried by matching keys

› E.g., HBase and Vertica

Summary
› Data can be classified into 4 types, structured, unstructured,
dynamic and static

› Different data types usually entail different database designs

› Databases can be scaled up or out

› The 2PC protocol can be used to ensure strict consistency

› Strict consistency limits scalability

Summary
› The CAP theorem states that any distributed database
with shared data can have at most two of the three
desirable properties:
– Consistency
– Availability
– Partition Tolerance

› The CAP theorem lead to various designs of databases

with relaxed ACID guarantees
Summary
› NoSQL (or Not-Only-SQL) databases follow the BASE
properties:
– Basically Available
– Soft-State
– Eventual Consistency

› NoSQL databases have different types:

– Document Stores
– Graph Databases
– Key-Value Stores
– Columnar Databases