Showing posts with label Normalization. Show all posts
Showing posts with label Normalization. Show all posts

Find the candidate keys of a table in dbms an example

Find the candidate keys of a relation, How to find the candidate keys, Which is the key for the given table, concept of candidate key in dbms, candidate key examples


Question:
Consider a relation R with attributes ABCDEFGH and functional dependencies S as follows:
S = {A CD, ACF G, AD BEF, BCG D, CF AH, CH G, D B, H DEG}
Find all keys for R.

Solution:
We can find keys (candidate keys) for a relation by finding the closure of an/set of attributes. Checking each attribute or all subsets of the given set of attributes for a key is time consuming job. Hence, we may employ some of the following heuristics/assumptions in identifying the keys;

  • We may start checking all the left hand side attributes of any/all of the given set of functional dependencies.
  • If we find the closure of an attribute and that attribute is the candidate key then any superset cannot be the candidate key. For example, if A is a candidate key, then AB is not a candidate key but a super key.

LHS
Result
Decision
A+
= ACD from A CD
= ACDBEF from AD BEF
= ACDBEFG from ACF → G
= ACDBEFGH from CF → AH
Result includes all the attributes of relation R. That is, if we know A, then all the attributes of R could be uniquely determined. Hence, A is one candidate key.
ACF+
No need to find the closure of (ACF) because the subset A is already a candidate key.
ACF is a super key but not candidate key.
AD+
No need to find the closure of (AD) because the subset A is already a candidate key.
AD is a super key but not candidate key.
BCG+
= BCGD from BCG D
Result does not include all the attribute of relation R. Hence, (BCG) cannot be a candidate key.
CF+
= CFAH from CF AH
Further, as we know A now, then we can conclude that CF will uniquely determine all the other attributes of A.
Result includes all the attributes of relation R. Hence, (CF) is one candidate key.
D+
= DB from D → B
Result does not include all R. Hence, D cannot be a key.
H+
= HDEG from H DEG
= HDEGB from D B
Result does not include all R. Hence, H cannot be a key.
From the above table, it is clear that only A and CF are the candidate keys.



Go to - 1NF,    2NF,    3NF,    BCNF












Find the functional dependencies that are violating BCNF

Find the functional dependencies that are violating BCNF, Find the FDs that are not violating the BCNF rules, Find FD for BCNF decomposition


Question:
Consider a relation schema R with attributes ABCDEFGH with functional dependencies S:
S = {B CD; BF H; C AG; CEH F; CH B}
Which of these functional dependencies violate BCNF (Boyce-Codd Normal Form)?

Solution:

BCNF requires that the LHS of an FD be a super key. Hence, we would find the closure for all the Left Hand Side attributes/sets of attributes to check whether the LHS forms the key or not. [Note: B+ means the closure of the attribute B]
LHS
Result
Decision
B+
= BCD from B CD
= BCDAG from C A
Result does not include attributes E, F and H. Hence, B is not a super key and B CD violates BCNF.
BF+
= BFH from BF H
= BFHCD from B CD
= BFHCDAG from C AG
Result does not include E. Hence, (BF) is not a super key and BF H violates BCNF.
C+
= CAG from C AG
Result does not include B, D, E, F, and H. Hence C is not a super key and C AG violates BCNF.
CEH+
= CEHF from CEH F
= CEHFB from CH B
= CEHFBAG from C AG
= CEHFBAGD from B CD
Result includes all the attributes of relation R. Hence, (CEH) is the super key of R and CEH F does not violate BCNF.
CH+
= CHB from CH B
= CHBD from B CD
= CHBDAG from C AG
Result does not include E and F. Hence, (CH) is not a super key and CH B violates BCNF.

 *************************



Go to - 1NF,    2NF,    3NF,    BCNF









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)