Transcript Example

Functional Dependencies
函数依赖
Meaning of FD’s
Keys and Superkeys
Functional Dependencies
1
Functional Dependencies
 X → A is an assertion about a relation R that
whenever two tuples of R agree on all the attributes
of X, then they must also agree on the attribute A.
 Say “X → A holds in R.”
 Convention: …, X, Y, Z represent sets of attributes; A, B, C,…
represent single attributes.
 Convention: no set formers in sets of attributes, just ABC,
rather than {A,B,C }.
2
Example
title
year
length film type studioName starName
Star Wars
Star Wars
Star Wars
Mighty Ducks
Wayne’s World
Wayne’s World
1977
1977
1977
1991
1992
1992
124
124
124
104
95
95
color
color
color
color
color
color
Fox
Fox
Fox
Disney
Paramount
Paramount
Carrie Fisher
Mark Hamill
Harrison Ford
Emilio Estevez
Dana Carvey
Mike Meyers
Movies(title, year,length,filmType,studioname)
 Reasonable FD’s to assert:
1. tile year → length
2. tile year →filmType
3. tile year → studioName
3
FD’s With Multiple Attributes
No need for FD’s with > 1 attribute on
right.
 But sometimes convenient to combine FD’s
as a shorthand.
 Example: tile year → length , tile year
→filmType and tile year →
studioName become tile year → length
filmType studioName
4
Keys of Relations
 K is a superkey for relation R if
K
functionally determines all of R.
 K is a key for R if K is a superkey, but no
proper subset of K is a superkey.
5
Example
Movies(title, year,length,filmType,studioname)
 {tile, year,starName} is a superkey because
together these attributes determine all the
other attributes.
{tile, year,starName,length,filmType} is a
superkey too.
6
E/R and Relational Keys
Keys in E/R concern entities.
Keys in relations concern tuples.
Usually, one tuple corresponds to one entity,
so the ideas are the same.
But --- in poor relational designs, one entity
can become several tuples, so E/R keys and
Relational keys are different.
7
Example
name
addr
name
Bars
Beers
Sells
license
Note:
license =
beer, full,
none
Frequents
name
Drinkers
manf
Likes
Bars sell some
beers.
Drinkers like
some beers.
Drinkers frequent
some bars.
addr
8
Example Data (Cont.)
name
Janeway
Janeway
Spock
addr
Voyager
Voyager
Enterprise
beersLiked
Bud
WickedAle
Bud
manf
A.B.
Pete’s
A.B.
favBeer
WickedAle
WickedAle
Bud
Relational key = {name beersLiked}
But in E/R, name is a key for Drinkers, and beersLiked is a key
for Beers.
Note: 2 tuples for Janeway entity and 2 tuples for Bud entity.
9
Where Do Keys Come From?
1. Just assert a key K.

The only FD’s are K → A for all attributes A.
2. Assert FD’s and deduce the keys by
systematic exploration.

E/R model gives us FD’s from entity-set keys
and from many-one relationships.
10
More FD’s From “Physics”
Example: “no two courses can meet in the
same room at the same time” tells us: hour
room → course.
11
Rules About Functional Dependencies
The Splitting/Combining Rule
 We can replace a FD A1A2…An→ B1B2…Bm by a set
of FD’s A1A2…An→ Bi,for i=1,2,…,m. This
transformation we call splitting rules.
 We can replace a set of FD’s A1A2…An→ Bi for
i=1,2,…,m by a set A1A2…An→ B1B2…Bm,. This
transformation we call combining rules.
12
Examples
title year → length
title year → studioName
title year → length studioName
13
More
Consider FD:
title year → length
if we try to split the left side into
title → length
year → length
Then we get two false FD’s.
14
Trivial Dependencies
A functional dependency A1A2…An→B is said
to be trivial(平凡) if B is one of the A’s,
otherwise is said to be nontrivial(非平凡).
 Example: Suppose Functional Dependencies
title, year → title
is a trivial dependency.
15
The Closure of Attributes
Suppose {A1,A2,…,An} is a set of attributes and S is a
set of FD’s. The closure of {A1,A2,…,An} under the FD’s
in S is the set of attributes B such that every relation
that satisfies all the FD’s in the set S also satisfies
A1A2…An→ B.
That is, A1A2…An→ B follows from the FD’s of S.
16
Computing the closure
An easier way to test is to compute the
closure of Y, denoted Y +.
Basis: Y + = Y.
Induction: Look for an FD’s left side X that is
a subset of the current Y +. If the FD is X ->
A, add A to Y +.
17
X
Y+
A
new Y+
18
Example
 R = (A, B, C, G, H, I)
 F = {A  B
AC
CG  H
CG  I
B  H}
 (AG)+
1.
2.
3.
4.
result = AG
result = ABCG (A  C and A  B)
result = ABCGH (CG  H and CG  AGBC)
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
19
Another Examples
例 设关系模式R（U,F）,其中,
U={A,B,C,D,E,I},F={A→D,AB→C,BI→C,E
D→I,C→E},求（AC）F+ 。
解：
(1) 令X={AC},则X(0)=AC。
(2) 在F中找出左边是AC子集的函数依赖：
A→D,C→E。
(3) X(1)=X(0)∪D∪E=ACDE。
20
(4) 很明显X(1)≠X(0),所以X(i)=X(1),并转向算法中的步
骤(2)。
(5) 在F中找出左边是ACDE子集的函数依赖： ED→I。
(6) X(2)=X(1)∪I=ACDEI。
(7) 虽然X(2)≠X(1),但是F中未用过的函数依赖的左边属性
已没有X(2)的子集,所以,可停止计算,输出（AC） F+ =
X(2)=ACDEI。
21
The transitive rule
Transitive(传递) Functional Dependencies
 Suppose we have a relation R with three attributes A,
B, and C, the FD’s A→B and B→C both hold for R.
Then it is easy to see that the FD A→C also holds for
R, So C is said to depend on A transitively, via B.
22
Examples
title
year
length
film type
studioName
studioAddr
Star Wars
Mighty Ducks
Wayne’s World
1977
1991
1992
124
104
95
color
color
color
Fox
Disney
Paramount
Holleywood
Buena Vista
Holleywood
Two of the FD’s
 title year → studioName
 studioName →studioAddr
Combine the two FD’s above to get
 title year → studioAddr
23
Closing Sets of Functional Dependencies
 Any set of given FD’s from which we can infer all the
FD’s for a relation will be called a basis for that
relation. If no proper subset of the FD’s in the basis
can also derive the complete set of FD’s, then we say
the basis is minimal, that is the closing set of the
functional dependencies of the relation
 Consider a relation R(A,B,C), One of its FD’s is
{A→B,B →A, B→C,C →B}
 Another is
{A→B,B→C,C →A}
24