Homework 3 Solutions

1a)  A relational design in BCNF can always be provided from a universal
     relation (i.e. given a set of functional dependencies) over a given
     set of attributes.  What is not guaranteed is that all functional 
     dependencies will be preserved.

1b)  Yes.  See algorithms 15.1, 15.4.  The limitation to algorithm 15.1 is that
     it does not guarantee a lossless join.  15.4 preserves dependencies
     and has the lossless join property.  (15.3 can also be mentioned.  It
     results in BCNF relations, with lossless join, but does not preserve
     dependencies.)

1c)  Any binary relation (AB) where AB is the key is an example of a 
     trivial MVD.  For example, (Student Course).

     Also, X->>Y is trivial in R if Y is included in X, or X U Y = R.
    
     This dependency is called trivial because it does not cause problems
     such as update anomalies, it does not cause duplication which has
     to be eliminated, and it does not specify any true constraint. 

     For a three column relation, consider BOOK(ISBN#, subject, author).
     It may have:
       fd1:  ISBN#->subject
      mvd1:  ISBN#->>author|subject
     Note that mvd1 is a trivial MVD.  The ISBN#->>subject part of the MVD
     is truly an fd, which makes it trivial.

1d)  requirements collection and analysis - ...
     conceptual database design - ...
     choice of DBMS - ...
     data model mapping - ...
     physical database design - ...
     database system implementation and tuning - ...


2a)  Use algorithm 14.2
     step 1:
     F = G = {A->C, AB->C, C->DI, CD->I, EC->AB, EI->C}
     step 2:
     G = {A->C, AB->C, C->D, C->I, CD->I, EC->A, EC->B, EI->C}
     step 3:
     G = {A->C, C->D, C->I, EC->A, EC->B, EI->C}
     step 4:
     G = same as above (no further reduction)

2b)  Use algorithm 15.4a
     K := R
     Cannot remove A, B, C, F, I.
     Can remove D, because G->DE.
     Can remove E, because G->DE.
     Cannot remove G.
     Can remove H, because G->DE, BEG->DH.
     Result = K := {ABCFGI}.

     The key is not unique.
     See:  K := {ABCEFI}.
     This is the same because E->G

3a)  Yes, it does.  You can use the test (R1 intersect R2) -> R1 - R2 or
     (R1 intersect R2) -> R2 - R1.  To be lossless, DI->ABC or DI->EJ 
     must hold. Since DE->J and I->E, DI->EJ.  (Propert LJ1)

     -OR-  

     You can use the algorithm (15.1) for lossless join testing from the book.
     (from dwada)

     Step1:
     R1 a1 a2 a3 a4 b  a6 b
     R2 b  b  b  a4 a5 a6 a7

     Step2:
     I->E
     R1 a1 a2 a3 a4 a5 a6 b
     R2 b  b  b  a4 a5 a6 a7

     Step3:
     DE->J
     R1 a1 a2 a3 a4 a5 a6 a7
     R2 b  b  b  a4 a5 a6 a7

3b)  
     First, you might want to draw out:

     +-----+-----------+      
     |     |           |     
     V     |           V
           +-----+-----------+ 
           |     |           |
           |     V           |
     A     B     C     D     I

     Clearly, BI is the only possible key (the only minimal set defining 
     everything else).

           +-----+
           |     |
           V     |
     +-----+-----------+
     |     |           |
     |     |           V
     D     E     I     J

     Again, DI is the only possible key for the relation.

     (ABCDI)

     3NF? No.  Consider the fd B->AD.  B is not a superkey (does not
     uniquely determine C), and AD are both nonprime.  Thus, it's not in BCNF
     either.  Is it in 2NF?  ACD are nonprime, and AD are not fully
     fd on BI, the key of the relation.  So, it's in 1NF.

     (DEIJ)

     3NF? No.  Consider the fd DE->J. DE is not a superkey (does not
     uniquely determine I) and J is clearly not prime.  Is it in 2NF?
     DI is the (only) key, and EJ are nonprime.  But E is not fully
     fd on DI (because I->E).  So, it's again in 1NF.


     BCNF?  No, by the definition of BCNF.  (See section 14.5.)

    3c)
    Make ->> Model|Color - No, because color and model are not independent,
    e.g., (Acura Integra Green) is not true.
    Model ->> Make|Color - No, because make and color are not independent,
    e.g., there are no green Hondas.
    (Make,Model) ->> Color - This exists, but is trivial.

    3d)
    i)  (Model#, Year) -> Price
        Model# -> Manuf_plant -> Color
    The above dependencies determine all the attributes in REFRIG.

    ii)
    Not in 3NF, because of the transitive dependency:
    Model# -> Manuf_plant -> Color
    Not in 2NF, because Manuf_plant is partially depenedent on the key.
    In 1NF.  All attribute values are atomic.

    iii)
    2NF:
    2NFa(MODEL#, YEAR, Price)
    2NFb(MODEL#, Manuf_plant, Color)
    3NF, BCNF:
    3NFa(MODEL#, YEAR, Price)
    3NFb(MODEL#, Manuf_plant)
    3NFc(MANUF_PLANT, Color)

    iv) The relations in iii is in BCNF because all
    left-hand-sides of nontrivial dependencies are keys.