Functional Dependency
Murat Kantarcioglu
Functional Dependencies
• Let R be a relation schema
R and R
• The functional dependency
holds on R if and only if for any legal relations
r(R), whenever any two tuples t1 and t2 of r agree
on the attributes , they also agree on the
attributes . That is,
t1[] = t2 [] t1[ ] = t2 [ ]
Example
• Example: Consider r(A,B ) with the following
instance of r.
A B
1 3
1 6
2 7
• On this instance, A B does NOT hold, but B
A does hold.
Example
A B C D
a1 b1 c1 d1
a1 b1 c1 d2
a1 b2 c2 d1
a2 b1 c3 d1
• Does AB C hold?
• Does ABC D hold ?
• Does BC D hold?
Example
SSN LastName FirstName City
111111111 Smith John Richardson
222222222 Li Peng Richardson
333333333 Kant John Plano
444444444 Smith Mark Plano
• Does {ssn} {LastName} hold?
• Does {ssn} {LastName,FirstName} hold ?
• Does {LastName, FirstName} {City} hold?
• Does {City} {FirstName} hold?
Procedure for Computing F+
F+=F
repeat
for each functional dependency f in F+
apply reflexivity and augmentation rules on f
add the resulting functional dependencies to F +
for each pair of functional dependencies f1and f2 in F +
if f1 and f2 can be combined using transitivity then
add the resulting functional dependency to F +
until F + does not change any further
Example
• R = (A, B, C, G, H, I)
F = { A B, A C, CG H, CG I, B H}
• some members of F+
– AH
• by transitivity from A B and B H
– AG I
• by augmenting A C with G, to get AG CG
and then transitivity with CG I
– CG HI
• by augmenting CG I to infer CG CGI, and
augmenting of CG H to infer CGI HI,
and then transitivity
Closure of Attribute Sets
• Given a set of attributes define the closure of under
F (denoted by +) as the set of attributes that are
functionally determined by under F
• Algorithm to compute +, the closure of under F
result := ;
while (changes to result) do
for each in F do
begin
if result then result := result
end
Example of Attribute Set
Closure
• R = (A, B, C, G, H, I)
• F = {A B,A C ,CG H,CG I,B H}
• (AG)+
1. result = AG
2. result = ABCG (A C and A B)
3. result = ABCGH (CG H and CG AGBC)
4. result = ABCGHI (CG I and CG AGBCH)
• Is AG a candidate key?
1. Is AG a super key?
1. Does AG R? == Is (AG)+ R
2. Is any subset of AG a superkey?
1. Does A R? == Is (A)+ R
2. Does G R? == Is (G)+ R
