Update, Inser@on, Dele@on ? • Remove redundancy by decomposi)on – Since hourly wage is completely determined by ra@ng, factor out hourly wage. • Pros: less redundancy less anomalies • Cons: retrieving the hourly wage of an employee requires a join Lipyeow Lim -‐-‐ University of Hawaii at Manoa 3 SSN Name Lot Ra3ng Hours_ worked 123-‐22-‐2366 AUshoo 48 8 40 231-‐31-‐5368 Smiley 22 8 30 131-‐24-‐3650 Smethurst 35 5 30 434-‐26-‐3751 Guldu 35 5 32 612-‐67-‐4134 Madayan 35 8 40 Ra3ng Hourly_ wages 5 7 8 10 Hourly_Emps RatingWages
need to refine the schema ? • If a rela@on is in a certain normal form (BCNF, 3NF etc.), it is known that certain kinds of problems are avoided/minimized. This can be used to help us decide whether decomposing the rela@on will help. • Role of FDs in detec@ng redundancy: – Consider a rela@on R with 3 a`ributes, ABC. • No FDs hold: There is no redundancy here. • Given A → B: Several tuples could have the same A value, and if so, they’ll all have the same B value! Lipyeow Lim -‐-‐ University of Hawaii at Manoa 4
a rela@on, X a set of a`ributes from R, A an a`ribute from R, and F the set of FDs that hold over R. • R is in BCNF if for all X → A in F+, – A ∈ X (trivial FD) or – X is a superkey • Nega3on: R is not in BCNF if there exists an X → A in F+, such that A ∉ X (non-‐trivial FD) AND X is not a key Lipyeow Lim -‐-‐ University of Hawaii at Manoa 5 The only non-‐trivial FDs that hold are key constraints
Lipyeow Lim -‐-‐ University of Hawaii at Manoa 6 Firstname Lastname DOB Street CityState Zipcode Telephone John Smith Sep 9 1979 1680 East West Rd. Honolulu,HI 96822 808-‐343-‐0 809 Firstname Lastname DOB Address Telephone John Smith Sep 9 1979 Honolulu,HI 808-‐343-‐0809 F= { FLD → FLDSCZT, C→Z } F= { FLD → FLDAT}
a rela@on, X a set of a`ributes from R, A an a`ribute from R, F the set of FDs for R. • R is in 3NF if for all X → A in F+, – A ∈ X (trivial FD) or – X is a superkey or – A is part of some key • Nega3on: R is not in 3NF if there exists an X → A in F+, such that – A ∉ X (non-‐trivial FD) AND – X is not a key AND A is not part of some key • If R is in BCNF, obviously in 3NF. • If R is in 3NF, some redundancy is possible. It is a compromise, used when BCNF not achievable (e.g., no ``good’’ decomp, or performance considera@ons). Lipyeow Lim -‐-‐ University of Hawaii at Manoa 7
3NF and which in BCNF ? Lipyeow Lim -‐-‐ University of Hawaii at Manoa 8 Firstname Lastname DOB Street CityState Zipcode Telephone John Smith Sep 9 1979 1680 East West Rd. Honolulu,HI 96822 808-‐343-‐0 809 Firstname Lastname DOB Address Telephone John Smith Sep 9 1979 Honolulu,HI 808-‐343-‐0809 F= { FLD → FLDSCZT, C→Z } F= { FLD → FLDAT} Student Course Instructor Smith OS Mark F= { SC → I, I→C }
have the following poten@al problems: 1. Some queries become more expensive. 2. Given instances of the decomposed rela@ons, we may not be able to reconstruct the corresponding instance of the original rela@on! 3. Checking some dependencies may require joining the instances of the decomposed rela@ons. • Two desirable proper@es: – Lossless-‐join decomposi@on – Dependency-‐preserving decomposi@on Lipyeow Lim -‐-‐ University of Hawaii at Manoa 10
Y is lossless-‐join w.r.t. a set of FDs F if, for every instance r that sa@sfies F: πX (r) join πY (r) = r • In general one direc@on πX (r) join πY (r) ⊆ r is always true, but the other may not hold. • Defini@on extended to decomposi@on into 3 or more rela@ons in a straighnorward way. • It is essen0al that all decomposi0ons used to deal with redundancy be lossless! (Avoids Problem (2).) Lipyeow Lim -‐-‐ University of Hawaii at Manoa 11
into X and Y is lossless-‐ join wrt F if and only if the closure of F contains: – X ∩ Y → X, or – X ∩ Y → Y • In par@cular, the decomposi@on of R into UV and R -‐ V is lossless-‐ join if U → V holds over R. Lipyeow Lim -‐-‐ University of Hawaii at Manoa 12 A B C 1 2 3 4 5 6 7 2 8 A B 1 2 4 5 7 2 B C 2 3 5 6 2 8 A B C 1 2 3 4 5 6 7 2 8 1 2 8 7 2 3
lipyeow
kuranuki
masuda220
nilpe
hirokunimaeta
yusukebe
yaotti
yoshikouki
musan
o0h
handlename
htkym
pvcresin
danielanewman
marktimemedia
katarinadahlin
codingconduct
mfonobong
inesmontani
marketingsoph
kimpetersen
aleyda
joshbly
jonoalderson
