Skip to main content

Relational database design


Closure Of Functional Dependency Introduction


The Closure Of Functional Dependency means the complete set of all possible attributes that can be functionally derived from given functional dependency using the inference rules known as Armstrong’s Rules.
If “F” is a functional dependency then closure of functional dependency can be denoted using “{F}+”.

There are three steps to calculate closure of functional dependency. 

These are

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.


Closure Of Functional Dependency Examples


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

Now, We will calculate the closure of all the attributes present in the relation using the three steps mentioned below.

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, Name,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 [icon name="long-arrow-right" class="" unprefixed_class=""] 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,D}


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.

Example1:
Consider the following set F of functional dependencies

F= {
A ->BC
B ->C
A ->B
AB ->C
}

Steps to find canonical cover


There are two functional dependencies with the same set of attributes on the left:
A ->BC
A ->B
These two can be combined to get
A ->BC.
Now, the revised set F becomes:
F= {
A ->BC
B ->C
AB ->C
}

There is an extraneous attribute in AB ->C because even after removing AB ->C from the set F, we get the same closures. This is because B ->C is already a part of F.
Now, the revised set F becomes:
F= {
A ->BC
B ->C
}
C is an extraneous attribute in A ->BC, also A ->B is logically implied by A ->B and B  C (by transitivity).
F= {
A ->B
B ->C
}
After this step, F does not change anymore. So,
Hence the required canonical cover is,
Fc= {
A ->B
B ->C
}

Example 2

Consider another set F of functional dependencies:
F={
A ->BC
CD ->E
B ->D
E ->A
}
The left side of each functional dependency in F is unique.
None of the attributes in the left or right side of any functional dependency is extraneous (Checked by applying definition of extraneous attributes on every functional dependency).
Hence, the canonical cover  is equal to F.

Normalization


Normalization is the process of organizing the data in the database.
Normalization is used to minimize the redundancy from a relation or set of relations. 

It is also used to eliminate the undesirable characteristics like Insertion, Update and Deletion Anomalies.

Normalization divides the larger table into the smaller table and links them using relationship.
The normal form is used to reduce redundancy from the database table.

Types of Normal Form


  • 1NF
  • 2NF
  • 3NF
  • BCNF

First Normal Form


A relation will be 1NF if it contains an atomic value.
It states that an attribute of a table cannot hold multiple values.

It must hold only single-valued attribute.
First normal form disallows the multi-valued attribute, composite attribute, and their combinations.

Example: Relation EMPLOYEE is not in 1NF because of multi-valued attribute EMP_PHONE.

Second Normal Form 2NF


In the 2NF, relational must be in 1NF.
In the second normal form, all non-prime attributes are fully functional dependent on the primary key

Example: Let's assume, a school can store the data of teachers and the subjects they teach. In a school, a teacher can teach more than one subject.


Consider Relation R(A,B,C,D) with functional dependancies
AB->D
B->C
From above relation & FD wecamn find out Candidate Key.

Candidate key for R(A,B,C,D) will be AB.
Because if if we will find (AB)+ then it will be Relation R.
So we can say AB is Candidate Kay.And also it will be the primary key.

Prime Attributes
and Non Prime Attributes


Here A & B are prime attributes because they are part of candidate key.
C & D are non prime attributes.
According to 2NF all non-prime attributes are fully functional dependent on the primary key,

In AB->D the non prime attribute D is fully functionally dependant on Primary key.
But In B->C the non prime attribute C is not fully functionally dependant on AB it is partially dependant on prime attribute.
Therefore relation is not in 2NF.
In 2NF Partial dependency is not allowed.


How to translate table in 2NF


Now lets decompose above relation R(A,B,C,D) .
In first table there will be always contain candidate Key and with those attributes which are entirely dependant on candidate key.

Therefore, R1(ABD) and R2(BC).
Now both tables can satisfy definition of 2NF.
Now in second table B is primary key.
So above relation is in 2NF.

R(ABCD)
AB->C
D->E 

So here Candidate Key will be ABD.
The C is non prime attribute which depends on proper subset of candidate key therefore here partial dependency is present.
So relation is not in 2NF.

Lets decompose relation.
R1(ABD)
R2(ABC)
R3(DE)

Third Normal Form


A relation will be in 3NF if it is in 2NF and not contain any transitive partial dependency.
3NF is used to reduce the data duplication. It is also used to achieve the data integrity.
If there is no transitive dependency for non-prime attributes, then the relation must be in third normal form.

A relation is in third normal form if it holds atleast one of the following conditions for every non-trivial function dependency X → Y.
X is a super key.
Y is a prime attribute, i.e., each element of Y is part of some candidate key.

The Relation R(A,B,C,D) is having following FD 
A->B
B->C

Check whether given relation is in 3NF or not.

Solution

Calculate Candidate key for given relation.
A will be Candidate key for given relation.
Lets Consider first F.D i.e. A->B
Here in this FD A is super key.
So Condition for 3NF is get satisfied. But in FD B->C B is not super key and C is non prime attribute it is not part of candidate key.
Therefore violating definition of 3NF.
Also in above relation transitive dependency is present.
So given relation is not in 3NF.
To convert the given relation in 3NF decompose the relation.
In first table there will be candidate key and its dependant attribute.
So R1(AB),Here A is key attribute.
In second table there will be B & C
S R2(BC),Here B is key attribute.
R1(AB)
R2(BC)
Now,above relation is in 3NF.

Boyce Codd Normal Form BCNF


BCNF is the advance version of 3NF. 
It is stricter than 3NF.
A table is in BCNF if every functional dependency X → Y, X is the super key of the table.
For BCNF, the table should be in 3NF, and for every FD, LHS is super key.
Example: Let's assume there is a company where employees work in more than one department.

Super Key


Super key is set of attributes with the help of which you can uniquely identify a row or tuple in  a table or you can identify all the remaining attributes.

Candidate Key


Minimal super key is candidate key.
The super key is called candidate key if and only if its any proper subset should not be super key. 

Menu card just for you !

Select Your favourite topic to learn.

Labels:

Comments

Post a Comment

Please give us feedback through comments

Trending⚡

Happy birthday Hardik Pandya | In C programming

  Happy birthday Hardik Pandya . Now you are  28 years old. Great achievement you have. Let's we want to talk more about Hardik pandya. He is great cricketer. Pandya is awesome. In this Blog Post we are going to wish pandya " Happy birthday using C program". Let's tune with us till end. Now we have to wish pandya, so we are going to use printf () function printing message to pandya as " Happy birthday Hardik pandya Now you are 28 years old". Hardik pandya was born on 11 October in 1993. Now we are going to declare a variable called as current_age = 2021 - 1993. It calculate current age Of Hardik pandya. See the "Happy birthday pandya" using c programming. If you liked this Blog Post then don't forget to share with your computer science learning friends. Once again " Happy birthday Hardik Pandya sir". Read also Happy Rakshabandhan wish using C program Friendship day 2021 greetings in C
Post a Comment
Read more

What is programming explained in simple words

Hi my dear friends today in this blog post we are going to know what programming is? In simple words I will explain to you programming. Nowadays we are watching real life use of programming. How computers learn to speak, talk and do the specified complex task for us. We are all keen to know what is exactly programming? Programming is the process of creating instructions that a computer can understand and execute. These instructions, also known as code, are written in a programming language that is specific to the task at hand. The history of programming can be traced back to the mid-20th century, with the development of the first electronic computers. The first programming languages were known as machine languages, which were specific to a particular type of computer. As computers became more sophisticated, high-level programming languages were developed, such as FORTRAN and COBOL, which were easier for humans to read and write. These languages allow programmers to write code t
Post a Comment
Read more

check number is prime or odd or even using c program

Here is the c program to check if the user entered number is prime ,even and odd. These few lines of code solve three problems. In the above program we used integer type num variable for storing user entered numbers. Then we used the IF condition statement. That's all. IF condition for even number In the First IF statement we have a logic. If the number is divided by two then the reminder should be 0 then the number is an even number else not an even number. That simple logic is implemented in the first if statement. IF condition for odd number In the second IF statement we Implemented odd number logic. We identify odd numbers just by making little change in even number logic. If the number is divided by two then the reminder should not be a zero. Then the number is odd. That's simple logic used to identify whether a number is odd or not an odd number. IF condition for prime number In the third IF condition we implemented the logic of the prime number. In this IF
Post a Comment
Read more

Graph Data Structure

Graph A graph can be defined as a group of vertices and edges that are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent child relationship. A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G) represents the set of edges which are used to connect these vertices. A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is shown in the following figure. Directed and undirected graph Graph terminology Graph Representation Directed Graph Adjancency Matrix Graph Traversal Depth first search algorithm Directed and undirected graph A graph can be directed or undirected. However, in an undirected graph, edges are not associated with the directions with them. An undirected graph does not have any edges in directions. If an edge exists between ver
Post a Comment
Read more

How to write programs in Bhai language

Bhai Language Bhai language is fun Programming language , with this language you can makes jokes in hindi. Bhai language written in typescript. It's very funny , easy and amazing language. Keywords of this language written in Hindi . Starting and ending of the program Start program with keyword " hi bhai " and end with " bye bhai ". It's compulsory to add this keyword before starting and end on the program. You write your programming logic inside this hi bhai and bye bhai . How to declare variables in Bhai language We use " bhai ye hai variable_name" keyword for declaring variables. In javascript we use var keyword for declaring variables but here you have to use " bhai ye hai " keyword. If you are declaring string then use " " double quotes. You can use Boolean variable like sahi and galat for true and false . How to print output in Bhai language You have to use " bol bhai " keyword for
Post a Comment
Read more