Understanding Design Theory: Lecture 6 Overview & Normal Forms

Lectures 6 Lectures 6 Lecture 6: Design Theory

Lecture 6 Lecture 6 Announcements Solutions to PS1 are posted online. Grades coming soon! Project part 1 is out. Check your groups and let us know if you have any issues. We have assigned people to groups that had only two members. Activities and Notebooks are there for your benefit!

Lecture 6 Lecture 6 Lecture 6: Design Theory I

Lecture 6 Lecture 6 Today s Lecture 1. Normal forms & functional dependencies ACTIVITY: Finding FDs 2. Finding functional dependencies 3. Closures, superkeys & keys ACTIVITY: The key or a key? 4

Lecture 6 > Section 1 Lecture 6 > Section 1 1. Normal forms & functional dependencies 5

Lecture 6 > Section 1 Lecture 6 > Section 1 What you will learn about in this section 1. Overview of design theory & normal forms 2. Data anomalies & constraints 3. Functional dependencies 4. ACTIVITY: Finding FDs 6

Lecture 6 > Section 1 > Overview Lecture 6 > Section 1 > Overview Design Theory Design theory is about how to represent your data to avoid anomalies. It is a mostly mechanical process Tools can carry out routine portions We have a notebook implementing all algorithms! We ll play with it in the activities!

Lecture 6 > Section 1 > Overview Lecture 6 > Section 1 > Overview Normal Forms 1st Normal Form (1NF) = All tables are flat 2nd Normal Form = disused DB designs based on functional dependencies, intended to prevent data anomalies Boyce-Codd Normal Form (BCNF) Our focus for this lecture + the next two ones 3rd Normal Form (3NF) 4th and 5th Normal Forms = see text books

Lecture 6 > Section 1 > Overview Lecture 6 > Section 1 > Overview 1st Normal Form (1NF) Student Mary Mary Joe Joe Courses CS564 CS368 CS564 CS552 Student Mary Joe Courses {CS564,CS368} {CS564,CS552} In 1st NF Violates 1NF. Violates 1NF. 1NF Constraint 1NF Constraint: : Types must be atomic!

Lecture 6 > Section 1 > Data anomalies & constraints Lecture 6 > Section 1 > Data anomalies & constraints Data Anomalies & Constraints

Lecture 6 > Section 1 > Data anomalies & constraints Lecture 6 > Section 1 > Data anomalies & constraints Constraints Prevent (some) Anomalies in the Data A poorly designed database causes anomalies anomalies: Student Mary Joe Sam .. Course CS564 CS564 CS564 .. Room B01 B01 B01 .. If every course is in only one room, contains redundant redundant information!

Lecture 6 > Section 1 > Data anomalies & constraints Lecture 6 > Section 1 > Data anomalies & constraints Constraints Prevent (some) Anomalies in the Data A poorly designed database causes anomalies anomalies: Student Mary Joe Sam .. Course CS564 CS564 CS564 .. Room B01 C12 B01 .. If we update the room number for one tuple, we get inconsistent data = an update update anomaly anomaly

Lecture 6 > Section 1 > Data anomalies & constraints Lecture 6 > Section 1 > Data anomalies & constraints Constraints Prevent (some) Anomalies in the Data A poorly designed database causes anomalies anomalies: Student .. Course .. Room .. If everyone drops the class, we lose what room the class is in! = a delete delete anomaly anomaly

Lecture 6 > Section 1 > Data anomalies & constraints Lecture 6 > Section 1 > Data anomalies & constraints Constraints Prevent (some) Anomalies in the Data A poorly designed database causes anomalies anomalies: Student Mary Joe Sam .. Course CS564 CS564 CS564 .. Room B01 B01 B01 .. Similarly, we can t reserve a room without students = an insert insert anomaly anomaly CS368 C12

Lecture 6 > Section 1 > Data anomalies & constraints Lecture 6 > Section 1 > Data anomalies & constraints Constraints Prevent (some) Anomalies in the Data Is this form better? Student Mary Joe Sam .. Course CS564 CS564 CS564 .. Course CS564 CS368 Room B01 C12 Redundancy? Update anomaly? Delete anomaly? Insert anomaly? Today: develop theory to understand why this design may be better and and how to find this decomposition

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies Functional Dependencies

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies Functional Dependency Def Def: : Let A,B be sets of attributes We write A B or say A functionally determines if, for any tuples t1 and t2: t1[A] = t2[A] implies t1[B] = t2[B] and we call A B a functional dependency functional dependency functionally determines B A->B means that whenever two tuples agree on A then they agree on B.

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies A Picture Of FDs Defn (again): Given attribute sets A={A B = {B B = {B1 1, , B Bn n} } in R, R, A={A1 1, ,A , ,Am m} } and A1 Am B1 Bn

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies A Picture Of FDs Defn (again): Given attribute sets A={A B = {B B = {B1 1, , B Bn n} } in R, R, A={A1 1, ,A , ,Am m} } and A1 Am B1 Bn The functional dependency functional dependency A A holds if for any any ti,tj in R: B on R B on R ti tj

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies A Picture Of FDs Defn (again): Given attribute sets A={A B = {B B = {B1 1, , B Bn n} } in R, R, A={A1 1, ,A , ,Am m} } and A1 Am B1 Bn The functional dependency functional dependency A A holds if for any any ti,tj in R: B on R B on R ti tj ti[A1] = tj[A1] AND ti[A2]=tj[A2] AND AND ti[Am] = tj[Am] If t1,t2 agree here..

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies A Picture Of FDs Defn (again): Given attribute sets A={A B = {B B = {B1 1, , B Bn n} } in R, R, A={A1 1, ,A , ,Am m} } and A1 Am B1 Bn The functional dependency functional dependency A A holds if for any any ti,tj in R: B on R B on R ti tj if if ti[A1] = tj[A1] AND ti[A2]=tj[A2] AND AND ti[Am] = tj[Am] then then ti[B1] = tj[B1] AND ti[B2]=tj[B2] AND AND ti[Bn] = tj[Bn] If t1,t2 agree here.. they also agree here!

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies FDs for Relational Schema Design High-level idea: why do we care about FDs? 1. Start with some relational schema 2. Model its functional dependencies (FDs) 3. Use these to design a better schema 1. One which minimizes the possibility of anomalies

Lecture 6 > Section 1 Lecture 6 > Section 1 Functional Dependencies as Constraints Student Mary Joe Sam .. Course CS564 CS564 CS564 .. Room B01 B01 B01 .. A functional dependency is a form of constraint Holds on some instances not others. Part of the schema, helps define a valid instance. Note: The FD {Course} -> {Room} holds on this holds on this instance instance Recall: an instance tuples conforming to that schema, i.e. a table instance of a schema is a multiset of i.e. a table

Lecture 6 > Section 1 Lecture 6 > Section 1 Functional Dependencies as Constraints Note that: You can check if an FD is violated by examining a single instance; Student Mary Joe Sam .. Course CS564 CS564 CS564 .. Room B01 B01 B01 .. However, you cannot prove that an FD is part of the schema by examining a single instance. This would require checking every valid instance However, cannot prove that the FD {Course} -> {Room} is part of the part of the schema schema

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies More Examples An FD is a constraint which holds, or does not hold on an instance: EmpID E0045 E3542 E1111 E9999 Name Smith Mike Smith Mary Phone 1234 9876 9876 1234 Position Clerk Salesrep Salesrep Lawyer 25

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies More Examples EmpID E0045 E3542 E1111 E9999 Name Smith Mike Smith Mary Phone 1234 9876 Salesrep 9876 Salesrep 1234 Position Clerk Lawyer {Position} {Phone} 26

Lecture 6 > Section 1 > Functional dependencies Lecture 6 > Section 1 > Functional dependencies More Examples EmpID E0045 E3542 E1111 E9999 Name Smith Mike Smith Mary Phone 1234 Clerk 9876 9876 1234 Lawyer Position Salesrep Salesrep but not {Phone} {Position} 27

Lecture 6 > Section 1 > ACTIVITY Lecture 6 > Section 1 > ACTIVITY ACTIVITY Find at least three FDs which are violated on this instance: A B C D E 1 3 1 1 3 2 2 4 2 2 4 5 4 4 5 3 1 5 3 1 6 8 7 6 8 { } { } { } { } { } { } 28

Lecture 6 > Section 2 Lecture 6 > Section 2 2. Finding functional dependencies 29

Lecture 6 > Section 2 Lecture 6 > Section 2 What you will learn about in this section 1. Good vs. Bad FDs: Intuition 2. Finding FDs 3. Closures 4. ACTIVITY: Compute the closures 30

Lecture 6 > Section 2 > Good vs. Bad FDs Lecture 6 > Section 2 > Good vs. Bad FDs Good vs. Bad FDs We can start to develop a notion of good vs. bad FDs: EmpID E0045 E3542 E1111 E9999 Name Smith Mike Smith Mary Phone 1234 9876 9876 1234 Position Clerk Salesrep Salesrep Lawyer Intuitively: EmpID -> Name, Phone, Position is good FD Minimal redundancy, Minimal redundancy, less possibility of less possibility of anomalies anomalies 31

Lecture 6 > Section 2 > Good vs. Bad FDs Lecture 6 > Section 2 > Good vs. Bad FDs Good vs. Bad FDs We can start to develop a notion of good vs. bad FDs: EmpID E0045 E3542 E1111 E9999 Name Smith Mike Smith Mary Phone 1234 9876 9876 1234 Position Clerk Salesrep Salesrep Lawyer Intuitively: EmpID -> Name, Phone, Position is good FD But Position -> Phone is a bad FD Redundancy! Redundancy! Possibility of data Possibility of data anomalies anomalies 32

Lecture 6 > Section 2 > Good vs. Bad FDs Lecture 6 > Section 2 > Good vs. Bad FDs Good vs. Bad FDs Returning to our original example can you see how the bad FD {Course} -> {Room} could lead to an: Update Anomaly Insert Anomaly Delete Anomaly Student Mary Joe Sam .. Course CS564 CS564 CS564 .. Room B01 B01 B01 .. Given a set of FDs (from user) our goal is to: 1. 1. Find all FDs, and Find all FDs, and 2. 2. Eliminate the Bad Ones". Eliminate the Bad Ones".

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs FDs for Relational Schema Design High-level idea: why do we care about FDs? 1. Start with some relational schema This part can be tricky! 2. Find out its functional dependencies (FDs) 3. Use these to design a better schema 1. One which minimizes possibility of anomalies

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs Finding Functional Dependencies There can be a very large numberof FDs How to find them all efficiently? We can t necessarily show that any FD will hold on all instances How to do this? We will start with this problem: Given a set of FDs, F, what other FDs must must hold?

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs Finding Functional Dependencies Equivalent to asking: Given a set of FDs, F = {f1, fn}, does an FD g hold? Inference problem: How do we decide?

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs Finding Functional Dependencies Example: Products Provided FDs: 1. {Name} {Color} 2. {Category} {Department} 3. {Color, Category} {Price} Name Gizmo Color Green Category Gadget Dep Price 49 Toys Widget Black Gadget Toys 59 Gizmo Green Whatsit Garden 99 Given the provided FDs, we can see that {Name, Category} {Price} must also hold on any instance Which / how many other FDs do?!?

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs Finding Functional Dependencies Equivalent to asking: Given a set of FDs, F = {f1, fn}, does an FD g hold? Inference problem: How do we decide? Answer: Three simple rules called Armstrong s Rules. Rules. 1. 1. Split/Combine, Split/Combine, 2. 2. Reduction, and Reduction, and 3. 3. Transitivity Transitivity ideas by picture Armstrong s

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs 1. Split/Combine A1 Am B1 Bn A1, , Am B1, ,Bn

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs 1. Split/Combine A1 Am B1 Bn A1, , Am B1, ,Bn is equivalent to the following nFDs A1, ,Am Bi for i=1, ,n

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs 1. Split/Combine A1 Am B1 Bn And vice-versa, A1, ,Am Bi for i=1, ,n is equivalent to A1, , Am B1, ,Bn

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs 2. Reduction/Trivial A1 Am A1, ,Am Ajfor any j=1, ,m

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs 3. Transitive Closure A1 Am B1 Bn C1 Ck A1, , Am B1, ,Bn and B1, ,Bn C1, ,Ck

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs 3. Transitive Closure A1 Am B1 Bn C1 Ck A1, , Am B1, ,Bn and B1, ,Bn C1, ,Ck implies A1, ,Am C1, ,Ck

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs Finding Functional Dependencies Example: Products Provided FDs: 1. {Name} {Color} 2. {Category} {Department} 3. {Color, Category} {Price} Name Gizmo Color Green Category Gadget Dep Price 49 Toys Widget Black Gadget Toys 59 Gizmo Green Whatsit Garden 99 Which / how many other FDs hold?

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs Finding Functional Dependencies Example: Inferred FDs: Provided FDs: 1. {Name} {Color} 2. {Category} {Dept.} 3. {Color, Category} {Price} Inferred FD Rule used 4. {Name, Category} -> {Name} 5. {Name, Category} -> {Color} ? ? 6. {Name, Category} -> {Category} ? 7. {Name, Category -> {Color, Category} ? 8. {Name, Category} -> {Price} ? Which / how many other FDs hold?

Lecture 6 > Section 2 > Finding FDs Lecture 6 > Section 2 > Finding FDs Finding Functional Dependencies Example: Inferred FDs: Provided FDs: 1. {Name} {Color} 2. {Category} {Dept.} 3. {Color, Category} {Price} Inferred FD Rule used 4. {Name, Category} -> {Name} 5. {Name, Category} -> {Color} Trivial Transitive (4 -> 1) 6. {Name, Category} -> {Category} Trivial 7. {Name, Category -> {Color, Category} Split/combine (5 + 6) 8. {Name, Category} -> {Price} Transitive (7 -> 3) Can we find an algorithmic way to do this?

Lecture 6 > Section Lecture 6 > Section 2 2 > Closures > Closures Closures

Lecture 6 > Section Lecture 6 > Section 2 2 > Closures > Closures Closure of a set of Attributes Given Given a set of attributes A A1 1, , A Then Then the closure closure, {A {A1 1, , A , , An n and a set of FDs F: F: , , An n} }+ + is the set of attributes B B s.t. {A A1 1, , , , A An n} } B B Example: F = {name} {color} {category} {department} {color, category} {price} {name}+ = {name, color} {name, category}+ = {name, category, color, dept, price} {color}+ = {color} Example Example Closures: Closures: 49

Lecture 6 > Section Lecture 6 > Section 2 2 > Closures > Closures Closure Algorithm Start with X = {A1, , An} and set of FDs F. Repeat until Repeat until X doesn t change; do do: if if {B1, , Bn} C is entailed by F and and {B1, , Bn} X then then add C to X. Return Return X as X+ 50