CSE 344: Section 5

Database Design Theory

February 1st, 2024

Announcements

• Homework 3 due tomorrow 2/2 @ 11pm
• Late due date 2/4 @ 11pm
• Homework 4 release soon

Database Design

3

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?

​

• Domain approach
• 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

12

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)

�

​

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

Worksheet