Scribd Logo
Upload

Welcome to Scribd!

  • 226 views

    BCNF Vs 3Nf: - N.B., No Subset of A Key Is A Key

    Uploaded by

    Vinay Singh
    BCNF requires that for every functional dependency X -> Y, either Y is a subset of X or X is a superkey. 3NF is less restrictive, also allowing Y to be a subset of some key K. This makes 3NF easier to satisfy but can allow some redundancy, while BCNF ensures full normalization with no redundancy but is sometimes harder to achieve.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    BCNF Vs 3Nf: - N.B., No Subset of A Key Is A Key

    Uploaded by

    Vinay Singh
    226 views8 pages
    BCNF requires that for every functional dependency X -> Y, either Y is a subset of X or X is a superkey. 3NF is less restrictive, also allowing Y to be a subset of some key K. This makes 3NF easier to satisfy but can allow some redundancy, while BCNF ensures full normalization with no redundancy but is sometimes harder to achieve.

    Original Title

    BCNF vs 3NF

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    BCNF requires that for every functional dependency X -> Y, either Y is a subset of X or X is a superkey. 3NF is less restrictive, also allowing Y to be a subset of some key K. This makes 3NF easier to satisfy but can allow some redundancy, while BCNF ensures full normalization with no redundancy but is sometimes harder to achieve.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    226 views8 pages

    BCNF Vs 3Nf: - N.B., No Subset of A Key Is A Key

    Uploaded by

    Vinay Singh
    BCNF requires that for every functional dependency X -> Y, either Y is a subset of X or X is a superkey. 3NF is less restrictive, also allowing Y to be a subset of some key K. This makes 3NF easier to satisfy but can allow some redundancy, while BCNF ensures full normalization with no redundancy but is sometimes harder to achieve.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 8

    BCNF 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 key
    For every functional
    dependency X->Y in a set F 3NF Schema
    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 Client, Office -> Client, Office, Account
    some key K of R Account -> Office

    Account Client Office


    A Joe 1
    B Mary 1
    A John 1
    C Joe 2
    For every functional
    dependency X->Y in a set F 3NF Schema
    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 Client, Office -> Client, Office, Account
    some key K of R Account -> Office

    Account Client Office


    A Joe 1
    B Mary 1
    A John 1
    C Joe 2
    BCNF vs 3NF
    For every functional 3NF has some redundancy
    dependency X->Y in a set F
    of functional dependencies
    BCNF does not
    over relation R, either:
    – Y is a subset of X or, Unfortunately, BCNF is not dependency
    – X is a superkey of R preserving, but 3NF is
    – Y is a subset of K for
    Account Office
    some key K of R
    A 1

    Account Client Office B 1

    A Joe 1 C 2

    B Mary 1 Account -> Office


    Lossless
    decomposition
    A John 1 Account Client
    C Joe 2 A Joe
    Client, Office -> Client, Office, Account B Mary
    Account -> Office
    A John
    C Joe

    No non-trivial FDs
    Closure
    • Want to find all attributes A such that X -> A is true, given a set of functional
    dependencies F

    define closure of X as X*

    Closure(X):
    c=X
    Repeat
    old = c
    if there is an FD Z->V such that
    Z  c and
    V  c then
    c=cUV
    until old = c
    return c
    Closure(X):
    c=X
    Repeat
    BCNFify
    For every functional
    old = c
    dependency X->Y in a set F
    if there is an FD Z->V such that
    Z  c and
    of functional dependencies
    V  c then over relation R, either:
    c=cUV – Y is a subset of X or,
    until old = c – X is a superkey of R
    return c

    BCNFify(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 S
    replace 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)
    End
    return D
    B-tree Insertion
    INSERTION 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 Kollios


    B-tree deletion - pseudocode
    DELETION 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 Kollios

    You might also like