Semistructured Data

October 19, 2023

Data 101, Fall 2023 @ UC Berkeley

Lisa Yan https://fa23.data101.org/

1

LECTURE 17

Join at slido.com�#707070

ⓘ

Click Present with Slido or install our Chrome extension to display joining instructions for participants while presenting.

Translate into a Relational Schema

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

3

[from last time]

Lecture 17, Data 101 Fall 2023

[Review] From ER Diagrams to Relational Schema

Recall: The ER diagram is a part in the design process we can use to�build a relational schema.

• We have just finished describing key components the ER Diagram.

Next, the design process is three-step:

1. Start with data requirements. (we skip this step)
2. Design the ER Diagram.

​

• Translate to fit the relational model, i.e.,�convert the ER Diagram into a relational schema.

4

Three key principles:

• Be faithful to reality.
• Pick the right kind of element.
• Avoid redundancy.

#707070

[Review] Relationship to Relation: Many-to-one

5

ER Design → Relational Schema:

• One relation per entity set.
• One relation per relationship.
• Many-to-one: Can merge into entity set.

If the relationship is many-one or one-one, it may make sense to combine representations,�since all columns are foreign keys or attributes of the relation.

Instead of:� Product(price,name,category)� Makes(Product.name,category,� startyear,Company.name)

Company(name,stockprice)

Combine to:

Product(name,category,

startdate,companyname)

Company(name, stockprice)

name

category

price

Product

name

startyear

typo fixed post-�lecture

at most one

many

#707070

[cont.] Part 2. Relationship to Relation: Many-to-one

6

If the relationship is many-one or one-one, it may make sense to combine representations,�since all columns are foreign keys or attributes of the relation.

Instead of:� Product(price,name,category)� Makes(Product.name,category,� startdate,Company.name)� Company(name,stockprice)

Combine to:

Product(name,category,

startdate,companyname)

Company(name, stockprice)

name

category

price

Product

name

startyear

typo fixed post-�lecture

at most one

many

#707070

Exercise: ER Diagram on Movies

7

🤔

title

director

rdate

Movies

Studios

name

addr

(release date)

Presidents

name

salary

• Movies(title, director)
• Releases(movie_title, cost,� rdate, studio_name)
• Studios(name, addr)
• Runs(studio_name, pres_name)
• Presidents(name, salary)

How can we reduce redundancy of one-to-one and many-to-one?

Format: A schema in the resulting less redundant relational schema, e.g.,

Movies(title, director)

#707070

How can we reduce redundancy of one-to-one and many-to-one?

Format: A schema in the resulting less redundant relational schema, e.g., Movies(title, director)

ⓘ

Click Present with Slido or install our Chrome extension to activate this poll while presenting.

Exercise: One possible solution

9

title

director

rdate

Movies

Studios

name

addr

(release date)

Presidents

name

salary

• Movies(title, director)
• Releases(movie_title, cost,� rdate, studio_name)
• Studios(name, addr)
• Runs(studio_name, pres_name)
• Presidents(name, salary)

Many-to-one,�movie must have studio

Movies(title, director,� cost, rdate, studio_name)

#707070

Exercise: One possible solution, continued

10

title

director

rdate

Movies

Studios

name

addr

cost

(release date)

Presidents

name

salary

• Movies(title, director)
• Releases(movie_title, cost,� rdate, studio_name)
• Studios(name, addr)
• Runs(studio_name, pres_name)
• Presidents(name, salary)

Movies(title, director,� cost, rdate, studio_name)

One-to-one, president must have studio; studio has at most one president

Many-to-one,�movie must have studio

Studios(name, addr,� pres_name, pres_salary)

#707070

Exercise

11

Why not go all the way and have all the information in one table? We risk massive redundancy! (because of the many-one)

Studios

name

addr

Movies(title, director,� cost, rdate, studio_name)

One-to-one, president must have studio; studio has at most one president

Many-to-one,�movie must have studio

Studios(name, addr,� pres_name, pres_salary)

There are many ways to redesign relational schema; we’ve just shown you some examples here. Next up: a preview of a generalized process.

title

director

rdate

Movies

cost

(release date)

Presidents

name

salary

#707070

Normalization

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

12

Lecture 17, Data 101 Fall 2023

Two final pieces: Functional Dependencies and Normalization

Our current process:

1. Start with data requirements.
2. Design the ER Diagram.
3. Translate to fit the relational model, i.e., convert the ER Diagram into a relational schema.

⚠️ We are not quite done!

• There can still be issues with the relations that cause us problems.
• Or, we don’t have an ER diagram, and we may need to “fix” an existing set of relations.

Two final intuitive pieces:

• Normalization is the process of splitting (decomposing) relations into multiple relations to minimize redundancy.
• Functional dependencies are forms of constraints between two sets of attributes�in a relation.
• Functional dependencies inform normalization.

For now, let’s consider an example where our current process is insufficient. We’ll then do an intuitive overview of normalization/functional dependencies…but we’ll skip the details.

13

#707070

Individual with several phones

Why might this be a bad design?

• Redundancy: Address repeated multiple times
• Update anomalies
• If we update address of person with�phone number (201) 233-1456…
• …there will be two addresses of that person
• Deletion anomalies
• If we delete the phone number for a person…
• …we need to check another phone number exists for said person. Otherwise we lose address info (dangling pointers)

The issue:

• Each record seemingly refers to an entity set with consistent entities
• But there is no “verb” that defines relationships for us to split this relation.

14

#707070

Individual with several phones: A Normalized Design

This design was achieved through normalization.

• From before: Normalization is the process of splitting (decomposing) relations into multiple relations to minimize redundancy.

Why might this be a better design?

• Each bit of information only exists “once”!

15

How do we recover the original relation? Use a natural join!

Note: Minimizing redundancy is just one objective; there are others, but we won’t cover them here.

#707070

Individual with several phones: A Normalized Design

How do we perform normalization?

• We won’t detect the proposed “normalized” design even with principled ER design and translation!
• We use functional dependencies to guide normalization.

This design was achieved through normalization.

• From before: Normalization is the process of splitting (decomposing) relations into multiple relations to minimize redundancy.

Why might this be a better design?

• Each bit of information only exists “once”!

Tradeoffs of normalization:

• Benefits: removes redundancy, minimizes update/delete anomalies
• Downsides: Joins are costly, and we want to avoid them.

16

How do we recover the original relation? Use a natural join!

#707070

Functional Dependencies

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

Document Store: JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

17

This will not be covered in lecture! It will be covered in Discussion 8.

See Lecture 16 for preview.

Lecture 17, Data 101 Fall 2023

Semi-Structured Data

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

18

Lecture 17, Data 101 Fall 2023

The advent of the Data Lake

19

#707070

Structured Data Models

So far:

• Matrices M x N array of values consisting of a uniform type
• Relations (aka tables) Has a well-defined schema
• Dataframes Hybrid of relations and matrices, more flexible

All of these data models are still rectangular, i.e., structured.

20

#707070

Structured Data Models

So far:

• Matrices M x N array of values consisting of a uniform type
• Relations (aka tables) Has a well-defined schema
• Dataframes Hybrid of relations and matrices, more flexible

All of these data models are still rectangular, i.e., structured.

21

Structured, rectangular assumptions:

1. There is a fixed set of attributes.

• A fixed number of attributes/columns across all records in the rectangular data model.

2. Attributes are atomic.

• Each value per attribute/column is atomic, i.e., single values represented the field type.
• (Exception: dataframes allows more complex values in the catch-all object type)

3. Attributes can’t be nested.

• Each attribute contains values, not other attributes within it.
• Attributes can’t be nested within other attributes
• Records can’t be nested within other records

#707070

From Structured to Semi-Structured Data

Semi-structured data is a data representation or data model that is less “rigid” than structured or rectangular data.

Removes all three of the following assumptions:

1. There is a fixed set of attributes. → Flexible schema.

​

2. Attributes are atomic. → Attributes can be multivalued.

​

3. Attributes can’t be nested. → Attributes can be nested.

​

Semi-structured data is exemplified by a few popular formats:

• XML (Document Store)
• JSON (Document Store)
• Key-Value Stores (older, see extra slides)

​

​

​

22

#707070

Is Semi-Structured New?

Semi-structured data actually existed prior to structured data!

• In fact, some of the earliest�database systems used�nested or hierarchical models.
• Eventually, most of these�were abandoned.

In modern situations, semi-structured data works well as a data exchange format.

• i.e., exchanging data between different apps.
• XML, JSON, Protobuf (protocol buffers) are flexible formats that can then be translated into, say, relational models.

Increasingly, some DBMSes support (or even only support) semi-structured data models:

• Postgres, SQL Server both support JSON/XML-valued attributes, as does Snowflake.
• NoSQL databases: CouchBase, MongoDB

23

wikipedia

#707070

JSON

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

24

Lecture 17, Data 101 Fall 2023

JSON: JavaScript Object Notation

JSON is a textual representation of complex data types.

• This representation is designed for human-readable data interchange.
• It can be stored in a binary format for a more compact representation.

25

JSON is widely used for transmitting data between applications and storing complex data.

• Incredibly common in internet applications, e.g., transferring data to the browser
• Manipulated easily by JavaScript within the browser
• Interfaces in C, C++, Java, Python, Perl, etc.

[

{

"title":"Benchmarking Spreadsheet Systems",

"link": "https://people.eecs.berkeley.edu/~adityagp/papers/spreadsheet_bench.pdf",

"authors": "Sajjadur Rahman, Kelly Mack, Mangesh Bendre, Ruilin Zhang, Karrie Karahalios, Aditya Parameswaran",

"conf":"SIGMOD Int'l Conf. on Management of Data",

"location": "Portland, USA",

"date": "June 2020",

...

},

{

"title":"ShapeSearch: A Flexible and Efficient System for Shape-based Exploration of Trendlines",

"link": "https://arxiv.org/abs/1811.07977",

"authors":"Tarique Siddiqui, Zesheng Wang, Paul Luh, Karrie Karahalios, Aditya Parameswaran",

"status":"Unpublished Manuscript",

"date": "June 2020",

"price": 7.95,

...

},

"this is just a string",

...

]

#707070

JSON Types and Values

Values can be Primitives, Objects, or Arrays.

26

[

{

"title":"Benchmarking Spreadsheet Systems",

"link": "https://people.eecs.berkeley.edu/~adityagp/papers/spreadsheet_bench.pdf",

"authors": "Sajjadur Rahman, Kelly Mack, Mangesh Bendre, Ruilin Zhang, Karrie Karahalios, Aditya Parameswaran",

"conf":"SIGMOD Int'l Conf. on Management of Data",

"location": "Portland, USA",

"date": "June 2020",

...

},

{

"title":"ShapeSearch: A Flexible and Efficient System for Shape-based Exploration of Trendlines",

"link": "https://arxiv.org/abs/1811.07977",

"authors":"Tarique Siddiqui, Zesheng Wang, Paul Luh, Karrie Karahalios, Aditya Parameswaran",

"status":"Unpublished Manuscript",

"date": "June 2020",

"price": 7.95,

...

},

"this is just a string",

...

]

Primitive: number, string, boolean, null

Object: collection of key-value pairs.

{"key1": value1,� "key2": value2, ... }

Array: ordered list of values.

[val1, val2, val3, ...]

#707070

JSON Semantics are a Tree!

27

person

Mary

name

address

name

address

street

no

city

Maple

345

SF

John

Thai

phone

23456

0​

1

{"person":

[

{

"name": "Mary",

"address":

{

"street":"Maple",

"no":345,

"city": "SF"

}

},

{

"name": "John",

"address": "Thailand",

"phone":2345678

}

]

}

In JSON, arrays are ordered.

#707070

Back to the Papers example

Why use JSON for representing paper data?

1. Flexibility in set of attributes

• Can add a new attribute for the new tuples without changing others

2. Self-describing

• The key-value format means I must explicitly list what I’m talking about
• More human-readable

28

3. JSON can be easily parsed within JavaScript�for rendering

4. Very small data! Likely <100 papers for even a full faculty

[

{

"title":"Benchmarking Spreadsheet Systems",

"link": "https://people.eecs.berkeley.edu/~adityagp/papers/spreadsheet_bench.pdf",

"authors": "Sajjadur Rahman, Kelly Mack, Mangesh Bendre, Ruilin Zhang, Karrie Karahalios, Aditya Parameswaran",

"conf":"SIGMOD Int'l Conf. on Management of Data",

"location": "Portland, USA",

"date": "June 2020",

...

},

{

"title":"ShapeSearch: A Flexible and Efficient System for Shape-based Exploration of Trendlines",

"link": "https://arxiv.org/abs/1811.07977",

"authors":"Tarique Siddiqui, Zesheng Wang, Paul Luh, Karrie Karahalios, Aditya Parameswaran",

"status":"Unpublished Manuscript",

"date": "June 2020",

"price": 7.95,

...

},

"this is just a string",

...

]

#707070

How do we represent Papers in the Relational Model?

Option 1: All applicable attributes in one schema:�(title, link, authors, conf, location, date, status)

• published → conf, location; unpublished → status
• Con: conf, location are empty for unpublished�(similarly, status is empty for published)
• Con: need to scan entire relation for unpublished papers, unless there is an index

​

Option 2: Split into two relations based on un/published� published(title,link,authors,date,conf,location)� unpublished(title,link,authors,date,status)

• Con: Union needed to combine info across relations (common use case: compiling curriculum vitae)

Option 3: Split into three relations via normalization

• all_papers(title,link,authors,date)�published(title,conf,location)�unpublished(title,status)
• Con: Join/union needed (likely very common)

​

29

[

{

"title":"Benchmarking Spreadsheet Systems",

"link": "https://people.eecs.berkeley.edu/~adityagp/papers/spreadsheet_bench.pdf",

"authors": "Sajjadur Rahman, Kelly Mack, Mangesh Bendre, Ruilin Zhang, Karrie Karahalios, Aditya Parameswaran",

"conf":"SIGMOD Int'l Conf. on Management of Data",

"location": "Portland, USA",

"date": "June 2020",

...

},

{

"title":"ShapeSearch: A Flexible and Efficient System for Shape-based Exploration of Trendlines",

"link": "https://arxiv.org/abs/1811.07977",

"authors":"Tarique Siddiqui, Zesheng Wang, Paul Luh, Karrie Karahalios, Aditya Parameswaran",

"status":"Unpublished Manuscript",

"date": "June 2020",

"price": 7.95,

...

},

"this is just a string",

...

]

All three options are not ideal for this use case. Nevertheless, sometimes we need to transform JSON data to rectangular data, and vice versa. Let’s do this!

#707070

Transforming between Rectangular Data and JSON

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

30

Lecture 17, Data 101 Fall 2023

Transform Rectangular Data → JSON

Rectangular data can be represented by a balanced tree, which then translates to a JSON.

• Order of records could have been arbitrary in the relation! But now fixed in JSON.
• Possible fix: use index order, if available

31

Person

{“person”: [�{“name”: “John”, “phone”:3634},�{“name”: “Aliyah”, “phone”:6343},

{“name”: “Dirk”, “phone”:6383}�] }

#707070

Transform Rectangular Data → JSON

Rectangular data can be represented by a balanced tree, which then translates to a JSON.

• Order of records could have been arbitrary in the relation! But now fixed in JSON.
• Possible fix: use index order, if available

May inline (i.e., nest) multiple relations if related.

• Nest based on foreign keys
• Note the redundancy!

32

Person

{“Person”:

[{"name": "John",

"phone":3646,�"Orders":[�{"date":2002,"product":"Gizmo"},�{“date”:2004,"product":"Gadget"}�]

},

{"name": "Aliyah",�"phone":6343,�"Orders":[

{"date":2002,"product":"Gadget"}�]

}

]

}

Person

Product

orders

name

phone

date

name

Orders

#707070

Many-many relationships are much more difficult!

33

Person

Orders

Person

Product

orders

name

phone

date

name

Product

price

Note: We now have a separate Product relation because price is a non-index Product attribute that would be redundant to append to Orders.

#707070

Many-many relationships are much more difficult!

Several options for the JSON file. Here’s a few:

1. Array of 3 flat relations:�[Person, Orders, Product]�loses foreign key relationship encoding
2. Person→Orders→Product�product attributes are duplicated
3. Product→Orders→Person�person attributes are duplicated
4. Orders→Person→Product�person, product attributes are duplicated�

34

Person

Orders

Product

#707070

Many-many relationships are much more difficult!

Several options for the JSON file. Here’s a few:

• Array of 3 flat relations:�[Person, Orders, Product]�loses foreign key relationship encoding
• Person→Orders→Product�product attributes are duplicated
• Product→Orders→Person�person attributes are duplicated
• Orders→Person→Product�person, product attributes are duplicated�

35

Person

Orders

Product

🤔

Suppose we convert the relational database using Option 2. How many times will the 9.99 price be present in the resulting JSON?

A. 0

B. 1

C. 2

D. 3

E. 4

F. Something� else

#707070

Suppose we convert the relational database using Option 2. How many times will the 9.99 price be present in the resulting JSON?

ⓘ

Click Present with Slido or install our Chrome extension to activate this poll while presenting.

Many-many relationships are much more difficult!

Several options for the JSON file. Here’s a few:

• Array of 3 flat relations:�[Person, Orders, Product]�loses foreign key relationship encoding
• Person→Orders→Product�product attributes are duplicated
• Product→Orders→Person�person attributes are duplicated
• Orders→Person→Product�person, product attributes are duplicated�

37

Person

Orders

Product

Suppose we convert the relational database using Option 2. How many times will the 9.99 price be present in the resulting JSON?

{"Person":

[{"name": "John",

"phone":3646,�"Orders":[�{"date":2002,"Product":

{"name": "Gizmo",

"price": "19.99},

}]

], …

}

​

Price value is repeated as many times as it is ordered! (here: 2x)

JSON does not (natively) support joins.

Subsequently, redundancy is a necessary product of denormalization due to nesting..

#707070

Transform JSON → Rectangular Data

This transformation process is much more complicated and requires high-touch design.

Straightforward:�Fixing the unfixed schema.�Missing attributes → NULL values.

38

{"person":� [{"name":"Or", "phone":1234},� {"name":"Aliyah"}]�}

#707070

Transform JSON → Rectangular Data

This transformation process is much more complicated and requires high-touch design.

Straightforward:�Fixing the unfixed schema.�Missing attributes → NULL values.

More complicated: Converting multivalues to atomic values.

39

{"person":� [{"name":"Or", "phone":1234},� {"name":"Noor",� "phone": "23-4565"}]�}

Text wrangling/�canonicalization needed!

#707070

Transform JSON → Rectangular Data

This transformation process is much more complicated and requires high-touch design.

Straightforward:�Fixing the unfixed schema.�Missing attributes → NULL values.

More complicated: Converting multivalues to atomic values.

More complicated: Converting nested values to atomic values.

​

40

❌ Impossible (because of fixed schema)

Most phone2’s are likely NULL!

Index on phones will break!

Indexes on names will break!

{"person":� [{"name":"Or", "phone":1234},� {"name":"Noor",� "phone": [2345, 3456]}]�}

#707070

Transform JSON → Rectangular Data

This transformation process is much more complicated and requires high-touch design.

Straightforward:�Fixing the unfixed schema.�Missing attributes → NULL values.

More complicated: Converting multivalues to atomic values.

More complicated: Converting nested values to atomic values.

​

41

❌ Impossible (because of fixed schema)

Most phone2’s are likely NULL!

Index on phones will break!

Indexes on names will break!

{"person":� [{"name":"Or", "phone":1234},� {"name":"Noor",� "phone": [2345, 3456]}]�}

#707070

Transform JSON → Rectangular Data

This transformation process is much more complicated and requires high-touch design.

Straightforward:�Fixing the unfixed schema.�Missing attributes → NULL values.

More complicated: Converting multivalues to atomic values.

More complicated: Converting nested values to atomic values.

​

Even more difficult representations:

• Nested collections
• Heterogeneous collections

42

{"person":� [{"name":"Or", "phone":1234},� {"name": {"first": "Noor",

"last": "Cohen"},� "phone": [2345, 3456]}]�}

#707070

Exercise: Transform JSON → Rectangular Data

{

"ID": "22222",

"name": {

"firstname": "Albert",

"lastname": "Einstein"

},

"deptname": "Physics",

"children": [

{

"firstname": "Hans",

"lastname": "Einstein"

},

{

"firstname": "Eduard",

"lastname": "Einstein"

}

]

}

1. Denormalized representation:� (ID, firstname, lastname, deptname,� childfn, childln)

​

2. Normalized representation:� (ID, firstname, lastname, deptname)� (ID, childfn, childln)

43

🤔

What are disadvantages of the following rectangular representations?

A. Repeated information for each child

B. Unnecessary joins

C. Something else

#707070

What are disadvantages of the following rectangular representations?

ⓘ

Click Present with Slido or install our Chrome extension to activate this poll while presenting.

Exercise: Transform JSON → Rectangular Data

1. Denormalized representation:� (ID, firstname, lastname, deptname,� childfn, childln)

​

2. Normalized representation:� (ID, firstname, lastname, deptname)� (ID, childfn, childln)

{

"ID": "22222",

"name": {

"firstname": "Albert",

"lastname": "Einstein"

},

"deptname": "Physics",

"children": [

{

"firstname": "Hans",

"lastname": "Einstein"

},

{

"firstname": "Eduard",

"lastname": "Einstein"

}

]

}

45

What are disadvantages of the following rectangular representations?

A. Repeated information for each child

B. Unnecessary joins

#707070

JSON: Pros and Cons

Cons:

• Update/delete anomalies
• Redundancy of relation data due to denormalization/nesting

Pros:

• Flexibility in attributes
• Very easy to add new tuple without adjusting any fixed schema
• Avoid unnecessary joins
• Denormalization, i.e., capturing info across multiple relations
• Easy-to-read data
• Self-describing

46

• Finding information about one relation still requires examining the entire JSON.
• Depending on the outer nesting, could make it tricky to find inner-nested information
• e.g., Person→Order→Product means Product information is hard to find

• Harder to make compact due to “self-describing” nature
• Repeated keys occupy space!
• For fixes, see: binary JSON representations, or assuming fixed structure of specific tuples

#707070

Aside: XML

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

47

Lecture 17, Data 101 Fall 2023

XML: eXtensible Markup Language

XML is an older semi-structured data format (from the late 90s).

• Flexible support for complex data types.
• HTML is another such markup language: Hyper Text Markup Language

48

<purchase order>

<identifier> P-101 </identifier>

<purchaser>

<name> Wile E. Coyote </name>

<address> Route 66, Mesa Flats, Arizona 86047, USA</address>

</purchaser>

<supplier>

<name> Acme Supplies </name>

<address> 1 Broadway, New York, NY, USA </address>

</supplier>

<itemlist>

<item>

<identifier> RS1 </identifier>

<description> Atom powered rocket sled </description>

<quantity> 2 </quantity>

<price> 199.95 </price>

</item>

<item>

...

</item>

</itemlist>

<total cost>

429.85

</total cost>

</purchase order>

2013

A precursor to JSON!

Wikipedia [XML, JSON]

#707070

XML: eXtensible Markup Language

XML is an older semi-structured data format (from the late 90s).

• Flexible support for complex data types.
• HTML is another such markup language: Hyper Text Markup Language

A lot of effort went into developing XML formalism and query languages

• Schema specification:
• Simple: DTD (document type definition)
• More powerful: XML Schema
• Query languages
• Simple: XPath: a “path” based query language
• (because XML is also tree-structured) Path from root to specific node with certain characteristics
• More powerful: XQuery

49

<purchase order>

<identifier> P-101 </identifier>

<purchaser>

<name> Wile E. Coyote </name>

<address> Route 66, Mesa Flats, Arizona 86047, USA</address>

</purchaser>

<supplier>

<name> Acme Supplies </name>

<address> 1 Broadway, New York, NY, USA </address>

</supplier>

<itemlist>

<item>

<identifier> RS1 </identifier>

<description> Atom powered rocket sled </description>

<quantity> 2 </quantity>

<price> 199.95 </price>

</item>

<item>

...

</item>

</itemlist>

<total cost>

429.85

</total cost>

</purchase order>

#707070

Document Stores

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

50

[for next time]

Lecture 17, Data 101 Fall 2023

Why not Semi-structured Data?

While semi-structured data models existed prior to structured data, it is clear that relational databases “won” in the long term.

51

Several reasons for why nested relations fell out of DBMS vogue:

• Complex and cumbersome to traverse nested relations to find specific bits of data
• (e.g., traversing a film hierarchy just to find information about actors)
• Nested model mixes physical and logical data organization.
• In the relational model, we can rearrange the data on disk and the relation would still be equivalent (e.g., CLUSTER).
• For nested models, however, we can’t; therefore we can’t optimize it for queries.
• Lots of redundancy, leading to update and deletion anomalies.

See:

• Bailis, Hellerstein, Stonebraker. Red Book / Readings in Database Systems. [link]
• Hellerstein and Stonebraker. What goes around comes around.

However, many data transfer lake/lakehouse applications means that we will have to work with semi-structured data somehow!

#707070

Document Stores are JSON-Native Data Systems

Document Stores are data systems that primarily operate on JSON.

• A document: Each JSON element. Basic unit of retrieval in document stores.

52

MongoDB (more next time):

• A popular example of a document store
• More next time (and in Project 4!)

Document stores support a set of operations:

• Searching across documents (essentially, selections / filters)
• Primitive aggregation
• However, typically no joins (beyond what is already done via denormalization)
• Possibly primitive indexing, e.g., to retrieve documents based on certain criteria.

#707070

When Should We Use Document Stores?

It makes sense to use document stores if our data is inherently denormalized, and

• We only want to operate on the denormalized data as a whole.
• I.e., we rarely want to look at pieces of the data
• Example: If data is organized by film→Actors, and we never want to look at Actors.
• We don’t need the full power of SQL.
• e.g., no joins needed
• The schema often changes, and yet we rarely update old data.
• i.e., having redundancy doesn’t create issues.

53

#707070

When Should We Use Document Stores?

Compelling example: All Facebook User Profiles in a single JSON document.

• Keep all “user” information together.
• Of course, drawbacks: Find all friends of a given user who are based in Berkeley needs joins.
• Promising alternative: Use JSON or XML within relational databases! (more later)

It makes sense to use document stores if our data is inherently denormalized, and

• We only want to operate on the denormalized data as a whole.
• I.e., we rarely want to look at pieces of the data
• Example: If data is organized by film→Actors, and we never want to look at Actors.
• We don’t need the full power of SQL
• e.g., no joins needed.
• The schema often changes, and yet we rarely update old data.
• i.e., having redundancy doesn’t create issues.

54

Compelling example 2: Transfer/share/data across media

• e.g., across network; across different data systems; on the internet; “export to JSON”
• High emphasis on flexibility!
• Self-describing nature highly valuable for portability!

#707070

NoSQL and Scaling

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

55

[for next time]

Lecture 17, Data 101 Fall 2023

NoSQL: Motivation

NoSQL is a hip name for document stores.

• Literally, “No SQL used” in database design.
• Ability to store semi-structured AND unstructured data.
• Reduced functionality with simpler data model
• Restricted queries/updates, but optimized for querying and scaling.

​

56

NoSQL as a phrase emerged in late 2000s (but again, it’s existed since the 1960s with XML systems).

• Modern applications: Requirements for data may change constantly!
• Developers need flexibility!
• Startups and growing customer bases: Scale database workloads significantly.
• Motivated by Web 2.0 applications including Facebook, Amazon, etc.

#707070

NoSQL: Scalability

• Without the rectangular / structured data constraints, NoSQL databases can easily be distributed across different data stores
• Horizontally scalable! (e.g. can easily scale to millions of users)

​

• With NoSQL, we don’t perform joins or ensure consistency
• Only have to guarantee eventual consistency
• Data will be “eventually” consistent
• Used to guarantee that the system would be highly available

57

#707070

NoSQL systems are scalable

Without the rectangular / structured data constraints:

• NoSQL databases can easily be distributed across different data stores.
• Horizontally scalable! (e.g. can easily scale to millions of users)

58

With NoSQL, we don’t perform joins or ensure strong consistency.

• Consistency: Guarantee that any transactions started in the future necessarily see the effects of other transactions committed in the past.
• In other words, the database always reflects the most current changes.

Instead, with NoSQL we only have to guarantee eventual consistency.

• In other words, transactions will eventually be consistent across the database.
• Used to guarantee that the system would be highly available.
• Two approaches to scaling, both of which are used (sometimes in combination)�partitioning and replication.

#707070

Two approaches to scaling: Partitioning and Replication

Replication

• Create multiple copies of each database partition.
• Spread queries across these replicas.
• Can increase throughput and lower latency.�
• Pros/Cons:
• Can also improve fault-tolerance
• Easy for reads
• Writes become expensive!

Partitioning (aka Sharding)

• Partition the database across many machines in a cluster
• Each database partition now fits in main memory.
• Queries spread across these machines.
• Pros/Cons:
• Can increase throughput!
• Easy for writes!
• However, reads become expensive!

59

#707070

Scalability is HARD in Relational Models!

Relational models are difficult to replicate/partition.

• Partition: we may be forced to join across servers, sometimes there is no easy way to partition a single table
• Replication: local copy has inconsistent versions

60

Relational databases are required to maintain consistency!

• Consistency is hard in both cases!
• Scalability in relational databases is a very challenging problem which makes for a complex database architecture
• How do we do better? See guest lecture…

#707070

SQL or NoSQL?

1. The goal is to build a service for tens of millions of Amazon shoppers, which will store each shopper’s past 100 viewed products. The stored data is shopper specific, and should be used for targeted product advertisements towards that shopper. It’s fine if this data is a little out-of-date. What kind of database should be used?

• Hint: This database should be able to look up the cached result by the SQL query (string).
• Hint 2: The stored data is non-relational.

​

​

2. The goal is to build a service at PayPal that can allow users to apply for loans through the app. The service needs a database to store loan applications. In addition to the loan amount, the application also needs information regarding the user’s current balance and prior transaction history. What kind of database should be used?

• Hint: This is a financial application where data consistency is very important.
• Hint 2: Data about the loan, user’s balance and transaction history all need to be stored, and there’s relationships between these data.

​

​

​

​

61

🤔

A. SQL

B. NoSQL

#707070

SQL or NoSQL?

ⓘ

Click Present with Slido or install our Chrome extension to activate this poll while presenting.

SQL vs NoSQL?

1. The goal is to build a service for tens of millions of Amazon shoppers, which will store each shopper’s past 100 viewed products. The stored data is shopper specific, and should be used for targeted product advertisements towards that shopper. It’s fine if this data is a little out-of-date. What kind of database should be used?

• Hint: This database should be able to look up the cached result by the SQL query (string).
• Hint 2: The stored data is non-relational.

​

​

2. The goal is to build a service at PayPal that can allow users to apply for loans through the app. The service needs a database to store loan applications. In addition to the loan amount, the application also needs information regarding the user’s current balance and prior transaction history. What kind of database should be used?

• Hint: This is a financial application where data consistency is very important.
• Hint 2: Data about the loan, user’s balance and transaction history all need to be stored, and there’s relationships between these data.

​

​

​

​

63

A. SQL

B. NoSQL

#707070

[Extra] Key-Value Stores

Translate into a Relational Schema

Normalization

Functional Dependencies

Semi-Structured Data

JSON

Transforming b/t Rectangular Data & JSON

XML

Why Semi-Structured Data?

NoSQL

[Extra] Key-Value Stores

64

[extra material]

Lecture 17, Data 101 Fall 2023

Data Models for Semi-structured Data

• Key Value Stores
• e.g. Amazon DynamoDB, Voldemort, Memcached
• Document Stores
• Popular Formats: JSON, XML
• e.g. MongoDB, CouchDB, SimpleDB

65

#707070

Key-Value Stores

• Data model: (key,value) pairs
• Key = string/integer, unique for the entire data
• Value = can be anything (very complex object)
• Operations
• get(key), put(key,value)
• Operations on value not supported

66

#707070

Key-Value Stores Scaling

• Partitioning:
• Use a hash function h
• Store every (key,value) pair on server h(key)
• Replication:
• Store each key on (say) three servers, e.g., key k stored at h1(k),h2(k),h3(k)
• On update, propagate change to the other servers; eventual consistency
• Issue: when an app reads one replica, it may be stale
• Usually: combine partitioning+replication
• Result: fast reads and writes, no need to access multiple servers

67

#707070

Example

How would you represent the Flights data as key, value pairs?

​

• Option 1: key=fid, value=entire flight record
• Option 2: key=date, value=all flights that day
• Option 3: key=(origin,dest), value=all flights between

​

• Depends on common query access patterns! (different design principle from relational databases)
• Indexes are generally supported

68

Flights(fid, date, carrier_id, flight_num, origin, dest, ...) Carriers(cid, name)

#707070