CS 347 -- Assignment #4

Relational Database Design

Due Wednesday, October 15 by 5pm
 

A feature diagram is a common modeling representation for configuring products. A diagram is a tree.  Nodes are terminal if they have no children, otherwise they are non-terminal (aka parents).  There are three possible relationships between a parent node and its children:

• AND -- children are either mandatory (indicated by a filled circle) or optional (indicated by an unfilled circle).
• OR -- one or more children can be chosen
• CHOOSE1 -- exactly one child can be selected

An AUTO feature diagram is depicted below.  The parent-child relationship between Car and its children is AND: Every car will have a body, transmission, and engine.  Optionally it will have cruise control.  The parent-child relationship between Engine and its children is OR: Every engine will be gasoline, electric, or both.  Finally, the parent-child relationship between Transmission and its children is CHOOSE1 -- a transmission is either manual or automatic, but not both.

Another feature diagram, called SERVICES, is shown below.  Every AVservice has a video, internet connection, or both.  An internet connection is either via a powerline, ADSL, or wireless (choose1).

1. Draw an ER diagram to model the structure of a feature model. Remember, feature models have names, and you should use their names to differentiate entities in one feature model to those of another. Use Visio to draw your diagram
2. Derive database relations from your model in (1).
3. Populate your relations from (2) using tuples that would capture the data in the AUTO and SERVICES diagrams.
   
4. Identify the functional dependencies that are represented in your feature model.
5. Derive the database relations from the FDs you found in (4).  The resulting tables should be the same as those you created in (2).
   
6. Prove or disprove the following inference rules for functional dependencies.  A proof can be made either by a proof argument or by using inference rules IR1 through IR6 (see classnotes).  If a proof cannot be found, present a counter example demonstrating a relation instance that satisfies the conditions and functional dependencies in the left hand side of the inference rule, but does not satisfy the dependencies on the right-hand side.
   
   1. { W -> Y, X -> Z} implies { WX->Y }
   2. {X->Y} and Y >= Z implies X->Z
      Note: Y >= Z means Z is a proper subset of Y
   3. { X->Z, Y->Z } implies X->Y
       
7. Consider the universal relation R = { A, B, C, D, E, F, G, H, I, J } and the set of dependencies F = { AB->C, A ->DE, B->F, F->GH, D->IJ }  What is the key for R?  Decompose R into 3NF relations.