CSE 344: Section 4

ER diagrams, FDs

Apr 21st, 2025

​

Announcements

• Homework 3
• Late deadline tonight at 10pm!
• Quiz 1
• Deadline tonight at 10pm, NO LATE SUBMISSIONS
• Homework 4
• Due at 10:00 pm on Tuesday, April 29
• Focus on ER diagrams, FDs, and BCNF decomposition
• Questions?

​

Database Design

E/R diagram Basics

is a

Subclass

Attribute

Entity set

Relationship

Weak Entity

Subclass

CREATE TABLE Product (

pname VARCHAR(30) PRIMARY KEY,

price INT)

​

CREATE TABLE Toy (

pname VARCHAR(30) PRIMARY KEY REFERENCES Product,

age INT)

​

CREATE TABLE Candy (

pname VARCHAR(30) PRIMARY KEY REFERENCES Product,

isChoc VARCHAR(5))

Relationships

• One-to-one
• Many-to-one
• Many-to-many

Integrity Constraints in ER Diagrams

makes

makes

makes

Single Value Constraints (many-one) [at most one]

Referential Integrity Constraints (many-one) [exactly one]

Other Constraints

>2

Examples of Relationships

• one-one: ssn - UW student id
• one-many: ssn - phone#
• many-many: students - courses
• is-a: PC - computer and Mac - computer

​

Question: "at most one" vs. "exactly one"?

Keys and FKs

• Key should be underlined
• For composite keys, all attributes should be underlined

​

• Foreign keys implied by relationship
• Don’t need to explicitly include them as attributes

​

Product

price

name

category

owns

Company

name

E/R to SQL

• Use NOT NULL to enforce >0
• Also use for required attributes
• Only many-to-many relationships should have extra tables
• Ask yourself: for a many-to-X relationship, is it reasonable to add X extra FKs in an existing table?
• For many-to-many, X is potentially infinite!

​

CREATE TABLE 3PlayerGame (

gid VARCHAR(30) PRIMARY KEY,

player1 VARCHAR(30) NOT NULL REFERENCES Players,

player2 VARCHAR(30) NOT NULL REFERENCES Players,

player3 VARCHAR(30) NOT NULL REFERENCES Players,

)

​

CREATE TABLE Players (

pid VARCHAR(30) PRIMARY KEY,

name VARCHAR(30)

)

Weak Entity Set

Worksheet Exercise 1:

Entity Relationship Diagrams

Worksheet 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 (required), 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

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 (required), 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 (required), 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 (required), 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 2

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) NOT NULL 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.

Functional Dependencies

Functional Dependency

A → B

Indicates that attribute A determines attribute B (B is dependent on A).

• Can also say "A yields B"

​

Some examples:

• student_id → graduation_year
• origin_city → origin_state, (population)
• flight_id → carrier_id, origin_city, dest_city, price, …

Transitive Dependency

If A → B and B → C

then A → C

​

{A}+ = Closure of attribute A: Set of all attributes that can be determined by A.

{A}+ = {ABC}

Example

Student(studentID, name, dateOfBirth, phoneNumber)

​

​

​

​

Example

Do the following FDs hold for�this relation?

​

{studentID} → {name}

​

{studentID} → {name, dateOfBirth}

​

{studentID} → {phoneNumber}

​

​

​

Example

Do the following FDs hold for�this relation?

​

{studentID} → {name}

​

{studentID} → {name, dateOfBirth}

​

{studentID} → {phoneNumber}

​

​

​

Example

Do the following FDs hold for�this relation?

​

{studentID} → {name}

​

{studentID} → {name, dateOfBirth}

​

{studentID} → {phoneNumber}

​

​

​

Example

Do the following FDs hold for�this relation?

​

{studentID} → {name}

​

{studentID} → {name, dateOfBirth}

​

{studentID} → {phoneNumber}

​

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

​

​

​

Closure

Closure Definition

Goal:

• “If we are given the attribute/set of attributes {A1, …, Am}, what attributes will we know from using those attributes and their functional dependencies.”

Closure

Closure Algorithm

Algorithm Steps:

1. Find some attribute(s) C to add to right side

2. Add them

3. Look back at the FDs to find more C

​

Closure Example

• Suppose we have the functional dependencies ID → Name and Name → Job, what is the closure of ID?

​

• Step 1:

To determine the closure of ID we start with trivial FD: ID → ID because if we are given ID, then we know ID

• So we add ID to X = {ID}

Closure Example

• Suppose we have the functional dependencies ID → Name and Name → Job, what is the closure of ID?

​

• Step 2: (X from Step 1: X = {ID})
• ID → Name
• Since we already know ID (X currently contains ID), we can use this functional dependency to get Name
• So we add Name to X = {ID, Name}

Closure Example

• Suppose we have the functional dependencies ID → Name and Name → Job, what is the closure of ID?

​

• Step 3: (X from Step 2: X = {ID, Name})
• Name → Job
• Since we already know Name (X currently contains Name), we can use this functional dependency to get Job
• So we add Job to X = {ID, Name, Job}

​

Closure Example

• Suppose we have the functional dependencies ID → Name and Name → Job, what is the closure of ID?

​

• Step 4: (X from Step 3: X = {ID, Name, Job})
• Since we have run out of functional dependencies, X will no longer change so the algorithm is done!

​

​

Formally, the closure of ID is written as {ID}⁺ = {ID, Name, Job}

​

Closures (quicker)

Goal:

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

Observation:

• If we have ID → Name and Name → C, then ID → Job
• So really, ID → Name, Job
• Add ID to the RHS so ID → ID, Name, Job
• Formally, the closure of ID is written as {ID}⁺ = {ID, Name, Job}

​

Keys

We call the attribute(s) that determines all other attributes in a schema to be a superkey.

Ex. for R(A, B, C), the set {A, B, C} determines all attributes in R

If no subset of a superkey is also a superkey, then that superkey is a minimal key or key for short. If a relation has multiple keys, each key is a candidate key

Ex. if AB → ABC and C → ABC, then {AB} and {C} are candidate keys for R

Superkey

​

​

​

​

​

Minimal Key

Worksheet