24‐10‐2024

Functional Dependency
Dr. Rupa Mehta
Professor,
Computer Engineering Department
SVNIT, Surat

Informal Design Guidelines for Relational

Databases
• Relational database design: The grouping of
attributes to form "good" relation schemas
• Two levels of relation schemas:
• The logical "user view" level
• The storage "base relation" level
• Design is concerned mainly with base relations
• Criteria for "good" base relations:
• Discuss informal guidelines for good relational design
• Discuss formal concepts of functional dependencies and
normal forms 1NF 2NF 3NF BCNF

1
 24‐10‐2024

Semantics of the Relation Attributes

• Each tuple in a relation should represent one entity or relationship
instance
• Only foreign keys should be used to refer to other entities
• Entity and relationship attributes should be kept apart as much as possible
• Design a schema that can be explained easily relation by relation. The
semantics of attributes should be easy to interpret.

2
 24‐10‐2024

Redundant Information in Tuples and Update

Anomalies
• Mixing attributes of multiple entities may cause problems
• Information is stored redundantly wasting storage
• Problems with update anomalies:
• Insertion anomalies
• Deletion anomalies
• Modification anomalies

3
24‐10‐2024

4
 24‐10‐2024

EXAMPLE OF AN UPDATE ANOMALY

Consider the relation:
EMP_PROJ ( Emp#, Proj#, Ename, Pname, No_hours)
• Update Anomaly
• Changing the name of project number P1 from “Billing” to “Customer‐Accounting” may
cause this update to be made for all 100 employees working on project P1
• Insert Anomaly
• Cannot insert a project unless an employee is assigned to .
• Inversely‐ Cannot insert an employee unless he/she is assigned to a project.

EXAMPLE OF AN UPDATE ANOMALY (2)

• Delete Anomaly
• When a project is deleted, it will result in deleting all the employees who
work on that project. Alternately, if an employee is the sole employee on a
project, deleting that employee would result in deleting the corresponding
project.

5
 24‐10‐2024

Null Values in Tuples (self)

• Relations should be designed such that their tuples will have as few
NULL values as possible
• Attributes that are NULL frequently could be placed in separate relations
(with the primary key)
• Reasons for nulls:
• a. attribute not applicable or invalid
• b. attribute value unkown (may exist)
• c. value known to exist, but unavailable

Spurious Tuples
• Rows in a table occurred as a result of joining two tables in the wrong
manner.

6
 24‐10‐2024

Example 1 : Split the table in Two

Example 1 : After Join

7
 24‐10‐2024

Example 1 : After Join

• No information Loss
• Loss less Join
• The condition for no spurious tuples, R1 ⨝ R2 = R, is met.

Spurious Tuples
• Rows in a table occurred as a result of joining two tables in the wrong
manner.
• Bad designs for a relational database may result in erroneous results
for certain JOIN operations

8
 24‐10‐2024

Example 2: Bad Design

Example 2: Bad Design

• The condition for spurious tuples, R ⊂ R1 ⨝ R2

9
 24‐10‐2024

Example 3 : Bad
Design

Functional Dependencies
• Functional dependencies (FDs) are used to specify formal measures
of the "goodness" of relational designs
• FDs and keys are used to define normal forms for relations
• FDs are constraints that are derived from the meaning and
interrelationships of the data attributes

10
 24‐10‐2024

Functional Dependencies (2)

• A set of attributes X functionally determines a set of attributes
Y
• if the value of X determines a unique value for Y
• X Y holds
• if whenever two tuples have the same value for X, they must have the
same value for Y
• If t1[X]=t2[X], then t1[Y]=t2[Y] in any relation instance r(R)
• X  Y in R specifies a constraint on all relation instances r(R)
• FDs are derived from the real‐world constraints on the
attributes

Examples of FD constraints
• Social Security Number determines employee name
• SSN  ENAME
• Project Number determines project name and location
• PNUMBER  {PNAME, PLOCATION}
• Employee SSN and project number determines the hours per week that
the employee works on the project
• {SSN, PNUMBER}  HOURS

11
 24‐10‐2024

types Of Functional Dependencies-

Trivial Functional Dependencies

• A functional dependency X → Y is said to be trivial if and only if Y ⊆ X.
• Thus, if RHS of a functional dependency is a subset of LHS, then it is called
as a trivial functional dependency.

• Examples‐
• AB → A
• AB → B
• AB → AB Emp_id Emp_name
AS555 Harry
• E.g. AS811 George
• {Emp_id, Emp_name} -> Emp_id is a trivial fd AS999 Kevin
• as Emp_id is a subset of {Emp_id,Emp_name}.

12
 24‐10‐2024

Non‐Trivial Functional Dependencies‐

• A functional dependency X → Y is said to be non‐trivial if and only if Y ⊄ X.
• Thus, if there exists at least one attribute in the RHS of a functional
dependency that is not a part of LHS, then it is called as a non‐trivial
functional dependency.

• Examples‐
• AB → BC
• AB → CD
Company CEO Age
• E.g. (Company} -> {CEO}
Microsoft Satya Nadella 51
• CEO is not a subset of Company, Google Sundar Pichai 46
• and hence it's non-trivial FD Apple Tim Cook 57

Rules for FD
• Rule‐01:
• A functional dependency X → Y will always hold if all the values of X are unique A B C D E
(different) irrespective of the values of Y.
5 4 3 2 2
• For the given table
8 5 3 2 1
• The following functional dependencies will always hold since all 1 9 3 3 5
the values of attribute ‘A’ are unique‐
• A→B 4 7 3 3 8
• A → BC
• A → CD
• A → BCD
• A → DE
• A → BCDE
• Following functional dependency will always hold‐
• A → Any combination of attributes A, B, C, D, E
• Similar will be the case for attributes B and E.

13
 24‐10‐2024

Rules for FD
• Rule‐02: A B C D E

• A functional dependency X → Y will always hold if all the 5 4 3 2 2

values of Y are same irrespective of the values of X. 8 5 3 2 1

• The following functional dependencies will always hold 1 9 3 3 5

since all the values of attribute ‘C’ are same‐ 4 7 3 3 8
• A→C
• AB → C
• ABDE → C
• DE → C
• AE → C
• In general, we can say following functional dependency will
always hold true‐
• Any combination of attributes A, B, C, D, E → C

Rules for FD

• Rule‐03:
• For a functional dependency X → Y to hold, if two tuples in the table agree on
the value of attribute X, then they must also agree on the value of attribute Y.
• Rule‐04:
• For a functional dependency X → Y, viola on will occur only when for two or
more same values of X, the corresponding Y values are different.

14
 24‐10‐2024

Inference Rules for FDs

• Given a set of FDs F, we can infer additional FDs that hold whenever
the FDs in F hold
• Armstrong's inference rules
A1. (Reflexive) If Y subset-of X, then X  Y
A2. (Augmentation) If X  Y, then XZ  YZ
(Notation: XZ stands for X U Z)
A3. (Transitive) If X  Y and Y  Z, then X  Z
• A1, A2, A3 form a sound and complete set of inference rules

Additional Useful Inference Rules

• Decomposition
• If X  YZ, then X  Y and X  Z
• Union
• If X  Y and X  Z, then X  YZ
• Psuedotransitivity
• If X  Y and WY  Z, then WX  Z
• Closure of a set F of FDs is the set F+ of all FDs that can be inferred
from F

15
 24‐10‐2024

Inference Rules-
• Reflexivity-
• If B is a subset of A, then A → B always holds.
Transitivity-
• If A → B and B → C, then A → C always holds.
Augmentation-
• If A → B, then AC → BC always holds.
Decomposition-
• If A → BC, then A → B and A → C always holds.
Composition-
• If A → B and C → D, then AC → BD always holds.
Additive-
• If A → B and A → C, then A → BC always holds.

Advantages of Functional Dependency

• Functional Dependency avoids data redundancy.

• Therefore same data do not repeat at multiple locations in that
database
• It helps you to maintain the quality of data in the database
• It helps you to defined meanings and constraints of
databases
• It helps you to identify bad designs
• It helps you to find the facts regarding the database design

16
 24‐10‐2024

FD: Example1
If one set of attributes in a table determines another set of
attributes in the table, then the second set of attributes is said
to be functionally dependent on the first set of attributes.

Example 1

ISBN Title Price Table Scheme:

0-321-32132-1 Balloon $34.00 {ISBN, Title, Price}
0-55-123456-9 Main Street $22.95 FD:
0-123-45678-0 Ulysses $34.00 {ISBN}  {Title}
1-22-233700-0 Visual $25.00 {ISBN}  {Price}
Basic

FD: Examples
Example 2
PubID PubName PubPhone Table Scheme: {PubID, PubName, PubPhone}
1 Big House 999‐999‐9999 FDs:
2 Small House 123‐456‐7890
{PubId}  {PubPhone}
3 Alpha Press 111‐111‐1111
{PubId}  {PubName}
{PubName, PubPhone}  {PubID}
Example 3
AuID AuName AuPhone
1 Sleepy 321‐321‐1111
Table Scheme: {AuID, AuName, AuPhone}
2 Snoopy 232‐234‐1234 FDs:
3 Grumpy 665‐235‐6532 {AuId}  {AuPhone}
4 Jones 123‐333‐3333
{AuId}  {AuName}
5 Smith 654‐223‐3455
{AuName, AuPhone}  {AuID}
6 Joyce 666‐666‐6666

7 Roman 444‐444‐4444

17
 24‐10‐2024

FD – Example: Review Paper

Database to track reviews of papers submitted to an academic
conference. Prospective authors submit papers for review and
possible acceptance in the published conference proceedings.
Details of the entities
• Author information includes a unique author number, a name, a mailing
address, and a unique (optional) email address.
• Paper information includes the primary author, the paper number, the
title, the abstract, and review status (pending, accepted,rejected)
• Reviewer information includes the reviewer number, the name, the
mailing address, and a unique (optional) email address
• A completed review includes the reviewer number, the date, the paper
number, comments to the authors, comments to the program
chairperson, and ratings (overall, originality, correctness, style, clarity)

FD – Example: Review Paper

• Author information includes a unique author number, a
name, a mailing address, and a unique (optional) email
address.
• AuthNo  AuthName, AuthEmail, AuthAddress
• AuthEmail  AuthNo
• Paper information includes the primary author, the paper
number, the title, the abstract, and review status (pending,
accepted,rejected)
• PaperNo  Primary‐AuthNo, Title, Abstract, Status

18
 24‐10‐2024

FD – Example: Review Paper

• Reviewer information includes the reviewer number, the
name, the mailing address, and a unique (optional) email
address
• RevNo  RevName, RevEmail, RevAddress
• RevEmail  RevNo
• A completed review includes the reviewer number, the date,
the paper number, comments to the authors, comments to
the program chairperson, and ratings (overall, originality,
correctness, style, clarity)
• RevNo, PaperNo  AuthComm, Prog‐Comm, Date,
Rating1, Rating2, Rating3, Rating4, Rating5

Closure of an Attribute Set-

 The set of all those attributes which can be functionally determined from an attribute set
is called as a closure of that attribute set
 Closure of a set F of FDs is the set F+ of all FDs that can be inferred from F
 Closure of attribute set {X} is denoted as {X}+.

19
 24‐10‐2024

Find Closure of an Attribute Set-

Step-01:

Add the attributes contained in the attribute set for which closure is being
calculated to the result set.
Step-02:

Recursively add the attributes to the result set which can be functionally
determined from the attributes already contained in the result set.

Closure Set : Example 1

• Given R ( A , B , C , D , E , F , G )
• Given the Functional Dependencies
• A → BC
• BC → DE
• D→F
• CF → G

20
 24‐10‐2024

Closure of attribute A
• A → BC
• BC → DE
• D→F
• CF → G
A+ = { A }
={A,B,C} ( Using A → BC )
={A,B,C,D,E} ( Using BC → DE )
={A,B,C,D,E,F} ( Using D → F )
={A,B,C,D,E,F,G} ( Using CF → G )

A+ = { A , B , C , D , E , F , G }

Closure of attribute D
• A → BC
• BC → DE
• D→F
• CF → G
Closure of attribute D‐

D+ = { D }
= { D , F } ( Using D → F )
D+ = { D , F }

21
 24‐10‐2024

Closure of an Attribute Set (Cont)

A → BC, BC → DE, D → F, CF → G

Closure of attribute D-

D+ = { D }
= { D , F } ( Using D → F )
Ans : D+ = { D , F }

Closure of attribute {BC}+

A → BC, BC → DE, D → F, CF → G

• Closure of attribute set {B, C}‐

• { B , C }+ = { B , C }
•={B,C,D,E} ( Using BC → DE )
•={B,C,D,E,F} ( Using D → F )
• = { B , C , D , E , F , G } ( Using CF → G )
• Thus,
• { B , C }+ = { B , C , D , E , F , G }

22
 24‐10‐2024

Finding the Keys Using Closure

• Super Key‐
• If the closure result of an attribute set contains all the attributes of the
relation, then that attribute set is called as a super key of that relation.
• Thus, we can say‐
• “The closure of a super key is the entire relation schema.”
• Example‐
• The closure of attribute A is the entire relation schema.
• Thus, attribute A is a super key for that relation.

Finding the Keys Using Closure

• Candidate Key‐
• If there exists no subset of an attribute set whose closure
contains all the attributes of the relation, then that attribute set
is called as a candidate key of that relation.
• Example‐
• No subset of attribute A contains all the attributes of the
relation.
• Thus, attribute A is also a candidate key for that relation.

23
 24‐10‐2024

Closure set : Example 2

• Consider the given functional dependencies‐

• AB → CD
• AF → D
• DE → F
• C→G
• F→E
• G→A

Find :

• { CF }+
• { BG }+
• { AF }+
• { AB }+

AB → CD, AF → D, DE → F, C → G, F → E, G → A

{ CF }+ = { C , F }
={C,F,G} ( Using C → G )
={C,E,F,G} ( Using F → E )
={A,C,E,E,F} ( Using G → A )
={A,C,D,E,F,G} ( Using AF → D )

{ BG }+ = { B , G }
={A,B,G} ( Using G → A )
={A,B,C,D,G} ( Using AB → CD )

24
 24‐10‐2024

AB → CD, AF → D, DE → F, C → G, F → E, G → A

{ AF }+ = { A , F }
={A,D,F} ( Using AF → D )
={A,D,E,F} ( Using F → E )

{ AB }+ = { A , B }
={A,B,C,D} ( Using AB → CD )
={A,B,C,D,G} ( Using C → G )

Closure set of Attribute : Example

R (A, B, C) set of attribute having

A B, B  C transactions
Find closure of all set of the attribute?
Solve: Given, transaction
{A} --- > {A, B, C}
+

{B} --- > {B, C}

+

{C} --- > {C}

+

25
 24‐10‐2024

Equivalence of sets of FDs.

• E is covered by F if every FD in E is also in F+, i.e., every FD in E can be inferred from F.

• E and F are equivalent if E+ = F+, i.e, E covers F and F covers E.

51

Equivalence of FD set : Example

F:
A  C, G:
R (A, C, D, E, H) AC  D, A  CD,
E AD, E  AH
Two set of FDs are given EH

Which of the following holds true

Conditions:
a) F is the subset of G, ? ( G ⊇ F ) (G Covers F)
b) G is the subset of F (F ⊇ G) (F Covers G)
c) F is equal to G (F = G)
d) F is not equal to G (F<>G)

26
 24‐10‐2024

Equivalence of FD set : Example (Cont)

Here, first we find closure of all the attributes:
F: {A}+ = {A, C, D}
{AC}+ = {A, C, D}
{E}+ = {A, C, D, E, H}

G: {A}+ {A, C, D}
{E}+ {A, D, C, E, H}

Equivalence of FD set : Example (Cont)

1.F is the subset of G:
• True
• because in F & G : {A}+ and {E}+ have same set of attribute
• where {AC}+closure is same as {A}+
• means F is the subset of G
• G Covers F

2.G is the subset of F:

• True,
• similarly to the first Condition F & G functions all attribute closure are
same means G is a subset of F
• F covers G

27
 24‐10‐2024

Equivalence of FD set : Example (Cont)

3. F is equal to G:
• If F is the subset of G and G is the subset of F means
• F Covers G and G covers F so
• F is equal to G

4. F is not equal to G:
• In the third condition, we have proved F is equal to G.
• So, this condition is false.

Irreducible set of functional dependency

Also known as
• Canonical Cover
• Canonical Set
• Canonical form
• Minimal Set of FDs

56

28
 24‐10‐2024

Canonical Cover
• Whenever a user updates the database, the system must check violation of any of
the FDs

• In case of the violation in the new database state, the system must roll back

• Working with a huge set of FDs can cause unnecessary added computational time

• A canonical cover of a set of functional dependencies F is a simplified set of

functional dependencies that has the same closure as the original set F.

Canonical Cover
• F is minimal if
‐ every dependency in F has a single attribute for its right hand side;
‐ we cannot remove any FD from F and still have a set of FDs
equivalent to F;
‐ we cannot replace any FD X  A in F with a FD Y  A where
Y  X and still have a set of FDs equivalent to F.

• Minimal set: a standard or canonical form with no redundancies.

• A minimal cover of F is
• Fmin : a minimal set of dependencies, that is equivalent to F.

58

29
 24‐10‐2024

Extraneous attributes
• If Removal of any attribute A of a FD without changing the closure of
the set of FDs
• A is Extraneous

Canonical cover

• A canonical cover F’ of a set of functional dependencies F such that

ALL the following properties are satisfied:
• F logically implies all dependencies in F’.
• F’ logically implies all dependencies in F.
• No functional dependency in F’ contains an extraneous attribute.
• Each left side of a functional dependency in F’ is unique.
• E.g. There are no two dependencies
• A B and PQ in such that AP

30
 24‐10‐2024

Extraneous Attribute
For given set of FDs find the Extraneous Attributes
x  w, wz  y, y  xz, xz  w
• Only FDs need to be considered are, with multiple attributes on left

wzY
• {wz}+={w,x,y,z}
• {w}+={w}
• {z}+={z}
All three Closures are unique
No Extraneous Attribute

Extraneous FD (Example)
For the Given set of Fds find one Extraneous FD (transaction) and one non‐
Extraneous Transaction
x  w , wz  x, wz y, y  w, y  x, y  z
xw
Including the transaction
{x}+={x,w}
Excluding the transaction
{x}+={x}
Closure are different in both cases so we can’t ignore this transaction
xw not an Extraneous transaction

31
 24‐10‐2024

Extraneous FD (Example) (cont)

x  w , wz  x, wz y, y  w, y  x, y  z

wz  x
• Including the transaction
{wz}+={x,y,w,z}
• Excluding the transaction
{wz}+={w,x,y,z}
• Closure is same in both cases so, we ignore this transaction.
• Wzx is an Extraneous transaction

Canonical cover (Minimal Cover)

• Algorithm : Find a minimal cover G for F.
1. G := f;
2. Replace each FD X  A1, A2,…, AK in G by the k FDs X  A1, X  A2,
X  AK;
3. (Find Extraneous Attribute)
for each FD X  A in G
for each attribute B X
if (X – B)+ with‐respect‐to G contains A
then replace X  A with X – {B}  A in G;
4. (Find Extraneous FDs)
For each FD X  A in G
if X+ with‐respect‐to G‐{X  A} contains A
then remove X  A from G;
• There is at least one minimal cover for any F, maybe several. 64

32
 24‐10‐2024

Canonical Cover: Example1

Example:
Given Relation R (w, x, y, z) Find the Minimal Set of FDs
• x w
• wz  xy
• y  wxz
Solve:
Step 1: Decompose all the transactions:
• x w
• wz  x
• wz  y
• y w
• y x
• y z
Step 2 : Find Extraneous Transection

Example1 : Step2 (Finding Extraneous FDs)

1) x  w
• Including the transaction
{x}+={x,w}
• Excluding the transaction
{x}+={x}
• Closure are different in both cases so we can’t ignore this transaction

33
 24‐10‐2024

Example1 : Step2 (Finding Extraneous FDs)

2) wz  x
• Including the transaction
{wz}+={x,y,w,z}
• Excluding the transaction
{wz}+={w,x,y,z}
• Closure is same in both cases so, we ignore this transaction.
• Remaining transactions:

Example1 : Step2 (Finding Extraneous FDs)

x  w, wz  y y  w y  x y  z
3) wz  y
• Including the transaction
{wz}+={x,y,w,z}
• Excluding the transaction
{wz}+={w,z}
• Closure is different in both cases so, we can’t ignore this transaction.

34
 24‐10‐2024

Example1 : Step2 (Finding Extraneous FDs)

x  w, wz  y y  w y  x y  z
4) y  w
• Including the transaction
{y}+={x,y,w,z}
• Excluding the transaction
{y}+={w,x,y,z}
• Closure are same in both cases so we ignore this transaction.
Remaining Transactions
x  w, wz  y y  x y  z

Example1 : Step2 (Finding Extraneous FDs)

x  w, wz  y y  x y  z
5) y  x
• Including the transaction
{y}+={x,y,w,z}
• Excluding the transaction
{y}+={y,z}
• Closure are different in both cases so we can’t ignore this transaction.

35
 24‐10‐2024

Example1 : Step2 (Finding Extraneous FDs)

• 6) y  z
• Including the transaction
{y}+={x,y,w,z}
• Excluding the transaction
{y}+={w,x,y}
• Closure are different in both cases so we can’t ignore this transaction.

Example1 : Step2 (Finding Extraneous FDs)

After Step 2: Set of all irreducible transactions :
• x w
• wz  y
• y  x
• y z

Step 3: (Remove Extraneous Attributes)

Find closure of each attribute of wz ‐‐‐ > y
to find Extrenous Attribute

36
 24‐10‐2024

Example1 : Finding Extraneous Attributes

• Find closure of each attribute of wz ‐‐‐ > y for cross check its value are
same or different.
{wz}+={w,x,y,z}
{w}+={w}
{z}+={z}
• Closure are different so now we can say that it is in the reducible form.
• The, the final transactions are:
x w
wz  y
y  xz

Canonical Cover : Effect on Database Design

• Help to check the consistency after each update in the database
design
• After update FDs should not be violated
• In case of violation
• the system must roll back
• Extra FDs will result in extra tables will cause unnecessary added
computational time

37
 24‐10‐2024

Example : 2 (Canonical Cover)

For the relation R(A,B,C) consider the following set F of functional dependencies:
F: { A  BC, B  C, A  B, AB  C}

Find canonical cover:

Example 2 (cont)
1. Decomposition
AB
A C
BC
AB
AB  C

2. Remove redundant FDs

AB
A C
BC
AB  C

38
 24‐10‐2024

Example 2 (cont)
3. Find closure of all Transactions
a. AB
Including AB
A+ = {A, B,C}
Excluding AB
A+ = {A, C}
Not same so cannot be ignored
b. A C
including AC
A+ = { A, B, C}
Excluding AC
A+ = { A,B,C}
Same so can be ignored

Remaining FDs
A  B B  C AB  C

Example 2 (cont)
3. Find closure of all Attributes (cont)
A  B B  C AB  C
c. BC
including BC
B+= { B,C}
Excluding BC
B+={B}
Not same so cannot be ignored
d. ABC
including ABC
AB+ = {A,B,C}
Excluding AB C
AB+ = {A,B,C}
Same so can be ignored

Remaining FDs
AB BC

39
 24‐10‐2024

Example 2 (cont)
4. Removing Extraneous Attributes

As all Fds LHS is singleton

No Extrenaous Attributes

Canonical Cover :
AB
BC
Validation: Same as the original Fds.
A+ = {A,B,C}
B+ = {B,C}
C+ = {C}

Example 2

Given set of FD {
F={A  BC,CD  E,B  D,E A}

40
 24‐10‐2024

F={A  BC,CD  E,B  D,E A}

1. Unique determinants of each FD in F

2. No extraneous attribute in any of the FD (left or right)
3. canonical cover F’ is equal to F.

Note: There can be more than one canonical cover F’ of a set F of

functional dependencies.

Example 4
Check whether a set of FDs F and G, weather F canonically cover G or not?

F = { A B, AB C, D  AC, D  E}
G = { A  BC, D  AB }

Find Canonical Cover of Both the FD set

41
 24‐10‐2024

F = { A B, AB C, D  AC, D ‐‐> E,}

Step 1:
• Create a singleton right hand side

•F={
AB
AB  C
DA
DC
DE
}

F = { A B, AB C, D  AC, D ‐‐> E,}

Step 2: Remove all extraneous attributes
AB C
• A+ = {A,B}
• B + = {B}
• B is Subset of A
• B can be determined from A so remove B from the AB  C

Resultant FDs
• F = {A  B, A  C, D  A, D  C, D  E }

42
 24‐10‐2024

F = {A  B, A  C, D  A, D  C, D  E}

Step 3: Remove all extraneous FDs.

AB AC DA DC DE
Including Including Including Including Including
A+ = {B,C} A+ = {A,C} D+={A,B,C,D,E} D+ = {A,B,C,D,E} D+ = {A,B,C,D,E}
Excluding Excluding Excluding Excluding Excluding
A+ = {A} AB+ = {A} D+ = {C,D,E} D+ = {A,B,C,D,E} D+ = {A,B,C,D}

Can be removed

Canonical Cover =
F = {A  B, A C, D  A, D  E }

G = { A  BC, D  AB }
1. Create a singleton right hand side. (Single RHS)
G = { A  B, A  C, D  A, D  B, }
2. Remove all extraneous attributes.
• Since the LHS of all f.d.’s contains only 1 attribute, there is no extraneous
attribute possible.
3. Remove all redundant functional dependencies.
• the closure of the LHS in all cases, f.d. D B is redundant as it can be obtained
through a combination of D  A and A  B.
4. = {A  B, A  C, D  A, }

• All FDs of G are already covered in F,

• we conclude that F covers G.

43