Chapter 16 Relational Database Design Algorithms and Further Dependencies Copyright 2011 Pearson Education Inc Publishing as Pearson Addison Wesley DESIGNING A SET OF RELATIONS 1 The Approach of Relational Synthesis Bottom up Design Assumes that all possible functional dependencies are known First constructs a minimal set of FDs Then applies algorithms that construct a target set of 3NF or BCNF relations Additional criteria may be needed to ensure the the set of relations in a relational database are satisfactory Copyright 2011 Ramez Elmasri and Shamkant Navathe DESIGNING A SET OF RELATIONS 2 Goals Lossless join property a must Dependency preservation property Algorithm 16 3 tests for general losslessness Algorithm 16 5 decomposes a relation into BCNF components by sacrificing the dependency preservation Additional normal forms 4NF based on multi valued dependencies 5NF based on join dependencies Copyright 2011 Ramez Elmasri and Shamkant Navathe 1 Properties of Relational Decompositions 1 Relation 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 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 2 Relation 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 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 2 Another 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 from generating spurious tuples Copyright 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 3 Dependency 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 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 4 Dependency 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 See examples in Fig 15 13a and Fig 15 12 Claim 1 It is always possible to find a dependencypreserving decomposition D with respect to F such that each relation Ri in D is in 3nf Copyright 2011 Ramez Elmasri and Shamkant Navathe Properties 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 r Note 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 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 6 Lossless Non additive Join Property of a Decomposition cont Algorithm 16 3 Testing for Lossless Join Property Input A universal relation R a decomposition D R1 R2 Rm of R and a set F of functional dependencies 1 Create an initial matrix S with one row i for each relation Ri in D and one column j for each attribute Aj in R 2 Set S i j bij for all matrix entries each bij is a distinct symbol associated with indices i j 3 For each row i representing relation schema Ri for each column j representing attribute Aj if relation Ri includes attribute Aj then set S i j aj each aj is a distinct symbol associated with index j CONTINUED on NEXT SLIDE Copyright 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 7 Lossless Non additive Join Property of a Decomposition cont Algorithm 16 3 Testing for Lossless Join Property 4 Repeat the following loop until a complete loop execution results in no changes to S for each functional dependency X Y in F for all rows in S which have the same symbols in the columns corresponding to attributes in X make the symbols in each column that correspond to an attribute in Y be the same in all these rows as follows If any of the rows has an a symbol for the column set the other rows to that same a symbol in the column If no a symbol exists for the attribute in any of the rows choose one of the b symbols that appear in one of the rows for the attribute and set the other rows to that same b symbol in the column 5 If a row is made up entirely of a symbols then the decomposition has the lossless join property otherwise it does not Copyright 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 8 Lossless nonadditive join test for n ary decompositions a Case 1 Decomposition of EMP PROJ into EMP PROJ1 and EMP LOCS fails test b A decomposition of EMP PROJ that has the lossless join property Copyright 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 8 Lossless nonadditive join test for n ary decompositions c Case 2 Decomposition of EMP PROJ into EMP PROJECT and WORKS ON satisfies test Copyright 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 9 Testing Binary Decompositions for Lossless Join Property Binary Decomposition Decomposition of a relation R into two relations PROPERTY LJ1 lossless join test for binary decompositions A decomposition D R1 R2 of R has the lossless join property with respect to a set of functional dependencies F on R if and only if either The f d R1 R2 R1 R2 is in F or The f d R1 R2 R2 R1 is in F Copyright 2011 Ramez Elmasri and Shamkant Navathe Properties of Relational Decompositions 10 Successive
View Full Document
Unlocking...