BCNF vs 3NF3NF SchemaSlide 3Slide 4ClosureBCNFifyB-tree InsertionB-tree deletion - pseudocodeBCNF vs 3NF•BCNF: For every functional dependency X->Y in a set F of functional dependencies over relation R, either: –Y is a subset of X or,–X is a superkey of R•3NF: For every functional dependency X->Y in a set F of functional dependencies over relation R, either: –Y is a subset of X or,–X is a superkey of R, or–Y is a subset of K for some key K of R•N.b., no subset of a key is a key3NF SchemaAccount Client OfficeA Joe 1B Mary 1A John 1C Joe 2For every functionaldependency X->Y in a set Fof functional dependenciesover relation R, either: – Y is a subset of X or,– X is a superk ey of R, or– Y is a subset of K for some key K of RClient, Office -> Client, Office, AccountAccount -> Office3NF SchemaAccount Client OfficeA Joe 1B Mary 1A John 1C Joe 2For every functionaldependency X->Y in a set Fof functional dependenciesover relation R, either: – Y is a subset of X or,– X is a superk ey of R, or– Y is a subset of K for some key K of RClient, Office -> Client, Office, AccountAccount -> OfficeBCNF vs 3NFFor every functionaldependency X->Y in a set Fof functional dependenciesover relation R, either: –Y is a subset of X or,–X is a superke y of R–Y is a subset of K for some key K of R3NF has some redundancyBCNF does notUnfortunately, BCNF is not dependency preserving, but 3NF isClient, Office -> Client, Office, AccountAccount -> OfficeAccount Client OfficeA Joe 1B Mary 1A John 1C Joe 2Account OfficeA 1B 1C 2Account ClientA JoeB MaryA JohnC JoeAccount -> OfficeNo non-trivial FDsLossless decompositionClosure•Want to find all attributes A such that X -> A is true, given a set of functional dependencies Fdefine closure of X as X*Closure(X): c = XRepeatold = cif there is an FD Z->V such that Z c and V c then c = c U V until old = creturn cBCNFifyClosure(X): c = XRepeatold = cif there is an FD Z->V such that Z c and V c then c = c U V until old = creturn cBCNFify(schema R, functional dependency set F):D = {{R,F}}while there is a schema S with dependencies F' in D that is not in BCNF, do:given X->Y as a BCNF-violating FD in F such that XY is in Sreplace S in D with S1={XY,F1} and S2={(S-Y) U X, F2} where F1 and F2 are the FDs in F over S1 or S2(may need to split some FDs using decomposition)Endreturn DFor every functionaldependency X->Y in a set Fof functional dependenciesover relation R, either: –Y is a subset of X or,–X is a superkey of RB-tree InsertionINSERTION OF KEY ’K’ find the correct leaf node ’L’; if ( ’L’ overflows ){ split ’L’, by pushing the middle key upstairs to parent node ’P’; if (’P’ overflows){ repeat the split recursively; } else{ add the key ’K’ in node ’L’; /* maintaining the key order in ’L’ */ }Slide from Mitch Cherniak and George KolliosB-tree deletion - pseudocodeDELETION OF KEY ’K’ locate key ’K’, in node ’N’ if( ’N’ is a non-leaf node) { delete ’K’ from ’N’; find the immediately largest key ’K1’; /* which is guaranteed to be on a leaf node ’L’ */ copy ’K1’ in the old position of ’K’; invoke this DELETION routine on ’K1’ from the leaf node ’L’; else { /* ’N’ is a leaf node */ if( ’N’ underflows ){ let ’N1’ be the sibling of ’N’; if( ’N1’ is "rich"){ /* ie., N1 can lend us a key */ borrow a key from ’N1’ THROUGH the parent node; }else{ /* N1 is 1 key away from underflowing */ MERGE: pull the key from the parent ’P’, and merge it with the keys of ’N’ and ’N1’ into a new node; if( ’P’ underflows){ repeat recursively } } }Slide from Mitch Cherniak and George
View Full Document
Unlocking...