6 - Chapter 3 - Functional Dependencies

Database Systems
Session 6
Chapter 3 - Design theory for
Relational Database - FDs
Objectives
1 Understand what are functional dependencies
2 Understand the rules about FDs
33 Understand what are keys, super-keys
4 Understand what are closure-sets and how to determine them
5 Understand what are closing sets of FD’s and how to determine them
6 Understand what is projecting FD’s

Contents
1 Functional Dependencies
2 Rules about FDs
3 Key & Super-Key
4 Closure-sets and Algorithm for calculating the closure-set of a relation
5 Closing set of FD’s
6 Projecting FD’s
1. Functional Dependency Definition
 A functional dependency (FD) is a constraint between two

sets of attributes in a relation from a database
 Given a relation R, a set of attributes X in R is said to

functionally determine another set of attributes Y, also in
R, (written X → Y) if and only if each X value is associated
with precisely one Y value
 Customarily we call X the determinant set and Y the

dependent attribute
 A functional dependency FD: is called trivial if Y is a subset

of X
1. Functional Dependency Definition
A Functional Dependency (FD) X → Y on

a relation R is a statement of the form:
“If 2 tuples of R agree on attribute X, then

they must also agree on Y”
XY  (t1(X) = t2(X)  t1(Y) = t2(Y))

Example: Functional Dependency
 Easy to see that: the following FD is true

(title, year) → (length, genre, studioName)
 Exercise: How about this FD (TRUE or FALSE)?

(title, year) → (starName)
2. Rules about functional dependencies
Given that X, Y, and Z are sets of attributes in a relation R, one can

derive several properties of functional dependencies. Among the
most important are Armstrong’s axiom, which are used in database
normalization:
 Subset Property (Axiom of Reflexivity):
If Y is a subset of X, then X → Y
 Augmentation (Axiom of Augmentation): If X → Y, then XZ → YZ
 Transitivity (Axiom of Transitivity): If X → Y and Y → Z, then X → Z
From these rules, we can derive these secondary rules:

 Union: If X → Y and X → Z, then X → YZ
 Decomposition: If X → YZ, then X → Y and X → Z
 Pseudo transitivity: If X → Y and YZ → W, then XZ → W
 Accumulation: If X → YZ and Z → V, then X → YZV
 Extension: If X → Y and W → Z, then WX → YZ
Find functional dependencies
Course Roll# Name Comments

DB 00511 Nguyen Van A Good
DB 00139 Nguyen Van C Good
DB 00981 Tran Van X Bad
Find functional dependencies
Date Slot StartTime EndTime Class Subject

21/10/2018 1 7:00 8:30 SE1023 Database
21/10/2018 2 8:45 10:15 SE1022 Database
21/10/2018 3 10:30 12:00 SE1016 Database
Date Slot Room Teacher# Teacher Name

1/1/2011 1 133 00788 Thutv
1/2/2011 1 135 00788 Thutv
3/1/2011 1 129 00788 Thutv
3. Keys
 A set of one or more attributes {A1, A2, .., An} is

called a key of the relation R if:
1. Those attributes functionally determine all

other attributes of R.
This means that: It is impossible for 2 tuples of R to
agree on all of {A1, A2, .., An}
2. No proper subset of {A1, A2, .., An}

functionally determines all other attributes of R
This means that: A Key must be minimal
Example: Keys
 Exercise 1:
(title, year) forms a key?
 Exercise 2:
(title, year, starName) forms a key ?
3. Super-keys
A set of attributes that contains a key is called

a Super-key, short for “superset of a key”
Every key is a superkey
A superkey is a set of attributes of a relation
whose values can be used to uniquely
identify a row
A superkey need not satisfy the second
condition of a key: minimality
Example: Super-key
 There are many Super-key in the above schema:
(title, year, starName)

(title, year, starName, length, studioName)
 Exercise: Can (title, year, starName, length, studioName)

form a key?
Exercise
People(name, Social Security number, street

address, city, state, ZIP code, area code,
phone)
 What FD’s would you expect to hold?

 What are the keys for the relation
4.Closure sets
 Suppose: {A1,…, An} is a set of attributes. And S is a

set of FD’s.
 The closure of {A1,…, An} under the FD’s in S is the
set of attributes B such that: Every relation that satisfies
all the FD’s in set S also satisfies: {A1,..,An}→B
 This means that: {A1,..,An}→B follows from the FD’s of
S
 Closure of a set of attributes {A1, ..., An} is denoted
{A1, A2, ..., An}+
 Closure of a set of FD’s S is the set of functional
dependencies Q that includes all FDs are derived from
S by Amstrong rules.
Example: Closure Set
R (A, B, C, D, E, F)
S = {A → C, A → D, D → E,
E → F}
Easy to see that:
{A}+ = {A, C, D, E, F}
5. Closure set algorithm
Exercises
R (A, B, C, D, E, F)
S = {AB → C, BC → AD, D → E,
CF → B}
compute {AB}+
An efficient algorithm to finding KEYS for
a relation

L contains those attributes that occur only on the left-hand side of FDs
Suppose
Suppose R contains those attributes that occur only on the right-hand side of

FDs

Suppose M contains those attributes that occur on both side of FDs
 Note:
 L Intersects M = EMPTY
 M Intersects R = EMPTY
 L Intersects R = EMPTY
Some LEMAs
 Lemma 1: for every attribute A, if A is in L then A

must be part of every key
 Lemma 2: if L+ is super-key then L is the only key
 Lemma 3: for every attribute A, if A is in R then A
will not be part of any key
 Conclusion: we only focus only on L and M to find

all keys
Exercises
R (A, B, C, D)
S = {BC→D, D→A, A→B}
What are all the keys of R?
What are all the super-keys for R that
are not keys?
Exercises
R (A, B, C, D)
S = {AD→B, AB→C, BC→D, CD→A}
What are all the keys of R?
What are all the super-keys for R that
are not keys?
Closing sets of FD’s
 Given a set of FD’s S, any set of FD’s equivalent

to S is said to be a basis for S
 A minimal basic (or closing sets) of FD’s for a
relation is a set of functional dependencies B
that satisfies three conditions:
 All the FD’s in B have singleton right sides.
 If any FD is removed from B, the result is no longer
the basis.
 If for any FD in B we remove one or more attributes
from the left side, the result is no longer a basis.
Closing sets of FD’s
Example: R(A,B,C) and FD’s: A->B, A->C,

B->A, B->C, C->A, C->B, AB->C, BC->A,
AC->B, A->BC, B->AC, C->AB;
Minimal basic (or closing sets) of FD’s:

 {A->B, B->A, B->C, C->B}
 {A->B, B->C, C->A}
Projecting FD’s
Suppose we have R with set of FD’s S,

and we project R by computing R1 = ΠL(R)
for some list of attributes R. What FD’s
hold in R1?
Projection of FD’s S includes all FD’s that:
 Follow from S, and
 Involve only attributes of R1.
Algorithm for projecting a set of FD’s
Input: Relation R, FD’s S that hold in R.

Relation R1 = ΠL(R)
Output: The set of FD’s that hold in R1.
Method:
 Initially, T is empty
 ∀ X ⊂ R1, compute X+ based on S. Add to T
all non trivial FD’s X->A such that A is both in
X+ and R1
 Now T is a basic for the FD’s that hold in R1.
We must construct a minimal basis of T.
Example
R(A,B,C,D) and FD’s: A->B, B->C, C->D

Project the set of FD in R1(A,C,D)
Example
R(A,B,C,D) and FD’s: A->B, B->C, C->D

Project the set of FD in R1(A,C,D)
T=A->C, C->D;

6 - Chapter 3 - Functional Dependencies

Uploaded by

Copyright:

Available Formats

6 - Chapter 3 - Functional Dependencies

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

6 - Chapter 3 - Functional Dependencies

Uploaded by

Copyright:

Available Formats

Database Systems

1 Understand what are functional dependencies

2 Understand the rules about FDs

33 Understand what are keys, super-keys

4 Understand what are closure-sets and how to determine them

6 Understand what is projecting FD’s

2 Rules about FDs

3 Key & Super-Key

4 Closure-sets and Algorithm for calculating the closure-set of a relation

5 Closing set of FD’s

 A functional dependency (FD) is a constraint between two

 Given a relation R, a set of attributes X in R is said to

 Customarily we call X the determinant set and Y the

 A functional dependency FD: is called trivial if Y is a subset

A Functional Dependency (FD) X → Y on

“If 2 tuples of R agree on attribute X, then

XY  (t1(X) = t2(X)  t1(Y) = t2(Y))

 Easy to see that: the following FD is true

 Exercise: How about this FD (TRUE or FALSE)?

Given that X, Y, and Z are sets of attributes in a relation R, one can

From these rules, we can derive these secondary rules:

Course Roll# Name Comments

Date Slot StartTime EndTime Class Subject

Date Slot Room Teacher# Teacher Name

 A set of one or more attributes {A1, A2, .., An} is

1. Those attributes functionally determine all

2. No proper subset of {A1, A2, .., An}

A set of attributes that contains a key is called

 There are many Super-key in the above schema:

(title, year, starName)

 Exercise: Can (title, year, starName, length, studioName)

People(name, Social Security number, street

 What FD’s would you expect to hold?

 Suppose: {A1,…, An} is a set of attributes. And S is a

 Lemma 1: for every attribute A, if A is in L then A

 Conclusion: we only focus only on L and M to find

 Given a set of FD’s S, any set of FD’s equivalent

Example: R(A,B,C) and FD’s: A->B, A->C,

Minimal basic (or closing sets) of FD’s:

Suppose we have R with set of FD’s S,

Input: Relation R, FD’s S that hold in R.

R(A,B,C,D) and FD’s: A->B, B->C, C->D

R(A,B,C,D) and FD’s: A->B, B->C, C->D

You might also like