Lecture:�Design Theory – Part 1

Example Enrollment table - “v0”

~375

cs145

students

~300

cs245

students

Problems

Repeats?

Room/time change?

Deletes?

Properties

Class -> Room/time

Room -> Lat, Lng

​

(more compact)

Example Enrollment table - “v1”

375

cs145

students

300

cs245

students

Design Theory

• Design theory: how to represent your data to avoid anomalies.
• Note: different than concurrency anomalies.

​

• Simple algorithms for “best practices”

​

​

​

​

​

​

Data Anomalies & Constraints

Constraints Prevent (some) �Anomalies in the Data

If every course is in only one room, contains redundant information!

A poorly designed database causes anomalies:

Constraints Prevent (some) �Anomalies in the Data

If we update the room number for one tuple, we get inconsistent data = an update anomaly

A poorly designed DB can have anomalies:

Constraints Prevent (some) �Anomalies in the Data

If everyone drops the class, we lose what room the class is in! = a delete anomaly

A poorly designed database causes anomalies:

Constraints Prevent (some) �Anomalies in the Data

Similarly, we can’t reserve a room without students = an insert anomaly

A poorly designed database causes anomalies:

Constraints Prevent (some) �Anomalies in the Data

What are “good” decompositions?

Is this form better?

​

• Redundancy?
• Update anomaly?
• Delete anomaly?
• Insert anomaly?

Functional Dependencies

A Picture Of FDs

Definition:

Given attribute sets A={A₁,…,A_m} and B = {B₁,…B_n} in R,

​

The functional dependency A→ B on R holds if for any t_i,t_j in R:

​

if t_i[A₁] = t_j[A₁] AND t_i[A₂]=t_j[A₂] AND … AND t_i[A_m] = t_j[A_m]

​

then t_i[B₁] = t_j[B₁] AND t_i[B₂]=t_j[B₂] AND … AND t_i[B_n] = t_j[B_n]

t_i

t_j

If ti,tj agree here..

…they also agree here!

A->B means that

“whenever two tuples agree on A then they agree on B.”

FDs for Relational Schema Design

High-level idea: why do we care about FDs?

​

• Start with some relational schema

​

• Find functional dependencies (FDs)

​

• Use these to design a better schema

One which minimizes the possibility of anomalies

​

​

Functional Dependencies as Constraints

Note: The FD {Course} -> {Room} holds on this table instance

However, cannot prove that the FD {Course} -> {Room} holds on all instances. That is, FDs are for an instance and not for schema

Functional Dependencies as Constraints

Note that:

• You can check if an FD is violated by examining a single instance;
• However, you cannot prove that an FD is part of the schema by examining a single instance.
• This would require checking every valid instance

More Examples

An FD is a constraint which holds, or does not hold on an instance:

More Examples

{Position} → {Phone}

More Examples

but not {Phone} → {Position}

Example

(mega)

Enrollment table - “v0”

~375

cs145

students

~300

cs245

students

Problems

Repeats?

Room/time change?

Deletes?

FDs

Class -> Room,Time

Room -> Lat, Lng

​

(more compact)

Table Decomposition

R₁ = the projection of R on A₁, ..., A_n, B₁, ..., B_m

R(A₁,...,A_n,B₁,...,B_m,C₁,...,C_p)

R₁(A₁,...,A_n,B₁,...,B_m)

R₂(A₁,...,A_n,C₁,...,C_p)

R₂ = the projection of R on A₁, ..., A_n, C₁, ..., C_p

Conceptual Design

For a “mega” table

​

• Search for “bad” dependencies

​

• If any, keep decomposing the table into sub-tables until no more bad dependencies

​

• When done, the database schema is normalized

Note: there are several “good” (normal) forms…

Finding Functional Dependencies

1. {Name} → {Color}

2. {Category} → {Department}

3. {Color, Category} → {Price}

Which / how many other FDs do?!?

Provided FDs:

Products

Given the provided FDs,

{Name, Category} → {Price} must also hold on any instance…

Example:

Inferring FDs

Given a set of FDs, F = {f₁,…f_n}, does an FD g hold?

(Similar idea to Logic inferencing. E.g, A implies B, B implies C, so A implies C)

​

Armstrong’s Rules.

1. Split/Combine
2. Reduction
3. Transitivity

1. Split/Combine

A₁, …, A_m → B₁,…,B_n

… is equivalent to the following n FDs…

A₁,…,A_m → B_i for i=1,…,n

1. Split/Combine

A₁, …, A_m → B₁,…,B_n

… is equivalent to …

And vice-versa, A₁,…,A_m → B_i for i=1,…,n

2. Reduction/Trivial

If B is subset of A (=A₁,…,A_m ) for any j=1,…,m

​

A → B

3. Transitive Closure

A₁, …, A_m → B₁,…,B_n and

B₁,…,B_n → C₁,…,C_k

3. Transitive Closure

A₁, …, A_m → B₁,…,B_n and

B₁,…,B_n → C₁,…,C_k

implies

A₁,…,A_m → C₁,…,C_k

Finding Functional Dependencies

1. {Name} → {Color}

2. {Category} → {Department}

3. {Color, Category} → {Price}

Which / how many other FDs hold?

Provided FDs:

Products

Example:

Finding Functional Dependencies

1. {Name} → {Color}

2. {Category} → {Dept.}

3. {Color, Category} → {Price}

What’s an algorithmic way to do this?

Provided FDs:

Example:

Trivial

Transitive (4 -> 1)

Trivial

Transitive (7 -> 3)

Split/Combine (5 + 6)