Chapter 16Properties of Relational DecompositionsSlide 3Slide 4Example – spurious tuplesPowerPoint PresentationSlide 7Slide 8Slide 9Slide 10Properties of Relational Decompositions (5)Algorithms for Relational Database Schema DesignAlgorithms for Relational Database Schema DesignSlide 14Slide 15About Nulls, Dangling Tuples and Alternative Relational DesignsProblems with NULL values and dangling tuplesSlide 18Algorithms for Relational Database Schema Design (7)Chapter 16Relational Database Design Algorithms and Further DependenciesCopyright © 2007 Ramez Elmasri and Shamkant B. Navathe 2Properties of Relational DecompositionsRelation Decomposition and Insufficiency of Normal Forms: Universal Relation Schema:A relation schema R = {A1, A2, …, An} that includes all the attributes of the database.Universal relation assumption:Every attribute name is unique.Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe 3Properties of Relational DecompositionsRelation Decomposition and Insufficiency of Normal Forms (cont.): Decomposition:The process of decomposing the universal relation schema R into a set of relation schemas D = {R1,R2, …, Rm} that will become the relational database schema by using the functional dependencies. Attribute preservation condition:Each attribute in R will appear in at least one relation schema Ri in the decomposition so that no attributes are “lost”.Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe 4Properties of Relational DecompositionsAnother goal of decomposition is to have each individual relation Ri in the decomposition D be in BCNF or 3NF. Additional properties of decomposition are needed to prevent the generation of spurious tuplesCopyright © 2007 Ramez Elmasri and Shamkant B. NavatheExample – spurious tuplesCopyright © 2007 Ramez Elmasri and Shamkant B. NavatheExample – spurious tuplesCopyright © 2007 Ramez Elmasri and Shamkant B. NavatheProperties of Relational DecompositionsGoals: Dependency preservation property (can be sacrificed)Lossless join property (a must)Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe 9Properties of Relational DecompositionsDependency Preservation Property of a Decomposition: Definition: Given a set of dependencies F on R, the projection of F on Ri, denoted by pRi(F) where Ri is a subset of R, is the set of dependencies X Y in F+ such that the attributes in X υ Y are all contained in Ri.Hence, the projection of F on each relation schema Ri in the decomposition D is the set of functional dependencies in F+, the closure of F, such that all their left- and right-hand-side attributes are in Ri.Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe 10Properties of Relational DecompositionsDependency Preservation Property of a Decomposition (cont.):Dependency Preservation Property:A decomposition D = {R1, R2, ..., Rm} of R is dependency-preserving with respect to F if the union of the projections of F on each Ri in D is equivalent to F; that is((R1(F)) υ . . . υ (Rm(F)))+ = F+ Claim 1:It is always possible to find a dependency-preserving decomposition D with respect to F such that each relation Ri in D is in 3NF.Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe 11Properties of Relational Decompositions (5)Lossless (Non-additive) Join Property of a Decomposition: Definition: Lossless join property: a decomposition D = {R1, R2, ..., Rm} of R has the lossless (nonadditive) join property with respect to the set of dependencies F on R if, for every relation state r of R that satisfies F, the following holds, where * is the natural join of all the relations in D: * ( R1(r), ..., Rm(r)) = rNote: The word loss in lossless refers to loss of information, not to loss of tuples. In fact, for “loss of information” a better term is “addition of spurious information”Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe 12Algorithms for Relational Database Schema Design Dependency-Preserving Decomposition into 3NF SchemasCopyright © 2007 Ramez Elmasri and Shamkant B. Navathe 13Algorithms for Relational Database Schema DesignNon-Additive Join Decomposition into BCNF SchemasCopyright © 2007 Ramez Elmasri and Shamkant B. Navathe 14Boyce-Codd Normal FormCopyright © 2007 Ramez Elmasri and Shamkant B. Navathe 15Algorithms for Relational Database Schema DesignDependency-Preserving and Non-Additive Join Decomposition into 3NF SchemasCopyright © 2007 Ramez Elmasri and Shamkant B. Navathe 16About Nulls, Dangling Tuples and Alternative Relational DesignsCopyright © 2007 Ramez Elmasri and Shamkant B. Navathe 17Problems with NULL values and dangling tuples18Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe 19Algorithms for Relational Database Schema Design (7)Discussion of Normalization Algorithms:Problems:The database designer must first specify all the relevant functional dependencies among the database attributes. These algorithms are not deterministic in general. It is not always possible to find a decomposition into relation schemas that preserves dependencies and allows each relation schema in the decomposition to be in BCNF (instead of
View Full Document
Unlocking...