Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Normal Forms 1

Lipyeow
October 16, 2015

Normal Forms 1

Normal Forms 1

Lipyeow

October 16, 2015
Tweet

More Decks by Lipyeow

Other Decks in Programming

Transcript

  1. ICS  321  Data  Storage  &  Retrieval   Normal  Forms  1

      Prof.    Lipyeow  Lim   Informa@on  &  Computer  Science  Department   University  of  Hawaii  at  Manoa   1   Lipyeow  Lim  -­‐-­‐  University  of  Hawaii  at  Manoa  
  2. The  Problem  with  Redundancy   Lipyeow  Lim  -­‐-­‐  University  of

     Hawaii  at  Manoa   2   Hourly_Emps •  Suppose  hourly  wages  are  determined  by  ra@ng   •  Redundant  storage  :  (8,10)  stored  mul@ple  @mes   •  Update  anomaly  :  change  hourly  wages  in  row  1   •  Inser3on  anomaly  :  requires  knowing  hourly  wages  for   the  ra@ng   •  Dele3on  anomaly  :  dele@ng  all  (8,10)  loses  info   SSN   Name   Lot   Ra3ng   Hourly_wages   Hours_worked   123-­‐22-­‐2366   AUshoo   48   8   10   40   231-­‐31-­‐5368   Smiley   22   8   10   30   131-­‐24-­‐3650   Smethurst   35   5   7   30   434-­‐26-­‐3751   Guldu   35   5   7   32   612-­‐67-­‐4134   Madayan   35   8   10   40  
  3. Using  Two  Smaller  Tables   •  Any  more  anomalies  ?

     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
  4. Normal  Forms   •  Helps  with  the  ques@on:  do  we

     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  
  5. Boyce-­‐Codd  Normal  Form    (BCNF)   •  Let  R  denote

     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  
  6. Examples:  BCNF   •  Are  the  following  in  BCNF  ?

      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}
  7. Third  Normal  Form  (3NF)   •  Let    R  denote

     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  
  8. Example:  3NF   •  Which  of  the  following  is  in

     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 }
  9. Redundancies  &  Decomposi@ons   Lipyeow  Lim  -­‐-­‐  University  of  Hawaii

     at  Manoa   9   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 Hourly_Emps SSN   Name   Lot   Ra3ng   Hourly_wages   Hours_worked   123-­‐22-­‐2366   AUshoo   48   8   10   40   231-­‐31-­‐5368   Smiley   22   8   10   30   131-­‐24-­‐3650   Smethurst   35   5   7   30   434-­‐26-­‐3751   Guldu   35   5   7   32   612-­‐67-­‐4134   Madayan   35   8   10   40  
  10. Decomposi@ons   •  Reduces  redundancies  and  anomalies,  but  could  

    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  
  11. Lossless-­‐join  Decomposi@on   •  Decomposi@on  of  R  into  X  and

     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  
  12. Condi@ons  for  Lossless  Join   •  The  decomposi@on  of  R

      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