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









Normalization solved exercise bcnf 1

Normalize up to BCNF, Boyce-codd normal form normalization, steps in normalizing a relation to bcnf relation


Question:

Normalize the following table. Show all work and clearly indicate the primary and foreign keys.
R(elevator_no, building_no, building_name, capacity, staff_no, first_name, last_name, date_examined) with the following functional dependencies:
1. elevator_no building_no,capacity
2. building_no building_name
3. staff_no first_name,last_name
4. elevator_no,staff_no date_examined
Normalize table R up to BCNF.

Solution:
1NF – The table R is already in first normal form because of atomic attributes. All the attributes of R are atomic.

2NF – Second normal form is about elimination of partial key functional dependency. To proceed further, we need to find the key for R. For that we need to find the how to find attribute closure for all the left hand side attributes of the given functional dependencies.
elevator_no+
Result = building_no, capacity from the FD elevator_no building_no,capacity
           = building_no, capacity, building_name - from building_no building_name
Result of elevator_no+ does not include all attributes of R. Hence, elevator_no cannot be the key of R.
staff_no+
Result = first_name, last_name – from the FD staff_no first_name,last_name
Result of staff_no+ does not include all attributes of R. hence, staff_no cannot be the key of R.
(Elevator_no, staff_no)+
Result = date_examined
from the FD elevator_no,staff_no date_examined
            = date_examined, building_no, capacity
from elevator_no building_no,capacity
            = date_examined, building_no, capacity, building_name
            from building_no building_name
            = elevator_no, building_no, building_name, capacity, staff_no, first_name, last_name, date_examined
            from staff_no first_name,last_name
The result includes all the attributes of R for (Elevator_no, staff_no)+. Hence, (Elevator_no, staff_no) is the key (composite key) of R.
Do we have partial key dependencies in R?
Yes. The following are the partial key dependencies.
elevator_no building_no,capacity
staff_no first_name,last_name
The reason is, both elevator_no and staff_no are parts of the key of R. They can uniquely identify some of the non-key attributes. Because of these partial key dependencies, R is not in 2NF.
To convert R into 2NF relations, we need to decompose R on partial key dependencies. Thus, we get the following relations; (primary keys are underlined)
R1 (elevator_no, building_no, capacity, building_name)
          From FDs elevator_no building_no,capacity and building_no building_name
R2 (staff_no, first_name, last_name)
From FD staff_no first_name,last_name
R3 (elevator_no, staff_no, date_examined)
From FD elevator_no,staff_no date_examined
 in R3 elevator_no is one foreign key referencing R1, and staff_no is another foreign key referencing the relation R2.
Are R1, R2, and R3 in 2NF?
Yes. In all the relations, all non-key attributes are fully-functionally dependent on the primary keys.

3NF – Third normal form is about elimination of non-key dependencies, that is, a functional dependency with a non-key attribute is dependent on another non-key attribute.
Do we have non-key dependencies in R1?
Yes. See below;
R1 (elevator_no, building_no, capacity, building_name)
          F = {elevator_no → building_no,capacity and building_no → building_name}
In R1 we have a non-key dependency building_no → building_name, that is the non-key attribute building_no uniquely determines the other non-key attribute building_name.
R1 is in 2NF because of no partial key dependencies and not in 3NF because of non-key dependencies.
To convert R1 into 3NF relations, decompose R1 on non-key dependencies. Thus, we get the following relations;
R11 (elevator_no, building_no, capacity)
From FD elevator_no building_no, capacity
R12 (building_no, building_name)
From FD building_no building_name a non-key dependency.
in R12 building_no is the primary key and in R11 building_no is the foreign key referencing the relation R12.
Do we have non-key dependencies in R11 and R12?
No. Hence, R11 and R12 are in 3NF.
Do we have non-key dependencies in R2 and R?
No. Hence, R2 and R3 are in 3NF.

BCNF – The determinants in a FD should be the key for the relation.
Are R11, R12, R2, and R3 are in BCNF?
Yes. Each relation have only one functional dependency. And the determinants of the functional dependencies are the primary keys. Hence the relations R11, R12, R2, and R3 are in BCNF.
***************

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