IT 322

Health Data Challenges

Spring 2015

Week 12 – NoSQL
Zeehasham Rasheed

1
 Relational Databases are awesome…
• Relational Databases solve most data
problems
– Persistence
We can store data, and it will remain stored!
– Integration
We can integrate lots of different apps through a central DB
– SQL
Standard(ish), well understand, very expressive
– Transactions
ACID transactions, strong consistency
 Trends and Issues
• A few key trends and issues…
…In use cases
…In technology

• Key trends include:

– Increasing volume of data and traffic
– More complex data connectedness

• Key Issues include:

– The impedance mismatch problem
is a set of conceptual and technical difficulties that are often encountered when a
relational database management system (RDBMS) is being used by a program due to
structure complexity.
 Issue – Impedance Mismatch
Player Table

ID: 1001
Player/Game
USER: Steve
Games Played:
Date Res K D A
01/04/2009 WIN 20 2 10
Games Table Player/Team
01/05/2009 LOOSE 5 22 3

Teams:
Team Table
Name: Killer Bee Keepers
Icon:
[Link]
 Trend – Data Size
• We (the world) are
… Creating, Storing, Processing…
… more data than ever before!
“From 2005 to 2020, the digital universe will grow by a
factor of 300, from 130 exabytes to 40,000 exabytes, or
40 trillion gigabytes (more than 5,200 gigabytes for
every man, woman, and child in 2020).
From now until 2020, the digital universe will about
double every two years.”
- IDC – The Digital Universe in 2020
[Link]
 Dealing with data size Trends
• Two options when dealing with these
trends:
• Build Bigger Database machines
– This can be expensive
– Fundamental limits to machine size
• Build Cluster of smaller machines
– Lots of small machines (commodity
machines)
– Each machine is cheap, potentially
unreliable
– Needs a DBMS which understands
cluster
 Relational Databases suck…
• RDBMS have fundamental issues

– Designed to work on single, large machines

– Difficult to distribute effectively
– Normalization becomes difficult sometimes
– Unnecessary joins
 NoSQL – A movement
• NoSQL came to address
– “web-scale problems”
– … impedance mismatch solution on the way
• Key attributesinclude:
– Non-Relational (Though they can be, but aren’t good at it)
– Schema Free (Except the implicit schema, application side)
– Inherently Distributed (In different ways, Some more so
than others)
– Open Source (e.g. Oracle’s NoSQL, MongoDB)
 What is NoSQL?
 Stands for No-SQL or Not Only SQL

 Class of non-relational data storage systems

 Usually do not require a fixed table schema nor do

they use the concept of joins

 All NoSQL offerings relax one or more of the ACID

properties (will talk about the CAP theorem)
 Typical NoSQL API
 Basic API access:
 get(key) -- Extract the value given a key
 put(key, value) -- Create or update the value
given its key
 delete(key) -- Remove the key and its associated
value
 execute(key, operation, parameters) -- Invoke an
operation to the value (given its key) which is a
special data structure (e.g. List, Set, Map .... etc).
Three Eras of Databases

• RDBMS for transactions

• Data Warehouse for analytics
• NoSQL for scalability

11
 NoSQL Distinguishing Characteristics
• Large data volumes
– Google’s “big data”
• Scalable replication and distribution
– Potentially thousands of machines
– Potentially distributed around the world
• Queries need to return answers quickly
• Mostly query, few updates
• Asynchronous Inserts & Updates
• Schema-less (some say schema-free)
• ACID transaction properties are not used– BASE
– CAP Theorem
• • Open source development
 Transactions – ACID Properties

• Atomic – All of the work in a transaction completes (commit) or

none of it completes
• Consistent – A transactiontransformsthe database from one
consistent state to another consistent state. Consistency is
defined in terms of constraints.
• Isolated – The results of any changes made during a transaction
are not visible until the transaction has committed.
• Durable – The results of a committed transaction survive
failures
 Dropping Relaxing ACID
• ACID is a big deal in traditional RDBMS
– Broken transactions in Banking is a big deal
– Money leaving your account but not entering the
seller’s account is a big deal

• BUT In some situations the use case doesn’t need

all or some of ACID
– Seeing an old version of a facebook post
– An amazon shopping cart forgetting your items
– A tweet or two out of the 138 million per day being
lost
 CAP Theorem
 Three properties of a system
 Consistency (all copies have same value)
 Availability (system can run even if parts have failed)
 Via replication
 Partitions (network can break into two or more parts, each with
active systems that can’t talk to other parts)

 Brewer’s CAP “Theorem”: You can have at most two of

these three properties for any system

 Very large systems will partition at some point

 Choose one of consistency or availability
 Traditional database choose consistency
 Most Web applications choose availability
 Availability
 Traditionally, thought of as the server/process
available five 9’s (99.999 %).
 However, for large node system, at almost any
point in time there’s a good chance that a node
is either down or there is a network disruption
among the nodes.
 Want a system that is resilient in the face of
network disruption
 Eventual Consistency
 When no updates occur for a long period of time, eventually all
updates will propagate through the system and all the nodes will
be consistent
 For a given accepted update and a given node, eventually either
the update reaches the node or the node is removed from
service
 Known as BASE (Basically Available, Soft state, Eventual
consistency), as opposed to ACID
 Soft state: copies of a data item may be inconsistent

 Eventually Consistent – copies becomes consistent at some later

time if there are no more updates to that data item

CAP Theorem – The DB perspective
 BASE Transactions
• Acronym contrived to be the opposite of ACID
– Basically Available,
– Soft state,
– Eventually Consistent
• Characteristics
– Weak consistency – inconsistent data is accepted
– Availability first
– Best effort
– Approximate answers OK
– Aggressive (optimistic)
– Simpler and faster
 Common Advantages of NoSQL Systems
 Cheap, easy to implement (open source)
 Data are replicated to multiple nodes (therefore
identical and fault-tolerant) and can be
partitioned
 When data is written, the latest version is on at least
one node and then replicated to other nodes
 No single point of failure
 Easy to distribute
 Don't require a schema
 What does NoSQL Not Provide?
 Joins (not as straight forward as in SQL)
 Group By
 ACID transactions
 SQL
 Integration with applications that are based on
SQL
Should I be using NoSQL Databases?
 NoSQL Data storage systems makes sense for
applications that need to deal with very very large
semi-structured data
 Log Analysis

 Social Networking Feeds

 Most of us work on organizational databases, which

are not that large and have low update/query rates
 regular relational databases are the correct solution

for such applications

NoSQL Data Storage/Database
 Amazon S3 (Dynamo)
 BigTable, Cassandra, HBase (ordered keys, semi-
structured data)
 Sherpa/PNuts (unordered keys, JSON)
 MongoDB (based on JSON)
 CouchDB (name/value in text)
NoSQL Varieties
 NoSQL Varieties
Document Oriented (Lotus
Key-Value stores notes? Bit of a stretch! Still
(Amazon Dynamo) cool, MongoDB)

Graph DBs
Column Oriented (Triples! SPARQL!
(Google’s BigTable) Ontologies! Woo!)
Six Types of Databases

25
NoSQL Databases

26
 Key-Value Stores - Basics
• Take away message: A hashtable with
persistence (sometimes, but an API at least!)
• Use a key, ask a database for a value
• The key is usually a string
• The value can be anything (text, structure, an
image etc.)
– Database often unaware of value content
Using Key-Value Store

28
 Key-Value Store Example

“Values” can contain any type of data, e.g. images, video

29
Key-Value Store Example

Websites: using URLs as keys

30
Key-Value Store Example Systems
• Project Voldemort
– [Link]
– LinkedIn’s NoSQL key-value storage engine
• DynamoDB
– [Link]
– NoSQL database service by Amazon
• MemCacheDB
– [Link]
– Backend storage is Berkeley DB

31
 Column Family
• Key includes a row, column family and column
name
• Store versioned blobs in one large table
• Queries can be done on rows, column families
and column names
• Pros: Good scale out
• Cons: Cannot query blob content, row and
column designs are critical
34
 Column DBs - Basics
• Entries held in rows
– Rows have unique keys
• Tables define a set of “column families”

• No Schema

• On Querying:
– Key lookup is fast
– Batch processing via mapreduce (OLAP lives here)
 Column DBs - Basics
Player Details Name “darren”
Column family
Team “killerbee…"

… …

SOME_KEY game1 <gamedata>

game2 <gamedata>

… …

Games Column game3 <gamedata>

Family
 Column Family Basics
Simplified view: as a spreadsheet. The key for the cell containing
“Hello World!” is 3B

More complicated keys:

37
 Column-Family Keys

Source:
[Link]

Original example from Google’s BigTable paper.

38
 Column-Family Example Systems
• Google BigTable
– Almost all column-family store systems are
influenced on BigTable

• Hadoop/HBase

• Cassandra
– [Link]
– Developed at Facebook
– the most popular column-family store system
[Link]

39
 Some Statistics For Cassandra
• Facebook Search
• MySQL > 50 GB Data
– Writes Average : ~300 ms
– Reads Average : ~350 ms
• Rewritten with Cassandra > 50 GB Data
– Writes Average : 0.12 ms
– Reads Average : 15 ms
 Google apps that use BigTable
• Google Earth
– RowID for the longitude portion of the map
– Column name for latitude
• one map for each square mile on Earth, you could have
15,000 distinct rowIDs and 15,000 distinct columnIDs
 Google apps…
• Google Analytics: allows you to track visits to
your website
– Every click is stored in a single row-column entry
with the rowID being the URL and timestamp
– Summarizes the data every day (like a warehouse)
 Google…
• Google Maps
– Each location identified by longitude and latitude
– Map layers in columns
• E.g., Photos from your trip to a location
 Document Store

• Like key-value stores except: value is document and

searchable, key is never seen or used
• Data stored in nested hierarchies
• Document: JSON, XML, other semi-structured formats
• Any item in the document can be queried
• Pros: No object-relational mapping layer, ideal for
search
• Cons: Complex to implement, incompatible with SQL
43
 Document Database - Basics
• Database as storage of a mass of different
documents
• A document…
– is a complex data structure
– can contain completely different data from
other documents
• Document data stores understand their documents
– Queries can run against values of document fields
– Indexes can be constructed for document fields
– Batch style (mapreduce etc.)often supported
Document Database - Basics
{
"_id": "1",
"name": "steve",
"games_owned": [
{"name":"Super Meat Boy"},
{"name":"FTL"},
],
}

{
"_id": "2",
"name": "darren",
"handle":"zerocool",
"games_owned": [
{"name":“FTL"},
{"name":“Assassin’s Creed 3“, “dev”: “ubisoft”},
],
}
 Document Database - Examples
• MongoDB
– Master/Slave design
– .find() queries like ORM
– Geo-spatial indexing

• CouchDB
– Only map reduce queries
Weird but pretty cool, see:
[Link]
[Link]
– Favours availability to consistency (more on this in a bit)
 MongoDB
• Data are organized in collections. A collection
stores a set of documents.
• Collection are like table and documents are
like record
– but: each document can have a different set of
attributes even in the same collection
– Semi-structured schema!
• Only requirement: every document should
have an “_id” field (default object id by mongoDB)
 MongoDB Example
{ "_id”:ObjectId("4efa8d2b7d284dad101e4bc9"),
"Last Name": ” Cousteau",
"First Name": ” Jacques-Yves",
"Date of Birth": ”06-1-1910" },

{ "_id": ObjectId("4efa8d2b7d284dad101e4bc7"),
"Last Name": "PELLERIN",
"First Name": "Franck",
"Date of Birth": "09-19-1983",
"Address": "1 chemin des Loges",
"City": "VERSAILLES" }
MongoDB Document Example

[Link]({
first: ‘john’,
last: ‘smith’,
gender: ‘m’,
hair_color: ‘brown’,
occupation: ‘developer’,
nationality: ‘american’
});

• “first”, “last”, “gender”, etc. are arbitrary tags.

• Database is schema-less
52
 Graph Store

• Data is stored in a series of nodes and

properties
• Queries are really graph traversals
• Ideal when relationships between data is key,
e.g. social networks
• Pros: Fast network search, works with public
linked datasets
• Cons: Poor scalability when graphs don’t fit
into RAM, specialized query language
53
 Graph DBs - basics
The Matrix Revolution

Keanu Reeves

The Matrix Reloaded Laurence Fishburne

Acts In

Carrie-Anne Moss The Matrix

 Graph Data

Social network
Internet
Human cells
Brain
Road network
:
:
• Query examples:
– Mutual friends between two people?
– How many “degrees of separation” are there between two
people?
– Find “influencers” in a group (to target as potentialcustomers)
55
Graph Store Example: LinkedIn InMap

GMU

UCR
56
 Graph DBs - examples
• Neo4j
– Not distributed
– ACID transactions START
m=node:node_auto_index(id="603")
– Cypher for query: MATCH m<-[:ACTS_IN]-actor
RETURN actor;

• 4store
– RDF and Semantic Web technologies
– 5store supports 1000s of machines easily
– SPARQL for query: SELECT ?a WHERE{?a ACTS_IN ?m; ?
m HAS_ID 603}
58
 MongoDB Example: E-Commerce
• Problem: Product catalogs store different types of
objects with different sets of attributes.
• This is not easily done within the relational model,
need a more “flexible schema”
• Relational Solutions
– Create a table for each product category
– Put everything in one table
– Use inheritance
– Entity-Attribute-Value
– Put everything in a BLOB
56
RDBMS (1): Table per Product
CREATE TABLE `product_audio_album`
( `sku` char(8) NOT NULL, ...
`artist` varchar(255) DEFAULT NULL,
`genre_0` varchar(255) DEFAULT NULL,
`genre_1` varchar(255) DEFAULT NULL, ...
PRIMARY KEY(`sku`)) ...

CREATE TABLE `product_film`

( `sku` char(8) NOT NULL, ...
`title` varchar(255) DEFAULT NULL,
`rating` char(8) DEFAULT NULL, ...
PRIMARY KEY(`sku`)) ...
57
 RDBMS (2): Single table for all
CREATE TABLE `product`
( `sku` char(8) NOT NULL, ...
`artist` varchar(255) DEFAULT NULL,
`genre_0` varchar(255) DEFAULT NULL,
`genre_1` varchar(255) DEFAULT NULL, ...
`title` varchar(255) DEFAULT NULL,
`rating` char(8) DEFAULT NULL, ...
PRIMARY KEY(`sku`))

58
 RDBMS (3): Inheritance
CREATE TABLE `product`
( `sku` char(8) NOT NULL,
`title` varchar(255) DEFAULT NULL,
`description` varchar(255) DEFAULT NULL,
`price`, ...
PRIMARY KEY(`sku`))

CREATE TABLE `product_audio_album`

( `sku` char(8) NOT NULL, ...
`artist` varchar(255) DEFAULT NULL,
`genre_0` varchar(255) DEFAULT NULL,
`genre_1` varchar(255) DEFAULT NULL, ...
PRIMARY KEY(`sku`),
FOREIGN KEY(`sku`) REFERENCES `product`(`sku`))
59
RDBMS (4): Entity Attribute Value
Entity Attribute Value
sku_00e8da9b Type Audio Album
sku_00e8da9b Title A Love
Supreme
sku_00e8da9b … …
sku_00e8da9b Artist John Coltrane
sku_00e8da9b Genre Jazz
sku_00e8da9b Genre General

60
 MongoDB Solution
• A “collection” can contain heterogeneous “documents”, e.g. for
an audio album we could store as
{ sku: "00e8da9b",
type: "Audio Album",
title: "A Love Supreme",
description: "by John Coltrane",
shipping: { weight: 6,
dimensions: { width: 10, height: 10, depth: 1 } },
pricing: { list: 1200, retail: 1100, savings: 100},
details: { title: "A Love Supreme [Original Recording]",
artist: "John Coltrane",
genre: [ "Jazz", "General" ]}
} 61
 MongoDB Marketing Spiel
• MongoDB (from "humongous") is a scalable, high-
performance, open source, document-oriented
database.
– Fast querying & In-place updates
– Full Secondary Index Support
– Replication & High Availability
– Auto-Sharding

• Currently used in a number of different applications

– Craigslist, ebay, New York Times, Shutterfly, Chicago Tribune,
Github, Disney…
62
 MondoDB Data Model
• A MongoDB deployment hosts a number of
databases. A database holds a set of
collections. A collection holds a set of
documents. A document is a set of key-value
pairs.
RDBMS MongoDB
Table Collection
Row(s) JSON Document
Index Index
Join Embedding & Linking
Partition Shard
Partition Key Shard Key
63
 Basic Data Types
• Null • ObjectId
• Boolean • Date
• Integer (32- and 64-bit) • Code (JavaScript)
• Floating point • Array
• String • Embedded document

64
 Sample MongoDB Document
mydoc = { Always indexed. Can be any BSON data type other
_id: 1, than an array
name: { first: “John”, last: “Backus” },
birthyear: integer,
contribs: [ “Fortran”, “ALGOL”, “Backus-Naur Form”, “FP” ],
awards: [ { award_id: “NMS001”,
year: 1975 },
Array of documents { award_id: “TA99”,
year: 1977} ]
}
> [Link](mydoc)

65
 Core MongoDB Operations
• CRUD: create, read, update, and delete
• Insert
– One at a time: [Link](mydoc)
– Batch insert (size limitation: less than 16 MB) -- you will use this
in the homework, syntax given there.
• Delete
– Documents that match some predicate, e.g. to remove the
document just added: [Link]({“_id”: 1})
– All documents in a collection: [Link]()
• The collection still remains, with indexes
– Remove a collection (faster): [Link]()
66
 Querying
• Use find/findOne functions and a query
document
• Ranges, set inclusion, inequalities using $
conditionals
• Complex queries using $where clause

67
 Another Sample Document
d={
_id : ObjectId(“4c4ba5c0672c685e5e8aabf3”),
author : “Kevin”,
date : new Date(“February 2, 2012”),
text : “About MongoDB...”,
birthyear: 1980,
tags : [ "tech", "databases" ]
}

> [Link](d)

68
 Find
[Link]()
returns entire collection in posts
[Link]({“author”: “Kevin”, “birthyear”: 1980})
Output is

{
_id :
ObjectId("4c4ba5c0672c685e5e8aabf3"),
author : "Kevin",
date : Date(“February 2, 2012”),
birthyear: 1980,
text : "About MongoDB...",
tags : [ "tech", "databases" ] 69

}
 Ranges, Negation, OR-clauses
• Comparison operators: $lt, $lte, $gt, $gte
– [Link]({“birthyear”: {“$gte”: 1970, “$lte”:
1990}})
• Negation: $ne
– [Link]({“birthyear”: {“$ne”: 1982}})
• Or queries: $in (single key), $or (different keys)
– [Link]({“birthyear”: {“$in”: [1982, 1985]}})
– [Link]({“$or”: [{“birthyear”: 1982},
{“name”: “John”}]})
70
 Arrays
• [Link]({“tags”: “tech”})
– Print complete information about posts which are
tagged “tech”
• [Link]({“tags”: {$all: [“tech”,
“databases”]},{“author”:1, “tags”:1})
– Print author and tags of posts which are tagged with
both “tech” and “databases” (among other things)
– Contrast this with:
[Link]({“tags”: [“databases”, “tech”]})

71
 Limits, Skips, Sort, Count
• [Link]().limit(3)
– Limits the number of results to 3
• [Link]().skip(3)
– Skips the first three results and returns the rest
• [Link]().sort({“author”:1, “title”: -1})
– Sorts by author ascending (1) and title descending (-1)
• [Link](…).count()
– Counts the number of documents in the people
collection matching the find(…)

72
 Revisiting Sample Document
mydoc = {
_id: 1,
name: { first: “John”, last: “Backus” },
birthyear: 1924,
contribs: [ “Fortran”, “ALGOL”, “Backus-Naur Form”, “FP” ],
awards: [ { award_id: “NMS001”,
year: 1975 },
{ award_id: “TA99”,
year: 1977} ]
}
> [Link](mydoc)

73
 Also assume…
award1=
{_id: “NMS001”,
title: “National Medal of Science” ,
by: “National Science Foundation”}

award2=
{_id: “TA99”,
title: “Turing Award”,
by: “ACM” }

[Link](award1)
[Link](award2)
74
 “SemiJoins”
• Suppose you want to print people who have
won Turing Awards

– Problem: object id of Turing Award is in collection

“awards”, collection “people” references it.

turing= [Link]({title: “Turing Award”})

[Link]({"awards.award_id": turing["_id"]})

75
 Summary of MongoDB
• MongoDB is an example of a document-oriented
NoSQL solution
• The query language is limited, and oriented
around “collection” (relation) at a time processing
– Joins are done via a query language
• The power of the solution lies in the distributed,
parallel nature of query processing
– Replication and sharding

76
 NoSQL Summary
• NoSQL databases reject:
– Overhead of ACID transactions
– “Complexity” of SQL
– Burden of up-front schema design
– Declarative query expression
 SQL vs. NoSQL Summary

• SQL Databases
– Predefined Schema
– Standard definition and interface language
– Tight consistency
– Fine-grained security on columns/rows using views
– Well defined semantics
• NoSQL Database
– No predefined Schema
– Per-product definition and interface language
– Getting an answer quickly is more important than getting a
correct answer
– Query standards have yet to be established
 Bottom Line
• NoSQL means “Not Only SQL”
• Relational databases will continue to be an
appropriate solution to many business problems for
the foreseeable future.
• RDBMSs are continuing to evolve and are making it
possible to relax ACID requirements and manage
document-oriented structures.
• But there are situations where relational databases
aren’t the best match for a business problem.
– Need to consider nature of data, business requirements,
and trade-offsbetween consistency, availability and
scalability
81
 Good Resources
• RDBMS vs. NoSQL: How Do You Pick?
– [Link]
you-pick-7000020803/

• SQL vs. NoSQL: Which is Better?

– [Link]
which-is-better/
– Good summary on arguments from both sides

82
 Web References
• “NoSQL -- Your Ultimate Guide to the Non - Relational Universe!”
[Link]
• “NoSQL (RDBMS)”
[Link]
• PODC Keynote, July 19, 2000. Towards Robust. Distributed Systems. Dr.
Eric A. Brewer. Professor, UC Berkeley. Co-Founder & Chief Scientist,
Inktomi .
[Link]/~brewer/cs262b-2004/[Link]
• “Brewer's CAP Theorem” posted by Julian Browne, January 11, 2009.
[Link]
• “How to write a CV” Geek & Poke Cartoon
[Link]

83
 Web References (2)
• “Exploring CouchDB: A document-oriented database for Web
applications”, Joe Lennon, Software developer, Core International.
[Link]
couchdb/[Link]

• “Graph Databases, NOSQL and Neo4j” Posted by Peter Neubauer on

May 12, 2010 at: [Link]

• “Cassandra vs MongoDB vs CouchDB vs Redis vs Riak vs HBase

comparison”, Kristóf Kovács. [Link]
mongodb-vs-couchdb-vs-redis

• “Distinguishing Two Major Types of Column-Stores” Posted by

Daniel Abadi onMarch 29, 2010
[Link]
major-types-of_29.html

3 August 2014 84
 Web References (3)
• “MapReduce: Simplified Data Processing on Large Clusters”,
Jeffrey Dean and Sanjay Ghemawat, December 2004.
[Link]

• “Scalable SQL”, ACM Queue, Michael Rys, April 19, 2011

[Link]

• “a practical guide to noSQL”, Posted by Denise Miura on March

17, 2011 at [Link]
guide-to-nosql/

85
 MongoDB References
• Read the following manuals:

• [Link]

• [Link]

• [Link]
 Books
• “CouchDB The Definitive Guide”, J. Chris Anderson, Jan Lehnardt
and Noah Slater. O’Reilly Media Inc., Sebastopool, CA, USA.
2010

• “Hadoop The Definitive Guide”, Tom White. O’Reilly Media Inc.,

Sebastopool, CA, USA. 2011

• “MongoDB The Definitive Guide”, Kristina Chodorow and

Michael Dirolf. O’Reilly Media Inc., Sebastopool, CA, USA.
2010

• “NoSQL Distilled,” P. Sadalage and M. Fowler, Addison-Wesley,

2012
86