Normalization - Solved exercises Home

Set of solved exercises in Normalization / Normalization Solved Examples / How to find candidate keys, and primary keys in database? / Sets of examples to find the keys of a tables / Process of finding Key in a database - Examples

INSERT, DELETE, MODIFY Anomalies Identification

• Identify the anomalies present in the given relational table

Primary key / Candidate key identification

• SET 1 - What functional dependencies are hold?

• SET 2 - What functional dependencies are hold?

• Find all the candidate keys 

• Find all the candidate keys - One more method - Solved exercise 

• Find all the candidate keys - Exercise

   

 Primary key / Candidate key identification

• SET 1 - Finding key of a given relation

• SET 2 - Finding key of a given relation

• SET 3 - Finding key of a given relation

• SET 4 - Finding key of a given relation

• SET 5 - Finding key of a given relation

• SET 6 - Finding key of a given relation

• SET 7 - Finding key of a given relation

• SET 8 - Finding key of a given relation

  ads.click()
  Normalization Solved Exercises

• SET 9 - Finding key of a given relation

• SET 10 - Finding key of a given relation

• SET 11 - Finding all candidate keys of a table

  Normalization

• SET 1 - Normalizing upto 3NF - User table

• SET 2 -Normalizing upto BCNF

• SET 3 -Normalizing upto BCNF 2

• SET 4 -Normalizing upto BCNF 3

• SET 5 -Normalizing upto BCNF 4

• SET 6 -Normalizing upto BCNF 5 

• SET 7 - Is this relation in 2NF?

• Exercise 8 - Normalize the table to 3NF

• Exercise 9 - Normalize the table to 3NF

• Exercise 10 - Normalize the table to BCNF

• Exercise 11 - Normalize the table to BCNF 

• Exercise 12 - Normalize the table to 3NF 

Find the functional dependencies that violate a normal form

• Exercise 1 - FDs that violate BCNF 

• Exercise 2 - Find FDs, Keys, and normalize to 3NF

Normalization Solved Questions

• Solved questions - Simple

Decomposition - Lossy or lossless

• Decomposition exercise 1 
• Decomposition exercise 2
• Decomposition exercise 3
•  

Equivalent Functional Dependencies

• Find whether sets of FDs are equivalent or not 01

• Find whether sets of FDs are equivalent or not 02

• Find whether sets of FDs are equivalent or not 03

normalization solved exercises

how to normalize a relation to second normal form (2nf)
how to normalize a relation to third normal form (3nf)
how to normalize a relation to Boyce-code normal form (BCNF)
find minimal cover
find canonical cover
lossless and lossy join decomposition
find candidate keys and super keys
what is candidate key
find functional dependencies
transitive functional dependency
armstrong's axioms

Finding Extraneous Attribute in DBMS

Finding Extraneous Attributes in DBMS / How to find extraneous attributes in the process of Normalization? / Finding Extraneous Attributes Examples / Extraneous attribute finding as part of finding Canonical cover

Extraneous Attribute

If we are able to remove an attribute from a functional dependency without changing the closure of the set of functional dependencies, that attribute is called as Extraneous Attribute.

[Dictionary meaning of ‘Extraneous’ is ‘irrelevant’, ‘inappropriate’, or ‘unconnected’]

Assume a set of functional dependencies F, and the closure of set of functional dependencies F⁺. Also, assume that we remove an attribute from any of the FDs under F and find the closure of new set of functional dependencies. Let us mention the new closure of set of functional dependencies as F1⁺.  If F⁺ equals the newly constituted closure F1⁺, then the attribute which has been removed is called as Extraneous Attribute. In other words, that attribute does not violate any of the functional dependencies.

Example 1:

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.

Example 2:

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.

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.

[Source: Database System Concepts – Korth]

Go to How to find closure of set of functional dependencies? page

Go to Normalization - Solved Exercises page

External source to find Extraneous attributes/ Canonical Cover

Go to Index Page

What is extraneous attributes?

Role of extraneous attributes in normalization process

How to find extraneous attributes in database normalization

Why do we need to find extraneous attributes in finding closures?

Closure of functional dependencies and extraneous attributes

Relationship between extraneous attributes and canonical cover

How to find key of a given table? - An alternate way

Closure of Attribute Set - Alternate Way / Closure of Attribute Set Algorithm / How do we find a key given a set of attributes? / How to find super key? / Attribute Closure in DBMS / Closure of Attributes Set Example

To find the Closure of attribute/attribute set A, we have to do the following;

          a) First of all find the set of all functional dependencies (F⁺) that are implied by a given set of functional dependencies (F).

            b) Then take all the FDs from F⁺ that has A on the left hand side of the arrow.

          C) Finally, find the union of right hand side of all those functional dependencies that have A on the left hand side. If the union includes all the attributes of the given relation R, then A is the key for the relation.

Example:

Assume a relation schema R = (A, B, C) with the set of functional dependencies F = {A → B, B → C}. Now, we can find the closure of attribute A as follows, according to this method;

Step 1: Find the F⁺.

F+ = { A → B, B → C, A → C } [A → C is derived using Transitivity rule]

Step 2: A → B, and A → C are the two functional dependencies that have common left hand side attribute A.

Step 3: The union of right hand sides ends with A → BC. Hence, A is the one of the keys for the relation R.

Advantages:

• Simple.

Drawbacks:

• The number of functional dependencies in F⁺ can be as many as 2ⁿ⁺¹ where n is the number of attributes. It costs too much of time.

Very very useful link in knowing closure, canonical cover, normalization etc.

Closure of Set of Functional Dependencies

Closure / Closure of Set of Functional Dependencies / Different ways to identify set of functional dependencies that are holding in a relation / what is meant by the closure of a set of functional dependencies illustrate with an example

Introduction

Functional Dependencies are the important components in database design which would help us in identifying bad designs. Another important functionality of FDs is that they really express the facts about the database we are designing. Hence, it is very vital to identify all the possible set of functional dependencies hold in a table (relation).

What are the ways to identify functional dependencies?

1. Very simple way is to look for the dependency of one or more columns on the other columns using a sample data set.
The problem here is that the data set we are about to use is not complete. Hence, for some attributes we can anticipate the future set of values to be stored. But for most of the attributes, it is impossible. Especially, when a table is of more number of columns, it’s a kind of impossibility to express all the FDs holding by all the attributes. Hence, the set of functional dependencies which one could infer from the table directly is incomplete.

2. The second way is to identify the basic set of functional dependencies holding on a table which are easily visible and error free. Then, apply closure of set of Functional dependencies rules to derive the other hidden functional dependencies holding on the relation. We would mention those hidden functional dependencies as “functional dependencies that are logically implied”. When we are able to identify all the set of FDs holding by a relation, then we could say that the set F of FDs is complete.

In this post let us discuss about Closure of Set of Functional Dependencies.

Closure of Set of Functional Dependencies

"The closure of F, denoted as F+, is the set of all regular Functional Dependencies that can be derived from F".

This is used to discover some of the hidden functional dependencies so as to design a better database.

Consider the Armstrong's axioms developed by William W.Armstrong. Those axioms provide simpler technique to identify set of other functional dependencies (hidden). Let us list all the axioms along with the additional rules once again.

Reflexivity rule	If X is a set of attributes, and Y is subset of X, then we would say, X → Y.
Augmentation rule	If X → Y, and Z is another set of attributes, then we write XZ → XY.
Transitivity rule	If X → Y, and Y → Z, then X → Z is true.
Union rule	If X → Y and X → Z, then X → YZ is true.
Decomposition rule	Its reverse of Rule 4. If X → YZ, then X → Y, and X → Z are true
Pseudotransitivity rule	If X → Y and ZY → A are true, then XZ → A is also true.

Let us consider set F of functional dependencies hold on a relation R. We can derive additional functional dependencies from the set of given functional dependencies. But, still we may have some more hidden functional dependencies. We could derive some of the additional hidden functional dependencies from F on applying the above listed rules. In other words, we could deduce a new functional dependency from two or more functional dependencies of set F. Suppose, R is a relation with attributes (A, B, C, D, E, F) and with the identified set F of functional dependencies as follows;

F = { A → B, A → C, CD → E, B → E, CD → F }

Let us apply the above listed rules on every functional dependency of F to identify the member of F⁺ (the closure of functional dependency is termed as F⁺, i.e, set F added with new members resulting in F⁺).

1. A → E is logically implied. From our F we have two FDs A → B and B → E. By applying Transitivity rule, we could infer A → E. That is, if A can uniquely determine B and B can uniquely determine E then A can determine E (through B).

2. A → BC is logically implied. It can be inferred from the FDs A → B and A → C using Union rule.

3. CD → EF is logically implied by FDs CD → E and CD → F using Union rule.

4. AD → F is logically implied by FDs A → C and CD → F using Pseudotransitivity rule.

Like this, we can continue identifying the new members for F⁺. The procedure to find set F+ can be written as follows in pseudo code.

F+ = F Repeat                 For each functional dependency FD in F+                                 Apply reflexivity and augmentation rules on f                                 Add the result to F+                 For each pair of functional dependencies f1 and f2 in F+                                 If f1 and f2 can be combined using Transitivity                                                 Add the result to F+ Until F+ does not change any further.

This procedure does not show the additional rules Union, Decomposition, and Pseudotransitivity. The reason is, these additional rules are actually inferred from basic axioms. Also additional rules can be proved using Armstrong’s axioms. The procedure can be stopped when we started to get the functional dependencies already existing in F⁺.

For a relation with set of n attributes, there are 2ⁿ⁺¹ possible functional dependencies. For example, if R has 3 attributes, then 2³⁺¹ = 16 functional dependencies are possible.

Go to Normalization - Solved Exercises page

Go to How to find closure of an attribute? page