Relational DesignDatabaseDesign ProcessSchema NormalizationExamples of Redundancy and Anomalies in Relational SchemeRedundancy leads to AnomaliesMore Anomalies...More Anomalies ...Redundancy and Integrity ConstraintsRedundancy Due to Multi-valued DependencyRedundancy due to Functional DependencyWhen does a relation contain no redundancy due to FDs?Boyce Codd Normal FormTesting for BCNFTesting if X is a superkeySlide 15Slide 16Slide 17Slide 18BCNF ExamplesEliminating Redundancy from RelationsLossless JoinsTesting for Lossless Join DecompositionIntuition behind Loss less decomposition testWhat if Decomposition consists of more than 2 subschemes.ExampleExample of a lossless Decomposition for which no sequence of binary lossless decomposition existsProof why the decomposition is loss lessSlide 28Functional Dependency PreservationExample of a Non-Dependency Preserving DecompositionDependency PreservationTesting for Dependency PreservationFinally what we wish of Schema NormalizationSo What can we do?Third Normal FormExamplesSlide 37Taking Advantage of 3NFHow to test Whether Subschemes in BCNF??Example (1)Example (2)Design AlgorithmsDecomposition to Reach BCNFDecomposition to Reach BCNF (II)Slide 45Example (II)Example (III)Decompose Drinkers2BCNF DecompositionDecomposition into 3NF subschemesRoadmapCanonical cover of FDsAlgorithm to Compute Canonical CoverSlide 54A Dependency-Preserving Decomposition (synthesis algorithm)Slide 56Dependency Preservation with LosslessnessSlide 58Some Comments...An Interesting Aside….Relational DesignDatabaseDesign Process•Conceptual Modeling -- ER diagrams•ER schema transformed to relational schema•Designer may add additional integrity constraints at this stage to reflect real world constraints.•Resulting relational schema is normalized to generate a good schema (schema normalization process)•Schema is tested over example databases to evaluate its quality and correctness•results are analyzed and corrections to schema are made•corrections may be translated back to conceptual model to keep the conceptual description of data consistent•Design tools automate some of the schema transformation, normalization, generation of example database to test the schema design, as well as evaluation.•Good Book: The design of relational databases, by Mannila and Raiha, Addison WesleySchema Normalization•Normalization process “decomposes” the relational schemes to –remove redundancy–remove anomalies•Results in a semantically equivalent relational scheme that represents the same information as the original:–must be able to reconstruct the original from the decomposed relations.Examples of Redundancy and Anomalies in Relational SchemeCs184projectsstudent proj title dateboris oodb 11/16/95stefan oodb 11/18/95monica par dbms 11/21/95•Redundancy:• date of presentation repeated per member of project groupRedundancy leads to AnomaliesCs184projectsstudent proj title dateboris oodb 11/16/95stefan oodb 11/18/95monica par dbms 11/21/95•Update Anomaly:•if we modify presentation date for the oodb project, we need to modify the date in each of the tuples in which it is stored (one per member). Else, database will be inconsistent.More Anomalies...•Insertion Anomaly: how to insert that the presentation on multimedia databases has been set for 12/1/95 without associating any students first with the project. (possible solution: use null values in the student field)Cs184projectsstudent proj title dateboris oodb 11/16/95stefan oodb 11/18/95monica par dbms 11/21/95More Anomalies ...•Deletion Anomaly:how to delete the fact that monica dropped out of the project without deleting information about the par dbms project. (possible solution: use null values in the student field)Cs184projectsstudent proj title dateboris oodb 11/16/95stefan oodb 11/18/95monica par dbms 11/21/95Redundancy and Integrity Constraints•An IC means that only a subset of all possible relations are ‘legal’ (representing possible states of the real world)•Thus, given some information about the current values of the relations and the set of IC, we can possibly deduce some more information about the current information of the relation (since it must be a legal state)•Thus, presence of ICs will possibly always result in redundancy•For certain ICs redundancy is more obvious as compared to other Ics•We will study redundancy due to functional dependencies only.•However, remember that redundancy might be present due to lots of other constraints (e.g., multi-valued dependency) we will ignore such redundancy in this course.Redundancy Due to Multi-valued Dependencyemp-info name telephone secretaryt1 boris 333-1222 bonniet2 boris 333-1230 andat3 boris 333-1230 bonniet4 boris 333-1222 andaMVD: • name telephone MVD tells us that if tuples t1 and t2 are present in the relation, then tuples t3 and t4 must also be present (redundancy --- since we could have deduced them using t1 and t2 + MVD)!Redundancy due to Functional Dependencycs311projectsstudent proj title datet1 boris oodb 11/16/95t2 stefan oodb 11/18/95t3 monica par dbms 11/21/95•Functional dependencies:student projtitle dateprojtitle datedate projtitleNotice that time in tuple t2 could be deduced using the FDs + tuple t1 + remaining of tuple t2. (redundancy!!)We will examine how to get rid of redundancy due to functional dependencies.Henceforth we will assume that the only dependencies present are functional.When does a relation contain no redundancy due to FDs?R X Y Zt1 x1 y1 z1t2 x1 y1 z2Assume functional dependency: X YSince t1[X] = t2[X], we have that t1[Y] = t2[Y] (redundancy- since we can deduce the value of t2[Y] using FDHowever, if X is a superkey of R, then it must be the case that t1[Z] = t2[Z]. Thus, t1 = t2 and hence there cannot be such a tuple t2 R (a relation is a set).Thus, a relation does not contain redundancy if for each FD X Y that holds on R, X is a superkey. Such a relational scheme is said to be boyce-codd normal formBoyce Codd Normal FormLet R be a relation scheme. F be the functional dependency set. R is in BCNF if for all functional dependencies X Y in F+, either Y is a subset of X, or X is a superkey.X is a superkey for R if X A1, A2, ..., An is in F+, where A1,A2, ....An is the set of attributes of R.Testing for BCNFLet R be a relation scheme. Let F be the set of functional dependencies. Is R in BCNF?R is in