Functional Dependencies and Keys

 

 

1. Functional Dependencies and Keys

Given Functional Dependencies

– A → BCD
– AD → E
– EFG → H
– F → GH

(a) Minimal Key for R

To find the minimal key for the relation R(A, B, C, D, E, F, G, H), we need to determine the attributes that can uniquely identify all other attributes based on the functional dependencies provided.

1. Start with A: From A → BCD, if we know A, we can derive B, C, and D.
2. Next, consider AD: Since knowing A gives us BCD and AD → E, we can derive E if we also know D.
3. Consider F: If we know F, we can derive G and H since F → GH and EFG → H requires both E and F.
4. Combining: To derive all attributes, we can start from A and include D and F in our key:- A + D derives B, C, D (from A), E (from AD), and F gives us G and H.
– Therefore, one minimal key can be ADF.

(b) Functional Dependency that Can Be Removed

To identify which functional dependency can be removed without altering the key:

1. Check each dependency:- Removing A → BCD: This cannot be removed since A is part of the minimal key.
– Removing AD → E: Cannot be removed as D is necessary to derive E.
– Removing EFG → H: Not critical as we can derive H through F alone.
– Removing F → GH: This dependency is crucial for deriving G and H.

Thus, the functional dependency that can be removed without altering the key is EFG → H.

2. UnivInfo Schema Analysis

Given Schema

UnivInfo(studID, studName, course, profID, profOffice)

(a) Nontrivial Functional Dependencies

Based on the assumptions provided:

1. studID → studName (Each student has one unique ID corresponding to one name)
2. profID → profOffice (Each professor has one unique ID corresponding to one office)
3. studID, course → profID (A specific student taking a specific course is taught by one professor)
4. course → profID (No course is taught by more than one professor)

(b) Minimal Keys for UnivInfo

To determine the minimal keys using the functional dependencies identified:

– From studID and course, we can identify profID:- Thus, a minimal key can be (studID, course).

This combination is sufficient to uniquely identify each tuple in the relation.

(c) Is UnivInfo in BCNF?

To check if UnivInfo is in BCNF:

– A relation is in BCNF if for every functional dependency X → Y, X is a superkey.

1. studID → studName: studID is not a superkey (there are multiple students with the same name).
2. profID → profOffice: profID is a superkey.
3. studID, course → profID: This is fine as it is a superkey.
4. course → profID: course is not a superkey.

Since there are dependencies where the left-hand side is not a superkey (specifically studID → studName and course → profID), UnivInfo is not in BCNF.

Decomposition into BCNF

To decompose:

1. Create a new relation for students:- Students(studID, studName)

2. Create a new relation for professors:- Professors(profID, profOffice)

3. The remaining relation:- CourseInfo(studID, course, profID)

This decomposition results in:

– Students(studID, studName)
– Professors(profID, profOffice)
– CourseInfo(studID, course, profID)

(d) Additional Assumptions Functional Dependencies

With additional assumptions:

1. No student takes two different courses from the same professor:- studID, course → profID

2. No course is taught by more than one professor:- course → profID

Additional dependencies:

– studID, course → profID (already included)
– course → profID (already included)

(e) Minimal Keys with Additional Dependencies

Based on all functional dependencies now:

– The minimal keys remain (studID, course) as this combination still allows us to uniquely identify each tuple in the relation.

(f) Is UnivInfo in BCNF with Additional Dependencies?

We revisit the functional dependencies:

1. studID → studName: studID is not a superkey.
2. profID → profOffice: profID is a superkey.
3. studID, course → profID: This is fine as it is a superkey.
4. course → profID: course is not a superkey.

Since there are still dependencies where the left-hand side is not a superkey (specifically studID → studName and course → profID), UnivInfo remains not in BCNF.

Decomposition into BCNF with Additional Dependencies

The same decomposition as earlier holds:

1. Create Students(studID, studName)
2. Create Professors(profID, profOffice)
3. Create CourseInfo(studID, course, profID)

This ensures that all relations are now in BCNF and adheres to the stated assumptions.