Transcript Functional Dependencies

Functional Dependencies
Babies
Exercise 2.2.5: At a birth, there is one baby (twins would
be represented by two births), one mother, any number
of nurses, and any number of doctors. Suppose,
therefore, that we have entity sets Babies, Mothers,
Nurses, and Doctors.
Suppose we also use a relationship Births, which
connects these four entity sets. Note that a tuple of the
relationship set for Births has the form
(baby, mother, nurse, doctor)
Babies (Cont’ed)
There are certain assumptions that we might wish
to incorporate into our design. For each, tell how
to add arrows or other elements to the E/R
diagram in order to express the assumption.
a) For every baby, there is a unique mother.
b) For every combination of a baby, nurse, and doctor,
there is a unique mother.
c) For every combination of a baby and a mother there is
a unique doctor.
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}.
Functional Dependencies - Example
• Let’s consider the relation:
– Movie(title, year, length, filmType, studioName, starName).
• There are several functional dependencies that we can reasonably
assert.
title year length
title year filmType
shorthand: title year length filmType studioName
title year studioName
• These assertions make sense if we remember the original design:
– Attributes title and year form a key for movie objects.
– Thus, given a title and a year there is a unique length, filmType and a
unique owning studio.
Example
Drinkers(name, addr, beersLiked, manf, favBeer)
• Reasonable FD’s to assert:
1. name -> addr
2. name -> favBeer
3. beersLiked -> manf
Example Data
name
Janeway
Janeway
Spock
addr
Voyager
Voyager
Enterprise
Because name -> addr
beersLiked
Bud
WickedAle
Bud
manf
A.B.
Pete’s
A.B.
favBeer
WickedAle
WickedAle
Bud
Because name -> favBeer
Because beersLiked -> manf
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: name -> addr and name -> favBeer
become name -> addr favBeer
• > 1 attribute on left may be essential.
– Example: bar beer -> price
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.
• Example. Attributes {title, year, starName} form a
key for the previous Movie relation. Why?
Keys of Relations (Continued)
• Because the first property of keyness is satisfied:
– title year functionally determines length, filmType and studioName. So does their
superset {title, year, starName}.
– starName functionally determines itself (starName). So does the superset {title,
year, starName}.
– Concluding title, year, starName functionally determine all the attributes.
• And, also the second property of keyness is satisfied: No proper subset of
{title, year, starName} functionally determines all attributes.
– {title, year}
• do not determine starName, because a movie can have many stars.
– {year, starName}
• do not determine title, because we can have a star in two movies in the same year.
– {title, starName}
• do not determine let’s say year, because we could have two movies with the same title
made in different years. It can be the case these two movies to have a star in common.
• It is very difficult to find such cases. However, if we make {title, starName} key, then
we prohibit the user to insert a new movie, which has the same title as a previous
inserted old movie, and where a star plays again (not necessary in the same role).
• Remember, the constraints are supposed to hold for all the instances, not only
for the current DB instance.