Slide 8.2 - Relational Database Design Show slide * Goal of relational database design is to * Generate a set of relation schemas that allows us to store information efficiently, that is, 1) without unnecessary redundancy 2) and retrieve info quickly and easily * Do this by designing schemas with an appropriate normal form * FORMAL approach to relational DB design * based on the notion of functional dependencies * Define the normal forms in terms of functional dependencies and other types of dependencies * Goal of functional DECOMPOSITION is to Eliminate redundancy by decomposing a relation into several relations in a higher normal form. * Start for now with what we know from our ER diagrams * Reduce an ER diagram into a set of relation schema * Schemas are only as good the ER diagram * How do we know if ER diagram is ANY good? Show University Relation Schemas (university_relation_schema.PDF ) Slide 8.3 - Combine Schemas? Show slide * What is wrong with combining Instructor and Department * Redundant department info * Inconsistent department info * What happens when we want to create a new department? * If id is PK, then what? * This relation should make your skin crawl We will formalize exactly why as we go through the chapter Slide 8.4 - A Combined Schema Without Repetition Show slide Show Chap_7_ER_reduction.htm #5 * sec_class - why can we combine these 2 schemas without redundancy? Slide 8.5 - What About Smaller Schemas? Go back to slide 8.3 * How did we know that the inst_dept relation had redundant info? By looking at it. Why would that NOT work in real life? * How would we know that in our university our each dept MUST reside in a single bldg? MUST have a single budget amount? How do we know that same values in different rows are NOT a coincidence? * We need to go back to the enterprise and find out what the rules really are * Does the univ REALLY require that every dept reside in ONE building and a single budget value? * DB design needs to be able to specify RULES * A FUNCTIONAL DEPENDENCY Show slide 8.5 READ slide - points 1 to 4 * This was easy What happens when there are a large number of attributes and rules? Need a FORMAL methodology * What if we had a set of schemas where each schema only had ONE attribute? Not even a possibility - relationship sets need at least 2 attributes However, it is possible to make schemas too small as well as too big READ slide - points 5 to 6 Slide 8.6 - A Lossy Decomposition Show slide * What happens when we try to regenerate the original schema from the decomposition? 2 different people named Kim with 2 different ids If you split id away from name Natural join on name can't put the pieces back together correctly * Even though we have MORE rows, we have actually LOST information * Lossy-Join Decomposition that results in a loss of information Slide 8.7 - A Lossless-Join Decomposition Show slide * Decompose relation R with attributes A,B,C into r1(A,B) and r2(B,C) NATURAL JOIN of r1 and r2 will get you back to where you were before the decomposition * Lossless-Join One that does NOT result in a loss of information A decomposition of a relation R is called a lossless decomposition for R if the NATURAL JOIN of the decomposed relations produces EXACTLY the original relation R. * What is wrong with the relational algebra at the bottom of the slide * Lossless-joins are a requirement for good design and this causes constraints on the set of possible relations Slide 8.8 - First Normal Form Show slide POINT 1 on slide * What does atomic mean? Indivisible * What two kinds of NON-atomic attributes did ER diagram allow an entity to have? Composite Multi-valued * When we created relation schemas from the ER diagram, how did we deal with non-atomic attributes? Composite Each SUB-component became an attribute in its own right Multi-valued Create a new entity set / relation schema each value becomes its own entity / tuple READ 2 * 1NF - First Normal Form Relation R is in 1NF if the domains of all attributes of R are ATOMIC READ 3 * What happens when you are coding Java on the front end and want to store an object in the DB That is a composite object and does NOTcomform to 1NF You have to break it down into atomic parts getting it in, and recompose it getting it out Slide 8.9 - First Normal Form Show slide * Example of NON-atomic attribute Suppose that employee ids take the following form First two chars => Department code (eg "CS") indicates their department Next 4 chars => unique id within the department What is wrong with this? Department would have to be stripped off in code Info gets encoded in the application rather than the database Extra programming Hidden and overlooked if there are changes What if it is used as a PK? What happens if an employee changes departments? Code may need to be re-written May return incorrect results NOT in First Normal Form If a relation schema had an attribute whose domain consists of ids like this, it would not be in 1NF It can conceptually be broken up into pieces HOWEVER, it IS atomic as far as the DB is concerned DB treats it as atomic As long as it does not attempt to split the id up and interpret the results Slide 8.10 - Goal — Devise a Theory for the Following READ slide * FORMAL methodology Notation Greek letter (eg alpha) One OR MORE attributes May be outside the context of a schema Uppercase Roman (eg, R) Set of attributes used in a schema lowercase Roman letter relation names are given in lowercase Roman lowercase Roman letter followed by uppercase Roman letter in parens (eg r(R) ) relation schema whose attributes are R Uppercase Roman (eg, R) may be abbreviated schema designation Uppercase Roman K superkey "K is a superkey of r(R) " * "instance of relation r" is what? particular value of r at a point in time Slide 8.11 - Functional Dependencies Show slide * A DB models a set of entities and relationships in the real world There are constraints (rules) on the data and relationship Domains of attributes Values Relationships Cardinality Keys superkeys, candidate keys, primary keys What are some of the rules we assume in the university DB? * Legal instance Instance of a relation r satisfies real-world constraints READ slide * One value in the relation may be DEPENDENT on another value Slide 8.12 - Functional Dependencies Show slide POINT 1 * What do Greek letters represent? * What do uppercase Roman letters represent? * Can anyone read POINT 1 on the slide ? alpha is a subset of R and beta is a subset of R * alpha is one of the attributes in R and beta is one of the attributes in R POINT 2 The functional dependency alpha -> beta (alpha implies beta) holds IF AND ONLY IF For ANY two tuples in the LEGAL relation r if the VALUE of alpha is the same in both tuples the VALUEs of beta are ALSO the same in both tuples An INSTANCE of r SATISFIES the functional dependency IF for all pairs of tuples IN THE INSTANCE the dependency is true A functional dependency HOLDS on a relation IF i in EVERY LEGAL instance of the relation SATISFIES the dependency READ 3 & 4 Slide 8.13 - Functional Dependencies - keys Show slide POINT 1 * What is this saying? K is a superkey of R if the funcitonal dependency K -> R holds on R eg if for every LEGAL instance of R, IF the VALUEs of K are the same in ANY two tuples THEN the VALUEs of the rest of the attributes R are ALSO the same in both tuples ie t1 = t2 If no duplicates are allowed, t1 IS t2 It is uniquely identified by its key values POINT 2 * K is a candidate key for R if and only if Given that K is a superkey for R (the functional dependency K -> R holds on R There is no smaller set of attributes within K (alpha ) for which it is true that alpha -> R ALSO holds on R There are no extraneous attributes in K READ 3 * building is dependent on dept_name * building MAY be dependent on ID * salary is NOT dependent on dept_name Slide 8.14 - Use of Functional Dependencies Show slide READ slide Show Figure 8.4 * Show that A -> C For every pair of tuples where ever the values of A are the same value , the values for C are also the same a1 -> c1, a2 -> c2 * Why - in this instance - does C -> A not hold Slide 8.15 - Use of Functional Dependencies Show slide * Some functional dependencies are said to be TRIVIAL because the are satisfied by ALL relations In any relation, A -> A always holds In any relation, AB -> A always holds Slide 8.16 - Closure of a Set of Functional Dependencies Show slide Slide 8.17 - Boyce Boyce-Codd Normal Form Show slide * One of the more disirable normal forms that we can obtain * Eliminates ALL redundancy that can be discovered based on functonal dependencies READ slide Show university schema definition DOC * instructor ( id, name, dept_name, salary ) is in BCNF id -> is a superkey for instructor There is no nontrivial functional dependency with any combinationo of name, dept_name, salary WITHOUT id on the side * department ( dept_name, building, budget ) is in BCNF dept_name is a superkey No other nontrivial functional dependencies that do NOT include dept_name Slide 8.18 - Decomposing a Schema into BCNF Show slide * General rule for decomposing relation schemas that are not in BCNF Break relation R into TWO new relations 1) The union of ALL attributes of the offending functional dependency 2) Take all the attributes in Beta that are NOT in alpha and REMOVE them from the relation Create inst_dept in BAD University Database Relation Schema.DOC * Offending functional dependency in inst_dept dept_name -> (building, budget) 1) UNION of all attributes in the offending functional dependency * create NEW relations using dept_name, building, budget 2a) beta - alpha => (building, budget) 2b) R - (beta - alpha) => * remove building, budget from original relation * What happens if after decomposing a relation, one of the new relations is not in BCNF ? Slide 8.19 - Decomposing a Schema into BCNF Show slide * What are all the ways to express database consistency constraints PKs Functional dependencies CHECK constraints assertions triggers READ 1 * If you have to check EVERY row in EVERY table ANY time data is updated, it is very costly READ 2 READ 3 * Decomposition into BCNF can prevet efficient testing of certain functional dependencies * Suppose we modify our university so that each instructor may only be associated with one department each student may have more than one advisor but at most one from each department Show Figure 8.6 Ternary relationship dept_advisor( student_id, instructor_id, dept_name ) Suppose ALSO that an instructor can only advise for one department We get the following functional dependencies instructor_id -> dept_name each instructor may only be associated with one department student_id, dept_name -> instructor_id each student may have more than one advisor but at most one from each department BCNF requires that either a -> b is trivial a is a superkey for R instructor_id is NOT a superkey (not part of ALL functional dependencies) Decompose into ( student_id, instructor_id ) ( instructor_id, dept_name ) There is now no schema that includes all attributes for functional dependency student_id, dept_name -> instructor_id Design is NOT dependency preserving Slide 8.20 - Third Normal Form Show slide Slide 8.22 - How good is BCNF? Show slide * 2 phones and 2 children Repeat phones for each child OR Imply that one phone number applies for each child Slide 8.23 - How good is BCNF? Show slide Slide 8.24 - How good is BCNF? Show slide * We will look at this later Slide 8.25 - Functional Functional-Dependency Theory Show slide Slide 8.26 - Closure of a Set of Functional Dependencies Show slide * We can PROVE that other functional dependencies hold given an initial set F Show BAD University Database Relation Schema.doc Slide 8.27 - Closure of a Set of Functional Dependencies Show slide * ALL of the logically implied functional dependencies may be found by applying Armstrong's Axioms SKIP TO Slide 8.30 - Closure of a Set of Functional Dependencies Show slide * Derived from Armstrong's Axiom Additional rules to make inference easier Show BAD University Database Relation Schema.doc Slide 8.28 - Closure of a Set of Functional Dependencies Show slide CG -> HI is NOT correct CG -> H given CG -> I given CG -> HI Union Slide 8.29 - Procedure for Computing F+ Show slide * Closure of F can be VERY large Slide 8.31 - Closure of Attribute Sets Show slide * Show Axioms in "Chap_8_DB_Extra.docx" * Test whether Alpha is a superkey Find all other attributes that are DEPENDENT on Alpha denoted as Alpha+ * Input is a set F of functional dependencies a set Alpha of attributes * Output Set of all attributes dependent on Alpha * Algorithm Loop through all functional dependencies in F until no more attributes are added to the result For each determinant in a functional dependency if that determinant is in the result set, add the new dependent attribute to the result set * Show "Closure on A+" in Clares function dependency.doc Slide 8.32 - Example of Closure of Attribute Sets Show slide Slide 8.33 - Uses of Attribute Sets Show slide * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * REALITY CHECK * Where do these functional dependecies come from? From the problem domain * Why is it important to know what they are for a particular application? Clarify how the data is related * What do we use them for when we design a database schema? To figure out what data goes in what tables * A Functional Dependency describes a relationship between attributes in a relation. * A set of attributes is functionally dependant on another if we can use the values of one set of attributes in a tuple (the key) to determine (ie, uniquely identify) the value of another set of attributes in the same tuple * What is the set F of Functional Dependencies? The set of FD determined during requirements analysis * Why is inference and Armstrong's Axioms important? Because ALL the inferred FDs are just important as the original set F They ALL have to be met Not all relationships between data attributes are obvious You might need to start reasoning about all the dependencies to figure out how it all needs to fit together SHOW slide 8.29 * What is F+ * Why would we want to generate F+ ? To find out what ALL the FDs are on a set of relations * Algorithm for finding F+ For each fd in F Apply reflexivity -> add it to the set F Apply augmentation -> add it to the set F For each pair Appy transitivity -> add it to the set F Until there are no more Fds to add to the set * Used in some algorithms for normalization There are 2^2n possible FDs where n is the number of attributes in R For a relation with 10 attributes, there are 2^20 possible FDs May be VERY expensive to calculate * What is normalization? Normalisation is the process of taking data from a problem and reducing it to a set of relations ensuring data integrity and eliminating data redundancy * Data integrity all of the data in the database are consistent, and satisfy all integrity constraints. * Data redundancy direct redundancy - data in the database can be found in two different locations indirect redundancy - data can be calculated from other data items * How does a DB enforce data and referencial integrity ? By checking data against the FDs * There HAS to be an easier way SHOW slide 8.31 * Find the closure of Alpha under F Start with a particular FD Put Alpha in the set For each of the other FDs If the attributes in the Alpha appear in the set Add Beta to the set * Proof of Algorithm (in case they ask) result := A A -> result reflexivity A -> A repeat for each B -> C given in F if B -> result then result ->B reflexivity if ß->a, then a->ß A -> B transitivity A -> result, result-> B, then A -> B A -> C transitivity A -> B, B -> C then A -> C A -> result, C union If a->ß and a->gamma, then a->ßgamma end loop SHOW slide 8.32 BLACKBOARD SHOW slide 8.33 * If the result set contains ALL the attributes of R, then the original Alpha is a superkey * Check if a particular Beta is determined by an Alpha Does it appear in Alpha + ? * Alternative way to Compute F+ Take each subset of attributes in R Compute closure on that set of attributes For EVERY attribute in the closure Output a FD for that attribute 2^n subsets * Canonical Cover * Find the minimal number of FDs that will guarentee all the rest are met by Eliminating redundant FDs Elliminating redundant attributes in a FD Slide 8.34 - Canonical Cover Show slide * Uppercase Roman letters are particular Attributes Greek letters are Sets of attributes * GOAL - Get rid of ALL redundencies in F using inference * Since Axioms are SOUND - guarenteed to be generate correct results F -> Fc and Fc -> F (ie, logically imply) * F and Fc are locally equivalent * FD may be COMPLETELY redundant * FD may be PARTIALLY redundant DON'T DERIVE REDUNCANCIES - WE WILL GET TO THAT LATER * RHS => right hand side A->B and B->C gives A->C; A->C and A->D gives A->CD LHS => left hand side Since A->D then AC->D since AC is a superkey of the candidate key A * Since the closure is the same on the minimized set as on the original set Testing the minimized set satisfies all dependencies in the original set With less resources * DB has to do less work Slide 8.35 - Extraneous Attributes Using Inference Show slide * An attribute is EXTRANEOUS if we can remove it without changing the closure of the set of functional dependencies POINT 1 * Attribute on the LEFT side is extraneous If we can make an inference - based on all the functional dependencies in F - such that, if we remove that attribute from the Alpha side of the dependency, we can still infer that the REVISED Alpha holds based on inference from the original set of dependencies * Attribute on the RIGHT side is extraneous If after taking away that attribute from the Beta side of the FD to create a REVISED one add it to the set F to create a REVISED set F ' the OLD, ORIGINAL dependency can still be derived based on the REVISED set of dependencies F ' BLACKBOARD * Show EXAMPLES on slide Ex 1: F = { A->C, AB->C } B is extraneous inAB->C Remove B from AB->C to get A->C Prove that the original F infers A->C. Since A->C is in the set, it is automatically inferred. Ex 2: F ' = { A->C, AB->D } C is extraneous in AB->CD Remove C from AB->CD to get a revised FD AB->D Replace old FD with new in the set F to get revised set F ' F ' = { A->C, AB->D } Prove that F ' infers AB->CD Since A->C and AB->D then AB->CD Since A->C, C may be added to any Beta Slide 8.36 -Testing if an Attribute is Extraneous Using Closure of Attributes Show slide * There is another, easier way to do this using Closure of Attributes POINT 1 POINT 2 - Left side * Revise the FD by removing the attribute A from Alpha on the LHS * Compute the closure of the revised Alpha on the original set F If the closure still contains all the dependent attributes contained in Beta, then A is extraneous in Alpha POINT 3 - Right side Revise the FD by removing the attribute A from Beta on the RHS * Create a new set of FDs F ' which replaces the original FD with the revised FD Compute the closure of original Alpha on the revised set of FDs that are in F ' If the closure on the revised FD still contains the attribute A, then A is extraneous in Beta Slide 8.37 - Canonical Cover Show slide * Fc is logically equivalent to F * There are no extraneous attributes in Alphas or Betas * Each of the Alphas is unique in F * Chap_8_DB_Extra.docx Computing Cover Fc for F Slide 8.38 - Computing Canonical Cover Show slide READ 1 Starting sets POINT 2 * Step 1- What FDs can we combine using UNION ? Which FDs have the same Alpha ? We want all Alphas to be unique What is the new Fc ? Fc = { A->BC, B->C, A->B } BLACKBOARD * Chap_8_DB_Extra.docx Example of Computing Cover Fc for F BLACKBOARD * Chap_8_DB_Canonical Cover.docx Better way of computing Canonical Cover using Closure of Attributes Slide 8.39 - Lossless Lossless-join Decomposition Show slide POINT 2 * If the intersection of the two sets of attributes form a superkey of either relation Decompostion is lossless * Chap_8_DB_Extra.docx - TOP OF DOC * What is the intersection of the two relations - instructor and department ? dept_name * Is dept_name a superkey of either of the two relations ? Yes - department * Is it a lossless join ? POINT 3 * Reference to what we may be seeing later - multivalued dependencies Slide 8.40 - Example Show slide POINT 1 * What other FDs can be inferred from this set ? A -> C POINT 2 * Lossless: B->B and B->C infers that B->BC * Dependency Preserving A->B in R1 and B->C in R2 directly hold POINT 3 * Lossless: A->A and A->B infers that A->AB * NOT Dependency Preserving B->C can no longer be preserved directly from one of the relations Slide 8.41 - Dependency Preservation Show slide * Decompose relation R into several relations R1..Rn Split R up into several pieces * Split up the set of functional dependencies F+ in to several sets F1..Fn Such that the FDs in F1 ONLY have attributes that appear in R1 This is the RESTRICTION of F to R1 READ 1 EXPLAIN * Algorithm Compute F+ For every Ri Fi := the restriction of F+ to Ri F ' := null For each Fi F ' = F ' U Fi Compute F ' + (closure of F ' ) if F '+ = F+ then decomposition is dependency preserving else it is not => We did not lose any dependencies along the way Slide 8.42 - Testing for Dependency Preservation Show slide * Easier alternatives for testing If each emember of F can be tested on ONE relation of the decomposition Decomposition is dependency preserving Doesn't always work May be a dependency that cannot be tested in any ONE relation Have to use the above expensive algorithm to compute F+ READ 1 * To check if a particular dependency is preserved in a decomposition Start by adding Alpha to the result set of attributes For each relation in the decomposition Find the intersection between the attributes in the result set and the relation Find the closure of that intersection Add that results of that intersection to the set of attributes in the result * If result contains all the attributes in the original Beta, Dependency if preserved * Test all the dependencies if F Slide 8.43 - Example Show slide READ 1 POINT 2 * Why is R not in BCNF? Not all the Alphas are keys in R POINT 3 * R1 and R2 are in BCNF A is key in R1 B is key in R2 * Lossless R1 Intersect R2 => B B is key in R2 * Dependency Preserving * Look at all dependencies in F A->B result := A R1: result Intersect R1(A,B) => A A+ = AB ABC Intersect R1 => AB result := AB R2: result Intersect R2 (B,C) => B B+ = BC BC Intersect R2(BC) => BC result := ABC A->B is preserved Same for B->C * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Slide 8.44 - Testing for BCNF Show slide HOW DO YOU KNOW WHETHER A RELATION IS IN BCNF? READ 1 Use the definition of BCNF If a relation is not in BCNF, it can be decomposed to create relations that are in BCNF READ 2 You ONLY need to check dependencies in F (not in F+) * Cheat Sheet - Testing for BCNF in R READ 3 * Decompose * We only have to check RESTRICTIONS of F on Ri dependencies where ALL the attributes in that FD appear in that relation * However A->B and BC->D by pseudo-transitivity gives AC->D AC+ = ACD (does not include E) * We may need a dependency that is in F+ but is not in F to show that a decomposed relation is not in BCNF Slide 8.45 - Testing Decomposition for BCNF Show slide TEST FOR BCNF on Ri READ 1a * Compute F+ Find all the restrictions of F for each Ri Test Ri for BCNF based on its set of restrictions READ 1b * For every Alpha in F whose attributes appear in Ri Computer Alpha+ using F 1. Does Alpha+ include ALL attributes in Ri OR 2. Does Alpha+ contain NO attributes that are in Ri but NOT in Alpha * Cheat Sheet - Testing for BCNF in Ri * If Alpha+ under F contains attributes in Ri that do not appear in Alpha * We take those attributes to further decompose Ri Slide 8.46 - BCNF Decomposition Algorithm Show slide * General method to decompose a realtion to satisfy BCNF If R is not in BCNF, we can decompose it into BCNF using the algorithm * Decomposition generated is not only BCNF it is also lossless * For a set of decomposed relations of R Compute the closure of all functional dependecies in F+ If there is a relation in that set that is not in BCNF For every FD that holds on that relation 1) If Alpha is NOT a superkey of Ri based on F+ 2) And there are no common attributes between Alpha and Beta Then Decompose Ri by 1) Removing beta attributes from Ri AND 2) Create new relation consisting of all the attributes in alpha and beta Until there are no more relations that are not in BCNF * Cheat Sheet - Decomposition into BCNF - Algorithm Slide 8.47 - Example of BCNF Decomposition Algorithm Show slide READ 1 The only key is A READ 2 READ 3 Alpha is B Beta is C Remove Beta from original R to get (A,B) Add New relation consisting of Alpha and Beta attributes to get (B,C) Slide 8.48 - Example of BCNF Decomposition Algorithm Show slide READ 1 READ 2 READ 3 READ 4 Create new relation just using alpha and beta attributes Revise the old relation by removing Beta attributes from it Slide 8.49 - Example of BCNF Decomposition Algorithm Show slide READ 1 How do we know this? The only FD that has attributes that ALL appear in course has Alpha that is a superkey Slide 8.50 - BCNF and Dependency Preservation Show slide Slide 8.51 - Third Normal Form: Motivation Show slide Slide 8.52 - 3NF Example Show slide * Cheat Sheet - Testing for 3NF in R READ 1a READ 1b READ 1c What is wrong with first bullet What should it read? Slide 8.53 - Redundancy in 3NF Show slide * For every student with instructor in that department, dept_name is redundant * For any instructor who is an advisor, but not advising any students, student is null Slide 8.54 - Testing for 3NF Show slide Slide 8.55 - 3NF Decomposition Algorithm Show slide * Cheat Sheet - Testing for 3NF in R * Set of FDs is Fc (not For F+) * The algorithm considers a set of schemas Rj where j=1..i. However i=0 initially, that is, the set is empty * For each FD in Fc If none of the schemas in the set contain all the attributes of Alpha AND all the attributes of Beta Then create a new relation with all those attributes If none of the schemas contains a candidate key for the original relation Then Create a new relation consisting of the candidate key If there are any redundant schemas whose attributes all appear in another relations Then delete that schema Slide 8.56 - 3NF Decomposition Algorithm Show slide Slide 8.57 - 3NF Decomposition: An Example Show slide Slide 8.58 - 3NF Decomposition: An Example Show slide Slide 8.59 - Comparison of BCNF and 3NF Show slide READ 1 * Alternative method for generating BCNF is to first decompose into 3NF and then decompose any schema that is not in BCNF into BCNF READ 2 * If the result is not dependency preserving revert to 3NF Slide 8.60 - Design Goals Show slide READ 1 READ 2 READ 3 * Primary Key and UNIQUE DO 461_QUIZ_1_DESIGN.DOC with class Slide 8.61 - Multivalued Dependencies Show slide READ 1 READ 2 READ 3 * Why? ID->child, and ID->phone both hold and ID is a superkey * So far the only dependency constraint we have seen is a FD * NEW form of constraint called a multivalued dependency * Use multivalued dependency to define a new normal form call FOURTH normal form * Every relation that is in 4NF is also in BCNF * NOT the other way around Slide 8.62 - Multivalued Dependencies Show slide * FDs rule out certain tuples from being in a relation If A -> B then no 2 tuples with the same value of A can have different values for B * Multivalued dependencies do NOT rule out the existence of certain tuples * They REQUIRE other tuples of a certain form be present in the relation * FDs => called equality-generating dependencies * MVDs => called tuple-generating dependencies READ 1 for any 2 tuples in R (t1 and t2) that have the same value in alpha there exist 2 other tuples in R (t3 and t4) such that all the alphas contain the SAME values in all 4 tuples odd numbered tuples have the SAME values for beta even numbered tuples have the SAME values for beta outside tuples save the SAME values for all the leftover attributes inside tuples save the SAME values for all the leftover attributes * the relationship between alpha and beta is independent of the realtionship between alpha and (R - beta) (the rest of the attributes in R not in beta) Slide 8.63 - Multivalued Dependencies Chart Show slide all the alphas contain the SAME values in all 4 tuples odd numbered tuples have the SAME values for beta even numbered tuples have the SAME values for beta outside tuples save the SAME values for all the leftover attributes inside tuples save the SAME values for all the leftover attributes * Notice the same set of values for A occurs for times * Once for each combination of Beta and the remaining attributes * Beta and the remaining attributes are independent from each other Slide 8.64 - Multivalued Dependencies Example Show slide * You start with a relations that has at least three sets of attributes => Y, Z, W * Y multidetermines Z IIF (goes both ways) there are 2 tuples that have the same values in the first set but different values in other 2 sets then there exists 2 more tuples in the relation such that they share the same values as the original tuples in the first set but have the values flipped in the second two sets * 2nd and 3rd sets are independent of each other Slide 8.65 - Multivalued Dependencies Example Show slide * Since Y -> Z we know that for each value of Y, there can only be one possible value of Z * By extension then, z1 and z2 must be the same value Slide 8.66 - Use of Multivalued Dependencies Show slide READ 1 READ 2 * Note that if a relation fails to satisfy a MVD, we can just add rows to it until it does Slide 8.67 - Theory of MVDs Show slide READ 1 * If Alpha -> Beta, then based on the definition of multidependency, Alpha -> -> Beta READ 2 * Not going into inference rules for MVDs Slide 8.68 - Fourth Normal Form Show slide READ 1 1a * What is the definition of trivial for a FD? * For MVD we need 3 sets of attributes If all of Beta's attributes are in Alpha, we only have 1 set If Alpha and Beta together are ALL the attributes in R, then we only have 2 sets Otherwise the MVD is trivial Stronger than triv 1b Alpha is a superkey READ 2 Slide 8.69 - Restriction of MVDs Show slide Slide 8.70 - 4NF Decomposition Algorithm Show slide * IDENTICAL to BCNF decomposition algorithm EXCEPT that is uses MVDs and uses the restrictions of D+ on Ri * Test fails because Alpha is not a superkey but requires that there be no common attributes between Alpha and Beta Slide 8.71 - 4NF Decomposition Example Show slide Slide 8.72 - Further Normal Forms Show slide Slide 8.73 - Overall Database Design Process Show slide Slide 8.74 - ER Model and Normalization Show slide READ 1 READ 2 * ER diagrams only show dependencies on key attributes READ 3 * ER diagrams tend to generate 4NF designs Problems arise with M : M relationships Multivalue attributes Slide 8.75 - Denormalization for Performance Show slide Slide 8.76 - Other Design Issues Show slide Slide 8.77 - Modeling Temporal Data Show slide Slide 8.78 - Modeling Temporal Data Show slide