• Preparation and Submission: All challenge problems must be submitted electronically. Please refer to Challenge Problems #1 for accepted formats, guidelines on typing solutions, and details on electronic submission. For this assignment call your solutions file challenge3.<ext>, and as usual submit your solutions using the script /afs/ir/class/cs145/bin/submit-challenge.

• Free Late Days: For this week only, the on-time deadline has been extended to 11:59 PM on Thursday, since you do not have any challenge problems the following week. However, no extra-late submissions beyond the extended Thursday deadline will be permitted.

• Honor Code reminder: You must indicate in your solution any assistance (human or otherwise) that you received. Any assistance received that is not given proper citation will be considered a violation of the Honor Code. In any event, you are responsible for understanding and being able to explain on your own all material that you submit.

The Problems

1. Consider a relation R(A1, A2, ..., An) with n > 0 attributes. Your goal is to construct an instance for this relation that satisfies the functional dependencies Ai -> A(i+1) for all i=1..(n-1). That is:

     A1 -> A2
     A2 -> A3
     A3 -> A4
     ...
     A(n-1) -> An
   

   Furthermore, the only functional dependencies your relation instance should satisfy are the ones above, and those that follow from them. All other functional dependencies (e.g., A2 -> A1, or A4,A3 -> A2, etc.) should be violated by your relation instance. Try to find an instance that has as few tuples as possible.

   Your solution writeup should consist of a clear description or depiction of how to generate your relation instance for any n > 0. As examples, show the actual instances for n=2, n=4, and n=6 (i.e., relations with 2, 4, and 6 attributes).
   
   

2. Consider a relation R(A,B,C). Write a relational algebra expression that returns empty if and only if the multivalued dependency A ->> B holds on R.
   
   

3. Prove the intersection rule for multivalued dependencies. Specifically, consider a relation R and three sets of R's attributes: AA, BB, and CC. Prove that if AA ->> BB and AA ->> CC hold for R, then AA ->> (BB intersect CC) also holds, where intersect is standard intersection of attribute sets. For simplicity you may assume that AA does not intersect BB or CC, and there are no attributes in R besides those in AA, BB, and CC.

   Your proof might have roughly the following form: "Suppose AA ->> BB and AA ->> CC hold. Then for all tuples t and u there exists a tuple v such that ... [fill in] ... Let DD = BB intersect CC. To prove that AA ->> DD holds, we need to prove that for all tuples t and u there exists a tuple v such that ... [fill in]. Therefore AA ->> DD holds."