​

​

Functional Dependency

​

B. Krishnakumar

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

title year →studioName

shorthand: title year →length filmType 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.

• A set of attributes that contain a key is called a superkey.

​

• Note that every superkey satisfies the first condition of a key:
• It functionally determines all the attributes of the relation.

​

• However, a superkey need not satisfy the second condition:
• Minimality.

​

• Example. In the relation Movie there are many superkeys.
• Not only the key:
• {title, year, starName} but also any superset of it:
• {title, year, starName, length} etc.

Superkeys

• If the relation comes from an entity set, then the key for the relation is the key of this entity set. Example:
• The keys for the Movies and Stars were {title, year} and {name} respectively. These are also the keys for the corresponding relations:
• Movies(title, year, length, filmType)
• Stars(name, address)

​

• If a relation R comes from a relationship then the multiplicity of the relationship affects the key for R.
• If the relationship is many-many,

then the keys of both connected entity sets are the key attributes for R.

• If the relationship is many-one from ES E₁ to E₂,

then the key attributes of E₁ are the key attributes of R, but those of E₂ are not.

• If the relationship one-one,

then the key attributes for either of the connected ES’s are key attributes of R.

Discovering Keys for Relations – �E/R to Relations

Example

• Example. Consider the relationship Owns, which is many-one from entity set Movies to entity set Studios.
• The key for the relation Owns is

title+year, which come from the key for Movies.

• Owns(title, year, studioName)

​

​

• Example. Consider the relationship Stars-in, which is many-many from entity set Movies to entity set Stars.
• The key for the relation Stars-in is

(title+year)+starName, which come from the key for Movies and the key for Stars.

• Stars-in(title, year, starName).

(Continued)

• Let’s consider multiway relationships.
• The book says: “Since we cannot describe all the possible dependencies by arrows…”
• Actually, as demonstrated in the example “Births” we can in fact describe the dependencies between ES’s by arrows & relationships.

​

• If we have expressed all the dependencies between ES’s by proper relationships and arrows then the key of a relation representing a multiway relationship will be:
• The key attributes of all ES’s connected with arrowless lines in the relationship. (many sides of the relationship)
• If an ES E participates more than one time in the relationship then the relation has distinct attributes representing the key of E for each role.

(Continued)

• Suppose we are told of a set of functional dependencies that a relation satisfies. Without knowing exactly, what tuples are in the relation we can deduce other dependencies.

​

• Example. If we are told that a relation R with attributes A, B and C satisfies the functional dependencies: A→B and B→C, then we can deduce that R also satisfies A→C.
• Let (a, b₁, c₁) and (a, b₂, c₂) be two tuples that agree on attribute A.
• Since R satisfies A→B it follows that b₁=b₂ so the tuples are: (a, b, c₁) and (a, b, c₂)
• Similarly, since R satisfies B→C and the tuples agree on B they will agree also on C. So, c₁=c₂.

Rules About Functional Dependencies

The Splitting/Combining Rule

A₁A₂…A_n→B₁

A₁A₂…A_n→B₂

…

A₁A₂…A_n→B_m

A₁A₂…A_n→B₁B₂…B_m.

Combining Rule

Splitting Rule

• A functional dependency A₁A₂…A_n→B is said to be trivial if B is one of A’s.
• For example: title year →title is a trivial dependency.

​

• We say that a dependency A₁A₂…A_n→B₁B₂…B_m is:
• Trivial if the B’s are subset of A’s.
• Nontrivial if at least one of the B’s is not among the A’s.
• Completely nontrivial if none of the B’s is also one of the A’s.

​

• Thus title year → year length is nontrivial but not completely nontrivial.

​

• The trivial dependency rule is: We can always remove from the right side of an FD those attributes that appear on the left.

Trivial Dependencies

• There is a general principle from which all possible FD’s follow.

​

• Suppose {A₁, A₂, …, A_n} is a set of attributes and S is a set of FD’s.

​

• Closure of {A₁, A₂, …, A_n} under the dependencies in S is the set of attributes B, which are functionally determined by A₁, A₂, …, A_n i.e.
• A₁A₂…A_n→B.

​

• That is A₁A₂…A_n→B follows from dependencies of S.

​

• We denote the closure of a set of attributes {A₁, A₂, …, A_n} by {A₁, A₂, …, A_n}⁺.

​

• Since we allow trivial dependencies A₁, A₂, …, A_n are in {A₁, A₂, …, A_n}⁺.

Computing the Closure of Attributes

• Starting with the given set of attributes, repeatedly expand the set by adding the right sides of FD’s as soon as we have included their left sides.
• Eventually, we cannot expand the set any more, and the resulting set is the closure.

​

• Let X be a set of attributes that eventually will become the closure. First we initialize X to be {A₁, A₂, …, A_n}.
• Now, repeatedly search for some FD in S:

B₁B₂…B_m→C

such that all of B’s are in the set X, but C is not. We then add C to X.

• Repeat step 2 as many times as necessary until no more attributes can be added to X.

Since X can only grow, and the number of attributes is finite, eventually nothing more can be added to X.

• The set X after no more attributes can be added to it is the: {A₁, A₂, …, A_n}⁺.

Computing the Closure of Attributes - Algorithm

• Let’s consider a relation with attributes A, B, C, D, E and F. Suppose that this relation satisfies the FD’s:

AB→C,

BC→AD,

D→E,

CF→B.

What is {A,B}⁺?

​

• Iterations:
• X = {A,B} Use: AB→C
• X = {A,B,C} Use: BC→AD
• X = {A,B,C,D} Use: D→E
• X = {A,B,C,D,E} No more changes to X are possible so X = {A,B}⁺.

​

• The FD: CF→B cannot be used because its left side is never contained in X.

Computing the Closure of Attributes - Example

• Summarizing: If we know how to compute the closure of any set of attributes, then we can test whether any given functional dependency A₁A₂…A_n→B follows from a set of dependencies S.

​

• First compute {A₁, A₂, … , A_n}⁺ using the set of dependencies S.

​

• If B ∈ {A₁, A₂, … , A_n}⁺ then the FD: A₁A₂…A_n→B does follow from S.

​

• If B ∉ {A₁, A₂, … , A_n}⁺ then the FD: A₁A₂…A_n→B doesn’t follow from S.

Computing the Closure of Attributes (Continued)

• Example. Consider the previous example. Suppose we want to test whether

AB→D

follows from the set of the dependencies.

Yes! Since D∈{A,B,C,D,E} = {A,B}⁺.

​

On the other hand consider testing the FD: D→A.

​

• First compute {D}⁺. Initially we have X={D}. Then we can use the given D→E and X becomes {D,E}. But here we are stuck, we have reached the closure.

​

• So {D}⁺ = {D,E} and A ∉ {D}⁺.

​

• Concluding D→A does not follow from the given set of dependencies.

Computing the Closure of Attributes (Continued)

• Notice that {A₁, A₂, … , A_n}⁺ is the set of all attributes if and only if {A₁, A₂, … , A_n} is a superkey for the relation in question.

​

• Only then does A₁, A₂, … , A_n functionally determines all the attributes.

​

• We can test if A₁, A₂, … , A_n is a key for a relation by checking:
• first that {A₁, A₂, … , A_n}⁺ contains all attributes,
• and that for no subset S of {A₁, A₂, … , A_n}⁺, is S⁺ the set of all attributes.

Closures and Keys