Closure of Attribute –

Step-1: Add the attributes which are present on Left Hand Side in the original functional
dependency.

Step-2: Now, add the attributes present on the Right-Hand Side of the functional dependency.

Step-3: With the help of attributes present on Right Hand Side, check the other attributes that
can be derived from the other given functional dependencies. Repeat this process until all the
possible attributes which can be derived are added in the closure.

Example-1: Consider the table student_details having (Roll_No, Name, Marks, Location) as
the attributes and having two functional dependencies.

FD1: Roll_No -> Name, Marks

FD2: Name -> Marks, Location

Step-1: Add attributes present on the LHS of the first functional dependency to the closure.
{Roll_no}+ = {Roll_No}

Step-2: Add attributes present on the RHS of the original functional dependency to the
closure.

{Roll_no}+ = {Roll_No, Marks}

Step-3: Add the other possible attributes which can be derived using attributes present on
the RHS of the closure. So Roll_No attribute cannot functionally determine any attribute but
Name attribute can determine other attributes such as Marks and Location using
2nd Functional Dependency(Name -> Marks, Location).

Therefore, complete closure of Roll_No will be:

{Roll_no}+ = {Roll_No, Marks, Name, Location}

Similarly, we can calculate closure for other attributes too i.e “Name”.

Step-1: Add attributes present on the LHS of the functional dependency to the closure.
{Name}+ = {Name}

Step-2: Add the attributes present on the RHS of the functional dependency to the closure.
{Name}+ = {Name, Marks, Location}

Step-3: Since, we don’t have any functional dependency where “Marks or Location” attribute
is functionally determining any other attribute, we cannot add more attributes to the closure.
Hence complete closure of Name would be:
{Name}+ = {Name, Marks, Location}
NOTE: We don’t have any Functional dependency where marks and location can functionally
determine any attribute. Hence, for those attributes we can only add the attributes
themselves in their closures. Therefore,
{Marks}+ = {Marks}
and
{Location}+ = {Location}

Example-2: Consider a relation R (A, B, C, D, E) having below mentioned functional

dependencies.
FD1: A -> BC
FD2: C -> B
FD3: D -> E
FD4: E -> D
Now, we need to calculate the closure of attributes of the relation R. The closures will be:

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

Closure Of Functional Dependency: Calculating Candidate Key

• “A Candidate Key of a relation is an attribute or set of attributes that can determine

the whole relation or contains all the attributes in its closure."
• Let’s try to understand how to calculate candidate keys.

Example-1: Consider the relation R (A, B, C) with given functional dependencies :

FD1: A -> B
FD2: B -> C
Now, calculating the closure of the attributes as:

{A}+ = {A, B, C}
{B}+ = {B, C}
{C}+ = {C}
Clearly, “A” is the candidate key as, its closure contains all the attributes present in the
relation “R”.

Example-2: Consider another relation R (A, B, C, D, E) having the Functional dependencies:

FD1: A -> BC
FD2: C -> B
FD3: D -> E
FD4: E -> D
Now, calculating the closure of the attributes as:

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

In this case, a single attribute is unable to determine all the attribute on its own like in
previous example. Here, we need to combine two or more attributes to determine the
candidate keys.

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

{A, E}+ = {A, B, C, D, E}
Hence, "AD" and "AE" are the two possible keys of the given relation “R”. Any other
combination other than these two would have acted as extraneous attributes.

NOTE: Any relation “R” can have either single or multiple candidate keys.

Closure Of Functional Dependency: Key Definitions

1. Prime Attributes: Attributes which are indispensable part of candidate keys. For
example: “A, D, E” attributes are prime attributes in above example-2.
2. Non-Prime Attributes: Attributes other than prime attributes which does not take part
in formation of candidate keys. For example.
3. Extraneous Attributes: Attributes which does not make any effect on removal from
candidate key.

For example: Consider the relation R (A, B, C, D) with functional dependencies:

FD1: A -> BC
FD2: B -> C
FD3: D -> C
Here, Candidate key can be “AD” only. Hence,

Prime Attributes: A, D.

Non-Prime Attributes: B, C

Extraneous Attributes: B, C (As if we add any of the to the candidate key, it will remain
unaffected). Those attributes, which if removed does not affect closure of that set.

Extraneous attributes: An attribute of a functional dependency is said to be extraneous if

we can remove it without changing the closure of the set of functional dependencies.

Canonical cover: A canonical cover Fc of a set of functional dependencies F such that ALL
the following properties are satisfied:
 • F logically implies all dependencies in Fc.
• Fc logically implies all dependencies in F.
• No functional dependency in Fc contains an extraneous attribute.
• Each left side of a functional dependency in Fc is unique. That is, there are no
two dependencies α1 -> β1 and α2 -> β2 in such that α1 -> α2
In DBMS,
• A canonical cover is a simplified and reduced version of the given set of
functional dependencies.
• Since it is a reduced version, it is also called as Irreducible set.

Characteristics-

• Canonical cover is free from all the extraneous functional dependencies.

• The closure of canonical cover is same as that of the given set of functional
dependencies.
• Canonical cover is not unique and may be more than one for a given set of
functional dependencies.

Formal definition of Extraneous Attribute

• In a set of functional dependencies F, consider a functional dependency α → β.
• Attribute A is extraneous in α, if A ∈ α, and F logically implies (F − {α → β}) ∪ {(α −
A) → β}.
• Attribute A is extraneous in β, if A ∈ β, and the set of functional dependencies
(F − {α →β}) ∪ {α → (β − A)} logically implies F.

For example, suppose F contains AB → CD, A → E, and E → C. To check if C is extraneous in

AB → CD, we compute the attribute closure of AB under F’ = {AB → D, A → E, and E → C}. The
closure is ABCDE, which includes CD, so we infer that C is extraneous.

Let us consider a relation R with schema R (A, B, C) and set of functional dependencies F = {
AB → C, A → C }. The closure for F is F+ = {AB → C, A → C}.
In AB → C, B is extraneous attribute. The reason is, there is another FD A → C, which means
when A alone can determine C, the use of B is unnecessary (redundant).
Now, we can find the closure for the new set of functional dependencies, which is same as F+.
Hence, we can declare that B is extraneous.

Let us consider a relation R with schema R (A, B, C, D) and a set of functional dependencies F
= { A → BC, B → C, AB → D }. What extraneous attributes are present in FDs of F?
C is extraneous in the RHS (Right Hand Side) of A → BC. Because, A can determine B (A → BC),
B can determine C (B → C). Hence, A can determine C also (Transitivity rule). Hence, it is
inappropriate to repeat or check an attribute many times.
B is extraneous in the LHS of AB → D. The reason is, from A → BC, it is clear that A determines
B. it would indirectly mean that if you know A and B then you know D also.
Finding Extraneous Attributes
Let us consider a set of functional dependencies F and any functional dependency of the
form α → β. Assume that α and β are set of one or more attributes.
Case 1 (LHS): To find if an attribute A in α is extraneous or not. That is, to test if an attribute
of Left-Hand Side of a functional dependency is Extraneous or not.
Step 1: Find ({α} – A)+ using the dependencies of F.
Step 2: If ({α} – A)+ contains all the attributes of β, then A is extraneous.

Case 2 (RHS): To find if an attribute A in β is extraneous or not. That is, to test if an attribute
of Right-Hand Side of a functional dependency is Extraneous or not.
Step 1: Find α+ using the dependencies in F’ where F’ = (F – {α → β}) U { α → (β – A) }.
Step 2: If α+ contains A, then A is extraneous.

Example 1 for LHS:

Given F = {P→Q, PQ→R}. Is Q extraneous in PQ→R?
In this example, we are looking for a LHS attribute. Hence, let us use Case 1 discussed above.
Step 1: Find ({α} – A)+ using the dependencies of F.
Here, α is PQ. So find (PQ – Q)+, ie., P+ (closure of P).
From F, if you know P, then you know Q (from P→Q).
If you know both P and Q then you know R (from PQ→R).
Hence, the closure of P is PQR.
Step 2: If ({α} – A)+ contains all the attributes of β, then A is extraneous.
(PQ – Q)+ contains R. Hence, Q is extraneous in PQ→R.

Example 2 for RHS:

Given F = {P→QR, Q→R}. Is R extraneous in P→QR?
In this example, we are looking for a RHS attribute. Hence, let us use the Case 2 given above.
Step 1: Find α+ using the dependencies in F’ where F’ = (F – {α → β}) U { α → (β – A) }.
Let us find F’ as stated above.
F’ = (F – {α → β}) U { α → (β – A) } = ({P→QR, Q→R} – {P→QR}) U {P→(QR-R)}
= ({Q→ R} U {P→Q})
F’ = {Q→R, P→Q}
Here, α is P. So find (P)+, ie., closure of P using the F’ which we found.
 From F’, if you know P, then you know Q (from P→Q).
If you know Q then you know R (from Q→R).
Hence, the closure of P is PQR.
Step 2: If α+ contains A, then A is extraneous.
P+ contains R. Hence, R is extraneous in P→QR.

Steps To Find Canonical Cover-

Step-01:
Write the given set of functional dependencies in such a way that each functional
dependency contains exactly one attribute on its right side.
Example-
The functional dependency X → YZ will be written as-
X→Y
X→Z

Step-02:
• Consider each functional dependency one by one from the set obtained in Step-01.
• Determine whether it is essential or non-essential.
To determine whether a functional dependency is essential or not, compute the closure of
its left side-
• Once by considering that the particular functional dependency is present in the set
• Once by considering that the particular functional dependency is not present in the
set
Then following two cases are possible-
Case-01: Results Come Out to be Same-
If results come out to be same,
• It means that the presence or absence of that functional dependency does not
create any difference.
• Thus, it is non-essential.
• Eliminate that functional dependency from the set.
NOTE-
• Eliminate the non-essential functional dependency from the set as soon as it is
discovered.
• Do not consider it while checking the essentiality of other functional dependencies.
Case-01: Results Come Out to be Different-
If results come out to be different,
• It means that the presence or absence of that functional dependency creates a
difference.
• Thus, it is essential.
• Do not eliminate that functional dependency from the set.
• Mark that functional dependency as essential.

Step-03:
• Consider the newly obtained set of functional dependencies after performing Step-
02.
• Check if there is any functional dependency that contains more than one attribute
on its left side.
Then following two cases are possible-
Case-01: No-
• There exists no functional dependency containing more than one attribute on its left
side.
• In this case, the set obtained in Step-02 is the canonical cover.
Case-01: Yes-
• There exists at least one functional dependency containing more than one attribute
on its left side.
• In this case, consider all such functional dependencies one by one.
• Check if their left side can be reduced.
Use the following steps to perform a check-
• Consider a functional dependency.
• Compute the closure of all the possible subsets of the left side of that functional
dependency.
• If any of the subsets produce the same closure result as produced by the entire left
side, then replace the left side with that subset.
After this step is complete, the set obtained is the canonical cover.
Example -
The following functional dependencies hold true for the relational scheme R ( W , X , Y , Z ) –
X→W
WZ → XY
Y → WXZ
Write the irreducible equivalent or canonical cover for this set of functional dependencies.
Step-01:
Write all the functional dependencies such that each contains exactly one attribute on its
right side-
X→W
WZ → X
WZ → Y
Y→W
Y→X
Y→Z
Step-02:
Check the essentiality of each functional dependency one by one.
For X → W:
• Considering X → W, (X)+ = { X , W }
• Ignoring X → W, (X)+ = { X }
Now,
• Clearly, the two results are different.
• Thus, we conclude that X → W is essential and cannot be eliminated.

For WZ → X:
• Considering WZ → X, (WZ)+ = { W , X , Y , Z }
• Ignoring WZ → X, (WZ)+ = { W , X , Y , Z }
Now,
• Clearly, the two results are same.
• Thus, we conclude that WZ → X is non-essential and can be eliminated.

Eliminating WZ → X, our set of functional dependencies reduces to-

X→W
WZ → Y
Y→W
Y→X
Y→Z
Now, we will consider this reduced set in further checks.

For WZ → Y:

• Considering WZ → Y, (WZ)+ = { W , X , Y , Z }
• Ignoring WZ → Y, (WZ)+ = { W , Z }

Now,
• Clearly, the two results are different.
• Thus, we conclude that WZ → Y is essential and cannot be eliminated.

For Y → W:
• Considering Y → W, (Y)+ = { W , X , Y , Z }
• Ignoring Y → W, (Y)+ = { W , X , Y , Z }
Now,
• Clearly, the two results are same.
• Thus, we conclude that Y → W is non-essential and can be eliminated.

Eliminating Y → W, our set of functional dependencies reduces to-

X→W
WZ → Y
Y→X
Y→Z
For Y → X:
• Considering Y → X, (Y)+ = { W , X , Y , Z }
• Ignoring Y → X, (Y)+ = { Y , Z }
Now,
• Clearly, the two results are different.
• Thus, we conclude that Y → X is essential and cannot be eliminated.

For Y → Z:
• Considering Y → Z, (Y)+ = { W , X , Y , Z }
• Ignoring Y → Z, (Y)+ = { W , X , Y }

Now,
 • Clearly, the two results are different.
• Thus, we conclude that Y → Z is essential and cannot be eliminated.

From here, our essential functional dependencies are-

X→W
WZ → Y
Y→X
Y→Z
Step-03:
• Consider the functional dependencies having more than one attribute on their left
side.
• Check if their left side can be reduced.

In our set,
• Only WZ → Y contains more than one attribute on its left side.
• Considering WZ → Y, (WZ)+ = { W , X , Y , Z }

Now,
• Consider all the possible subsets of WZ.
• Check if the closure result of any subset matches to the closure result of WZ.
(W)+ = { W }
(Z)+ = { Z }
Clearly,
• None of the subsets have the same closure result same as that of the entire left side.
• Thus, we conclude that we cannot write WZ → Y as W → Y or Z → Y.
• Thus, set of functional dependencies obtained in step-02 is the canonical cover.

Finally, the canonical cover is-

X→W
WZ → Y
Y→X
Y→Z