#Practical Session 7 - Design Aglorithms ###By Dr Edmund Sadgrove ### University of New England --- ## Reading * Chapter 8 from ***Fundamentals of Database Systems*** by Elmazri and Navathe --- ## Summary * Introduction * Normal Forms * Inference rules * Closures * Equivalence of Sets of Functional Dependencies * Minimal Sets of Functional Dependencies * The Non-additive join property * Algorithms for Relational Database Design * Examples --- ## Introduction * In this workshop we will revise and work through the concepts of design algorithms. Our exercises will explore the automated examination of a fictional database and look at ways to improve / optimise a solution. --- ## Normal Forms * Last week we looked at **normalization** to reduce redundancy and preserve meaning, there are two approaches to normalization: * **Top down approach** (last week): * High level conceptual design. * Mapping to a relational schema. * Relational design analysis. * **Bottom-up Approach** (this week): * Relational design by synthesis: * Start with functional dependencies. * Analyse using algorithms. ## Inference Rules * In design the **analyst** specifies **functional dependencies** (FD) that are *semantically obvious*. * From this initial set, other functional dependencies can be **inferred**. * **Example**: * mgr\_ssn(Dept\_no `\(\rightarrow \)`mgr\_ssn) *and* * mgr\_phone(mgr\_ssn `\(\rightarrow\)` mgr\_phone) *therefore* * dept_no `\(\rightarrow\)` mgr\_phone * It is evident that not all FDs are explicit - they are inferred from the stated FDs. * To systematically determine inferred functional dependencies, we use formal **inference rules**. These may be revision from AMTH140: * Reflexive Rule: `\(X \supseteq Y \vDash X \rightarrow Y\)` * Augmentation Rule: `\(\{X \rightarrow Y\}\ \vDash \ XZ \rightarrow YZ\)` * Transitive Rule: `\(\{X \rightarrow Y\ , Y \rightarrow Z\}\ \vDash \ X \rightarrow Z\)` * Decomposition Rule: `\(\{X \rightarrow YZ\}\ \vDash \ X \rightarrow Y\ \)` * Union Rule: `\(\{X \rightarrow Y\ , X \rightarrow Z\}\ \vDash \ X \rightarrow YZ\)` * pseudo-transitive Rule: `\(\{X \rightarrow Y\ , WY \rightarrow Z\}\ \vDash \ WX \rightarrow Z\)` * The first three are referred to as *Armstrong's axioms*, others can be inferred from these. ## Closures * Before we get to the **synthesis design algorithms**, we will discuss: * The concepts relating to the inference of new **functional dependencies**. * The concepts of: * **Closure**. * **Minimal cover**. * **Equivalence**. * Recall the desirable properties of normalization: * **Loss-less join property**. * **Dependency preservation property**. * It is useful to find all possible dependencies that can be inferred from a given set of **functional dependencies**. * This is referred to as the *closure*: * For the full set of functional dependencies (*F*). * This is referred to as the **closure of F**. * Denoted by **F +** * This will be useful in determining our desirable decomposition properties. * There is a systematic way to find the closure ***X*+** of each FD in *R*. * The **algorithm** (on the right): * Set *X+* to equal an FD in *R*. * For each FD in *R*: `\( (Y \rightarrow Z) \)`: * If *Y* is a subset of *X+*: * Add *Z* to *X+* * Finish when no more attributes are inferred. * The closure of each FD can be inferred this way. * **Example**: * Recall the EMP_PROJ relation contained the following set of functional dependencies *F*: * FD1: `\(ssn \rightarrow ename \)` * FD2: `\( pnumber \rightarrow \{pname, plocation\} \)` * FD3: `\( \{ssn,pnumber\} \rightarrow hours \)` * Using the algorithm, we can find the following closures for each of the attribute sets on the left side of each functional dependency. ``` F={ ssn→ename, pnumber→{pname,plocation}, {ssn,pnumber}→hours } First we will run through the algorithm to determine {ssn}^+ Step 1: {ssn}^+ = {ssn} Outer-Loop 1: {ssn}^+ = {ssn, ename} Outer-Loop 2: {ssn}^+ = {ssn, ename} End condition Met, therefore end {ssn}^+ = {ssn, ename} ``` ``` F={ ssn→ename, pnumber→{pname,plocation}, {ssn,pnumber}→hours } Now we will run through the algorithm to determine {pnumber}^+ Step 1: {pnumber}^+ = {pnumber} Outer-Loop 1: {pnumber}^+ = {pnumber, pname , plocation} Outer-Loop 2: {pnumber}^+ = {pnumber, pname , plocation} End condition Met, therefore end {pnumber}^+ = {pnumber, pname , plocation} ``` ``` F={ ssn→ename, pnumber→{pname,plocation}, {ssn,pnumber}→hours } Now we will run through the algorithm to determine {ssn,pnumber}^+ Step 1: {ssn,pnumber}^+ = {ssn,pnumber} Loop 1: {ssn,pnumber}^+ = {ssn,pnumber, ename, pname, plocation, hours} Loop 2: {ssn,pnumber}^+ = {ssn,pnumber, ename, pname, plocation, hours} End condition Met, therefore end {ssn,pnumber}^+ = {ssn,pnumber, ename, pname, plocation, hours} ``` * From attribute dependencies under the set of functional dependencies *F*: * We have the following closures: * {ssn}+ = {ssn, ename} * {pnumber}+ = {pnumber, pname , plocation} * {ssn,pnumber}+ = {ssn,pnumber, ename, pname, plocation, hours} ## Equivalence of Sets of Functional Dependencies * We can test if a set of FDs *F* is equivalent to a set *E*. * That is, every FD *E* is also in the *F*+ closure. * This implies that every FD in *E* can be inferred from *F*. * Or *E* is **covered by** *F*. * Two sets of functional dependencies *E* and *D*: * Are considered equivalent if *F*+ = *E*+: * All FDs in *F* can be inferred by those in *E* * All FDs in *E* can be inferred by those in *F* * **Example:** show that *F* and *G* are equivalent: * *F = {A→C, AC→D, E→AD, E→H}* * *G = {A→CD, E→AH}* * First calculate *F*+ with respect to *F* for each FD in *G*: * A+ = {A,C,D} * AC+ = {A,C,D} * E+ = {E,A,H,C,D} * Now calculate *F*+ with respect to *F* for each FD in *F*: * A+ = {A,C,D} * AC+ = {A,C,D} * E+ = {E,A,D,H,C} * Therefore *F* covers *G*. * Now flip these around: * First calculate *G*+ with respect to *G* for each FD in *F*: * A+ = {A,C,D} * E+ = {E,A,D,H,C} * Now calculate *G*+ with respect to *G* for each FD in *G*: * A+ = {A,C,D} * E+ = {E,A,H,C,D} * Therefore *G* covers *F* * Because *F* covers *G* and *G* covers *F*, these two sets of functional dependencies are equivalent. ## Minimal Sets of Functional Dependencies * The **minimal cover** of a set of functional dependencies ***F***: * Is a minimal set of dependencies that is equivalent to ***F*** * It must satisfies the following conditions: 1. Every FD in *F* has a single attribute on its right side. 2. We cannot **replace** an FD in *F* and still have equivalence to *F*. 3. We cannot **remove** an FD from *F* and have a set equivalent to *F*. * The **algorithm**: * **Step 1:** Start with a set of FDs. * **Step 2:** For each FD, put it in canonical form. * E.g. `\( X \rightarrow YZ = X \rightarrow Y, X \rightarrow Z\)`. * **Step 3:** Use inference rules: * Select an FD with multiple left hand attributes. * Determine if the FD can be inferred from the set. * **Step 4:** Use inference rules: * Remove any FD. * Determine if it can be inferred from the remaining set. ## Example: * Example: * **Step 1**: E = {B→A, D→A, AB→D} * **Step 2**: The FDs are already in canonical form. * **Step 3**: Determine if AB→D has any redundant attributes on the left side. * Can it be replaced by B→D or A→D? * By Augmenting B→A with B we get BB→BA. * This simplifies to B→BA and BA→D. * Therefore B→D (transive rule), we now have {B→A, D→A, B→D} * **Step 4**: B→A can be derived from {B→D, D→A} * Remove B→A. * Therefore the minimal cover for *E* is {B→D, D→A}. ## Minimal Sets of Functional Dependencies * Thankfully there is a *mechanical* way that doesn't rely on the use of the inference rules. * **Algorithm:** * **Step 1**: Put FDs in canonical form (decomposition rule - same as before). * **Step 2**: For each functional depdency in the set: * Hide the right hand side attributes (RHS). * Find the closure of the attributes on the left hand side (LHS) from remaing FDs. * If closure contains the RHS of the FD being withheld, then it is redundent. * **Step 3**: For each functional dependency with multiple attributes on the LHS: * Remove an attribute from the FD. * Take the closure of remaining attributes from the other FDs. * If the removed attribute exists in the closure, then it is redundant. * **Step 4**: If any found in 3, run through steps 2 and 3 again, otherwise jump to step 5. * **Step 5**: simplyfy the set using the union rule: `\(\{X \rightarrow Y\ , X \rightarrow Z\}\ \vDash \ X \rightarrow YZ\)` ## Example * Example: AB→CD , BC→D * **Step 1**: AB→C, AB→D , BC→D. * **Step 2**: * Find {AB}+, while hiding AB→C from the FD set. * Start: {AB}, Iteration 1: {ABD}, Iteration 2: {ABD} * Therefore AB→C is not redundent, as C is not in this closure. * Find {AB}+, while hiding AB→D from the FD set. * Start: {AB}, Iteration 1: {ABCD}, Iteration 2: {ABCD}. * Therefore AB→D is redundent, as D is in this closure. * Find {BC}+, while hiding BC→D from the FD set. * Start: {BC}, Iteration 1: {BC}. * Therefore BC→D is not redundent, as D is not in this closure. * **Step 3**: * Find {B}+, while hiding AB→C * Start: {B}, Iteration 1: {B}. * Therefore it is not redundent, A is not in the closure * Find {A}+, while hiding AB→C * Start: {A}, Iteration 1: {A}. * Therefore it is not redundent, B is not in the closure. * we now have {AB→C, BC→D}. * **Step 3**: * Find {B}+, while hiding BC→D * Start: {B}, Iteration 1: {B}. * Therefore it is not redundent, C is not in the closure. * Find {C}+, while hiding BC→D * Start: {C}, Iteration 1: {C}. * Therefore it is not redundent, B is not in the closure. * **Step 4**: proceed to step 5. * **Step 5**: not required. * Therefore, the minimal set of FDs is AB→C, BC→D ## The Non-additive join property * ***The non-additive join property***: * Another key property a decomposition should have. * Ensures that no **spurious tuples** result from a **NATURAL JOIN** of relations. * **Recall**: * Spurious tuples occur when relations are joined using non-key/incorrect attributes. * Therefore spurious tuples indicate a loss of correct relationships. * Information is lost - hence this property is sometimes called the ***lossless join property*** * We (of course) have an algorithm to test for the non-additive join property. * **Algorithm**: * **Step 1**. Create an initial matrix of size: * Attributes *i* by relations *j*. * **Step 2**. Place *bij* in each empty cell. * **Step 3**. Place *ai* in each cell that corresponds to an attribute in the relation row. * **Step 4**. For all key attributes per row (`\( X \rightarrow Y\)`): * Find cells in rows containing key *X* with corresponding attributes *Y* containing *bij* * Place *ai* in each cell associated with *Y*, if the FD exists in another Row. * Repeat for all dependencies. * **Step 5**. If a row contains all *ai* then the decomposition is loss-less. * Otherwise it may satisfy the dependency property, but is not loss-less. * Case 1 (a) does not satisfy the test, case 2 (c) does. ## Algorithms for Relational Database Design * The final algorithm generates a **3NF** decomposition that: * Preserves all **functional dependencies**. * Possesses the **non-additive join property**. * **Algorithm:** * **Step 1**: Find the minimal cover *G* of *F*. * **Step 2**: Create a relation *R* for each FD in *G*. * **Step 3**: If no joining key, create a new relation. * 15.2(a) in current textbook (to find key). * **Step 4**: If *R* is a projection of other relation *S* it is redundant and can be removed. * This algorithm is more desirable as it ensures most of the desirable properties. * Lets re-visit our example from before: * *U = (emp_ssn, pno,esal,ephone,dno,pname,plocation)* * FD1 emp_ssn → {esal,ephone,dno} * FD2 pno → {pname,plocation} * FD3 {emp_ssn, pno} → {esal,ephone,dno,pname,plocation} * Through the minimal cover algorithm we can determine that the minimal cover *G*: * *G = {emp_ssn → {esal,ephone,dno}, pno → {pname,plocation}}* * Everything is the same after step 1 as before. * Complete step 2 as before gives us: * *R1 (emp_ssn,esal,ephone,dno)* * *R2 (pno,pname,plocation)* * Now for step 3. * Recall that the key for the original relation *U* is *{emp_ssn, pno}* (by algorithm 2a from the text) * By inspection we can see that neither *R1* and *R2* contain our key. * Therefore we create a new relation *R3* that contains only the key: * *R3 (emp_ssn, pno)* * By generating this additional relation, we have ensured that no information is lost. * The final result is: * *R1 (emp_ssn,esal,ephone,dno)* * *R2 (pno,pname,plocation)* * *R3 (emp_ssn, pno)* * There are no redundant relations to remove in this decomposition. * This final decomposition makes semantically makes sense. * There are two additional examples on pages 550-551 for you to review. ## Example One from text * Apply final algoirthm: * *F={P→LCA,LC→AP,A→C}* * **Step 1**: minimal cover (we will use the 2nd algorithm) - * *F={P→L,P→C,P→A,LC→A,LC→P,A→C}* * *(Hide LC→A) LC+→{L,C,P,A}* - redundant * *(Hide LC→P) LC+→{L,C}* - No P, not redundant * *F={P→L,P→C,P→A,LC→P,A→C}* * *(Hide LC→A) L+→{L}* no C, not redundant * *(Hide LC→A) C+→{C}* no L, not redundant * Repeat steps for P→L,P→C,P→A,A→C no redundancy. * Simplify using union rule: *F={P→LCA,LC→P,A→C}* * **Step 2**: We now have R1(P,L,C,A), R2(L,C,P) and R3(A,C). * **Step 3**: Keys in all relations, no action needed. * **Step 4**: Remove projections: R2 and R3 are projections of R1. * Therefore our 3NF schema is R1(P,L,C,A) * Note that the minimal cover algorithm may produce different results depending on where we look for redundancy first. --- ## Exercises for You For these questions, feel free to make assumptions about the key attributes or functional dependencies, there may be more than one result, but there is typically a most efficient result, see if you can find it. ### Exercise 1: * Find the closure of the following relation and set of 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 ### Exercise 2: * Prove that the following 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 } ### Exercise 3: * Find the minimal set of Functional Dependencies for the following set: * Relation: R(A, B, C, D, E) * Initial FDs F: * A → B * B → C * AB → C * AC → D * D → E ### Exercise 4: * Check whether the following relations contain the lossless join property: * Relation 1 : R(A, B, C) * FDs: F = { A → B, A → C } * Decomposition: R1(A, B), R2(A, C), R3(A) * Relation 2 : R(A, B, C) * FDs: F = { A → B } * Decomposition: R1(A, B), R2(B, C), R3(A) ### Exercise 5: Use the algorithm that produces a decomposition in 3NF with the lossless join property and is dependency preserving, to find the optimal set of relations from the following table. 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