Functional Dependencies (FDs)
A functional dependency X Y holds over relation R if, for every allowable instance r of R:
- t1 r, t2 r, (t1) = (t2) implies (t1) = (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 attributes.)
An FD is a statement about all allowable relations.
- Must be identified based on semantics of application.
- 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!