Properties of Decomposition AndAn Algorithm for BCNFDecompostionBy David Stilliona presentation prepared forDr. Sin-Min LeeIntroduction to Database ManagementFall, 2005Why Do We Care?Because no amount of good SQLcode will overcome bad table design.It is very inefficient to do table joinsin order to apply and evaluateintegrity constraints.The Theoretical Explanation ofSchema DecompositionGiven R = (R*; F), where R* is the set of attributes of the schema and Fis its set of Functional Dependencies, is a collection of schemasR1=(R*1;F1), R2= (R*2 ;F2 ),…, Rn= (R*n ;Fn)These conditions must hold:1. Ri ∫ Rj, if i ∫ j2. R* = Uni=1R*i3. F entails Fi for every i = 1,2,…,nThe 2nd and 3rd conditions arethe most interesting• The second condition states that a decompositionshould not introduce new attributes, and it should notdrop attributes found in the original table.• The third condition states that the decompositionshould not introduce new functional dependences(butmay drop some).Schema Decomposition vs.Relation DecompositionThe decompostion of a schemanaturally leads to the decompositionof relations over it.The decompostion of a relationinstance is NOT the same as thedecompostion of its schema.Schema Decomposition vs.Relation Decomposition cont.Give relation r and our original schema R, arelation decomposition is a set of relationsr1= pR*1-(r), r2= p R*2 -(r),.., rn= pR*n-(r)Relation r No Longer exists.r has been decomposed as described in theprevious slide and now exists as relationsr1,r2,…,rn in the database.HOWEVER,the database must be able to reconstruct rfrom the projections r1,r2,…,rn.How to reconstruct?• Use any method that works.• Usually the best and most practical way to doit is through a natural join.Natural Join must satisfy 3conditions1. It is based on an equality.2. All common attributes participatein the join.3. One set of common fields appearsin the final result.Thus,r = r1 |x| r2 |x| …. |x| rnCaveatReconstructibility must be a property ofschema decompostion and NOT a particularinstance over a schema.Any transformation performed on a schemamust guarantee that reconstructibilty holds forall of its valid relations.What is Lossless?Given R = (R*; F), where R* is the set of attributes of the schema and Fis its set of Functional Dependencies, is a collection of schemasR1=(R*1;F1), R2= (R*2 ;F2 ),…, Rn= (R*n ;Fn)is LOSSLESS, if for every valid instance r of schema R,r = r1 |x| r2 |x| …. |x| rnwherer1= pR*1-(r), r2= p R*2 -(r),.., rn= pR*n-(r)otherwise the decomposition is lossy.What is Losslessness?Losslessness asserts the followingr û r1 |x| r2 |x|….|x| rnA lossy decomposition will return more tupleswhen joining its projections than in the originalundecomposed relation.The issue becomes what information is lost orwhich is accurate or complete or which is valid?With no way to tell the results are meaningless.Testing DecompositionTwo ways!• There is a general test of an n schemadecomposition that works but it is complexand it difficult to implement.• Easier and more practical - BinaryDecomposition(BD).With BD, lossless decomposition can bechecked as long as the originaldecomposition was done on a binary basis.Binary Decomposition RequiresOnce again: Given R = (R*; F), where R* is the set of attributes of theschema and F is its set of Functional Dependencies, is a collection of schemasR1=(R*1;F1), R2= (R*2 ;F2 ),…, Rn= (R*n ;Fn)This decomposition is lossless iff either of thefollowing is true:(R*1 … R*2) Ø R*1 œ F+(R*1 … R*2) Ø R*2 œ F+Dependency-PreservingDecompositionsConsider the decomposition of R = (R*; F), suchthatR1=(R*1;F1), R2= (R*2 ;F2 ),…, Rn= (R*n ;Fn).By definition, F entails Fi and thus F entails Uni=1Fibut Uni=1Fi need not entail F.That is to say not all functional dependencies need to bepreserved for a decomposition to be dependency preserving.Dependency-Preserving ….If and only ifwhen the sets of F and Uni=1Fi are equivalent is thedecomposition of R = (R*; F) intoR1=(R*1;F1), R2= (R*2 ;F2 ),…, Rn= (R*n ;Fn)Dependency preservingProjection of the set of F on SGiven R=(R*;F), a relation r, S(a decomposedschema from R) or S Œ R.The only FD’s guaranteed to hold over ps(r)are X Ø Y œ F+ s.t. X,Y Œ S gives rise tops(F) = ( X Ø Y | X Ø Y œ F+ and X»Y Œ S ).For F in ps(F) we must look at all FDs in F+not just in F.Projection of FunctionalDependencies.....opens a way to construct decompositions.If R=(R*;F) is a schema and R*1,…,R*n are subsetsof attributes s.t. R=Uni=1Ri, then theschemas (R1;pR1(Fa)),…,(Rn; pRn(Fz)) are adecomposition that preserves as many of the originalFDs as possible.Again, F must reflect the closure of F not just F.BCNF and DecompositionProperties of a relation in Boyce-Codd NormalForm -Already in 3NF,2NF and 1NF andall determinants are Super Keys.The goal of relations in BCNF is to eliminateredundancy due to functional dependencies.The Algorithm for BCNFDecompositionInput: R = (R*;F)Decomposition := /* Initially Decomposition consists of only oneschema*/whilethere is a schema S = (S*;F`) in Decomposition that is not in BCNFdo/* Let X Ø Y be a FD in F s.t. X,YŒS and it violates BCNF in S.Decompose using this FD */Replace S in Decomposition with schema S1=(X,Y;F1) and S2= ((S*-Y)» X; F`2), where F`1= pXY(F`) and F`2 = p ((S*-Y) » X(F`)endreturn DecompositionThe Algorithm is Very Clear...ExceptNo part of the algorithm addresses how toapply Armstrong’s Axioms - Reflexivity,Augmentation and Transitivity at eachiteration to determine F+.The algorithm simply says that we choosethe next FD not in BCNF.For ExampleConsider schema R=(R*;F) where R*= ABCDEFGH, andthe set of F being (ABH Ø C, A Ø DE, BGH Ø F, F ØADH, and BH Ø GE )When we start the Decomposition, R=S and algorithmselects an FD not in BCNFOur Resulting RelationsRelations and FDR1 (ADE; A Ø DE )R2( FAH; F Ø AH)R3 ( BCFG; FB Ø CG)Is this a lossless decomposition? - YESIs this a dependency-preservingdecomposition? - NOWhy not? Because F and Uni=1Fi are notequivalent.What Can we Count On? 1. A BCNF decomposition is alwayslossless.2. BCNF decompositions do not need to bedependency preserving.3. The BCNF decomposition isnondeterministic.This means different decompositions occurdepending on the order in which FDs areselected in the while loop.The Database Designer DecidesThe order of selection of FDs for theDecomposition may be a matter of taste.Objective criteria be developed and and applied
View Full Document
Unlocking...