Find the redundant extraneous attributes

Find the redundant (extraneous) attributes from the set of functional dependencies

Question:

Consider the relation STUDENT with the schema STUDENT(RegNo, Name, DOB, Age, Dept, Course, Semester, Grade) and set of functional dependencies F = {RegNo → Name, RegNo → DOB, RegNo DOB → Age, RegNo → Dept, RegNo Dept Course Semester → Grade}. Find the attributes that are redundant in the given set F of functional dependencies.

Solution:

What is redundant attribute?

An attribute in the left hand side (LHS) of a functional dependency, especially if more than one attribute present in the LHS, is said to be a redundant (extraneous) attribute if the RHS attribute(s) can be determined with the help of other LHS attributes.

How to identify a redundant attribute?

If the RHS of the said functional dependency can be derived without one of the attributes on the LHS, using the other FDs of that relation, then that particular attribute is said to be redundant. For example, in AB → C the attribute B is redundant if closure of A can determine C.

Let us solve the given question;

We don’t need to check for redundant attributes in a FD (functional dependency) where the LHS attribute is only one. Hence, we can omit the following FDs.

RegNo → Name,

RegNo → DOB,

RegNo → Dept,

(i) Now let us take the FD RegNo DOB → Age. To check either of the LHS attributes are redundant, we have to use the other attribute to derive the RHS.

Is DOB redundant?

To check, we have to find the closure of the other attributes. In this FD, RegNo is the only other attribute. Hence let us find the closure of RegNo.

(RegNo)⁺ = RegNo, Name, DOB, Dept, Age.

Observe from the closure that the attribute Age is part of the closure. Hence, DOB is redundant attribute. So we can remove DOB from RegNo DOB → Age results in the FD RegNo → Age.

Now our F becomes { RegNo → Name, RegNo → DOB, RegNo → Age, RegNo → Dept, RegNo Dept Course Semester → Grade}

(ii) Now let us take the last FD RegNo Dept Course Semester → Grade.

Is Dept redundant?

Find the closure of RegNo, Course, Semester.

(RegNo Course Semester)⁺ = RegNo, Name, DOB, Dept, Age, Course, Semester, Grade.

Result includes Grade. So attribute Dept is redundant and can be removed.

Now our F becomes { RegNo → Name, RegNo → DOB, RegNo → Age, RegNo → Dept, RegNo Course Semester → Grade}

(iii) Let us take the last FD given above, RegNo Course Semester → Grade.

Is Course redundant?

Find the closure of RegNo, Semester.

(RegNo Semester)⁺ = RegNo, Name, DOB, Age, Dept, Semester

The result does not include Grade. Hence, the attribute Course is not redundant. And our F does not change.

Is Semester redundant?

Find the closure of RegNo, Course.

(RegNo, Course)⁺ = RegNo, Name, DOB, Age, Dept, Course.

The result does not include Grade. Hence, the attribute Semester is not redundant. And our F does not change.

The final set of functional dependencies F is as follows;

F = { RegNo → Name, RegNo → DOB, RegNo → Age, RegNo → Dept, RegNo Course Semester → Grade}

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

Go to Normalization - Solved Exercises page

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

Go to How to find closure? page

Find the redundant attributes in a given functional dependency

How to remove redundant attributes

How to remove extraneous attributes

Find and remove redundant (extraneous) attributes

Normalize relational table by removing redundant attributes

How to eliminate extraneous attributes to find minimal cover

Find the functional dependencies and normalize the table to 3nf

Find the functional dependencies, 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, How many candidate keys are there for a table, Normalize the table to 3nf, Third Normal Form example

Question:

Consider a relation Student (StudentID, ModuleID, ModuleName, StudentName, StudentAddress, TutorId, TutorName). Each student is given a StudentID and each module given a ModuleID. A student can register more modules and a module can be registered by more students. TutorID is the ID of the student's personal tutor, it is not related to the modules that the student is taking. Each student has only one tutor, but a tutor can have many tutees. Different students can have the same name. Different students can be living at the same address.

Find all the functional dependencies holding in this relation and normalize the table to 3NF.

Solution:

Finding functional dependencies:

It is given that each student has unique ID and unique tutor. So,

• StudentID → StudentName, StudentAddress, TutorId, TutorName

It is given that each module is uniquely identified by an ID. So,

• ModuleID → ModuleName

Tutor is given a TutorID. Hence,

• TutorID → TutorName

Finding candidate key(s):

Find closure for left hand side attributes of above functional dependencies.

(StudentID)⁺ = StudentID StudentName, StudentAddress, TutorID, TutorName

Closure of StudentID does not give complete Student table. Hence, StudentID is not a candidate key.

(ModuleID)⁺ = ModuleID, ModuleName

Closure of ModuleID does not give complete Student table. Hence, ModuleID is not a candidate key.

(TutorID)⁺ = TutorID, TutorName

Closure of TutorID does not give complete Student table. Hence, TutorID is not a candidate key.

(StudentID, ModuleID)⁺ = StudentID StudentName, StudentAddress, TutorID, TutorName, ModuleID, ModuleName = Student.

Hence, the combination (StudentID, ModuleID) is the only candidate key for Student relation.

Is Student in 2NF?

If there are partial dependencies in the relation, then the relation is not in 2NF.

In our question, the key is composite hence there are possibilities for partial dependencies.

• StudentID alone identifies StudentID StudentName, StudentAddress, TutorID, TutorName attributes. This is one partial dependency.

• ModuleID identifies ModuleID, ModuleName attributes uniquely. This is another partial dependency.

Due to these partial dependencies, Student relation is not in 2NF. So, we need to decompose Student further on individual partial dependencies. In that process Student becomes as follows;

Student (StudentID, StudentName, StudentAddress, TutorID, TutorName)

Module (ModuleID, ModuleName)

To establish a conection between Student and Module, we need to create a new relation (man-to-many relationship) as follows;

Stu_Module (StudentID, ModuleID)

All these three tables are in 2NF.

Are they in 3NF?

To be in 3NF, a relation should not have any transitive dependency (non-key functional dependency).

New Student relation has a functional dependency TutorID → TutorName which is transitive. [How? StudentID → TutorID and TutorID → TutorName]

Student relation is not in 3NF. To convert it to 3NF, decompose the relation using the violating functional dependency. In this process, we get the following relations;

Stu (StudentID, StudentName, StudentAddress) and

Tutor (TutorID, TutorName)

Both of these relations are in 3NF.

No transitive dependencies are found in the other two relations Module and Stu_Module. Hence they are also in 3NF.

Following are the final relation schemas in 3NF;

Stu (StudentID, StudentName, StudentAddress)  

Tutor (TutorID, TutorName)

Module (ModuleID, ModuleName)

Stu_Module (StudentID, ModuleID)

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

Go to Normalization - Solved Exercises page

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

Go to How to find closure? page

 

Find all the candidate keys of the given relation R

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, How many candidate keys are there for a table

Question:

Given a schema R( A, B, C, D, E), and the following set of FDs: {A→ E, E → CD, BC → A, D → B}

Solution:

To find the key of a relation, we need to find the closure of attributes. If any attribute’s or set of attributes’ closure gives all the attributes of the relation, then we would say that attribute/set of attributes as the key for that relation.

To simplify this task or to avoid wasting time on finding closure of all attributes, let us do find the closure for left hand side (LHS) attributes of the given functional dependencies.

In the given exercise, all the attributes of R are present in the LHS of some functional dependencies. Hence, we need to try for all LHS attributes.

LHS	Due to the FDs	Result becomes	Description
A+	A→ E E→ CD D→ B	= AE (Reflexive) = AECD (Transitive) = AECDB (Transitive) = ABCDE	The result of A+ is equivalent to R. A is a candidate key.
E+	E→ CD D→ B BC→ A	= ECD (Reflexive) = ECDB (Transitive) = ECDBA (Transitive) = ABCDE	E+ gives R. E is a candidate key.
D+	= DB	D→ B (Reflexive)	D+ is not equivalent to R. D is not a candidate key.
B+ or C+	Neither B nor C alone form the LHS of any FDs. Hence, they individually cannot form a candidate key.
So far we have tried individual (singleton) attributes. We can now try the combination of different attributes. We do not need to test the combination of attributes that have either A or E. The superset of either A or E cannot be a candidate key.
(BC)+	BC→ A A→ E E→ CD	= BCA (Reflexive) = BCAE (Transitive) = BCAED (Transitive) = ABCDE	(BC)+ is equivalent to R. (BC) is a candidate key.
(CD)+	D→ B BC→ A A→ E	= CDB (Reflexive) = CDBA (Augment) = CDBAE (Transitive) = ABCDE	(CD) is a candidate key.

A, E, BC, and CD are the candidate keys of the relation R.

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

Go to Normalization - Solved Exercises page

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

Go to How to find closure? page

 

Find all the candidate keys of a given relation in RDBMS