Functional Dependencies

ICS 321 Data Storage & Retrieval Func8onal Dependencies
Prof. Lipyeow Lim Informa8on & Computer Science Department University of Hawaii at Manoa 1 Lipyeow Lim -‐-‐ University of Hawaii at Manoa

Example: Movies1 •  What are the keys for this
rela8on ? •  What if you ignore the column starName ? •  Can starName be a key ? Lipyeow Lim -‐-‐ University of Hawaii at Manoa 2

Func8onal Dependency •  A func8onal dependency X -‐> Y
holds over rela8on R if, for every allowable instance r of R: –  for all tuples t1,t2 in r, πX (t1) = πX (t2) implies πY (t1) = πY (t2) –  i.e., given two tuples in r, if the X values agree, then the Y values must also agree. (X and Y are sets of aVributes.) •  An FD is a statement about all allowable instances. –  Must be iden8ﬁed based on seman8cs of applica8on. –  Given some allowable instance r1 of R, we can check if it violates some FD f, but we cannot tell if f holds over R! •  K is a candidate key for R means that K -‐> R –  However, K -‐> R does not require K to be minimal! Lipyeow Lim -‐-‐ University of Hawaii at Manoa 3

Keys & Superkeys •  A set of one or
more aVributes {A1 , A2 , ... An } is a key for a rela8on R if : –  1 . Those aVributes func1onally determine all other aVributes of the rela8on . –  2 . No proper subset of {A1 , A2 , ... An } func8onally determines all other aVributes of R •  a key must be minimal . •  When a key consists of a single aVribute A , we o`en say that A ( rather than {A} ) is a key. •  Superkey : a set of aVributes that contain a key. Lipyeow Lim -‐-‐ University of Hawaii at Manoa 4

FD Example: Movies1 •  What are the FDs for
this rela8on ? •  What are the keys for this rela8on ? •  Can starName be a key ? Lipyeow Lim -‐-‐ University of Hawaii at Manoa 5

Reasoning about FDs •  Given some FDs, we can
usually infer addi8onal FDs: –  ssn -‐> deptID, deptID -‐> building implies ssn -‐> building •  T implies S, or S follows from T –  Every rela8on instance that sa8sﬁes all the FDs in T also sa8sﬁes all the FDs in S •  S is equivalent to T –  The set of rela8on instances sa8sfying S is exactly the same as the set sa8sfying T –  Alterna8vely, S implies T AND T implies S Lipyeow Lim -‐-‐ University of Hawaii at Manoa 6

Armstrong’s Axioms Let X, Y, Z are sets of
aVributes: •  Reﬂexivity –  If X is a subset of Y, then Y -‐> X •  Augmenta1on –  If X -‐> Y, then XZ -‐> YZ for any Z •  Transi1vity –  If X -‐> Y and Y -‐> Z, then X -‐> Z These are sound and complete inference rules for FDs! Lipyeow Lim -‐-‐ University of Hawaii at Manoa 7

Example: Armstrong’s Axioms •  Reﬂexivity: If X
is a subset of Y, then Y -‐> X –  SNLR is a subset of SNLRWH, SNLRWH -‐> SNLR •  Augmenta1on: If X -‐> Y, then XZ -‐> YZ for any Z –  S -‐> N, then SLR -‐> NLR •  Transi1vity: If X -‐> Y and Y -‐> Z, then X -‐> Z –  S -‐> R, R -‐> W, then S -‐> W Lipyeow Lim -‐-‐ University of Hawaii at Manoa 8 Hourly_Emps SSN Name Lot Ra8ng Hourly_Wages Hours_worked 123-‐22-‐2366 Aishoo 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

Two More Rules •  Union / Combining – 
If X → Y and X → Z, then X → YZ –  Eg. FLD → A and FLD → T, then FLD → AT •  Decomposi;on / Spli<ng –  If X → YZ, then X → Y and X → Z –  Eg. FLD → AT , then FLD → A and FLD → T •  Trivial FDs –  Right side is a subset of Le` side –  Eg. F → F, FLD → FD •  Does “XY → Z imply X →Z and Y →Z” ? Lipyeow Lim -‐-‐ University of Hawaii at Manoa 9 Firstname Lastname DOB Address Telephone John Smith Sep 9 1979 Honolulu,HI 808-‐343-‐0809

Closure •  Implica;on: An FD f is implied by
a set of FDs F if f holds whenever all FDs in F hold. – f=A →C is implied by F={ A→B, B →C} (using Armstrong’s transi8vity) •  Closure F+ : the set of all FDs implied by F – Algorithm: •  start with F+ =F •  keep adding new implied FDs to F+ by applying the 5 rules ( Armstrong’s Axioms + union + decomposi8on) •  Stop when F+ does not change anymore. Lipyeow Lim -‐-‐ University of Hawaii at Manoa 10

Example: Closure •  Given FLD is the primary key
and C → Z •  Find the closure: –  Start with { FLD → FLDSCZT, C→Z } –  Applying reﬂexivity, { FLD → F, FLD →L, FLD → D, FLD → FL, FLD → LD, FLD →DF, FLDSCZT → FLD, …} –  Applying augmenta8on, { FLDS → FS, FLDS → LS, …} –  Applying transi8vity … –  Applying union … –  Applying decomposi8on … –  Repeat un8l F+ does not change Lipyeow Lim -‐-‐ University of Hawaii at Manoa 11 Firstname Lastname DOB Street CityState Zipcode Telephone John Smith Sep 9 1979 1680 East West Rd. Honolulu,HI 96822 808-‐343-‐0 809

AVribute Closure •  Compu8ng the closure of a set
of FDs can be expensive. (Size of closure is exponen8al in # aVrs!) •  Typically, we just want to check if a given FD X → Y is in the closure of a set of FDs F. An eﬃcient check: –  Compute aEribute closure of X (denoted X+) wrt F: •  Set of all aVributes A such that X → A is in F+ •  There is a linear 8me algorithm to compute this. –  Check if Y is in X+ •  Does F = {A → B, B → C, C D → E } imply A → E? –  i.e, is A → E in the closure F+ ? Equivalently, is E in A+ ? Lipyeow Lim -‐-‐ University of Hawaii at Manoa 12

Functional Dependencies

Functional Dependencies

Lipyeow

More Decks by Lipyeow

Other Decks in Science

Featured

Transcript

ICS 321 Data Storage & Retrieval Func8onal Dependencies

Example: Movies1 •  What are the keys for this

Func8onal Dependency •  A func8onal dependency X -‐> Y

Keys & Superkeys •  A set of one or

FD Example: Movies1 •  What are the FDs for

Reasoning about FDs •  Given some FDs, we can

Armstrong’s Axioms Let X, Y, Z are sets of

Example: Armstrong’s Axioms •  Reﬂexivity: If X

Two More Rules •  Union / Combining –

Closure •  Implica;on: An FD f is implied by

Example: Closure •  Given FLD is the primary key

AVribute Closure •  Compu8ng the closure of a set