TOPICS (Click to Navigate)
- Advanced Database Concepts
- Data structures, Operating Systems
- Natural Language Processing
- Quiz Questions and Answers
- DBMS, ADBMS Question Bank
- SQL
- RDBMS Exam and Interview Questions
- Parallel Databases
- ADBMS Quizzes
- Advanced DBMS Concepts
- Distributed Databases
- Modern Databases - Special Purpose Databases
- Object Based Database Systems
Showing posts with label Normalization. Show all posts
Showing posts with label Normalization. Show all posts
Monday, December 12, 2016
Sunday, December 11, 2016
Normalize the relational schema to third normal form
How to normalize a table to 3NF? / Show the steps in 3nf normalization / Normalization solved exercises / 1nf, 2fn, 3nf
Question:
Consider the relation schema
Membership for a library database as follows;
Membership (MID, Name, Address,
PhoneNum, ParentMID, ISBN, Title, Authors, BorrowDate, ReturnedDate, FineDue,
FinePaid).
Here, ParentMID may have the values Null,
Father_Name, Mother_Name or both. The following is the set F of functional
dependencies that hold in Membership table;
F = { MID → Name, Address,
PhoneNum, ParentMID;
(MID, ISBN, BorrowDate) → ReturnedDate,
FinePaid, FineDue;
ISBN → Title, Authors}
Normalize the Membership schema to 3NF
and show the steps.
Answer:
Given set of FDs;
- FD 1: MID → Name, Address, PhoneNum, ParentMID
- FD 2: (MID, ISBN, BorrowDate) → ReturnedDate, FinePaid, FineDue
- FD 3: ISBN → Title, Authors
Is the table Membership in 1NF?
It is not in 1NF because of the
attribute ParentMID which is a multi-valued attribute (when both parents MIDs
are issued and stored for a member). To solve this we may create a separate
table with MID and ParentMID attributes as follows;
Parent (MID, ParentMID)
For parent table the key is {MID,
ParentMID}, hence the table is in 3NF.
After this decomposition, we have the
following schemas;
- Schema 1: Parent (MID, ParentMID)
- Schema 2: Membership (MID, Name, Address, PhoneNum, ISBN, Title, Authors, BorrowDate, ReturnedDate, FineDue, FinePaid)
At this stage, the Membership table is
in 1NF.
Is Membership in 2NF?
2NF is about eliminating partial keydependencies (if any) from a relational schema. To do this, we need to find the
primary key for Membership table.
Let us find the closure of LHS
attributes of given functional dependencies to check whether the LHS attributes
form a key or not;
From FD1,
(MID)+ = MID, Name, Address,
PhoneNum ≠ Membership
From FD2,
(MID, ISBN, BorrowDate)+ = MID,
Name, Address, PhoneNum, ISBN, Title, Authors, BorrowDate, ReturnedDate,
FineDue, FinePaid = Membership
Hence, the key for Membership is a composite
key (MID, ISBN, BorrowDate).
Now let us check for partial
dependencies;
- The attributes MID, Name, Address, and PhoneNum can be determined by using MID alone.
- The attributes ISBN, Title, and Authors can be determined by using ISBN alone. [from FD3].
So, the schema shows partial functional
dependencies;
We shall break schema 2 to convert into
a set of 2NF schemas;
Schema 2a: (MID, Name,
Address, PhoneNum)
Schema 2b: (ISBN,
Title, Authors)
Schema 2c: (MID, ISBN, BorrowDate,
ReturnedDate, FineDue, FinePaid)
Is schema 2a in 2NF? – Yes. MID is the
key and no partial key dependency.
Is schema 2b in 2NF? – Yes. ISBN is
the key and no partial dependencies.
Is schema 2c in 2NF? – Yes. (MID,
ISBN, BorrowDate) is the composite key and no partial dependencies.
Are schema 1, 2a, 2b and 2c are in 3NF?
As per the given set of functional dependencies,
we do not have any transitive functional dependencies in any of these tables. Hence,
the list of 3NF tables is as follows;
- Schema 1: Parent (MID, ParentMID)
- Schema 2a: (MID, Name, Address, PhoneNum)
- Schema 2b: (ISBN, Title, Authors)
- Schema 2c: (MID, ISBN, BorrowDate, ReturnedDate, FineDue, FinePaid)
Go to normalization multiple choice questions page
Friday, December 9, 2016
What is partial functional dependency in dbms
Partial functional dependency / What is partial functional dependency / Why it is called as partial functional dependency? / Define partial functional dependency
Partial Functional Dependency
A functional dependency A → B is said to be
partial if removal of any subset of A still able to recognize B
uniquely.
Partial Dependency is a form of Functional dependency that holds on a set of attributes. It is about the complete dependency of a right hand side attribute on one of the left hand side attributes.
For example, in a functional dependency PQ → R, if either P alone or Q alone can uniquely identify R, then this is said to be Partial Functional Dependency. We read this as R is partially functionally dependent on P or R is partially functionally dependent on Q.
Partial Dependency is a form of Functional dependency that holds on a set of attributes. It is about the complete dependency of a right hand side attribute on one of the left hand side attributes.
For example, in a functional dependency PQ → R, if either P alone or Q alone can uniquely identify R, then this is said to be Partial Functional Dependency. We read this as R is partially functionally dependent on P or R is partially functionally dependent on Q.
Another example: Assume the set of FDs for a relation Student as follows;
F = {regno → name, regno → dob, {regno, phone} → gender, regno → gender}
Here, in FD {regno, phone} → gender, the attribute gender is partially dependent on regno attribute or left hand side. Here, phone is not required to identify gender uniquely.
What is meant by full functional dependency
Define full functional dependency / When would you say that an attribute is fully functionally dependent on other attributes? / What is full functional dependency?
Full Functional Dependency
In a functional dependency A → B, (A is a set of attributes and B is another set of attributes), the dependency where B is fully dependent on A, and not on any of the subset of A is
called Full Functional dependency. For example, assume that attributes P
and Q together can only uniquely identify the value of the other
attribute R. Then, PQ → R is Full Functional Dependency.
As another example, let us consider the set F of functional dependencies; F = { A → B, AD → B }. In this case, the FD A → B is full functional dependency whereas AD → B is not full, that is B is not fully functionally dependent on AD, instead it depends on A alone.
What is trivial functional dependency in dbms
What is trivial functional dependency in DBMS? / Define trivial functional dependency / What is the trivial property in normalization process?
Trivial Functional Dependency
A FD is said to be as Trivial, if it holds for all relations. In other words, a functional dependency A → B is said to be trivial, if B is the subset or equal to that of A. That is, if you know the value of B already, you would uniquely determine the value of B.
If all of the right hand side attributes are either subset or equal to the left hand side attributes in a functional dependency, then that particular functional dependency is said to be trivial.
For example,
If all of the right hand side attributes are either subset or equal to the left hand side attributes in a functional dependency, then that particular functional dependency is said to be trivial.
For example,
- A → A is trivial,
- AB → B is trivial,
- {regno, phone} → phone and so on.
Go to keywords page
Describe trivial functional dependency in normalization process
What is functional dependency in dbms
What is functional dependency in DBMS? / Define Functional dependency / How to write a functional dependency? / Functional dependency examples
Functional Dependency
Functional
Dependency is the property which verifies the relationship between two
attributes / two sets of attributes. It means, determination of the
value(s) of one attribute (or one set of attributes) using the other (or
other set of attributes). This property is helping us in designing a
good database.
A FD can be written as A → B. This can be read as "A determines the value of B" or "value of B can be uniquely determined by A".
For example, if you know the register number of a student you would easily identify other details of that particular student. hence, all the other attributes of student table like name, branch, gender, dob etc. are all dependent on the register number attribute. In other words, register number determines all the other attributes uniquely.
To know more about functional dependencies Click here
For example, if you know the register number of a student you would easily identify other details of that particular student. hence, all the other attributes of student table like name, branch, gender, dob etc. are all dependent on the register number attribute. In other words, register number determines all the other attributes uniquely.
To know more about functional dependencies Click here
What is normalization
Define normalization / What is normalization / Define the term normalization
Normalization is the process that is a part of database design process which helps us to
eliminate some anomalies (problems / nature of data which would cause
problems) which are present in the design of a table. It actually examines the relationship between the attributes of a table (relation) to eliminate anomalies like insertion, deletion and updation.
Wednesday, November 30, 2016
One more way to find candidate keys in normalization process
How to find the candidate keys? Another way to find candidate keys in normalization process / Easy way to find key of relational table in DBMS
Another way to find candidate keys
When we try to find the candidate keys
we always start with the attributes that are in the left hand side and we try
to find the closure of Left Hand Side (LHS) attributes. In many cases, there
are possibilities such that the attributes that are on both sides may also
contribute in forming a candidate keys. Hence, we would use the following
method to find all the candidate keys.
We separate the attributes from the
given set of FDs as follows;
LHS only attributes (L)
|
Not listed attributes (N)
|
RHS only attributes (R)
|
Both LHS and RHS (B)
|
The attributes that are on the LHS
must present in a key. That is, L ⊇ Key (L is
subset or equal to a key).
The attributes that are not part of
any given FDs must be a part of a candidate key. That is, N ⊃ Key (N is
a subset of a key).
The attributes that are on the RHS
cannot be a part of key. That is, R ⊅ Key (R
cannot be part of a key).
The attributes that are present on
both sides of different functional dependencies may contribute in formation of
a candidate key. That is, R ⊇ Key (R may
be part of key).
Example 1:
Let us try this with an example;
Consider a relation R = ABCDEF with
set F of functional dependencies, F = {A -> B, B -> D, C -> D, E ->
F}; Find the candidate keys of R.
Using the set F, let us draw the
table;
LHS only attributes (L)
|
Not listed attributes (N)
|
RHS only attributes (R)
|
Both LHS and RHS (B)
|
A, C, E
|
-
|
D, F
|
B
|
As per the theory, LHS contributes in
forming a key. Hence, let us find the closure of LHS attributes first.
A+ = ABD
C+ = CD
E+ = EF
(AC)+ = ABCD
(AE)+ = ABDEF
(CE)+ = CDEF
(ACE)+ = ABCDEF
Hence, (ACE) is a candidate key.
We don’t need to find the closure for
RHS only attributes D and F.
Both side attribute may contribute. But
in the given example, B is the attribute available on both side but it already
can be determined by A. Hence, it may not contribute in forming the key.
So, only candidate key is (ACE).
Example 2:
Let us try another example;
Consider a relation R = (ABCDEF) with
set F as F = {DF -> C, BC -> F, E -> A, ABC -> E}. Find all the
candidate keys.
LHS only attributes (L)
|
Not listed attributes (N)
|
RHS only attributes (R)
|
Both LHS and RHS (B)
|
D, B
|
-
|
-
|
A, C, E, F
|
Let us find the closure of LHS
attributes.
D+ = D
B+ = B
(DB)+ = DB
Now we need the both sides attributes for
finding the candidate key. But they can form the key in association with LHS
attributes as LHS is must in a key.
A+ = A
C+ = C
E+ = AE
F+ = F
…
…
(DBA)+ = ABD
(DBAC)+ = ABCDEF – One candidate key
(DBEF)+ = ABCDEF – One candidate key
(ACEF)+ = ACEF
Hence, candidate keys are (ABCD) and
(BDEF).
Go to normalization solved exercises page
Go to How to find closure of an attributes(s) page
one more way to find the candidate keys of a relational table
Simpler way to find the candidate keys in dbms
Wednesday, November 16, 2016
Is the given decomposition is a lossless join decomposition?
Is the given decomposition a lossless join decomposition?
Question:
10. Assume a relation R(A, B, C, D, E)
with set F of functional dependencies as follows;
F = {A → BC, CD → E, B → D, E → A}
If R is decomposed in to R1(A, B, C)
and R2(A, D, E), which of the following holds?
(a) Decomposition is Loss-less Join Decomposition
(b) Decomposition is Dependency Preserving Decomposition
(c) Decomposition is both (a) and
(b)
(d) Decomposition is Lossy-Join
Decomposition
Answer:
(a) Decomposition is Loss-less Join
Decomposition
Discussion:
Is the given decomposition is loss-less?
YES
If either R1 ⋂ R2 → R1 is true or R1 ⋂ R2 → R2 is true for the given decomposition, then we would say that the decomposition is loss-less join decomposition.
What is R1 ⋂ R2? – The common
attribute(s) between R1 and R2.
In our case, R1 ⋂ R2 is A. We have
to check whether A can determine all attributes of R1 or all attributes of R2
uniquely using the given FDs.
From F we can determine A+ as
follows using the closure finding algorithm;
Result = A
Result = ABC from A → BC
Result = ABCD from B → D
Result = ABCDE from CD → E
From this, we would know that A is a
candidate key for R.
A determines A, B, and C which is
R1. So, R1 ⋂ R2 → R1 is true.
Hence, the given decomposition is
loss-less join decomposition.
Is the given decomposition is dependency
preserving?
NO
The above said decomposition of R into R1 and R2 is a dependency preserving decomposition if (F1 U F2)+ = F+, where F1 is set of FDs hold by R1, F2 is set of FDs hold by R2, and F is the set of FDs hold by R. (F1 U F2)+ is the closure of (F1 U F2), and F+ is the closure of F.
Step 1: for R1, the derivable
non-trivial functional dependency is A → BC. Hence, F1 = {A →
BC}
Step 1: for R1, the derivable
non-trivial functional dependency is E → A. Hence, F2 = {E → A}
(F1 U F2)+ = {A → BC, E → A}
F+ = {A → BC, CD → E, B → D, E → A, E → BC, A → E}
A → BC is there in F+,
hence preserved.
E → A is there in F+,
hence preserved.
CD → E, and B → D are not there in
F+, hence not preserved.
Hence, the decomposition is not
dependency preserving.
Subscribe to:
Posts (Atom)
Featured Content
Multiple choice questions in Natural Language Processing Home
MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...
All time most popular contents
-
Relational algebra in database management systems solved exercise Relational algebra – solved exercise Question: Consider the fo...
-
Top 5 Machine Learning Quiz Questions with Answers explanation, Interview questions on machine learning, quiz questions for data scienti...
-
Multiple Choice Questions MCQ on Distributed Database with answers Distributed Database – Multiple Choice Questions with Answers 1...
-
Top 5 Machine Learning Quiz Questions with Answers Explanation, Interview questions on machine learning, quiz questions for data scientist...
-
Parallel query execution - example SQL queries / Inter-query, Intra-query parallelism examples / Inter-operation and Intra-operation paral...