CSE 344: Section 5

Database Design Theory

Database Design

2

Arbitrary Data

Database

There are no good or bad designs, just tradeoffs.

Data Relationship Discovery

How do we find relationships between attributes?

​

Flights dataset:

Did you know that every canceled flight has an actual_time of 0?

​

1. Domain approach
2. Data mining approach

Data Relationship Discovery

Domain approach:

Before looking at the data, think about the domain

​

Research the domain and realize that �canceled flights have a 0 flight time!

​

Data Relationship Discovery

Data mining approach:

Don’t worry about the domain, find patterns in the data

​

Look at the data and notice that every time canceled = 1, then actual_time = 0.

SELECT DISTINCT actual_time

FROM Flights

WHERE canceled = 1;

Data Relationship Discovery

How do we find relationships between attributes?

​

Domain Approach

E/R Diagrams

Data Approach

Functional Dependencies (FDs)

Boyce-Codd Normal Form (BCNF)

Domain Approach

ER Diagrams

Visual graph of entities and relationships

Relationships

• one-one: ssn - UW student id
• one-many: ssn - phone #
• many-many: store - product
• is-a: computer - PC and computer - Mac
• has-a: country - city
• What country does the city of Cambridge belong to?

“at most one”

“exactly one”

​

​

is a

“subclass”

no constraint

other constraint

​

E/R Example

Create an ER diagram containing the following:

• The id, name, gender, country of birth, �and country region (continent) of birth for students and faculty
• The major of students
• The salary of faculty
• The courses that each student takes
• The department each course is offered in

​

E/R Example – Sample Solution

11

Country (name, region)

People (id, name, gender, Country.name)

Faculty (People.id, salary)

Student (People.id, major)

Course (courseID, dept)

Took (Student.People.id, Course.courseID)

�

​

Exercise 1: Entity Relationship Diagrams

Odegaard Library is in need of a new database, and they have asked you to help design it! Here are some of the requirements for what information needs to be stored in this database:

​

• Each book has a unique ID, a title, an author, a genre, and a number of pages
• Readers who visit the library have a unique email address, a first name, a last name, and an age
• Readers can “check out” multiple books from the library at a time, and one book can be checked out multiple times. We should keep track of the day that each book was checked out
• To make it easier to recommend books to readers, we should assign a recommended age for each genre
• Assume only one book fits in one genre

1. Design an ER diagram for this new library database.

Worksheet Exercise 1: Entity Relationship Diagrams

• Each book has a unique ID, a title, an author, a genre, and a number of pages

book

num_of_pages

id

title

author

Worksheet Exercise 1: Entity Relationship Diagrams

book

num_of_pages

id

title

author

• Each book has a unique ID, a title, an author, a genre, and a number of pages
• To make it easier to recommend books to readers, we should assign a recommended age for each genre

Worksheet Exercise 1: Entity Relationship Diagrams

book

num_of_pages

id

title

author

has_genre

genre

name

recommended_age

• Each book has a unique ID, a title, an author, a genre, and a number of pages
• To make it easier to recommend books to readers, we should assign a recommended age for each genre

Worksheet Exercise 1: Entity Relationship Diagrams

reader

email

first_name

last_name

age

• Readers who visit the library have a unique email address, a first name, a last name, and an age
• Readers can “check out” multiple books from the library at a time, and one book can be checked out multiple times. We should keep track of the day that each book was checked out

Worksheet Exercise 1: Entity Relationship Diagrams

• Readers who visit the library have a unique email address, a first name, a last name, and an age
• Readers can “check out” multiple books from the library at a time, and one book can be checked out multiple times. We should keep track of the day that each book was checked out

reader

email

first_name

last_name

age

book

num_of_pages

id

title

author

has_genre

genre

name

recommended_age

check_out

day_check_out

Worksheet Exercise 1: Entity Relationship Diagrams

2) Convert the ER diagram to a series of CREATE TABLE statements. Include primary key and foreign key statements.

reader

email

first_name

last_name

age

book

num_of_pages

id

title

author

has_genre

genre

name

recommended_age

check_out

day_check_out

Worksheet Exercise 1: Entity Relationship Diagrams

CREATE TABLE Checkouts (

day_check_out VARCHAR(10),

book_id INT REFERENCES Books,

reader_email VARCHAR(50) REFERENCES Readers,

PRIMARY KEY (book_id, reader_email, day_check_out)

);

CREATE TABLE Readers (

email VARCHAR(50) PRIMARY KEY,

first_name VARCHAR(20),

last_name VARCHAR(20),

age INT

);

CREATE TABLE Books (

id INT PRIMARY KEY,

title VARCHAR(100),

author VARCHAR(50),

genre VARCHAR(20) REFERENCES Genres,

num_pages INT

);

CREATE TABLE Genres (

name VARCHAR(20) PRIMARY KEY,

recommended_age INT

);

2) Convert the ER diagram to a series of CREATE TABLE statements. Include primary key and foreign key statements.

Data Approach

Functional Dependencies

A functional dependency (FD) for relation R is a formula of the form A → B

where A and B are sets or individual attributes of R.

​

We say the FD holds for R if, for any instance of R, whenever two tuples agree in value for all attributes of A, they also agree in value for all attributes of B.

​

DEPENDENCY != CAUSATION

*in other words: A determines B, or A is kinda sorta a key for B

Example

Student(studentID, name, dateOfBirth, phoneNumber)

​

​

​

​

Example

Do the following FDs hold?

​

{studentID} → {name}

​

{studentID} → {name, dateOfBirth}

​

{studentID} → {phoneNumber}

​

​

​

Example

Do the following FDs hold?

​

{studentID} → {name}

​

{studentID} → {name, dateOfBirth}

​

{studentID} → {phoneNumber}

​

​

​

Example

Do the following FDs hold?

​

{studentID} → {name}

​

{studentID} → {name, dateOfBirth}

​

{studentID} → {phoneNumber}

​

​

​

Example

Do the following FDs hold?

​

{studentID} → {name}

​

{studentID} → {name, dateOfBirth}

​

{studentID} → {phoneNumber}

​

There are two tuples that agree on studentID but don’t agree on phoneNumber!

​

​

​

Trivial FDs

Axiom of Reflexivity

​

A trivial FD is one where the RHS is a subset of the LHS

That is, every attribute on the RHS is also on the LHS

​

The two FDs below are trivial:

{name} → {name}

{studentID,name} → {name}

​

​

​

​

Inference Rules

• If b is a subset of a, then a → b (reflexivity or trivial FD)
• then a → a (if a and b are subsets of each other, aka a = b!)
• If a → b then a, c → b, c (augmentation)
• then a, c → b
• but not a → b, c
• “Adding on the left is chill. Adding on the right though 🚩🚩🚩🚩🚩🚩”
• If a → b & b → c then a → c (transitivity)
• If a → bc and c → d then a → bd (pseudo transitivity) or even a -> bcd

​

​

​

Closure

Goal:

• We want everything that an attribute/set of attributes determines

Observation:

• Suppose we have the attributes A → B and B → C
• To determine the closure of A we start with trivial FD: A → A and X = {A}
• Since we have A → B, we add B to X = {A, B}
• B is in X and B → C, so we can add C to X = {A, B, C}
• Formally, the closure of A is written as {A}⁺ = {A, B, C}

​

Closures (quicker)

Goal:

• We want everything that an attribute/set of attributes determines

Observation:

• Suppose we have the attributes A → B and B → C
• By transitivity, A → C
• So really, A → B, C
• Add A to the RHS so A → A, B, C
• Formally, the closure of A is written as {A}⁺ = {A, B, C}

​

Example

​

​

​

​

​

​

​

Given studentID → name, dateOfBirth:

{studentID}⁺ = {studentID, name, dateOfBirth}

Keys

We call an attribute (or a set of attributes) that determines all other attributes in a schema to be a superkey.

If it is the smallest set of attributes (in terms of cardinality) that does this we call that set a minimal key or just key

By definition, all minimal keys are superkeys, but a superkey is not necessarily a minimal key.

Superkeys and Minimal Keys

R(A, B, C, D)

A -> B

B -> C, D

​

Question: is {A, B} a superkey, minimal key, neither, or both?

​

Question: is {B} a superkey, minimal key, neither, or both?

​

Question: is {A} a superkey, minimal key, neither or both?

superkey

neither

both

A superkey determines all other attributes in a schema

A minimal key is the smallest set of attributes that determines all other attributes in a schema

By definition, all minimal keys are superkeys, but a superkey is not necessarily a minimal key.

Superkeys and Minimal Keys

R(A, B, C, D)

A -> B

C -> D

​

Question: is {A, C} a superkey, minimal key, or both?

​

Question: is {A, B, C, D} a superkey, minimal key, or both?

​

Question: is {A, C, D} a superkey, minimal key, or both?

both

superkey

superkey

A superkey determines all other attributes in a schema

A minimal key is the smallest set of attributes that determines all other attributes in a schema

By definition, all minimal keys are superkeys, but a superkey is not necessarily a minimal key.

Boyce-Codd Normal Form (BCNF)

A relation R is in BCNF if every set of attributes in R is either a superkey or its closure is the same set (trivial FD).

*that is, either {a}+ -> a OR {a}+ -> {all cols}, where a is any col in the table

• BCNF reduces redundancy at the expense of creating additional tables.
• BCNF may have several correct decompositions.
• Some functional dependencies may be lost.

​

​

Boyce-Codd Normal Form (BCNF)

Not BCNF! SSN is not a trivial FD or a superkey

BCNF Decomposition

Algorithm

C = the set of all attributes in the relation R

​

Look for an attribute (or a set of attributes) that meets the following conditions (non-BCNF flag!):

• X⁺ != X
• X⁺ != C

​

If such attribute exists, it is a violation of the BCNF condition; decompose R:

• R1 = X⁺
• R2 = (C - X⁺) union (X)
• Normalize each table (recursive call)

​

Else, the table is in BCNF

BCNF

Example

Relation: R (A, B, C, D, E)

FDs:

• A → E
• BC → A
• DE → B

​

Goal: Decompose R into BCNF

BCNF

Example

R (A, B, C, D, E)

​

A⁺ = {A, E}

​

BCNF compliant

​

​

​

BCNF compliant

​

​

​

BCNF compliant

​

​

​

{B, C}⁺ = {B, C, A}

BCNF

Example

Notice that {A}⁺ = {A,E}, which violates the BCNF condition

• We split R to R1(A,E) and R2(A,B,C,D)
• R1 satisfies BCNF
• R2 does not satisfy BCNF because: {B,C}⁺ = {B,C,A}

​

{B,C}⁺ = {B,C,A} violates the BCNF condition

• *Notice there is no E in R2 so we don't need to consider DE → B
• Split R2 to: R21(B,C,A) and R22(B,C,D)
• R21 and R21 satisfy BCNF now

BCNF Final Tips

• Split on closures, not FDs
• Depending on the order in which you split on closures, you may end up with different tables - there are multiple possible solutions!
• The PKs for your tables will depend on the FDs still preserved

Worksheet