CS 44800: Introduction to Relational Database Management Systems

Assignment 2: Relational Database Design

Due 11:59pmEDT Friday, 17 September 2021

Update 9/14 11:51 - 4: Added MVD question.

Please turn in a PDF through Gradescope. You'll need to access Gradescope through Brightspace the first time (to register you for the course in Gradescope.) Gradescope is pretty self-explanatory, ITaP provides these instructions. Make sure that you mark the start/end of each question in Gradescope. Assignments will be graded based on what you mark as the start/end of each question. Please typeset your answers. (You won't be doing handwritten responses for a Google Project work request, why would you do so for class?)

1. Functional dependencies

Given R=(A,B,C,D,E) and the set of functional dependencies F = {AB→D, AC→E, A→B, BC→E, A→E}:

  1. Give the closure F+ of F.
  2. Are there any extraneous dependencies (dependencies that can be derived from other dependencies) in F?
  3. Rewrite F into a canonical cover FC.
  4. What are candidate keys for R given the functional dependencies?

2. Lossless join decomposition

  1. Is the decompsition of R = (A,B,C,D,E,F) into R1=(A,B,C), R2=(A,B,D), and R3=(D,E,F) lossless? Assume the functional dependencies F={A→C, AB→D, B→E, BC→EF, DE→F}. Please explain your answer.
  2. Suppose that we decompose the schema R = (A, B, C, D, E) into R1=(A, B, C) and R2=(A, D, E). Show that this decomposition is a lossless-join decomposition given given that the following set F of functional dependencies holds: A→BC , CD→E , B→D , E→A .

3. Normalization

  1. Explain the differences between 3NF and BCNF. Give an advantage to having a schema in BCNF over 3NF, and an advantage to having a schema in 3NF but not BCNF.
  2. For a relation R=(C, S, J, D, P, Q, V) and the following Functional Dependencies: C→CSJDPQV, SD→P, JP→C, J→S, decompose into 3NF Form. Show your steps.
  3. For a relation R=(A, B, C, D, E, H) and the following Functional Dependencies: A→BC , E→HA Decompose into BCNF. Is the final BCNF dependency-preserving?

4. Multivalued dependency and 4th normal form

  1. Why do we need multi-valued dependency if we already preserve all the functional dependencies? Please give an example (other than the one below) of a situation that we need to further decompose using multi-valued dependencies.
  2. Consider the relation R:
    ID Age MovieLiked SnackLiked Name
    135 18 Avengers Popcorn Mike Smith
    486 17 Harry Potter Popcorn Rachel Johnson
    135 18 X-Men Cookies Mike Smith
    135 18 Avengers Cookies Mike Smith
    486 17 Frozen Chips Rachel Johnson
    135 18 X-Men Popcorn Mike Smith
    486 17 Frozen Popcorn Rachel Johnson
    486 17 Harry Potter Chips Rachel Johnson
    1. List functional dependencies that hold for R.
    2. List multivalued dependencies that hold for R.
    3. Suppose I deleted all rows where SnackLiked was Popcorn. Would the dependencies you list still hold? Explain.
    4. Give a 4NF decomposition of the relation R.

5. Open-ended question: Student Activities Database

You are developing a database to help keep track of student activities (clubs) and events. Clubs have a name, officers, and members, each officer has a title - for example, the Computer Science Undergraduate Board with President Lauren Lum, vice-president Arianna Smith, etc. Events have a name, a sponsoring club, a location, a date/time, and a list of attendees, e.g. USB Help Room, 9/7 6pm, Rewati Shitole and Chandiran Dhukkaram. You also have access to a table of students, containing their Purdue email (CAREER account ID), name, campus address, primary major, and class year.

  1. List the attributes in the Universal Relation view (all of the attributes in the databases), along with an appropriate SQL data type. You should include everything listed above, as well as at least one attribute that you think would be important to include that we haven't included. Try not to include attributes that could be calculated using a query (e.g., number of members.)
  2. List functional dependencies and multivalued dependencies that you think should apply. For each, give the dependency, and if not obvious, a brief description of why it should hold.
  3. Give a lossless, dependency-preserving BCNF, 3NF, or 4NF decomposition (as appropriate) based on your functional and multivalued dependencies. Show your work (e.g., if you compute the closure or a canonical cover as part of this, show it.) Constraint:Assume that you are stuck with the registrar-provided student table as is, you can't add attributes to it or decompose it. This sort of thing happens in the real world...
    1. Given your dependencies, is the student table BCNF or 3NF?
    2. Does this constraint, that you can't alter the student table, prevent you from having a lossless-join decomposition?
    3. Does this constraint prevent any of your other relations from being in BCNF or 3NF?
    4. Are there any dependencies that are not preserved because of this constraint? If so, list them and explain.
  4. List the keys that for each of your relations. Are all the functional and multivalued dependencies enforced by the schema and the keys? If so, explain briefly why (this could be explained in a couple of words). If not, list which functional dependencies are not enforced and why.
  5. Are there any attributes in your database where it would be appropriate to allow null values? If so, briefly explain why.
  6. Give SQL CREATE TABLE statements to create the tables, including specifying keys.

Valid XHTML 1.1