## Solutions - Relational Algebra Workshop 7

---

### Exercise 1. Find the closure for each functional dependencies.

* Relation: R(A, B, C, D, E, F, G, H)
* Functional dependencies F:
	* A → B, C
	* B → D
	* C → E
	* D, E → F
	* F → G
	* G → H
	
* Closures of each FD’s LHS (X+)
	* A+ = {A, B, C, D, E, F, G, H}
	* B+ = {B, D}
	* C+ = {C, E}
	* (DE)+ = {D, E, F, G, H}
	* F+ = {F, G, H}
	* G+ = {G, H}
	
*'A' can also be considered a candidate key for the universal relation.*

### Exercise 2. Prove the sets of Functional Dependencies are equivalent.

* Relation: R(A, B, C, D)
* Set F1: { A → B, A → C, C → D }
* Set F2: { A → BC, C → D }

These two FD sets are different but equivalent (they imply exactly the same FDs overall).

**1)** Show F1 ⊆ F2+ (each FD in F1 holds under F2)

* Compute closures under F2:
* A+ under F2:
	* Start {A}
	* A → BC ⇒ add B, C → {A, B, C}
	* C → D ⇒ add D → {A, B, C, D}
* Thus A → B and A → C hold under F2.
* C+ under F2:
	* Start {C}
	* C → D ⇒ add D → {C, D}
* Thus C → D holds under F2.
* So every FD in F1 is implied by F2.

| LHS |	RHS to check |	Closure under F2 |	Contains RHS? |
|:--------:|:----:|:----:|:----:|
| A |	B |	{A, B, C, D} |	Yes |
| A |	C |	{A, B, C, D} |	Yes |
| C |	D |	{C, D} |	Yes |


* Show F2 ⊆ F1+ (each FD in F2 holds under F1)
* Compute closures under F1:
* A+ under F1:
	* Start {A}
	* A → B, A → C ⇒ add B, C → {A, B, C}
	* C → D ⇒ add D → {A, B, C, D}
* Thus A → BC holds under F1.
* C+ under F1:
	* Start {C}
	* C → D ⇒ add D → {C, D}
* Thus C → D holds under F1.
* So every FD in F2 is implied by F1.

| LHS |	RHS to check |	Closure under F1 |	Contains RHS? |
|:--------:|:----:|:----:|:----:|
| A |	BC |	{A, B, C, D} |	Yes |
| C |	D |	{C, D} |	Yes |

* Conclusion: Since F1 ⊆ F2+ and F2 ⊆ F1+, we have F1+ = F2+, so F1 and F2 are equivalent.

### Exercise 3. Find the minimal set of Functional Dependencies:

* Relation: R(A, B, C, D, E)
* Initial FDs F:
	* A → B
	* B → C
	* AB → C
	* AC → D
	* D → E
* We’ll apply your algorithm step by step.

* **Step 1** — Canonical form (decompose RHS)
* All FDs already have a single attribute on the RHS, so F is already in canonical form.

* Current set: F = { A → B, B → C, AB → C, AC → D, D → E }

* **Step 2** — Remove redundant FDs (using closures)
* For each FD X → Y, temporarily remove it and compute X under the remaining FDs. If Y∈X , it’s redundant. 

* Test A → B: 
* Use F \ {A → B} = {B → C, AB → C, AC → D, D → E}
* A ={A} (no rule applies) ⇒ B ∉ A ⇒ not redundant.
  
* Test B → C:
* Use F \ {B → C} = {A → B, AB → C, AC → D, D → E}
* B ={B} ⇒ C ∉ B ⇒ not redundant.
  
* Test AB → C:
* Use F \ {AB → C} = {A → B, B → C, AC → D, D → E}
* (AB) :{A,B}⇒ via B → C add C ⇒ (AB) ={A,B,C}
* C ∈ (AB) ⇒ AB → C is redundant. Remove it.
  
* Test AC → D:
* Use {A → B, B → C, D → E}
* (AC) :{A,C}⇒ A → B gives B; B → C keeps C; no D ⇒ not redundant.
 
* Test D → E:
* Use {A → B, B → C, AC → D}
* D ={D} ⇒ E ∉ D ⇒ not redundant.
* After Step 2: F = { A → B, B → C, AC → D, D → E }

* **Step 3**  — Remove extraneous LHS attributes
* For each FD with multi-attribute LHS, try removing one attribute x from X → Y. 
* Compute (X−{x}) using the other FDs. If the removed attribute x ∈ (X−{x}), then x is extraneous (replace X → Y with (X − {x}) → Y).
* Only multi-LHS FD is AC → D.
* Remove A from AC → D:
* Use other FDs {A → B, B → C, D → E}
* C ={C} ⇒ A ∉ C ⇒ A is not extraneous.
* Remove C from AC → D:
* Use other FDs {A → B, B → C, D → E}
* A :{A}⇒ A → B add B; B → C add C ⇒ A ={A,B,C}
* C ∈ A ⇒ C is extraneous in AC → D. Replace AC → D with A → D.
* Now: F = { A → B, B → C, A → D, D → E }

* **Step 4** — Repeat Steps 2 and 3 (since we changed something)
* Run Step 2 again on { A → B, B → C, A → D, D → E }:

* A → B: withhold it ⇒ A ={A,D,E} ⇒ B ∉ A ⇒ keep.
* B → C: withhold ⇒ B ={B} ⇒ keep.
* A → D: withhold ⇒ A :{A}⇒ A → B, B → C; cannot reach D ⇒ keep.
* D → E: withhold ⇒ D ={D} ⇒ keep.
* No redundancies.

* **Step 3 again:** all LHS are singletons; nothing to test.

* **Step 5** — Union rule to simplify presentation
* Combine FDs with the same LHS: {X→Y, X→Z} ⊨ X→YZ.

* Combine A → B and A → D into A → BD.
* Final minimal set (canonical-cover form, unioned by LHS):

* { A → BD, B → C, D → E }
*This is minimal:

* No FD is redundant (each fails the Step-2 test if removed).
* No LHS has extraneous attributes (all LHS are singletons).
* Union is just a presentation convenience; the underlying minimal cover before union is:
	* { A → B, A → D, B → C, D → E }.

### Exercise 4. Find the minimal set of Functional Dependencies:

Lossless-join test (rows = relations, columns = attributes)
Legend: aX = "a for attribute X"; bXj = fresh symbol for (row j, attribute X)

============================================================
Example 1 — LOSSLESS

Relation: R(A, B, C)
FDs: F = { A → B, A → C }
Decomposition: R1(A, B), R2(A, C), R3(A)

Step 1–3: Initialize the matrix

| Relation |   A  |   B  |   C  |
|:--------:|:----:|:----:|:----:|
| R1(AB)   |  aA  |  aB  | bC1  |
| R2(AC)   |  aA  | bB2  |  aC  |
| R3(A)    |  aA  | bB3  | bC3  |

Step 4: Apply FDs until no change

FD A → B:
- Rows with A = aA: R1, R2, R3 → set B := aB in those rows.

Intermediate:

| Relation |   A  |   B  |   C  |
|:--------:|:----:|:----:|:----:|
| R1(AB)   |  aA  |  aB  | bC1  |
| R2(AC)   |  aA  |  aB  |  aC  |
| R3(A)    |  aA  |  aB  | bC3  |

FD A → C:
- Rows with A = aA: R1, R2, R3 → set C := aC in those rows.

After closure:

| Relation |   A  |   B  |   C  |
|:--------:|:----:|:----:|:----:|
| R1(AB)   |  aA  |  aB  |  aC  |
| R2(AC)   |  aA  |  aB  |  aC  |
| R3(A)    |  aA  |  aB  |  aC  |

Step 5: Check for a row of all a_i
- Every row is all a_i → decomposition is LOSSLESS.

============================================================
Example 2 — LOSSY

Relation: R(A, B, C)
FDs: F = { A → B }
Decomposition: R1(A, B), R2(B, C), R3(A)

Step 1–3: Initialize the matrix

| Relation |   A  |   B  |   C  |
|:--------:|:----:|:----:|:----:|
| R1(AB)   |  aA  |  aB  | bC1  |
| R2(BC)   | bA2  |  aB  |  aC  |
| R3(A)    |  aA  | bB3  | bC3  |

Step 4: Apply FDs until no change

FD A → B:
- Rows with A = aA: R1, R3 → set B := aB in those rows.

After closure:

| Relation |   A  |   B  |   C  |
|:--------:|:----:|:----:|:----:|
| R1(AB)   |  aA  |  aB  | bC1  |
| R2(BC)   | bA2  |  aB  |  aC  |
| R3(A)    |  aA  |  aB  | bC3  |

Step 5: Check for a row of all a_i
- No row is all a_i → decomposition is LOSSY.

### Exercise 5. Find the 3rd normal form using the algorithm provided:

Universal relation: Enrollment_BIG(
  StudentID, StudentName, StudentEmail,
  MajorID, MajorName, FacultyID, FacultyName,
  CourseID, CourseTitle, Term, Grade
)

Sample tuples

| StudentID | StudentName       | StudentEmail              | MajorID | MajorName            | FacultyID | FacultyName            | CourseID | CourseTitle            | Term    | Grade |
|:---------:|:------------------|:--------------------------|:-------:|:---------------------|:---------:|:-----------------------|:--------:|:-----------------------|:-------:|:-----:|
| S001      | Edmund Sadgrove   | edmund.sadgrove@uni.au    | MATH    | Mathematics          | FAC01     | Science & Engineering  | CS101    | Intro to Programming   | 2025-S1 | HD    |
| S001      | Edmund Sadgrove   | edmund.sadgrove@uni.au    | MATH    | Mathematics          | FAC01     | Science & Engineering  | STAT201  | Probability            | 2025-S1 | D     |
| S002      | Alice Brown       | alice.brown@uni.au        | ISYS    | Information Systems  | FAC02     | Business & IT          | ISYS100  | Information Systems    | 2025-S1 | C     |

* Business rules (intended FDs F):
	* Each student has one name, one email, and belongs to exactly one major.
	* Each major has one name and belongs to exactly one faculty.
	* Each faculty has one name.
	* Each course has one title and belongs to exactly one faculty.
	* Grades are recorded per (StudentID, CourseID, Term).

* Functional dependencies F:
	1. StudentID → StudentName
	2. StudentID → StudentEmail
	3. StudentID → MajorID
	4. MajorID → MajorName
	5. MajorID → FacultyID
	6. FacultyID → FacultyName
	7. CourseID → CourseTitle
	8. CourseID → FacultyID
	9. StudentID, CourseID, Term → Grade
	10. StudentID → FacultyID
	11. CourseID → FacultyName
	12. StudentID, CourseID, Term → CourseTitle 
	13. MajorID, CourseID → FacultyID

2) Apply your algorithm

Step 1: Find the minimal cover G of F.

* Step 1a: Ensure canonical form (all RHS are single attributes) — F already in canonical form.
* Step 1b: Remove extraneous attributes on LHS:
	* (13) MajorID, CourseID → FacultyID
	* Remove CourseID: MajorID+ ⊇ FacultyID via (5), so CourseID is extraneous.
	* This FD reduces to MajorID → FacultyID, which duplicates (5). Remove (13).
* Step 1c: Remove redundant FDs (implied by others):
	* (10) StudentID → FacultyID is implied by (3) and (5) → remove.
	* (11) CourseID → FacultyName is implied by (8) and (6) → remove.
	* (12) StudentID, CourseID, Term → CourseTitle is implied by (7) → remove.

* Minimal cover G (unioned by LHS only for display; internally still single-RHS):
	* StudentID → StudentName
	* StudentID → StudentEmail
	* StudentID → MajorID
	* MajorID → MajorName
	* MajorID → FacultyID
	* FacultyID → FacultyName
	* CourseID → CourseTitle
	* CourseID → FacultyID
	* StudentID, CourseID, Term → Grade

Step 2: Create a relation R for each FD in G (i.e., for each X → A create schema X ∪ {A})

* R1(StudentID, StudentName)
* R2(StudentID, StudentEmail)
* R3(StudentID, MajorID)
* R4(MajorID, MajorName)
* R5(MajorID, FacultyID)
* R6(FacultyID, FacultyName)
* R7(CourseID, CourseTitle)
* R8(CourseID, FacultyID)
* R9(StudentID, CourseID, Term, Grade)

Populate each with tuples consistent with Enrollment_BIG

R1(StudentID, StudentName)

| StudentID | StudentName       |
|:---------:|:------------------|
| S001      | Edmund Sadgrove   |
| S002      | Alice Brown       |

R2(StudentID, StudentEmail)

| StudentID | StudentEmail           |
|:---------:|:-----------------------|
| S001      | edmund.sadgrove@uni.au |
| S002      | alice.brown@uni.au     |

R3(StudentID, MajorID)

| StudentID | MajorID |
|:---------:|:-------:|
| S001      | MATH    |
| S002      | ISYS    |

R4(MajorID, MajorName)

| MajorID | MajorName           |
|:-------:|:--------------------|
| MATH    | Mathematics         |
| ISYS    | Information Systems |

R5(MajorID, FacultyID)

| MajorID | FacultyID |
|:-------:|:---------:|
| MATH    | FAC01     |
| ISYS    | FAC02     |

R6(FacultyID, FacultyName)

| FacultyID | FacultyName           |
|:---------:|:----------------------|
| FAC01     | Science & Engineering |
| FAC02     | Business & IT         |

R7(CourseID, CourseTitle)

| CourseID | CourseTitle           |
|:--------:|:----------------------|
| CS101    | Intro to Programming  |
| STAT201  | Probability           |
| ISYS100  | Information Systems   |

R8(CourseID, FacultyID)

| CourseID | FacultyID |
|:--------:|:---------:|
| CS101    | FAC01     |
| STAT201  | FAC01     |
| ISYS100  | FAC02     |

R9(StudentID, CourseID, Term, Grade)

| StudentID | CourseID |  Term   | Grade |
|:---------:|:--------:|:-------:|:-----:|
| S001      | CS101    | 2025-S1 | HD    |
| S001      | STAT201  | 2025-S1 | D     |
| S002      | ISYS100  | 2025-S1 | C     |

Step 3: If no joining key, create a new relation.

*  Find a key of Enrollment_BIG (15.2(a)-style using closure):
	Let K = {StudentID, CourseID, Term}.
	K+ includes:
	* From StudentID → StudentName, StudentEmail, MajorID.
	* From MajorID → MajorName, FacultyID.
	* From FacultyID → FacultyName.
	* From CourseID → CourseTitle, FacultyID (already present).
	* From StudentID, CourseID, Term → Grade.
 	Thus K+ = {all attributes} → K is a key.
* Relation R9 already contains the key (StudentID, CourseID, Term), so Step 3 is satisfied (no extra relation needed).

Step 4: Remove any relation that is a projection (subset) of another.

* None of R1–R9 is a strict subset of another schema as constructed → no removal.

================================================================================
3) Final 3NF decomposition (from Steps 2–4)

Schemas (dependency-preserving):

* R1(StudentID, StudentName)
* R2(StudentID, StudentEmail)
* R3(StudentID, MajorID)
* R4(MajorID, MajorName)
* R5(MajorID, FacultyID)
* R6(FacultyID, FacultyName)
* R7(CourseID, CourseTitle)
* R8(CourseID, FacultyID)
* R9(StudentID, CourseID, Term, Grade)

Why 3NF:

*  In each relation, its defining FD has a key on the LHS (e.g., StudentID is a key of R1, R2, R3; MajorID is a key of R4, R5; etc.), hence every nontrivial FD in each schema has a superkey on the LHS → 3NF.

Dependency preserving:

* Every FD in G appears verbatim in one of the relations above (X → A is enforced by relation X∪{A}), so the set of dependencies is preserved.

Lossless join:

*  The decomposition includes a relation (R9) that contains a key of the universal relation Enrollment_BIG. The standard 3NF synthesis theorem guarantees that including a key relation makes the decomposition lossless.

---

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