Lossless Decomposition (2)PowerPoint PresentationSlide 3Normal FormsSlide 5Why these undesirable phenomena?Functional dependenciesFunctional dependencies in the example schemaNon-trivial functional dependenciesAnomalies and functional dependenciesDependencies generating anomaliesSlide 12BCNF(non) BCNF ExamplesRedundancyThird Normal Form3NF Example3NF (Non) ExampleDecompositionsDecompositionExample DecompositionLossless Schema DecompositionLossy DecompositionLossy Decompositions: What is Actually Lost?ExampleIntuition Behind the Test for LosslessnessProof of Lossless ConditionDependency PreservationSlide 29Slide 30Slide 31BCNF Decomposition AlgorithmSimple ExampleA Larger ExampleExample (con’t)Properties of BCNF Decomposition AlgorithmSlide 37Slide 38Boyce–Codd Normal Form (BCNF)Slide 40Slide 41Decomposition into Boyce–Codd normal formSlide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Lossless Decomposition (2)Prof. Sin-Min LeeDepartment of Computer ScienceSan Jose State UniversityNormal form and normalization• A normal form is a property of a relational database.• When a relation is non-normalized (that is, does not satisfy a normalform), then it presents redundancies and produces undesirablebehavior during update operations.• This principle can be used to carry out quality analysis and constitutesa useful tool for database design.• Normalization is a procedure that allows the non-normalizedschemas to be transformed into new schemas for which thesatisfaction of a normal form is guaranteed.Example of a relation with anomaliesEmployee Salary Project Budget FunctionBrown 20 Mars 2 technicianGreen 35 Jupiter 15 designerGreen 35 Venus 15 designerHoskins 55 Venus 15 managerHoskins 55 Jupiter 15 consultantHoskins 55 Mars 2 consultantMoore 48 Mars 2 managerMoore 48 Venus 15 designerKemp 48 Venus 15 designerKemp 48 Jupiter 15 manager The key is made up of the attributes Employee and ProjectNormal Forms•Each normal form is a set of conditions on a schema that guarantees certain properties (relating to redundancy and update anomalies)•First normal form (1NF) is the same as the definition of relational model (relations = sets of tuples; each tuple = sequence of atomic values)•Second normal form (2NF) – a research lab accident; has no practical or theoretical value – won’t discuss•The two commonly used normal forms are third third normal formnormal form (3NF) and Boyce-Codd normal formBoyce-Codd normal form (BCNF)Anomalies in the example relation• The value of the salary of each employee is repeated in all the tuplesrelating to it: therefore there is a redundancy.• If the salary of an employee changes, we have to modify the value inall the corresponding tuples. This problem is known as the updateanomaly.• If an employee stops working on all the projects but does not leavethe company, all the corresponding tuples are deleted and so, eventhe basic information, name and salary is lost. This problem is knownas the deletion anomaly.• If we have information on a new employee, we cannot insert it untilthe employee is assigned to a project. This is known as the insertionanomaly.Why these undesirable phenomena?• Intuitive explanation: we have used a single relation to representitems of information of different types.• In particular, the following independent real-world concepts arerepresented in the relation:– employees with their salaries,– projects with their budgets,– participation of the employees in the projects with their functions.• To systematically study the principles introduced informally, it isnecessary to use a specific notion: the functional dependency.Functional dependencies• Given a relation r on a schema R(X) and two non-empty subsets Yand Z of the attributes X, we say that there is a functional dependencyon r between Y and Z, if, for each pair of tuples t 1 and t 2 of r havingthe same values on the attributes Y, t 1 and t 2 also have the samevalues of the Z attributes.• A functional dependency between the attributes Y and Z is indicatedby the notation Y -> ZFunctional dependencies in the example schema• Employee -> Salarythe salary of each employee is unique and thus each time a certainemployee appears in a tuple, the value of his or her salary alwaysremains the same.• Project -> Budgetthe budget of each project is unique and thus each time a certainproject appears in a tuple, the value of its budget always remainsthe same.Non-trivial functional dependencies• We then say that a functional dependency Y-> Z is non-trivial if noattribute in Z appears among the attributes of Y.– Employee -> Salary is a non-trivial functional dependency– Employee Project -> Project is a trivial functional dependencyAnomalies and functional dependencies• In our example, the two properties causing anomalies correspondexactly to attributes involved in functional dependencies:– the property ‘ the salary of each employee is unique and dependsonly on the employee’ corresponds to the functional dependencyEmployee -> Salary;– the property ‘ the budget of each project is unique and dependsonly on the project’ corresponds to the functional dependencyProject -> Budget.• Moreover, the following property can be formalized by means of afunctional dependency:– the property ‘ in each project, each of the employees involved cancarry out only one function’ corresponds to the functionaldependency Employee Project -> Function.Dependencies generating anomalies• The first two dependencies generate undesirable redundancies andanomalies.• The third dependency however never generates redundanciesbecause, having Employee and Project as a key, the relation cannotcontain two tuples with the same values of these attributes.• The difference is that Employee Project is a key of the relation.BCNF•Definition: A relation schema R is in BCNF if for every FD X Y associated with R either–Y X (i.e., the FD is trivial) or–X is a superkey of R•Example: Person1Person1(SSN, Name, Address)–The only FD is SSN Name, Address–Since SSN is a key, Person1Person1 is in BCNF(non) BCNF Examples•PersonPerson (SSN, Name, Address, Hobby)–The FD SSN Name, Address does not satisfy requirements of BCNF •since the key is (SSN, Hobby)•HasAccountHasAccount (AcctNum,
View Full Document
Unlocking...