Comp 419
Database Design
Final Exam Study Question Answers

Note: these study questions and answers pertain only to material covered since the midterm. The final is comprehensive! See the midterm and study questions for the midterm for more study questions.

1. Consider a relational database containing relations with the following schemes:

       Customer-scheme = (name, address, cust-num)
       Flyrod-scheme = (manufacture, length, line-weight, flyrod-stock-num)
       Purchased-scheme = (cust-num, flyrod-stock-num, date)

   One of the referential integrity constraints associated with this flyshop database is:

   

   1. (5 pts) When a tuple is inserted into purchased, what test needs to be performed to insure that this referential integrity constraint is maintained?
      
      If the tuple inserted is , then the test is .
      
      
   2. (5 pts) When a tuple is inserted into customer, what test needs to be performed to insure that this referential integrity constraint is maintained?
      
      none
      
      
2. A company that manufactures lava lamps uses a relational database to keep track of what parts it has in stock, suppliers of parts, and which suppliers supply what parts. The schemes of these relations are:

     Part-scheme = (part-num, description, groovyness, quantity)
     Supplier-scheme = (supplier-name, address, phone-number)
     Supplies-scheme = (part-num, supplier-name, address, cost)

   The primary key for relations on Part-scheme is part-num, and the primary key for relations on Supplier-scheme is {supplier-name, address}.
   1. (5 pts) What referential integrity constraint should hold between the supplier and supplies relations?
      
      

      

   2. (5 pts) Is there any referential integrity constraint between the part and supplies relations? Why or why not?
      
      There is no referential integrity constraint that references part on the left of the and supplies on the right, because part-num is not the primary key for supplies.

      There is no referential integrity constraint that references part on the right of the and supplies on the left (even though part-num is the primary key for part), because we only store parts that are in stock, and we may very well keep track of suppliers for parts that aren't in stock. Hence, there is no referential integrity constraint between these two relations.
      
      

   3. (5 pts) Give a functional dependency expressing the fact that two different addresses do not share the same phone-number.
      
      phone-number address
      
      
3. Now assume that the management of the lava lamp company decides that each supplier can supply at most one kind of part - i.e. that the company will buy at most one kind of part from each supplier, even if that supplier has other kinds of parts. Thus, the company will not have two different kinds of parts in stock that were supplied by the same supplier, and will not even store the information that a supplier has other kinds of parts and could potentially supply these parts.
   1. (5 pts) Under this assumption, if we view supplies as a relationship set from supplier to part (E-R model), what is the mapping cardinality of this relationship set?
      
      many-to-one
      
      
   2. (5 pts) Express your mapping cardinality from the first part of this question as one or more functional dependencies that relations on Supplies-scheme must satisfy.
      
      supplier-name, address part-num
      
      
4. (5 pts) Consider a scheme:

    Allparts-scheme = (part-num, description, groovyness, quantity, 
                       supplier-name, address, phone-number, cost)

   and set of functional dependencies on that scheme:

   
    F =   part-num    {description, groovyness, quantity},
          {supplier-name, address}    phone-number   
   

   Is the decomposition of Allparts-scheme into Part-scheme, Supplier-scheme, and Supplies-scheme a lossless-join decomposition? Why or why not?
   
   Yes. Let:

    Sup-scheme = (part-num, supplier-name, address, phone-number, cost)

   The intersection of Part-scheme and Sup-scheme is part-num, and part-num Part-scheme. (Easy proof omitted - make sure you include it in a similar situation on the exam.) Hence, decomposing Allparts-scheme into Sup-scheme and Part-scheme is a lossless join decomposition.

   Now decompose Sup-scheme into Supplier-scheme and Supplies-scheme. The intersection of these schemes is {supplier-name, address}, and {supplier-name, address} Supplier-scheme. (Easy proof omitted.) Hence, this is a lossless join decomposition.

   The result of a sequence of lossless join decompositions is a lossless join decomposition.
   
   

5. Consider the relation scheme and set of functional dependencies:

   

   that relations on scheme R must satisfy.

   1. (2 pts) Which rule or axiom allows us to conclude from ?
      
      decomposition
      
      
   2. (2 pts) Which rule or axiom allows us to conclude from and ?
      
      transitivity
      
      
   3. (2 pts) Which rule or axiom allows us to conclude from and ?
      
      union
      
      
   4. (4 pts) Is G a superkey for R? Why or why not?
      
      = GABDE

      Thus, G is not a superkey because R.
      
      

6. Consider the relation scheme and set of functional dependencies:

   

   that relations on scheme R must satisfy.

   1. (10 pts) Find a lossless join decomposition of R into BCNF.
      
      Compute = ABGE

      A is not a superkey and A   BG is not trivial, so the first decomposition is  = ABG and  = ACDE.

      Consider . A is clearly a superkey for , so we compute:

      = B (trivial)
      = GE (trivial when restricted to )
      = BGE (trivial when restricted to )

      Thus, is in BCNF.

      Consider . Compute:

      = CDE

      Thus, C is not a superkey for , and C D is on and not trivial. Decompose to produce  = CD and  = ACE.

      Consider . Clearly C is a superkey for . Compute:

      D+ = D (trivial)

      Hence, is in BCNF.

      Consider . Compute:

      = ABGE

      Hence, A E holds, A is not a superkey for , and A E is not trivial. Decompose to produce  = AE and  = AC. From closures previously computed and = E, these schemes are in BCNF. Hence, our decomposition is:

      { , , , }
      
      

   2. (7 pts) Compute , a canonical cover for F.
      
      

      

      Use the union rule to produce:

      

      If we replace A BG by A B,  = AB, so we lose A G. Hence, G is not extraneous.

      If we replace C DE by C D,  = CDE, so we can recover C DE. Hence, E is extraneous.

      

      If we replace CD E by C E, we compute  = CDE in . Hence, C E is in , and so D is extraneous.

      

      use the union rule to produce:

      

      If we replace C DE by C D,  = CD, so we can NOT recover C DE. Hence, E is not extraneous.

      If we replace C DE by C E,  = CE, so we can NOT recover C DE. Hence, D is not extraneous.

      Thus:

      

   3. (5 pts) Find a lossless join, dependency preserving decomposition of R into 3NF.
      
      None of the functional dependencies in the canonical cover is a subset of any other (just looking at the attributes in the f.d.), so step 2 of the algorithm produces: {ABG, CDE, GE}

      Compute closures:

      = ABGE
      = CDE
      = GE
      

      Thus, no scheme contains a superkey for R (much less a candidate key). However, = ACBGDE and clearly neither A nor C is a superkey. Hence, AC is a candidate key and our lossless join, dependency preserving 3NF decomposition is: {ABG, CDE, GE, AC}
      
      

7. Consider the relation scheme R = {A, B, C, G} and set of dependencies:

   

   that relations on scheme R must satisfy.

   1. (5 pts) Prove that A G is in .
      
      
      1. A CG (By A B and complementation.)
      2. A C (By A C and replication.)
      3. A BG (By 2 and complementation.)
      4. A G (By 1, 3 and intersection.)
   2. (5 pts) Prove that the decomposition {ABC, AG} is a lossless join decomposition.
      
      The intersection of these two schemes is A. To show that the decomposition is lossless, it suffices to show A AG.
      1. A G (from the previous part.)
      2. A A (trivial)
      3. A AG (1, 2, multivalued union)
   3. (10 pts) Find a lossless join decomposition of R into 4NF.
      
      Compute = AC. Hence, A is not a superkey for R. Clearly, A C is not trivial. Decompose into = AC and = ABG.

      Consider . Since A is a superkey for , and multivalued dependencies with C on the left are all trivial on (because C C is trivial and C A would be trivial on if it held), this scheme is in 4NF.

      Consider . From the previous problem, we have A G and we know that A is not a superkey for . Since A G is not trivial for , decompose into = AG and = AB.

      By the reasoning used for , we can conclude that and are in 4NF. Hence, the decomposition is: { , , }.
      
      

8. (10 pts) What kinds of problems associated with relational database design can decomposition help solve? Why does decomposition help?
   
   Duplication of information and inability to represent information (null values). Appropriate decompositions are needed to achieve normal forms, and the entire point of normal forms is to avoid duplication.

   Decomposition helps with inability to represent information because this problem usually arises from attributes that are not closely related being stored in the same relation. In this case, information for one subset of the attributes will often be available when the associated information for the remaining attributes is not (leading to null values). Decomposition solves this problem by splitting into schemes with only closely related attributes.
   
   

9. (5 pts) Are arbitrary decompositions helpful in designing relation schemes? Why or why not?
   
   NO! An arbitrary decomposition may be a lossy join decomposition, in which case information is actually lost from the relation! Even if a decomposition is lossless, if the decomposition isn't necessary to achieve a higher level of normalization, then it does not improve the design. In fact, it degrades the design by making querying more expensive (more joins).
   
   
10. (5 pts) Is it possible in general to have two primary indices on the same relation for different search keys? Justify your answer.
    
    No. In a primary index, the records in the file are stored in sorted order (by the search key). In general, it will not be possible to sort the records by two different search keys simultaneously. Hence, it is not possible in general to have two primary indices on different search keys.
    
    
11. (15 pts) Construct a B tree for the following key values: (2, 3, 4, 7, 11, 17, 19, 23, 29, 31). Assume that insertions happen in the order that the keys are listed in. You do not need to show the file that the leaves are pointing into - just the B tree.
    
    Solution omitted - this question is not from the material for the exam.

• About this document ...