Eliminate the redundant functional dependencies to find minimal cover

Find the functional dependencies that are redundant in a given set of FDs / Eliminate the redundant functional dependencies to find minimal cover / Eliminating unnecessary FDs to find canonical cover in normalization process

Question:

9. Let R(A, B, C) be a relation with the following set F of functional dependencies;

F = { A → B, B → A, A → C, C → A, B → C }

If we would like to find the minimal cover of F, then which of the following redundancies should be eliminated? ;

(a) B → A and A → C

(b) B → C

(c) Either (a) or (b)

(d) F is already minimal

Answer:

(c) Either (a) or (b)

Note: There can be more than one minimal cover for a set of functional dependencies.

Steps to find the minimal cover;

1. Ensure singleton attribute on the right hand side of each functional dependency.

2. Remove extraneous (redundant) attribute from the left hand side of each functional dependency.

3. Remove redundant functional dependency if any.

In our case, the functional dependencies given are already satisfying the first two rules.

According to rule 1, if we have any FDs with more than one attribute on the Right Hand Side, that FD should be decomposed using decomposition rule. We don’t have such FDs.

According to rule 2, if we have any FDs that have more than one attribute on the Left Hand Side (determiner), that FD must be checked for partial dependency. We don’t have such FDs.

Hence, the given set satisfies both rules.

For the third one we need to check.

Procedure : [refer here for different explanation].

Given : F = { A → B, B → A, A → C, C → A, B → C }

For the first FD A → B find A⁺ by hiding the FD A → B. A⁺ = AC which does not include B in it. Hence, A → B is not redundant.

For the second FD B → A find B⁺ by hiding the FD B → A.  B⁺ = ABC which includes A in it. Hence, B → A is redundant. We have to remove it immediately.

Now with the removal of B → A, our F becomes,

F = { A → B, A → C, C → A, B → C }

Find A⁺ by hiding A → C. A⁺ = ABC which includes C. Hence A → C is redundant and remove it immediately from F.

After removal of A → C, F becomes,

F = { A → B, C → A, B → C }

Find C⁺ by hiding C → A. C⁺ = C and this does not include A in the result. Hence, C → A is not redundant.

Finally find B⁺ by hiding B → C. B⁺ = B. Hence, B → C is mandatory.

We don’t have any more FDs. Our final set of functional dependencies are minimal after the removal of FDs B → A and A → C.

Hence, the minimal cover of F is as follows;

F_c = { A → B, C → A, B → C }

[Work out for the option B → C. While applying the above said procedure, start with the FD B → C. You will get the F_c as { A → B, B → A, A → C, C → A }]

         Previous Question                                                                                Next Question

Find the functional dependency that is not hold in a relation

Find the functional dependencies that are not holding on the given relation / Identify the wrong functional dependencies among the given / Find all valid functional dependencies of a relational table

Question:

8. Let R(A, B, C, D, E, F) be a relation with set F of functional dependencies as follows;

F = { A → B, A → C, CD → E, CD → F, B → E }

Which of the following functional dependencies does not hold in R?

(a) A → E

(b) CD → EF

(c) AD → F

(d) B → CD

Answer:

(d) B → CD

Discussion:

B → CD

B → CD is not true because the only functional dependency that has B on left hand side is B → E. now neither E nor B is not on the left hand side of any of the other functional dependencies.

A → E

A → E can be derived through the functional dependencies A → B and B → E. [ Transitivity rule ]

CD → EF

CD → EF can be derived through the functional dependencies CD → E and CD → F. [ Union rule]

AD → F

AD → F can be derived through the functional dependencies A → C and CD → F. [ Pseudo-transitivity rule]

         Previous Question                                                                                Next Question

Find the dependency preserving BCNF decomposition of the given relation

Find the dependency preserving BCNF decomposition of the given relation schema / Is the given decomposition is dependency preserving? / How to decompose a relation into BCNF with dependency preservation? / How to perform a dependency preserving decomposition? / Is the table in BCNF?

Question:

7. Assume a relation R(A, B, C, D, E) with the set of functional dependencies F = { A → B, BC → D } and the candidate key (ACE). The relation is not in BCNF. Which of the following is the dependency preserving decomposition for R into BCNF relations?

(a) R₁(B, C, D), R₂(A, B), R₃(A, C, E)

(b) R₁(A, B), R₂(A, C, D), R₃(A, C, E)

(c) R₁(A, B), R₂(A, C, D, E)

(d) All of the above

 

Answer:

(a) R₁(B, C, D), R₂(A, B), R₃(A, C, E)

• BCNF – In simpler terms, the Left Hand Side (LHS) of all the functional dependencies should be the key.

• Dependency preserving decomposition – If a relation R with set F of functional dependencies is decomposed into relations R₁, R₂, R₃, …, R_i then the closure of set of functional dependencies for these relations should satisfy the following; 
• (F₁ U F₂ U F₃ U … U F_i)⁺ = F⁺ 
• That is the closure of union of set of functional dependencies of relations R₁, R₂, …, R_i should be equal to the closure of set of functional dependencies F of R. In other words, all the functional dependencies in (F₁ U F₂ U F₃ U … U F_i)⁺ should be in F⁺ also.

Given: F = { A → B, BC → D }

Step 1: What is the candidate key for R?

A⁺ = AB

(BC)⁺ = BCD

E is not included in any of the functional dependencies, hence E should be in the left hand side and forms one of the key attributes.

(AE)⁺ = ABE

(BCE)⁺ = BCDE

(ACE)⁺ = ABCDE = R.

Hence, (ACE) is the candidate key for R.

Step 2: Which of the functional dependencies violate BCNF?

For the given table R, the following are the dependencies that violate the conditions for BCNF;

{ A → B, BC → D }

Because, the LHS of both FDs are not candidate keys.

Step 3: Break the relation using the violating FDs

Let us consider the FD BC → D and break (decompose) R using this functional dependency;

We create relation R₁ with the schema R₁(B, C, D). [all the attributes of functional dependency BC → D]

We create relation R₂ with the schema R₂(A, B, C, E). [the attributes for R₂ are derived by performing R – D, ie., {A, B, C, D, E} – {D}]

Step 4: R₁ is in BCNF?

The candidate key for R₁ is BC and the FD that holds in R₁ is BC → D. The LHS of the FD is the candidate key. Hence, R₁ is in BCNF.

Step 5: R₂ is in BCNF?

The candidate key for R₂ is ACE and the FD that holds in R₂ is A → B. The LHS of the FD is not the candidate key. Hence A → B violates the rule for BCNF.

Step 5.1: Break R₂ on FD A → B.

We create relation R₂₁(A, B) using A → B, the violating FD.

We create relation R₂₂(A, C, E) using R₂ – B.

Step 6: Is R₂₁ and R₂₂ are in BCNF?

The candidate key for R₂₁ is A and the LHS of A → B is A. Hence, R₂₁ is in BCNF.

The candidate key for R₂₂ is ACD and the FD holds in R₂₂ is trivial FD. Hence, R₂₂ is in BCNF.

Step 7: R into R₁, R₂₁, and R₂₂ is dependency preserving decomposition?

Let us consider the set of FDs of R, R₁, R₂₁, and R₂₂ as F, F₁, F₂₁, and F₂₂.

Apply the rule (F₁ U F₂ U F₃ U … U F_i)⁺ = F⁺.

(F₁ U F₂₁ U F₂₂)⁺ = F⁺

({BC → D} U {A → B} U {ACE → ACE})⁺ = ({ A → B, BC → D})⁺

All the FDs are found in decomposed relations. Hence, R into R₁(B, C, D), R₂₁(A, B), and R₂₂(A, C, E) is dependency preserving BCNF decompositions.

         Previous Question                                                                                Next Question

2NF, 3NF, and BCNF - Which is the correct normal form of the given relation.

Find the normal form of the given relation schema / Find keys of relational table / Normalize the relation to 2NF, 3NF, and BCNF

Question:

6. Consider the sample table CARS given below; here, SSN is the Social Security Number, OName is the name of the car owner, Car_Reg_No is the registration number of the car, KM_covered is the total number of kilometers the car travelled so far.

SSN	OName	Car_Reg_No	KM_Covered	Model	Manufacturer
123AV10	Steve	MH 01 AA 1100	1200	Figo	Ford
124CC23	Ramkumar	GJ 21 C 0025	10000	Figo	Ford
452PO90	Vishnu	TN 20 BC 1234	5000	Brezza	Maruti Suzuki
123AV10	Steve	MH 02 AB 1100	10000	Rapid	Skoda
323TY23	Sukumar	AP 12 C 2344	10289	Swift	Maruti Suzuki

Which of the following is TRUE for this table?

(a) CARS is in 2NF

(b) CARS is in 3NF

(c) CARS is in BCNF

(d) None of the above

Answer:

(d)None of the above
To find the normal of the given table, we need to find the set of functional dependencies that are holding in the given relation (table). Then we have to find the key for the given table.

From the given data, we can derive the following set of functional dependencies;

F = {SSN → OName, Car_Reg_No → KM_Covered, Model, Manufacturer}

The key for this relation will be,

(SSN)+ = SSN, OName

(Car_Reg_No)+ = Car_Reg_No, KM_Covered, Model, Manufacturer

(SSN, Car_Reg_No)+ = SSN, OName, Car_Reg_No, KM_Covered, Model, Manufacturer

The closure of (SSN, Car_Reg_No) identifies all the attributes of CARS. Hence, (SSN, Car_Reg_No) is the candidate key for CARS.

2NF – Table should be in 1NF and all non-key attributes should fully functionally dependent on the candidate key.

In our relation,

• Candidate key – (SSN, Car_Reg_No)

• Non-key attributes - OName, KM_Covered, Model, and Manufacturer

CARS is not in 2NF because of the following reasons;

The candidate key is the composite key of two attributes [SSN and Car_Reg_No]. The non-key attributes can be determined by either of the key attributes without the help of the other key attributes. For example, the non-key attribute OName can be determined uniquely by SSN alone without Car_Reg_No. Also, KM_Covered, Model, and Manufacturer non-key attributes can be determined by Car_Reg_No alone without SSN. This kind of functional dependency is called as partial functional dependency.

If a relation is not in 2NF, then we may not say that the relation is in further normal forms like 3NF, and BCNF.

         Previous Question                                                                                Next Question

Find all the candidate keys of the relational table R

Find the candidate keys of the given relation schema / Find keys of relational table / Which of the following is(are) the candidate key(s) for the relation R?

Question:

5. Given the following relation R and the set of functional dependencies S that hold on R, which of the following options shows the valid candidate keys for R. R(A, B, C, D, E, F) S: {DF → C, BC → F, E → A, ABC → E}

(a) ABC, DEF
(b) ABD, BDE
(c) ABCD, BDEF
(d) DEF, ACD, BCF

Answer:

(c) ABCD, BDEF


Refer the closure finding algorithm here. result := ABCD
result := ABCDE through the functional dependency ABC → E
result := ABCDEF through BC → F
Finally, result := R.
Hence, ABCD is one of the candidate keys.

result := BDEF
result := BCDEF through the functional dependency DF → C
result := ABCDEF through E → A
Finally, result := R
Hence, BDEF is one of the candidate keys.

         Previous Question                                                                                Next Question

Given the functional dependencies, find the candidate keys

Which of the following is the correct set of candidate keys for relation R.

Finding all valid candidate keys of a relational table R

Which of the normal form does the given relation satisfy

Find the normal form of the given relation schema / Which of the normal form does the given relation satisfy? / The relational table is in 2NF, 3NF or BCNF?

Question:

4. Assume a relation R with the schema R(A, B, C, D, E) and a set F of functional dependencies as follows; F = {A → B, C → D, D → E} The relation R is not in Second Normal Form (2NF). Why?

(a) R has no repeating groups
(b) R has transitive functional dependencies
(c) R has partial functional dependencies
(d) R has no key

Answer:

(c) R has partial functional dependencies

As per the question,

• Given - Schema of relation R and the set F of functional dependencies.

• Not known - The key.

The key for R is AC, a composite key (combination of two or more attributes). When we have composite keys, we need to verify that all the non-key attributes are fully functionally dependent on the whole key or not. In our question, the non-key attributes are B, D, and E. B is fully functionally dependent on A alone (A is part of AC, and B is partially dependent on AC), D is fully functionally dependent on C alone (C is part of AC, and D is partially dependent on AC). Hence, the rule for 2NF is violated and R is not in 2NF.

         Previous Question                                                                                Next Question

Find the normal form of the given relation

Find the normal form of the given relation schema / Is the relation in 1NF? / Is the table in 2NF? / Is the table in 3NF? / Is the table in BCNF?

Question:

3. Assume a relation R with the schema R(A, B, C, D, E). The primary key of R is A. Which of the following is correct for R?

(a) R is in 1NF only
(b) R is in both 1NF and 2NF
(c) R is in 3NF
(d) R is in BCNF

Answer:

(b) R is in both 1NF and 2NF

As per the question,

• Given - Schema of relation R and the key of R.

• Not known - The set of functional dependencies

1NF - We don't need functional dependencies. Hence, we would say that R is in 1NF.
2NF - We need functional dependencies and the key for R. If the key is composite (combination of two or more attributes), we need the set of functional dependencies to determine the normal form. If the key is single attribute we don't need functional dependencies. In our question the key is A, hence we would say that R is in 2NF.

Hence, R is in both 1NF and 2NF.



R is not in 3NF (we need functional dependencies to find Transitive dependencies), and not in BCNF (we need all the Candidate keys).

         Previous Question                                                                                Next Question

Find all the minimal keys of a relation R

Find all the possible minimal keys of a relation / How to find keys of a relation in database management system / Keys or minimal key concepts in dbms / Role of keys or candidate keys in relational database design

Question:

2. For a relation R(A, B, C, D, E) with the set of functional dependencies F = {A → B, CD → E, B → D, E → A}, which of the following are the candidate keys (minimal keys) of R?

(a) AB, CD
(b) AC, BC, CD, CE
(c) AC, BC, AEC
(d) A, D, DE

Answer:

(b) AC, BC, CD, CE

To find a key or minimal key of a relation, we need to find the closure of certain attributes (most of the cases, the attribute(s) on the left hand side of a functional dependency). The closure that includes all the attributes of R in the result is one of the keys (minimal keys/candidate keys). Refer here for a detailed example on how to find the key of a relation. Let us apply the closure finding algorithm on all LHS attributes of the given set of functional dependencies. The result is as follows;

Closure of A, ie., (A)⁺ = ABD [from A → B and B → D]. ABD is not equal to ABCDE. Hence A is not a candidate key (minimal key).

(B)⁺ = BD [from B → D]. BD ≠ ABCDE, hence B is not a candidate key.

(E)⁺ = ABDE [from E → A, A → B, and B → D]. So  E is not a key.

(CD)⁺ = ABCDE [from CD → E, E → A, and A → B]. As the closure of CD is results in all attributes of R. Hence, CD is one of the candidate keys.

The other candidate keys can be found by combining two or more LHS attributes. In the line,

(AC)⁺ = ABCDE [from A → B, B → D, and CD → E]

(BC)⁺ = ABCDE [from B → D, CD → E, and E → A]

(CE)⁺ = ABCDE [from E → A, A → B, and B → D]

In the option (C), AEC cannot be a minimal key. Because the proper subset {(AE), (AC), (EC), (A), (E), (C)} contains the minimal key. But (AEC) is regarded as the super key as it is a super set of a minimal key.

         Previous Question                                                                                Next Question

Find the inference rule of the given functional dependency

Find the inference rule of the given functional dependency / Armstrong's axioms / Inference rules / Normalization process

Question:

1. For a relation R(A, B, C), if A → B and A → C holds, then A → BC also holds. Which of the following rule ensures this?

(a) Augmentation rule
(b) Union rule
(c) Decomposition rule
(d) None of the above

Answer:

(b) Union rule

Union rule says that a set of functional dependencies that have same left hand side attributes can be combined to form a single functional dependency. For example, the FDs AC → B, AC → DE and AC → F can be combined to AC → BDEF.

Decomposition rule is the opposite of union rule. Augmentation rule is about adding same set of attributes on both sides of a functional dependency.

         Previous Question                                                                                Next Question

Identify the anomalies that are present in the given table

Finding anomalies that are present in a given relation table, Solved exercise for finding the anomalies like insertion, deletion and modifcation, Fix the given table by eliminating the anomalies

Question:

Consider the relation Treatment with the schema Treatment (doctorID, doctorName, patientID, diagnosis) and functional dependencies;

doctorID → doctorName and

(doctorID, patientID) → diagnosis.

Describe different types of anomaly that can arise for this table with example records.

Answer:

Example:

doctorID	doctorName	patientID	diagnosis
D001	Mohan	PAT123	Fever
D002	Vijay	PAT110	Alergy
D003	Jenifer	PAT112	Fever
D002	Vijay	PAT121	Cold

TREATMENT has two FDs. From the FDs, we can derive that the combination (doctorID, patientID) is the primary key for TREATMENT.

Anomalies:

Insertion anomaly: The inability to store certain attributes’ values without the other attributes. If we are not able to insert a record into a relational table because of the absence of values for other attributes is called insertion anomaly.

For Treatment, we cannot insert the doctor information like doctorID and doctorName without any patient. That is, we need at least one patient to include the doctor information into the table. For example, if one more doctor Dr.Neeraj is appointed, we need to allocate at least one patient to insert Dr.Neeraj’s information. This inability is insertion anomaly.

Deletion anomaly: Deletion of values of certain attributes from any records (rows) will lead to lose of other attributes’ values of the same records. That means, we lose the complete information about an entity if we delete few values. This is called as deletion anomaly.

Deleting patients’ diagnosis could delete the name of their doctor. For example, Dr.Mohan has only one patient PAT123 registered for him. If we delete the patient PAT123, we need to delete Dr.Mohan’s details as well. This is the deletion anomaly present in the TREATMENT table.

Modification anomaly: Modification of certain values in a table may lead to change the values in more than one record if that particular value has duplicates. If we miss any one occurrence of that data, that leads to inconsistency of the table. This is called as modification anomaly.

A doctor may have more than one patient, so an update anomaly may result if a doctor’s name is changed for a given doctorID for only one patient. For example, in our table TREATMENT Dr.Vijay has two patients. Suppose that we need to change the doctor name from Vijay to Vijay Kumar. This change has to be done on two records. What if we change with second record and not changing with fourth record? If we do such thing, we are not able to find the exact name of the doctor of doctor ID D002. This stage is called as modification anomaly.

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

Go back to Normalization – solved exercises page.