CSE 344: Section 4

ER diagrams, BCNF decomposition

Oct 19th, 2023

​

Announcements

• Homework 4:
• Due at 10:00 pm on Tuesday, October 24th
• Focus on ER diagrams and BCNF

​

Database Design

E/R diagram Basics

is a

Subclass

Attribute

Entity set

Relationship

Weak Entity

Subclass

CREATE TABLE Product (

pname INT PRIMARY KEY,

price INT)

​

CREATE TABLE Toy (

pname INT PRIMARY KEY REFERENCES Product,

age INT)

​

CREATE TABLE Candy (

pname INT PRIMARY KEY REFERENCES Product,

isChoc TEXT)

Weak Entity Set

Relationships

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

Integrity Constraints in ER Diagrams

Product

price

name

category

makes

makes

makes

Keys

Single Value Constraints (many-one) [possibly none]

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: store - product
• is-a: PC - computer and Mac - computer
• has-a: city - country
• What country does the city of Cambridge belong to?

​

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

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, 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, 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.

Functional Dependencies

Functional Dependency

A → B

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

​

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}

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

Super Key

​

​

​

​

​

Minimal Key

Boyce-Codd Normal Form (BCNF)

Motivation of BCNF

Recall the three anomalies:

• Redundancy anomaly
• Update anomaly
• Deletion anomaly

​

If a relation is in BCNF, then it does not have these anomalies

​

If it is not in BCNF, then it does have these anomalies

​

BCNF Algorithm

​

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

• Example: We know that popularity determines rec (ex: Okay = N, Respectable = N, Poppin = Y)
• What if we want to update the rec so that a popularity = ‘Respectable’ has rec= ‘Y’
• UPDATE Restaurant

SET rec? = ‘Y’

WHERE popularity = ‘Respectable’;

​

1. How many tuples in the Restaurant table do we need to update? How can we reduce this number?

​

Restaurant

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

• id -> name, rating
• rating -> popularity
• popularity -> rec?

rating⁺ = rating, popularity, rec?

Restaurant

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

R₂

R₁

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

popularity⁺ = popularity, rec?

R₂

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

popularity⁺ = popularity, rec?

R₂

R₄(popularity,rating)

R₃(popularity,rec?)

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

popularity⁺ = popularity, rec?

R₂

R₄(popularity,rating)

R₃(popularity,rec?)

R₃

R₄

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

• id -> name, rating
• rating -> popularity
• popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

popularity⁺ = popularity, rec?

R₂

R₄(popularity,rating)

R₃(popularity,rec?)

R₃

R₄

R2, R3, R4 is the normalized database schema. No more anomalies!

Example: BCNF Decomposition

Now when we update the rec? so that a popularity = ‘Respectable’ has rec?= ‘Y’

UPDATE R3 SET rec? = ‘Y’ WHERE popularity = ‘Respectable’;

​

• Now we only update 1 tuple in the R3 table so we have reduced redundancy, and therefore avoid redundancy anomalies, update anomalies and deletion anomalies

R₂

R₃

R₄

Worksheet

Nested Queries Review!

Nested Queries

• Avoid when possible
• Danger of making simple queries slow and complicated
• Just because you can do it, doesn’t mean you should

44

Subquery in SELECT

45

SELECT DISTINCT C.cname, (SELECT COUNT(*)

FROM Product P

WHERE P.cid = C.cid)

FROM Company C;

​

Subquery in SELECT

Unnest using JOIN and GROUP BY

​

46

SELECT C.cname, count(P.cid)

FROM Company C LEFT OUTER JOIN

Product P ON C.cid = P.cid

GROUP BY C.cname;

​

Nested Queries

• If the SQL subquery returns exactly one value it can be used where we use a field
• “one value” = one tuple with one attribute
• Otherwise, a SQL subquery can be thought of as an "extra table"
• Can name the table, its columns, etc

47

Subquery in FROM

48

SELECT X.pname

FROM (SELECT *

FROM Product

WHERE price > 20) AS X

WHERE X.price < 500;

​

More readable: WITH <name> AS (<subquery>)

Subquery in FROM

49

WITH price_more_20 AS (

SELECT *

FROM Product

WHERE price > 20

)

SELECT X.pname

FROM price_more_20 AS X

WHERE X.price < 500;

Subquery in FROM

Unnest using WHERE

​

50

SELECT X.pname

FROM Product AS X

WHERE X.price < 500 AND X.price > 20;

Subquery in WHERE

51

SELECT DISTINCT C.cname

FROM Company C

WHERE EXISTS (SELECT *

FROM Product P

WHERE C.cid = P.cid AND P.price < 200);

Subquery in WHERE

52

SELECT DISTINCT C.cname

FROM Company C, Product P

WHERE C.cid = P.cid AND P.price < 200;

Subquery in WHERE Syntax

• SELECT ……… WHERE EXISTS (<sub>);
• SELECT ……… WHERE NOT EXISTS (<sub>);
• SELECT ……… WHERE attribute IN (<sub>);
• SELECT ……… WHERE attribute NOT IN (<sub>);
• SELECT ……… WHERE attribute > ANY (<sub>);
• SELECT ……… WHERE attribute > ALL (<sub>);

53

Witnessing (i.e. argmax)

Find the student(s) who is taking the most classes.

Student(stu_id, id_num)

Enrolled(id_num, class)

​

SELECT S.stu_id

FROM Student S, Enrolled E

WHERE S.id_num = E.id_num

GROUP BY S.stu_id

HAVING count(E.class) >= ALL(

SELECT count(E1.class)

FROM Enrolled E1

GROUP BY E1.id_num);

54

Witnessing (i.e. argmax) (another way)

55

WITH class_counts AS (SELECT COUNT(E1.class) AS cnt

FROM Enrolled E1

GROUP BY E1.id_num),

max_counts AS (SELECT MAX(cnt) AS max FROM class_counts)

SELECT S.stu_id

FROM Students S, Enrolled E, max_counts Emax

WHERE S.id_num = E.id_num

GROUP BY S.stu_id, Emax.max

HAVING COUNT(E.class) = Emax.max;

To Nest or Not to Nest

• Not an exact science
• Figuring out what is actually wanted will help you find simpler solutions (best way is to practice)
• Trigger words to use sub-querying
• Every, All (universal quantifiers)
• No, None, Never (negation)
• Only

56