Functional Dependencies in Relational Schema Design

Lecture 09: Functional Dependencies

Outline Functional dependencies (3.4) Rules about FDs (3.5) Design of a Relational schema (3.6)

Relational Schema Design name Conceptual Model: Product buys Person price name ssn date Relational Model: plus FD s Normalization: Eliminates anomalies

Functional Dependencies Definition: A1, ..., Am B1, ..., Bn holds in R if: t, t R, (t.A1=t .A1 ... t.Am=t .Am t.B1=t .B1 ... t.Bm=t .Bm ) R A1 ... Am B1 ... Bm t t if t, t agree here then t, t agree here

Important Point! Functional dependencies are part of the schema! They constrain the possible legal data instances. At any point in time, the actual database may satisfy additional FD s.

Examples EmpID E0045 E1847 E3123 E9923 Name John Smith Zheng Li Lucy Larsen Zheng Li Phone 2376 2376 1264 1264 Position HR QA Developer Developer EmpID Name, Phone, Position Position Phone but Phone Position

Formal definition of a key A key is a set of attributes A1, ..., An s.t. for any other attribute B, A1, ..., An B A minimal key is a set of attributes which is a key and for which no subset is a key Note: book calls them superkey and key

Examples of Keys Product(name, price, category, color) name, category price category color Keys are: {name, category} and all supersets Enrollment(student, address, course, room, time) student address room, time course student, course room, time Keys are: [in class]

Inference Rules for FDs A1 , A2, An B1, B2, Bm Splitting rule and Combing rule Is equivalent to A1 , A2, An B1 A1 , A2, An B2 A1 ... Am B1 ... Bm AND A1 , A2, An Bm

Inference Rules for FDs (continued) A1 , A2, An Ai Trivial Rule where i = 1, 2, ..., n A1 ... Am Why ?

Inference Rules for FDs (continued) Transitive Closure Rule If A1 , A2, An B1, B2, Bm B1, B2, Bm C1 , C2, Ck and A1 , A2, An C1 , C2, Ck then Why?

A1 ... Am B1 ... Bm C1 ... Ck

Enrollment(student, major, course, room, time) student major major, course room course time What else can we infer ? [in class]

Closure of a set of Attributes Given a set of attributes {A1, , An} and a set of dependencies S. Problem: find all attributes B such that: any relation which satisfies S also satisfies: A1 , A2, An B The closure of {A1, , An}, denoted {A1, , An}+, is the set of all such attributes B

Closure Algorithm Start with X={A1, , An}. UntilX doesn t change do: if B1, B2, Bm C is in S, and B1, B2, Bm are all in X and C is not in X then add C to X

Example The schema - R(A,B,C,D,E,F) A, B A,D B A,F C E D B Closure of {A,B}: X = {A, B, } Closure of {A, F}: X = {A, F, }

Why Is the Algorithm Correct ? Show the following by induction: For every B in X: A1 , A2, An B Initially X = {A1 , A2, An } holds Induction step: B1, , Bm in X Implies A1 , A2, An B1, B2, Bm We also have B1, B2, Bm C By transitivity we have A1 , A2, An C This shows that the algorithm is sound; need to show it is complete

Relational Schema Design (or Logical Design) Main idea: Start with some relational schema Find out its FD s Use them to design a better relational schema

Relational Schema Design Recall set attributes (persons with several phones): Name Fred Fred Joe Joe SSN 123-45-6789 123-45-6789 987-65-4321 987-65-4321 PhoneNumber City 206-555-1234 206-555-6543 908-555-2121 908-555-1234 Seattle Seattle Westfield Westfield SSN Name, City, but not SSN PhoneNumber Anomalies: Redundancy Update anomalies Deletion anomalies = Fred drops all phone numbers: what is his city ? = repeated data = Fred moves to Bellevue

Relation Decomposition Break the relation into two: Name Fred Joe SSN 123-45-6789 987-65-4321 City Seattle Westfield SSN 123-45-6789 123-45-6789 987-65-4321 987-65-4321 PhoneNumber 206-555-1234 206-555-6543 908-555-2121 908-555-1234

Relational Schema Design name Conceptual Model: Product buys Person price name ssn date Relational Model: plus FD s Normalization: Eliminates anomalies

Decompositions in General R(A1, ..., An) Create two relations R1(B1, ..., Bm) and R2(C1, ..., Ck) such that: B1, ..., Bm C1, ..., Ck = A1, ..., An and: R1 = projection of R on B1, ..., Bm R2 = projection of R on C1, ..., Ck

Incorrect Decomposition Sometimes it is incorrect: Name Price Category Gizmo 19.99 Gadget OneClick 24.99 Camera DoubleClick 29.99 Camera Decompose on : Name, Category and Price, Category

Incorrect Decomposition Name Category Price Category Gizmo Gadget 19.99 Gadget OneClick Camera 24.99 Camera DoubleClick Camera 29.99 Camera Name Price Category Gizmo 19.99 Gadget When we put it back: OneClick 24.99 Camera OneClick 29.99 Camera Cannot recover information DoubleClick 24.99 Camera DoubleClick 29.99 Camera

Normal Forms First Normal Form = all attributes are atomic Second Normal Form (2NF) = old and obsolete Third Normal Form (3NF) = this lecture Boyce Codd Normal Form (BCNF) = this lecture Others...

Boyce-Codd Normal Form A simple condition for removing anomalies from relations: A relation R is in BCNF if: Whenever there is a nontrivial dependency A1, ..., An B in R , {A1, ..., An} is a key for R Including superkeys In English: Whenever a set of attributes of R determines one more attribute, it should determine all the attributes of R.

Example Name Fred Fred Joe Joe SSN 123-45-6789 123-45-6789 987-65-4321 987-65-4321 PhoneNumber City 206-555-1234 206-555-6543 908-555-2121 908-555-1234 Seattle Seattle Westfield Westfield What are the dependencies? SSN Name, City What are the keys? {SSN, PhoneNumber} Is it in BCNF?

Decompose it into BCNF Name Fred Joe SSN 123-45-6789 987-65-4321 City Seattle Westfield SSN Name, City SSN 123-45-6789 123-45-6789 987-65-4321 987-65-4321 PhoneNumber 206-555-1234 206-555-6543 908-555-2121 908-555-1234

Summary of BCNF Decomposition Find a dependency that violates the BCNF condition: A1 , A2, An B1, B2, Bm Heuristics: choose B1, B2, Bm as large as possible Decompose: Continue until there are no BCNF violations left. Others A s B s Exercise: Is there a 2- attribute relation that is not in BCNF ? R1 R2

Example Decomposition Person(name, SSN, age, hairColor, phoneNumber) SSN name, age age hairColor Decompose in BCNF (in class): Step 1: find all keys Step 2: now decompose

Other Example R(A,B,C,D) A B, B C Key: A, D Violations of BCNF: A B, B C, A C, A B,C Pick A B,C: split R into R1(A,B,C), R2(A,D) What happens if we pick A B first ?

Correct Decompositions A decomposition is lossless if we can recover: R(A,B,C) Decompose R1(A,B) R2(A,C) Recover R (A,B,C) should be the same as R(A,B,C) R is in general larger than R. Must ensure R = R

Correct Decompositions Given R(A,B,C) s.t. A B, the decomposition into R1(A,B), R2(A,C) is lossless

3NF: A Problem with BCNF Film Actor Character FD s: Character Film; So, there is a BCNF violation, and we decompose. Film, Actor Character Film Character Character Film Actor Character No FDs

So Whats the Problem? Film Character Austin Powers Dr. Evil Actor Character Austin Powers Dr. Evil Austin Powers Austin Powers Mike Myers Mike Myers No problem so far. All localFD s are satisfied. Let s put all the data back into a single table again: What happened here? Film Actor Character Austin Powers Dr. Evil Austin Powers Austin Powers Mike Myers Mike Myers Violates the dependency: Film, Actor Character!

Solution: 3rd Normal Form (3NF) A simple condition for removing anomalies from relations: A relation R is in 3rd normal form if : Whenever there is a nontrivial dependency A1, A2, ..., An B for R , then {A1, A2, ..., An } a key for R, or B is part of a key. Including superkeys 3NF has a dependency-preserving decomposition

Decomposition into 3NF Easy when we know BCNF decomposition (how?) Not-so-easy: if we want a dependency- preserving decomposition In the book (3.5)