Short Notes: Database Design | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


Types of keys
There are basically four types of keys:
• Candidate Key: Minimal Set of attributes which can be used to identify data 
records uniquely.
• Super key: Set of attributes which can be used to identify data records 
uniquely (may or may not be minimal).
• Foreign Key: Foreign key is basically set of attributes referencing to primary 
key of same relation or some other relation.it allows null values.
• Alternative key: Candidate key other than Primary key. it also allows null 
values.
Schema Refinement/Normalization
Decomposition of complex records into simple records. Normalization reduces 
redundancy using non-loss decomposition principle.
Decomposition
Splitting a relation R into two or more subrelation Ri and R2 such that redundancies 
can be removed. A fully normalized relation must have all the functional 
dependencies such that determiner is a a primary key or a super key.
Decomposition should satisfy: (i) Lossless join, and (ii) Dependency preservence
Lossless Join Decomposition
Join between the subrelations should not create any additional tuples( Spurious 
tuples) or there should not be a case such that more number of tuples in Ri than R2
R c Ri
Page 2


Types of keys
There are basically four types of keys:
• Candidate Key: Minimal Set of attributes which can be used to identify data 
records uniquely.
• Super key: Set of attributes which can be used to identify data records 
uniquely (may or may not be minimal).
• Foreign Key: Foreign key is basically set of attributes referencing to primary 
key of same relation or some other relation.it allows null values.
• Alternative key: Candidate key other than Primary key. it also allows null 
values.
Schema Refinement/Normalization
Decomposition of complex records into simple records. Normalization reduces 
redundancy using non-loss decomposition principle.
Decomposition
Splitting a relation R into two or more subrelation Ri and R2 such that redundancies 
can be removed. A fully normalized relation must have all the functional 
dependencies such that determiner is a a primary key or a super key.
Decomposition should satisfy: (i) Lossless join, and (ii) Dependency preservence
Lossless Join Decomposition
Join between the subrelations should not create any additional tuples( Spurious 
tuples) or there should not be a case such that more number of tuples in Ri than R2
R c Ri
R2 = > (Lossy)
R = Ri
o<
R2 = > (Lossless)
Dependency Preservence: Because of decomposition, there must not be loss of any 
single dependency i.e., if Ft and F2 be the decomposed FD set for Rt and R2, then 
F= Ft U F2.
Functional Dependency (FD): Dependency between the attribute is known as 
functional dependency. Let R be the relational schema and X, Y be the non-empty 
sets of attributes and t1 f t2, ... ,tn are the tuples of relation R. X -? Y {values for X 
functionally determine values for Y}
Trivial Functional Dependency: If X a Y, then X — ? Y will be trivial FD.
Here, X and Y are set of attributes of a relation R.
In trivial FD, there must be a common attribute at both the sides of arrow.
Non-Trivial Functional Dependency: If X fl Y = < p (no common attributes) and X — ? Y 
satisfies FD, then it will be a non-trivial FD.
Case of semi-trivial FD
Sid -? Sid Sname (semi-trivial)
Because on decomposition, we will get 
Sid - * ¦ Sid (trivial FD) and 
Sid -? Sname (non-trivial FD)
Properties of Functional Dependence (FD)
• Reflexivity If X a Y, then X -» Y (trivial)
• Transitivity If X -» Y and Y -» Z, then X -» Z
• Augmentation If X -» Y, then XZ -» YZ
• Splitting or Decomposition If X — » ¦ YZ, then X -» Y and X -» Z
• Union If X -? Y and X -? Z, then X -? YZ
Attribute Closure: Suppose R(X, Y, Z) be a relation having set of attributes i.e., (X, Y, 
Z), then (X+) will be an attribute closure which functionally determines other 
attributes of the relation (if not all then atleast itself).
Normal Forms/Normalization: In relational database design, the normalization is 
the process for organizing data to minimize redundancy. Normalization usually 
involves dividing a database into two or more tables and defining relationship 
between the tables. The normal forms define the status of the relation about the 
individuated attributes. There are five types of normal forms 
First Normal Form (INF): Relation should not contain any multivalued attributes or 
relation should contain atomic attribute. The main disadvantage of 1NF is high
(no common attribute at either side of arrow)
Page 3


Types of keys
There are basically four types of keys:
• Candidate Key: Minimal Set of attributes which can be used to identify data 
records uniquely.
• Super key: Set of attributes which can be used to identify data records 
uniquely (may or may not be minimal).
• Foreign Key: Foreign key is basically set of attributes referencing to primary 
key of same relation or some other relation.it allows null values.
• Alternative key: Candidate key other than Primary key. it also allows null 
values.
Schema Refinement/Normalization
Decomposition of complex records into simple records. Normalization reduces 
redundancy using non-loss decomposition principle.
Decomposition
Splitting a relation R into two or more subrelation Ri and R2 such that redundancies 
can be removed. A fully normalized relation must have all the functional 
dependencies such that determiner is a a primary key or a super key.
Decomposition should satisfy: (i) Lossless join, and (ii) Dependency preservence
Lossless Join Decomposition
Join between the subrelations should not create any additional tuples( Spurious 
tuples) or there should not be a case such that more number of tuples in Ri than R2
R c Ri
R2 = > (Lossy)
R = Ri
o<
R2 = > (Lossless)
Dependency Preservence: Because of decomposition, there must not be loss of any 
single dependency i.e., if Ft and F2 be the decomposed FD set for Rt and R2, then 
F= Ft U F2.
Functional Dependency (FD): Dependency between the attribute is known as 
functional dependency. Let R be the relational schema and X, Y be the non-empty 
sets of attributes and t1 f t2, ... ,tn are the tuples of relation R. X -? Y {values for X 
functionally determine values for Y}
Trivial Functional Dependency: If X a Y, then X — ? Y will be trivial FD.
Here, X and Y are set of attributes of a relation R.
In trivial FD, there must be a common attribute at both the sides of arrow.
Non-Trivial Functional Dependency: If X fl Y = < p (no common attributes) and X — ? Y 
satisfies FD, then it will be a non-trivial FD.
Case of semi-trivial FD
Sid -? Sid Sname (semi-trivial)
Because on decomposition, we will get 
Sid - * ¦ Sid (trivial FD) and 
Sid -? Sname (non-trivial FD)
Properties of Functional Dependence (FD)
• Reflexivity If X a Y, then X -» Y (trivial)
• Transitivity If X -» Y and Y -» Z, then X -» Z
• Augmentation If X -» Y, then XZ -» YZ
• Splitting or Decomposition If X — » ¦ YZ, then X -» Y and X -» Z
• Union If X -? Y and X -? Z, then X -? YZ
Attribute Closure: Suppose R(X, Y, Z) be a relation having set of attributes i.e., (X, Y, 
Z), then (X+) will be an attribute closure which functionally determines other 
attributes of the relation (if not all then atleast itself).
Normal Forms/Normalization: In relational database design, the normalization is 
the process for organizing data to minimize redundancy. Normalization usually 
involves dividing a database into two or more tables and defining relationship 
between the tables. The normal forms define the status of the relation about the 
individuated attributes. There are five types of normal forms 
First Normal Form (INF): Relation should not contain any multivalued attributes or 
relation should contain atomic attribute. The main disadvantage of 1NF is high
(no common attribute at either side of arrow)
redundancy.
Second Normal Form (2NF): Relation R is in 2NF if and only if R should be in 1NF, 
and R should not contain any partial dependency.
Partial Dependency: Let R be the relational schema having X, Y, A, which are non­
empty set of attributes, where X = Any candidate key of the relation, Y = Proper 
subset of any candidate key, and A = Non-prime attribute (i.e., A doesn't belong to 
any candidate key)
Model showing partial dependency
In the above example, X — ? A already exists and if Y — ? A will exist, then it will 
become a partial dependency, if and only if
• Y is a proper subset of candidate key.
• A should be non-prime attribute.
If any of the above two conditions fail, then Y — ? A will also become fully functional 
dependency.
Full Functional Dependency: A functional dependency P — ? Q is said to be fully 
functional dependency, if removal of any attribute S from P means that the 
dependency doesn't hold any more.
(Student_Name, College_Name -? College_Address)
Suppose, the above functional dependency is a full functional dependency, then we 
must ensure that there are no FDs as below.
(Student_Name -? College_Address) 
or (College_Name -? Collage_Address)
Third Normal Form (3NF): Let R be a relational schema, then any non-trivial FD X — ? 
Y over R is in 3NF, if X should be a candidate key or super key or Y should be a 
prime attribute. •
• Either both of the above conditions should be true or one of them should be 
true.
• R should not contain any transitive dependency.
• For a relation schema R to be a 3NF, it is necessary to be in 2NF.
Transitive Dependency: A FD, P — ? Q in a relation schema R is a transitive if
• There is a set of attributes Z that is not a subset of any key of R.
• Both X — ? Z and Z — ? Y hold
Candidate Not a candidate Non-prime
key or super key attribute
R (ABCD)
Transition state diagram 
showing transitive dependency
R, (ABCD) R2 (DE)
A fl - » C D -> £
C->D
• The above relation is in 2NF.
Page 4


Types of keys
There are basically four types of keys:
• Candidate Key: Minimal Set of attributes which can be used to identify data 
records uniquely.
• Super key: Set of attributes which can be used to identify data records 
uniquely (may or may not be minimal).
• Foreign Key: Foreign key is basically set of attributes referencing to primary 
key of same relation or some other relation.it allows null values.
• Alternative key: Candidate key other than Primary key. it also allows null 
values.
Schema Refinement/Normalization
Decomposition of complex records into simple records. Normalization reduces 
redundancy using non-loss decomposition principle.
Decomposition
Splitting a relation R into two or more subrelation Ri and R2 such that redundancies 
can be removed. A fully normalized relation must have all the functional 
dependencies such that determiner is a a primary key or a super key.
Decomposition should satisfy: (i) Lossless join, and (ii) Dependency preservence
Lossless Join Decomposition
Join between the subrelations should not create any additional tuples( Spurious 
tuples) or there should not be a case such that more number of tuples in Ri than R2
R c Ri
R2 = > (Lossy)
R = Ri
o<
R2 = > (Lossless)
Dependency Preservence: Because of decomposition, there must not be loss of any 
single dependency i.e., if Ft and F2 be the decomposed FD set for Rt and R2, then 
F= Ft U F2.
Functional Dependency (FD): Dependency between the attribute is known as 
functional dependency. Let R be the relational schema and X, Y be the non-empty 
sets of attributes and t1 f t2, ... ,tn are the tuples of relation R. X -? Y {values for X 
functionally determine values for Y}
Trivial Functional Dependency: If X a Y, then X — ? Y will be trivial FD.
Here, X and Y are set of attributes of a relation R.
In trivial FD, there must be a common attribute at both the sides of arrow.
Non-Trivial Functional Dependency: If X fl Y = < p (no common attributes) and X — ? Y 
satisfies FD, then it will be a non-trivial FD.
Case of semi-trivial FD
Sid -? Sid Sname (semi-trivial)
Because on decomposition, we will get 
Sid - * ¦ Sid (trivial FD) and 
Sid -? Sname (non-trivial FD)
Properties of Functional Dependence (FD)
• Reflexivity If X a Y, then X -» Y (trivial)
• Transitivity If X -» Y and Y -» Z, then X -» Z
• Augmentation If X -» Y, then XZ -» YZ
• Splitting or Decomposition If X — » ¦ YZ, then X -» Y and X -» Z
• Union If X -? Y and X -? Z, then X -? YZ
Attribute Closure: Suppose R(X, Y, Z) be a relation having set of attributes i.e., (X, Y, 
Z), then (X+) will be an attribute closure which functionally determines other 
attributes of the relation (if not all then atleast itself).
Normal Forms/Normalization: In relational database design, the normalization is 
the process for organizing data to minimize redundancy. Normalization usually 
involves dividing a database into two or more tables and defining relationship 
between the tables. The normal forms define the status of the relation about the 
individuated attributes. There are five types of normal forms 
First Normal Form (INF): Relation should not contain any multivalued attributes or 
relation should contain atomic attribute. The main disadvantage of 1NF is high
(no common attribute at either side of arrow)
redundancy.
Second Normal Form (2NF): Relation R is in 2NF if and only if R should be in 1NF, 
and R should not contain any partial dependency.
Partial Dependency: Let R be the relational schema having X, Y, A, which are non­
empty set of attributes, where X = Any candidate key of the relation, Y = Proper 
subset of any candidate key, and A = Non-prime attribute (i.e., A doesn't belong to 
any candidate key)
Model showing partial dependency
In the above example, X — ? A already exists and if Y — ? A will exist, then it will 
become a partial dependency, if and only if
• Y is a proper subset of candidate key.
• A should be non-prime attribute.
If any of the above two conditions fail, then Y — ? A will also become fully functional 
dependency.
Full Functional Dependency: A functional dependency P — ? Q is said to be fully 
functional dependency, if removal of any attribute S from P means that the 
dependency doesn't hold any more.
(Student_Name, College_Name -? College_Address)
Suppose, the above functional dependency is a full functional dependency, then we 
must ensure that there are no FDs as below.
(Student_Name -? College_Address) 
or (College_Name -? Collage_Address)
Third Normal Form (3NF): Let R be a relational schema, then any non-trivial FD X — ? 
Y over R is in 3NF, if X should be a candidate key or super key or Y should be a 
prime attribute. •
• Either both of the above conditions should be true or one of them should be 
true.
• R should not contain any transitive dependency.
• For a relation schema R to be a 3NF, it is necessary to be in 2NF.
Transitive Dependency: A FD, P — ? Q in a relation schema R is a transitive if
• There is a set of attributes Z that is not a subset of any key of R.
• Both X — ? Z and Z — ? Y hold
Candidate Not a candidate Non-prime
key or super key attribute
R (ABCD)
Transition state diagram 
showing transitive dependency
R, (ABCD) R2 (DE)
A fl - » C D -> £
C->D
• The above relation is in 2NF.
• In relation Ri, C is not a candidate key and D is non-prime attribute. Due to 
this, Ri fails to satisfy 3NF condition. Transitive dependency is present here.
AB — ? C and C -» D , then AB — ? D will be transitive.
Boycee Codd Normal Form (BCNF): Let R be the relation schema and X — ? Y be the 
any non-trivial FD over R is in BCNF if and only if X is the candidate key or super 
key.
X — < • Y
candidate sup er key
If R satisfies this dependency, then of course it satisfy 2NF and 3NF.
Hierarchy of normal forms 
Summary of 1 NF, 2 NF and 3 NF:
N orm al
F orm
Test R em edy (N orm alization)
1 NF
Relation should have no non- 
atomic attributes or nested 
relations.
Form name relation for each non- 
atomic attribute or nested relation.
2NF
F or relations where primary key 
contains multiple attributes, no 
non-key attribute should be 
functionally dependent on a part 
of the primary key.
Decompose and set up a new 
relation for each partial key with 
its .dependent attributes. Make 
sure to keep a relation with the 
original primary key and any 
attributes that are fully 
functionally dependent on it.
3NF
Relation should not have a non- 
key attribute functionally 
determined by another non-kev 
attribute (or by a set of non -key 
attributes), i.e., 'there should be no 
transitive dependency of a non-kev 
attribute on the primary key.
Decompose and setup a relation 
that includes the non-key 
attribute(s) that functionally 
determine(s) other non-key 
attribute(s)
Fourth Normal Form (4NF): 4NF is mainly concerned with multivalued dependency 
A relation is in 4NF if and only if for every one of its non-trivial multivalued 
dependencies X X is a super key (i.e., X is either a candidate key or a 
superset) and all the multivalued dependencies are in BCNF.
Fifth Normal Form (5NF): It is also 'known as Project Join Normal From (PJ/NF). 
5NF reduces redundancy in relational database recording multivalued facts by 
isolating semantically related multiple relationships. A table or relation is said to be 
in the 5NF, if and only if every join dependency in it is implied by the candidate 
keys.