## Solutions - Relational Algebra Workshop 6

---
### Exercise 1. find the functional dependencies based on the relation.

| StudentID | CourseID | StudentName  | DeptID | DeptName          | CourseTitle | Grade |
|:---------:|:--------:|:-------------|:------:|:------------------|:------------|:-----:|
| S01       | C101     | Alice Brown  | D10    | Computer Science  | Databases   | A     |
| S01       | C102     | Alice Brown  | D10    | Computer Science  | Networks    | B+    |
| S02       | C101     | Ben Clark    | D20    | Mathematics       | Databases   | B     |
| S02       | C103     | Ben Clark    | D20    | Mathematics       | Algorithms  | B-    |
| S03       | C103     | Chloe Diaz   | D10    | Computer Science  | Algorithms  | A-    |
| S03       | C102     | Chloe Diaz   | D10    | Computer Science  | Networks    | A     |

* Functional dependencies include:
	* StudentID → StudentName
	* CourseID → CourseTitle
	* DeptID → DeptName
	* {CourseID, StudentID} → Grade
	
### Exercise 2. from the FDs in exericse 1, decompose the relation into 3NF.

Why not 2NF? StudentName depends only on StudentID; CourseTitle depends only on CourseID. These are partial dependencies on the composite key.
Why not 3NF? DeptName depends on DeptID, and DeptID depends on StudentID, so DeptName is transitively dependent on the key.

— Decompose to 2NF (remove partial dependencies off the composite key)

Put attributes that depend only on StudentID into STUDENT.
Put attributes that depend only on CourseID into COURSE.
Keep the “fully key-dependent” attribute (Grade) with the composite key in ENROLLMENT.



STUDENT(StudentID, StudentName, DeptID, DeptName)   -- 2NF

| StudentID | StudentName | DeptID | DeptName         |
|:---------:|:------------|:------:|:-----------------|
| S01       | Alice Brown | D10    | Computer Science |
| S02       | Ben Clark   | D20    | Mathematics      |
| S03       | Chloe Diaz  | D10    | Computer Science |


COURSE(CourseID, CourseTitle)   -- 2NF

| CourseID | CourseTitle |
|:--------:|:------------|
| C101     | Databases   |
| C102     | Networks    |
| C103     | Algorithms  |


ENROLLMENT(StudentID, CourseID, Grade)   -- 2NF

| StudentID | CourseID | Grade |
|:---------:|:--------:|:-----:|
| S01       | C101     | A     |
| S01       | C102     | B+    |
| S02       | C101     | B     |
| S02       | C103     | B-    |
| S03       | C103     | A-    |
| S03       | C102     | A     |


Now there are no partial dependencies in any relation (each relation’s key is single-attribute or the only non-key attribute, Grade, depends on the full composite key).

— Decompose to 3NF (remove transitive dependencies)

In STUDENT, DeptName depends on DeptID (not on StudentID directly), so split the department out.


DEPARTMENT(DeptID, DeptName)   -- 3NF

| DeptID | DeptName         |
|:------:|:-----------------|
| D10    | Computer Science |
| D20    | Mathematics      |


STUDENT(StudentID, StudentName, DeptID)   -- 3NF

| StudentID | StudentName | DeptID |
|:---------:|:------------|:------:|
| S01       | Alice Brown | D10    |
| S02       | Ben Clark   | D20    |
| S03       | Chloe Diaz  | D10    |

Alternatively, you could use R( CourseID, DeptID) to the above.


COURSE(CourseID, CourseTitle)   -- 3NF

| CourseID | CourseTitle |
|:--------:|:------------|
| C101     | Databases   |
| C102     | Networks    |
| C103     | Algorithms  |


ENROLLMENT(StudentID, CourseID, Grade)   -- 3NF

| StudentID | CourseID | Grade |
|:---------:|:--------:|:-----:|
| S01       | C101     | A     |
| S01       | C102     | B+    |
| S02       | C101     | B     |
| S02       | C103     | B-    |
| S03       | C103     | A-    |
| S03       | C102     | A     |

Result:

2NF achieved by removing attributes that depended on only part of the composite key.
3NF achieved by removing the transitive dependency DeptID → DeptName from STUDENT into DEPARTMENT.
A natural join of the 3NF tables reconstructs the original 1NF relation (no closures or inference rules needed to follow the reasoning—just the normal-form definitions).

### Exercise 3. Decompose the relation into 3NF.
* R(A, B, C, D, E, F)
* 1) A → B
* 2) C → D
* 3) AC → E
* 4) E → F

* Composite Key AC inferred by determining every other attribute. 
* The relation is in the first normal form, as there are no multi-valued attributes.
* Relation R is not in the 2nd normal form, as:
	* D is only partially determined by AC, as C->D
	* R1(A, B, C, E, F)
	* R2(C, D)
	
* Relations R1,R2 is stiill not in 2nd normal form as:
	* B is only partially determined by AC, as A -> B
	* Decompose:
		* R1(A, C, E, F)
		* R2(C, D)
		* R3(A, B)
		
* The relations R1,R2,R3 are not in 3NF:
	* As AC -> E and E -> F is a transitive dependency.
	* Decompose:
		* R1(A, C, E)
		* R2(C, D)
		* R3(A, B)
		* R4(E, F)
		
* Relations R1,R2,R3,R4 are in the third normal form.

### Exercise 4. Decompose the relation into 3NF.

Schema (single relation):

* R(A, B, C, D, E)

Functional dependencies:

* F = { A → BC, CD → BE }

* The relation R is in the first normal form, no multi-valued attributes.
* Composite key is AD, inferred by transitive rule A-> C and CD -> BE, thereforce AD -> BE.
* We will cover the transitive rule next week, but it is worth exploring here.
* The relation R is not in the second normal form, as C is only partially dependent on AD, as A -> C
	* Decompose:
		* R1(A, B, D, E)
		* R2(A, C)
		
* The relations R1,R2 are not in the second normal form, as B is only partially dependent on AD, as A->B
	* Decompose:
		* R1(A, D, E)
		* R2(A, C)
		* R3(A, B)
		
The relations R1,R2,R3 are in the third normal form, as there is no transitive dependencies.







---

 Remember that there are multiple ways to solve these problems, if you are unsure, post your solution in the workshop forums for discussion.