Search code examples
bcnf

Find keys and decompose it into BCNF

I have this relation:

wiki(url,title,abstract,link,category_id,category,heading,heading_pos)

And the FD's are:

F = {
    url → title, abstract
    category_id → category
    url, heading_pos → heading
}

I need to find the keys and decompose into a set of Boyce-Codd normalized relations. I have tried to read related and similar questions but I'm unable to understand the given answers. Hope someone will help me with this assignment

Solution

  • Assuming 'wiki' as relation R and its attributes url,title,..heading_pos to be A,B,...H respectively.

    We have,

    R = {A,B,C,D,E,F,G,H}
    FD's = {A->BC, E->F, AH->G}

    The key here is ADEH.

    We can first convert the relation R to 3NF and then to BCNF.

    To convert a relation R and a set of functional dependencies(FD's) into 3NF you can use Bernstein's Synthesis. To apply Bernstein's Synthesis -

    • First we make sure the given set of FD's is a minimal cover
    • Second we take each FD and make it its own sub-schema.
    • Third we try to combine those sub-schemas

    For example in your case:

    First we check whether the FD's is a minimal cover (singleton right-hand side , no extraneous left-hand side attribute, no redundant FD)

    • Singleton RHS: We write the FD's with singleton RHS. So now we have FD's as {A->B, A->C, E->F, AH->G}
    • No extraneous LHS attribute: We remove the extraneous LHS attribute if any. There are no extraneous LHS attributes here.
    • No redundant FD's: We remove the redundant dependencies if any. There are no redundant dependencies here.

    Second we make each FD its own sub-schema. So now we have - (the keys for each relation are in bold)

    R1={A,B}
    R2={A,C}
    R3={E,F}
    R4={A,H,G}

    Third we combine all sub-schemas with the same LHS. So now we have -

    S1 = {A,B,C}
    S2 = {E,F}
    S3 = {A,H,G}

    Since none of the above decomposed relations contain contain a key of R, we need to create an additional relation schema that contains attributes that form of a key of R. This is to ensure lossless join decomposition that preserves dependencies. So we add -

    S4 = {A,D,E,H}

    This is in 3NF. Now to check for BCNF we check if any of these relations (S1,S2,S3,S4) violate the conditions of BCNF (i.e. for every functional dependency X->Y the left hand side (X) has to be a superkey) . In this case none of these violate BCNF and hence it is also decomposed to BCNF.

    Note - The importance of some of these steps may not be clear in this example. Have a look at other examples here and here.